第12讲函数依赖的理论省公开课金奖全国赛课一等奖微课获奖课件

第5章关系模式规范化设计——函数依赖理论数据库原理与应用

11/53关系模式规范化设计所要处理问题什么是“好”关系数据模式怎样评价一个好关系数据模式怎样设计一个“好”关系数据模式22/53关系模式规范化设计主要内容关系模式设计问题关系模式规范化基本概念和理论关系模式分解理论基础和算法33/53回顾1NF2NF3NFBCNF去除非主属性对于候选键部分函数依赖去除非主属性对于候选键传递函数依赖去除主属性对于候选键部分和传递函数依赖去除不被候选键所蕴涵非平凡多值依赖4NF－－－－消除决定原因非码非平凡函数依赖44/53理论研究必要性对于应用所表示语义用一组函数依赖是否能充分表示模式属性间约束关系，即得到一个给定关系模式完整函数依赖集F？能否将完整函数依赖集F缩小到一个可管理范围?即找到一个远远小于F集合T，蕴含集合F全部函数依赖，则DBMS只要实现函数依赖集T，函数依赖集F中全部函数依赖便会自动实现。函数依赖理论55/53主要内容Armstrong公理逻辑蕴含函数依赖集F闭包F+Armstrong公理推理规则属性集闭包函数依赖集等价和最小函数依赖集候选码及其求解方法函数依赖理论66/53【例】设相关系模式R（A，B，C），及其函数依赖集F={A→B，B→C}，判断A→C是否成立。Armstrong公理解：对于关系模式R任一实例r任意元组ti、tj，i≠j，若ti[A]=tj[A]，依据函数依赖定义由A→B可推出ti[B]=tj[B]又由B→C可推出ti[C]=tj[C]所以，若ti[A]=tj[A]，可推出ti[C]=tj[C]依据函数依赖定义，则可得出A→C。77/53逻辑蕴含设F是关系模式R上函数依赖集，X→Y是R上一个函数依赖，若对于R每个满足F关系r也满足X→Y，则称F逻辑蕴含X→Y记为：F┝X→Y。Armstrong公理88/53【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩}，

F={学生学号→学生姓名，学生学号→所在系，所在系→系主任，（学生学号，课程名称）→成绩}Armstrong公理逻辑蕴含99/53【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩}

F={学生学号→学生姓名，学生学号→所在系，所在系→系主任，（学生学号，课程名称）→成绩}Armstrong公理逻辑蕴含学生学号→学生学号,学生学号→系主任（学生学号，所在系）→学生学号（学生学号，所在系）→所在系（学生学号，课程名称）→所在系（学生学号，所在系）→系主任（学生学号，课程名称）→(学生学号，学生姓名，所在系，系主任，课程名称，成绩)1010/53函数依赖集F闭包F+F逻辑蕴含全部函数依赖集合称为函数依赖集F闭包，并记为F+F+={X→Y│F┝X→Y}Armstrong公理1111/53Armstrong公理推理规则经过推理规则，能够从给定函数依赖中推出其所蕴含新函数依赖。假设U为关系模式R属性集，F是U上函数依赖集，X、Y、Z是U任意子集，并采取把子集X、Y并集记为XY方式，对关系模式R<U，F>来说有以下推理规则：基本规则（3条）扩充规则（3条）Armstrong公理1212/53Armstrong公理推理规则基本规则Al.自反律（Reflexivity）

若Y

X

U，则X→Y为F所蕴含。A2.增广律（Augmentation）若X→Y为F所蕴含，且Z

U，则XZ→YZ为F所蕴含。A3.传递律（Transitivity）若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。Armstrong公理1313/53Armstrong公理推理规则扩充规则

合并规则由X→Y，X→Z，有X→YZ。（A2，A3）

伪传递规则由X→Y，WY→Z，有XW→Z。（A2，A3）

分解规则由X→Y及Z

Y，有X→Z。（A1，A3）Armstrong公理1414/53Armstrong公理推理规则依据合并规则和分解规则：引理1：

X→A1A2…Ak

成立充分必要条件是

X→Ai成立（i=l，2，…，k）Armstrong公理1515/53Armstrong公理推理规则Armstrong公理【例】设相关系R，它属性集U={A,B,C,D,E,F}，R满足以下函数依赖：

F={A→BC,B→E,CD→EF}，试证AD→F

证实：∵A→BC（已知）∴AD→BCD（增广律）∵BCD→CD（自反律）∵CD→EF（已知）∴BCD→EF（传递律）∴AD→EF（传递律）∴AD→F（分解规则）1616/53Armstrong公理有效性从F中已经有函数依赖关系利用Armstrong公理推出每一个函数依赖X→Y∈F+Armstrong公理完备性给定函数依赖集F,该函数依赖集所蕴含函数依赖，即F+中每一个函数依赖都能够利用Armstrong公理推导出来。Armstrong公理推出全部函数依赖为真能够推出全部函数依赖1717/53函数依赖集F闭包F+

Armstrong公理

【例】计算函数依赖集F={A→B,B→C}闭包F+

F中全部函数依赖都是其闭包中元素，即：A→B∈F+B→C∈F+依据自反规则，下述函数依赖(平凡)也是其闭包中元素A→AB→BC→CAB→AAB→BAB→ABAC→AAC→C

AC→ACBC→BBC→CBC→BCABC→A

ABC→B

ABC→CABC→ABABC→ACABC→BCABC→ABC1818/53函数依赖集F闭包F+Armstrong公理

【例】计算函数依赖集F={A→B,B→C}闭包F+

A→B,B→C及传递规则：A→C

A→B,A→C及合并规则：A→BC

A→B及增广规则：A→ABAC→BCAC→ABC

B→C及增广规则：AB→ACB→BCAB→ABC

A→C及增广规则：A→ACAB→BC

A→BC及增广规则：A→ABC

AB→B,B→C及传递规则：AB→C

AC→A,A→B及传递规则：AC→B……1919/53属性集闭包设F是属性集U上一组函数依赖，X

U，则属性集X关于函数依赖集F闭包XＦ＋定义为：XF+={Ai|Ai

U且X→Ai可由F经Armstrong公理导出}

即XF+={Ai|X→Ai∈F+，Ai

U}

XF+就是可由函数依赖集F经Armstrong公理导出全部函数依赖于属性集X全部属性集合。

Armstrong公理2020/53属性集闭包引理1：

X→A1A2…Ak

成立充分必要条件是

X→Ai成立（i=l，2，…，k）Armstrong公理引理2：

设F为属性集U上一组函数依赖，X、Y

U，X→Y能由F依据Armstrong公理导出充分必要条件是Y

XF+2121/53属性集闭包引理2：设F为属性集U上一组函数依赖，X、Y

U，X→Y能由F依据Armstrong公理导出充分必要条件是Y

XF+Armstrong公理用途：将判定X→Y是否能由F依据Armstrong公理导出问题，就转化为求出XF+，判定Y是否为XF+子集问题。2222/53属性集闭包

Armstrong公理算法1

求XF+一个算法。输入：属性集X和函数依赖集F。输出：XF+算法：XF+:=X;repeatoldXF+:=XF+;foreachfunctionaldependencyY→ZinFdoifY

XF+thenXF+:=XF+∪Z;until(oldXF+=XF+）2323/53属性集闭包

Armstrong公理【例】设F={(f1)B→CD,(f2)AD→E,(f3)B→A}，计算{B}F+

解：{B}F+

={B}第一遍循环

1）X={B}F

+={B}2）f1决定原因是{B}F+一个子集，所以{B}F+={B}F+∪{C,D}={B,C,D}3）f2决定原因不是{B}F+子集,所以f2不影响此次循环计算结果4）f3决定原因是{B}F+一个子集，所以{B}F+={B}F+∪{A}={A,B,C,D}5）X≠{B}F+,返回开始执行第二遍循环2424/53属性集闭包

Armstrong公理【例】设F={(f1)B→CD,(f2)AD→E,(f3)B→A}，计算{B}F+

第二遍循环1）X={B}F+={A,B,C,D}2）f1、f2、f3决定原因均是{B}F+子集,所以{B}F+={B}F+∪{C,D}∪{A}∪{E}={A,B,C,D,E}3）X≠{B}F+,返回开始执行第三遍循环2525/53属性集闭包

Armstrong公理【例】设F={(f1)B→CD,(f2)AD→E,(f3)B→A}，计算{B}F+第三遍循环

1）X={B}F+={A,B,C,D,E}2）F中全部函数依赖都已处理过（其依赖原因都已经被并入到{B}F+中）3）所以在此次循环中X={B}F+，算法执行结束返回结果{B}F+=ABCDE2626/53属性集闭包

Armstrong公理【例】F={A→BC，E→CF，B→E，CD→EF}，求(AB)F+解：X（0）=AB;∵A→BC,B→E，∴X（1）=AB∪BC∪E=ABCE又∵A→BC、B→E和E→CF∴X（2）=ABCE∪BC∪E∪CF=ABCEF又∵A→BC、B→E、E→CF，则X（3）=ABCEF∪BC∪E∪CF=ABCEFX（3）=X（2）

∴(AB)F+=ABCEF2727/53函数依赖集等价和最小函数依赖集定义：设F、G为两个函数依赖集，若F+=G+，则称F和G是等价，也可称F和G相互覆盖。

引理：

F+=G+充分必要条件是F⊆G+，G⊆F+。Armstrong公理

要判定F⊆G+

，只需逐一对F中函数依赖X→Y，考查Y是否属于XＧ＋就行了。2828/53函数依赖集等价和最小函数依赖集定义：

函数依赖集F当且仅当满足以下条件时，称为最小函数依赖集，或极小函数依赖集，或最小覆盖。1）F中每个函数依赖右部为单一属性。（右部不可约）2）F中不存在这么函数依赖X→A，使得F-{X→A}与F等价。3）F中不存在这么函数依赖X→A，使得Z⊂X，且F-{X→A}∪{Z→A}与F等价。（左部不可约）Armstrong公理引理：

任一函数依赖集F总能够为一右部恒为单属性函数依赖集所覆盖。2929/53函数依赖集等价和最小函数依赖集定理：

每一个函数依赖集F都等价于一个最小函数依赖集Fm。Armstrong公理3030/53函数依赖集等价和最小函数依赖集Armstrong公理进行结构性证实：

1）对F中每个函数依赖X→Y，若Y=A1A2…Ak，k≥2，则用{X→Aj|j=1,2,…,k}来取代X→Y。2）对F中每个函数依赖X→A，令G=F-{X→A}，若A∈XG+

，说明X→A为F-{X→A}所蕴含，F与F-{X→A}等价，则从F中去掉此函数依赖X→A。3）对F中每个函数依赖X→A，设X=B1B2…Bk，对每个Bi（i=1,2,…,k）若A∈(X-Bi)F+

，说明(X-Bi)→A为F所蕴含，函数依赖X→A是左部可约，F与F-{X→A}∪{(X-Bi)→A}等价，则以X-Bi取代X。3131/53Armstrong公理函数依赖集等价和最小函数依赖集【例】设F={A→BC,B→AC,C→A},求Fm。1)函数依赖右边属性单一化

F={A→B,A→C,B→A,B→C,C→A}2)去掉冗余函数依赖判断A→B是否冗余：G1={A→C,B→A,B→C,C→A}AＧ1＋=AC,B不属于AＧ1

＋，A→B不冗余；判断A→C是否冗余：G2={A→B,B→A,B→C,C→A}AＧ2

＋=ABC，C∈AＧ2

＋，A→C冗余

F={A→B,B→A,B→C,C→A}；3232/53Armstrong公理函数依赖集等价和最小函数依赖集【例(续)】设F={A→BC,B→AC,C→A},求Fm。判断B→A是否冗余：G3={A→B,B→C,C→A}BＧ3

＋=ABC，A∈BＧ3

＋，B→A冗余

F={A→B,B→C,C→A}；判断B→C是否冗余：G4={A→B,C→A}

BＧ4

＋=B，C不属于BＧ4

＋，B→C不冗余；判断C→A是否冗余：G5={A→B,B→C}

CＧ5

＋=C，A不属于CＧ5

＋，C→A不冗余。

3333/53Armstrong公理函数依赖集等价和最小函数依赖集【例(续)】设F={A→BC,B→AC,C→A},求Fm。

3)因为例中函数依赖决定原因均为单属性，因而不需要第三步检验，上述结果就是最小函数依赖集。

Fm＝{A→B,B→C,C→A}3434/53Armstrong公理函数依赖集等价和最小函数依赖集【例】函数依赖集F={AB→C,A→B,B→A}，求Fm。解：1）全部函数依赖右部均为单属性，此步完成。

2）去掉冗余函数依赖，按前例方法，经过检验，函数依赖集仍为F；

3）去掉各函数依赖左部冗余属性。

本题只需考虑AB→C。3535/53Armstrong公理函数依赖集等价和最小函数依赖集【例】函数依赖集F={AB→C,A→B,B→A}，求Fm。解：方法1：在决定原因中去掉B,若C∈AF+,则以A→C代替AB→C。求得AF+＝ABC,∵C∈AF+,∴Fm＝{A→C,A→B,B→A};方法2：在决定原因中去掉A,若C∈BF+,则以B→C代替AB→C。求得BF+＝ABC,∵C∈BF+

∴Fm＝{B→C,A→B,B→A};最小函数依赖集不是唯一3636/53主要内容Armstrong公理逻辑蕴含函数依赖集F闭包F+

Armstrong公理推理规则属性集闭包函数依赖集等价和最小函数依赖集候选键及其求解方法

函数依赖理论3737/53候选键概念在关系模式R（U，F）中，假如属性集K满足KU，K为关系模式R候选键。

候选键及其求解方法怎样判断？3838/53候选键求解方法方法一：在关系模式R（U，F）中，K

U，利用Armstrong公理中推导规则，从已知函数依赖集F中推导得到以下函数依赖关系，则K为候选键。

K→U，且不存在K真子集K’→U候选键及其求解方法3939/53【例1】R(A,B,C,D)，F={B→D,AB→C}，求解R候选键。候选码及其求解方法解：由B→D利用增广规则可得：AB→AD………….(1)

由(1),AB→C及合并规则可得:AB→ACD…………(2)

由(2)利用增广规则可得：AB→ABCD因为不存在A→ABCD和B→ABCD，则AB为候选键。AB是否是唯一候选键？4040/53候选键求解方法方法二：在关系模式R（U，F）中，K

U，依据候选键定义及属性集闭包概念，假如K满足下面两个条件，则K为候选键：KF+=U对于K任意一个真子集K’，都有K’F

+≠U

候选码及其求解方法4141/53【例1】R(A,B,C,D)，F={B→D,AB→C}，求解R候选键。候选码及其求解方法解：验证方法一候选键是否是AB，因为：{A}F+={A}≠{A,B,C,D}{B}F+={B,D}≠{A,B,C,D}{AB}F+={A,B,C,D}

所以AB是关系模式R一个候选键。AB是否是唯一候选键？4242/53【例2】设相关系模式R(U,F)，U={A,B,C,D}，F={A→B，B→C}，求解R全部候选码。候选码及其求解方法解：

AF+={ABC},BF+={BC},CF+={C},DF+={D}(AB)F+=(AC)F+={ABC},(AD)F+={ABCD},

(BC)F+={BC},(BD)F+={BCD},(CD)F+={CD}(ABC)F+={ABC},(BCD)F+={BCD}

(ACD)F+=(ABD)F+={ABCD}

故R只有一个候选码AD4343/53算法：寻找关系模式R(U,F)某一候选键K候选码及其求解方法1.setK:=U;2.foreachattributeAinK{compute(K–A)F+;if(K–A)F+containsalltheattributesinU,then{setK:=K–{A};}}4444/53【例2】设相关系模式R(U,F)，U={A,B,C,D}，F={A→B，B→C}，求解R全部候选码。候选码及其求解方法解：

K={A,B,C,D}∵{K–A}F+={B,C,D}≠U∴该候选键中必定含有属性A∵{K–B}F+={A,B,C,D}=U∴K=K–B={A,C,D}∵{K–C}F+={A,B,C,D}=U∴K=K–C={A,D}∵{K–D}F+={A,B,C}≠U∴该候选键中必定含有属性D最终得到该关系候选键{A,D}AD是否是唯一候选键？4545/53【例3】利用算法寻找候选键。模式R(U,F)，U={A,B,C,D}，F={A→C,CD→B}。候选码及其求解方法解：K={A,B,C,D}∵{K–A}F+={B,C,D}≠U∴该候选键中必定含有属性A∵{K–B}F+={A,B,C,D}=U∴K=K–B={A,C,D}∵{K–C}F+={A,B,C,D}=U∴K=K–C={A,B,D}∵{K–D}F+={A,C}≠U∴该候选键中必定含有属性D最终得到该关系一个候选键{A,D}