第12讲函数依赖的理论

,第5章关系模式的规范化设计函数依赖的理论,数据库原理与应用,关系模式的规范化设计,所要解决的问题什么是“好”的关系数据模式如何评价一个好的关系数据模式如何设计一个“好”的关系数据模式,关系模式的规范化设计,主要内容关系模式的设计问题关系模式规范化的基本概念和理论关系模式分解的理论基础和算法,回顾,1NF,2NF,3NF,BCNF,去除非主属性对于候选键的部分函数依赖,去除非主属性对于候选键的传递函数依赖,去除主属性对于候选键的部分和传递函数依赖,去除不被候选键所蕴涵的非平凡的多值依赖,4NF,理论研究的必要性对于应用所表达的语义用一组函数依赖是否能充分表达模式属性间的约束关系，即得到一个给定的关系模式的完整函数依赖集F？能否将完整函数依赖集F缩小到一个可管理的范围?即找到一个远远小于F的集合T，蕴含集合F的所有函数依赖，则DBMS只要实现函数依赖集T，函数依赖集F中的所有函数依赖会自动实现。,函数依赖的理论,主要内容Armstrong公理逻辑蕴含函数依赖集F的闭包F+Armstrong公理推理规则属性集闭包函数依赖集等价和最小函数依赖集候选码及其求解方法,函数依赖的理论,【例】设有关系模式R（A，B，C），及其函数依赖集F=AB，BC，判断AC是否成立。,Armstrong公理,解：对于关系模式R的任一实例r的任意元组ti、tj，ij，若tiA=tjA，根据函数依赖的定义由AB可推出tiB=tjB又由BC可推出tiC=tjC因此，若tiA=tjA，可推出tiC=tjC根据函数依赖的定义，则可得出AC。,逻辑蕴含设F是关系模式R上的函数依赖集，XY是R上的一个函数依赖，若对于R的每个满足F的关系r也满足XY，则称F逻辑蕴含XY记为：FXY。,Armstrong公理,【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩，F=学生学号学生姓名，学生学号所在系，所在系系主任，（学生学号，课程名称）成绩,Armstrong公理,逻辑蕴含,【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩，F=学生学号学生姓名，学生学号所在系，所在系系主任，（学生学号，课程名称）成绩,Armstrong公理,逻辑蕴含,学生学号学生学号,学生学号系主任（学生学号，所在系）学生学号（学生学号，所在系）所在系（学生学号，课程名称）所在系（学生学号，所在系）系主任（学生学号，课程名称）(学生学号，学生姓名，所在系，系主任，课程名称，成绩),函数依赖集F的闭包F+F逻辑蕴含的所有函数依赖的集合称为函数依赖集F的闭包，并记为F+F+=XYFXY,Armstrong公理,Armstrong公理推理规则通过推理规则，可以从给定的函数依赖中推出其所蕴含的新的函数依赖。假设U为关系模式R的属性集，F是U上的函数依赖集，X、Y、Z是U的任意子集，并采用把子集X、Y的并集记为XY的方式，对关系模式R来说有以下的推理规则：基本规则（3条）扩充规则（3条）,Armstrong公理,Armstrong公理推理规则基本规则Al.自反律（Reflexivity）若YXU，则XY为F所蕴含。A2.增广律（Augmentation）若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。A3.传递律（Transitivity）若XY及YZ为F所蕴含，则XZ为F所蕴含。,Armstrong公理,Armstrong公理推理规则扩充规则合并规则由XY，XZ，有XYZ。（A2，A3）伪传递规则由XY，WYZ，有XWZ。（A2，A3）分解规则由XY及ZY，有XZ。（A1，A3）,Armstrong公理,Armstrong公理推理规则根据合并规则和分解规则：引理1：XA1A2Ak成立的充分必要条件是XAi成立（i=l，2，k）,Armstrong公理,Armstrong公理推理规则,Armstrong公理,【例】设有关系R，它的属性集U=A,B,C,D,E,F，R满足下列函数依赖：F=ABC,BE,CDEF，试证ADF,证明：ABC（已知）ADBCD（增广律）BCDCD（自反律）CDEF（已知）BCDEF（传递律）ADEF（传递律）ADF（分解规则）,Armstrong公理的有效性从F中的已有函数依赖关系利用Armstrong公理推出的每一个函数依赖XYF+Armstrong公理的完备性给定函数依赖集F,该函数依赖集所蕴含的函数依赖，即F+中的每一个函数依赖都可以利用Armstrong公理推导出来。,Armstrong公理,推出的所有函数依赖为真,可以推出所有的函数依赖,函数依赖集F的闭包F+,Armstrong公理,【例】计算函数依赖集F=AB,BC的闭包F+F中的所有函数依赖都是其闭包中的元素，即：ABF+BCF+根据自反规则，下述函数依赖也是其闭包中的元素AABBCCABAABBABABACAACCACACBCBBCCBCBCABCAABCBABCCABCABABCACABCBCABCABC,函数依赖集F的闭包F+,Armstrong公理,【例】计算函数依赖集F=AB,BC的闭包F+AB,BC及传递规则：ACAB,AC及合并规则：ABCAB及增广规则：AABACBCACABCBC及增广规则：ABACBBCABABCAC及增广规则：AACABBCABC及增广规则：AABCABB,BC及传递规则：ABCACA,AB及传递规则：ACB,属性集闭包设F是属性集U上的一组函数依赖，XU，则属性集X关于函数依赖集F的闭包X定义为：XF+=Ai|AiU且XAi可由F经Armstrong公理导出即XF+=Ai|XAiF+，AiUXF+就是可由函数依赖集F经Armstrong公理导出的所有“函数依赖于属性集X的所有属性的集合。,Armstrong公理,属性集闭包引理1：XA1A2Ak成立的充分必要条件是XAi成立（i=l，2，k）,Armstrong公理,引理2：设F为属性集U上的一组函数依赖，X、YU，XY能由F根据Armstrong公理导出的充分必要条件是YXF+,属性集闭包引理2：设F为属性集U上的一组函数依赖，X、YU，XY能由F根据Armstrong公理导出的充分必要条件是YXF+,Armstrong公理,用途：将判定XY是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题。,属性集闭包,Armstrong公理,算法1求XF+的一个算法。输入：属性集X和函数依赖集F。输出：XF+算法：,XF+:=X;repeatoldXF+:=XF+;foreachfunctionaldependencyYZinFdoifYXF+thenXF+:=XF+Z;until(oldXF+=XF+）,属性集闭包,Armstrong公理,【例】设F=(f1)BCD,(f2)ADE,(f3)BA，计算BF+解：BF+=B第一遍循环1）X=BF+=B2）f1的决定因素是BF+的一个子集，所以BF+=BF+C,D=B,C,D3）f2的决定因素不是BF+的子集,因此f2不影响本次循环的计算结果4）f3的决定因素是BF+的一个子集，所以BF+=BF+A=A,B,C,D5）XBF+,返回开始执行第二遍循环,属性集闭包,Armstrong公理,【例】设F=(f1)BCD,(f2)ADE,(f3)BA，计算BF+第二遍循环1）X=BF+=A,B,C,D2）f1、f2、f3的决定因素均是BF+的子集,所以BF+=BF+C,DAE=A,B,C,D,E3）XBF+,返回开始执行第三遍循环,属性集闭包,Armstrong公理,【例】设F=(f1)BCD,(f2)ADE,(f3)BA，计算BF+第三遍循环1）X=BF+=A,B,C,D,E2）F中的所有函数依赖都已处理过（其依赖因素都已经被并入到BF+中）3）因此在本次循环中X=BF+，算法执行结束返回结果BF+=ABCDE,属性集闭包,Armstrong公理,【例】F=ABC，ECF，BE，CDEF，求(AB)F+解：X（0）=AB;ABC,BE，X（1）=ABBCE=ABCE又ABC、BE和ECFX（2）=ABCEBCECF=ABCEF又ABC、BE、ECF，则X（3）=ABCEFBCECF=ABCEFX（3）=X（2）(AB)F+=ABCEF,函数依赖集等价和最小函数依赖集定义：设F、G为两个函数依赖集，若F+=G+，则称F和G是等价的，也可称F和G互相覆盖。引理：F+=G+的充分必要条件是FG+，GF+。,Armstrong公理,要判定FG+，只需逐一对F中的函数依赖XY，考察Y是否属于X就行了。,函数依赖集等价和最小函数依赖集定义：函数依赖集F当且仅当满足下列条件时，称为最小函数依赖集，或极小函数依赖集，或最小覆盖。1）F中每个函数依赖的右部为单一属性。（右部不可约）2）F中不存在这样的函数依赖XA，使得F-XA与F等价。3）F中不存在这样的函数依赖XA，使得ZX，且F-XAZA与F等价。（左部不可约）,Armstrong公理,引理：任一函数依赖集F总可以为一右部恒为单属性的函数依赖集所覆盖。,函数依赖集等价和最小函数依赖集定理：每一个函数依赖集F都等价于一个最小函数依赖集Fm。,Armstrong公理,函数依赖集等价和最小函数依赖集,Armstrong公理,进行构造性的证明：1）对F中的每个函数依赖XY，若Y=A1A2Ak，k2，则用XAj|j=1,2,k来取代XY。2）对F中的每个函数依赖XA，令G=F-XA，若AXG+，说明XA为F-XA所蕴含，F与F-XA等价，则从F中去掉此函数依赖XA。3）对F中的每个函数依赖XA，设X=B1B2Bk，对每个Bi（i=1,2,k）若A(X-Bi)F+，说明(X-Bi)A为F所蕴含，函数依赖XA是左部可约的，F与F-XA(X-Bi)A等价，则以X-Bi取代X。,函数依赖集等价和最小函数依赖集,Armstrong公理,【例】设F=ABC,BAC,CA,求Fm。1)函数依赖右边属性单一化F=AB,AC,BA,BC,CA2)去掉冗余的函数依赖判断AB是否冗余：G1=AC,BA,BC,CAA1=AC,B不属于A1，AB不冗余；判断AC是否冗余：G2=AB,BA,BC,CAA2=ABC，CA2，AC冗余F=AB,BA,BC,CA；,函数依赖集等价和最小函数依赖集,Armstrong公理,【例】设F=ABC,BAC,CA,求Fm。判断BA是否冗余：G3=AB,BC,CAB3=ABC，AB3，BA冗余F=AB,BC,CA；判断BC是否冗余：G4=AB,CAB4=B，C不属于B4，BC不冗余；判断CA是否冗余：G5=AB,BCC5=C，A不属于C5，CA不冗余。,函数依赖集等价和最小函数依赖集,Armstrong公理,【例】设F=ABC,BAC,CA,求Fm。3)由于例中函数依赖的决定因素均为单属性，因而不需要第三步检查，上述结果就是最小函数依赖集。FmAB,BC,CA,函数依赖集等价和最小函数依赖集,Armstrong公理,【例】函数依赖集F=ABC,AB,BA，求Fm。解：1）所有的函数依赖右部均为单属性，此步完成。2）去掉冗余的函数依赖，按前例方法，经过检验，函数依赖集仍为F；3）去掉各函数依赖左部冗余的属性。本题只需考虑ABC。,函数依赖集等价和最小函数依赖集,Armstrong公理,【例】函数依赖集F=ABC,AB,BA，求Fm。解：方法1：在决定因素中去掉B,若CAF+,则以AC代替ABC。求得AF+ABC,CAF+,FmAC,AB,BA;方法2：在决定因素中去掉A,若CBF+,则以BC代替ABC。求得BF+ABC,CBF+FmBC,AB,BA;,最小函数依赖集不是唯一的,主要内容Armstrong公理逻辑蕴含函数依赖集F的闭包F+Armstrong公理推理规则属性集闭包函数依赖集等价和最小函数依赖集候选键及其求解方法,函数依赖的理论,候选键的概念在关系模式R（U，F）中，如果属性集K满足KU，K为关系模式R的候选键。,候选键及其求解方法,如何判断？,候选键的求解方法方法一：在关系模式R（U，F）中，KU，利用Armstrong公理中的推导规则，从已知的函数依赖集F中推导得到如下的函数依赖关系，则K为候选键。KU，且不存在K的真子集KU,候选键及其求解方法,【例1】R(A,B,C,D)，F=BD,ABC，求解R的候选键。,候选码及其求解方法,解：由BD利用增广规则可得：ABAD.(1)由(1),ABC及合并规则可得:ABACD(2)由(2)利用增广规则可得：ABABCD由于不存在AABCD和BABCD，则AB为候选键。,AB是否是唯一的候选键？,候选键的求解方法方法二：在关系模式R（U，F）中，KU，根据候选键的定义及属性集闭包的概念，如果K满足下面两个条件，则K为候选键：KF+=U对于K的任意一个真子集K，都有KF+U,候选码及其求解方法,【例1】R(A,B,C,D)，F=BD,ABC，求解R的候选键。,候选码及其求解方法,解：验证方法一的候选键是否是AB，因为：AF+=AA,B,C,DBF+=B,DA,B,C,DABF+=A,B,C,D所以AB是关系模式R的一个候选键。,AB是否是唯一的候选键？,【例2】设有关系模式R(U,F)，U=A,B,C,D，F=AB，BC，求解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只有一个候选码AD,算法：寻找关系模式R(U,F)的某一候选键K,候选码及其求解方法,1.setK:=U;2.foreachattributeAinKcompute(KA)F+;if(KA)F+containsalltheattributesinU,thensetK:=KA;,【例2】设有关系模式R(U,F)，U=A,B,C,D，F=AB，BC，求解R的所有候选码。,候选码及其求解方法,解：K=A,B,C,DKAF+=B,C,DU该候选键中必定含有属性AKBF+=A,B,C,D=UK=KB=A,C,DKCF+=A,B,C,D=UK=KC=A,DKDF+=A,B,CU该候选键中必定含有属性D最后得到该关系的候选键A,D,AD是否是唯一的候选键？,【例3】利用算法寻找候选键。模式R(U,F)，U=A,B,C,D，F=AC,CDB。,候选码及其求解方法,解：K=A,B,C,DKAF+=B,C,DU该候选键中必定含有属性AKBF+=A,B,C,D=UK=KB=A,C,DKCF+=A,B,C,D=UK=KC=A,DKDF+=A,CU该候选键中必定含有属性D最后得到该关系的一个候选键A,D,候选键的求解方法方法三：先计算函数依赖集F的最小覆盖（即与F相等价的最小函数依赖集），然后采用快速判定法，以及候选键的定义来确定候选键。,候选码及其求解方法,快速判断方法：对于给定的关系R(U,F)，可将其属