函数依赖的理论.ppt

,第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）若Y X U，则X Y为F所蕴含。A2.增广律（Augmentation）若XY为F所蕴含，且Z U，则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：XA1 A2Ak 成立的充分必要条件是 XAi 成立（i=l，2，k）,Armstrong公理,Armstrong公理推理规则,Armstrong公理,【例】设有关系R，它的属性集U=A,B,C,D,E,F，R满足下列函数依赖：F=ABC,BE,CDEF，试证 ADF,证明：ABC（已知）ADBCD（增广律）BCD CD（自反律）CDEF（已知）BCD EF（传递律）AD EF（传递律）AD F（分解规则）,Armstrong 公理的有效性从F 中的已有函数依赖关系利用Armstrong 公理推出的每一个函数依赖XYF+Armstrong 公理的完备性给定函数依赖集F,该函数依赖集所蕴含的函数依赖，即F+中的每一个函数依赖都可以利用Armstrong公理推导出来。,Armstrong公理,推出的所有函数依赖为真,可以推出所有的函数依赖,函数依赖集F的闭包F+,Armstrong公理,【例】计算函数依赖集F=AB,BC 的闭包F+F中的所有函数依赖都是其闭包中的元素，即：AB F+BC F+根据自反规则，下述函数依赖(平凡)也是其闭包中的元素 AA BB CC ABA ABB ABAB ACA ACC ACAC BCB BCC BCBC ABCA ABCB ABCC ABCAB ABCAC ABCBC ABCABC,函数依赖集F 的闭包F+,Armstrong公理,【例】计算函数依赖集F=AB,BC 的闭包F+AB,BC及传递规则：AC AB,AC及合并规则：ABC AB及增广规则：AAB ACBC ACABC BC及增广规则：ABAC BBC ABABC AC及增广规则：AAC ABBC ABC及增广规则：AABC ABB,BC及传递规则：ABC ACA,AB及传递规则：ACB,属性集闭包 设F是属性集U上的一组函数依赖，X U，则属性集X关于函数依赖集F的闭包 X定义为：XF+=Ai|Ai U且XAi 可由F经Armstrong公理导出 即 XF+=Ai|X Ai F+，Ai U XF+就是可由函数依赖集F经Armstrong公理导出的所有函数依赖于属性集X的所有属性的集合。,Armstrong公理,属性集闭包 引理1：XA1 A2Ak 成立的充分必要条件是 XAi 成立（i=l，2，k）,Armstrong公理,引理2：设F为属性集U上的一组函数依赖，X、Y U，XY 能由F 根据Armstrong公理导出的充分必要条件是Y XF+,属性集闭包 引理2：设F为属性集U上的一组函数依赖，X、Y U，XY 能由F 根据Armstrong公理导出的充分必要条件是Y XF+,Armstrong公理,用途：将判定XY是否能由F 根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题。,属性集闭包,Armstrong公理,算法1 求XF+的一个算法。输入：属性集X和函数依赖集F。输出：XF+算法：,XF+:=X;repeat old XF+:=XF+;for each functional dependency YZ in F do if Y XF+then XF+:=XF+Z;until(old XF+=XF+）,属性集闭包,Armstrong公理,【例】设F=(f1)BCD,(f2)ADE,(f3)BA，计算BF+解：BF+=B 第一遍循环 1）X=BF+=B 2）f1的决定因素是BF+的一个子集，所以 BF+=BF+C,D=B,C,D 3）f2的决定因素不是BF+的子集,因此f2不影响本次循环的计算结果 4）f3的决定因素是BF+的一个子集，所以 BF+=BF+A=A,B,C,D 5）XBF+,返回开始执行第二遍循环,属性集闭包,Armstrong公理,【例】设F=(f1)BCD,(f2)ADE,(f3)BA，计算BF+第二遍循环 1）X=BF+=A,B,C,D 2）f1、f2、f3的决定因素均是BF+的子集,所以 BF+=BF+C,DAE=A,B,C,D,E 3）X BF+,返回开始执行第三遍循环,属性集闭包,Armstrong公理,【例】设F=(f1)BCD,(f2)ADE,(f3)BA，计算BF+第三遍循环 1）X=BF+=A,B,C,D,E 2）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和ECF X（2）=ABCEBCECF=ABCEF 又ABC、BE、ECF，则 X（3）=ABCEFBCECF=ABCEF X（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-XA ZA 与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,CA 2)去掉冗余的函数依赖 判断AB是否冗余：G1=AC,BA,BC,CA A1=AC,B不属于A1，AB不冗余；判断AC是否冗余：G2=AB,BA,BC,CA A2=ABC，CA2，AC冗余 F=AB,BA,BC,CA；,Armstrong公理,函数依赖集等价和最小函数依赖集,【例(续)】设F=ABC,BAC,CA,求Fm。判断BA是否冗余：G3=AB,BC,CA B3=ABC，AB3，BA冗余 F=AB,BC,CA；判断BC是否冗余：G4=AB,CA B4=B，C不属于B4，BC不冗余；判断CA是否冗余：G5=AB,BC C5=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,若C A F+,则以AC代替ABC。求得A F+ABC,C A F+,FmAC,AB,BA;方法2：在决定因素中去掉A,若C B F+,则以BC代替ABC。求得B F+ABC,C B F+FmBC,AB,BA;,最小函数依赖集不是唯一的,主要内容Armstrong公理逻辑蕴含 函数依赖集F 的闭包F+Armstrong公理推理规则 属性集闭包 函数依赖集等价和最小函数依赖集 候选键及其求解方法,函数依赖的理论,候选键的概念在关系模式R（U，F）中，如果属性集K满足K U，K为关系模式R的候选键。,候选键及其求解方法,如何判断？,候选键的求解方法 方法一：在关系模式R（U，F）中，K U，利用Armstrong公理中的推导规则，从已知的函数依赖集F中推导得到如下的函数依赖关系，则K为候选键。KU，且不存在K的真子集K U,候选键及其求解方法,【例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）中，K U，根据候选键的定义及属性集闭包的概念，如果K满足下面两个条件，则K为候选键：KF+=U对于K 的任意一个真子集K，都有K F+U,候选码及其求解方法,【例1】R(A,B,C,D)，F=BD,ABC，求解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是否是唯一的候选键？,【例2】设有关系模式R(U,F)，U=A,B,C,D，F=AB，BC，求解R的所有候选码。,候选码及其求解方法,解：A F+=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.set K:=U;2.for each attribute A in K compute(K A)F+;if(K A)F+contains all the attributes in U,then set K:=K A;,【例2】设有关系模式R(U,F)，U=A,B,C,D，F=AB，BC，求解R的所有候选码。,候选码及其求解方法,解：K=A,B,C,D KAF+=B,C,D U 该候选键中必定含有属性A KBF+=A,B,C,D=U K=KB=A,C,D KCF+=A,B,C,D=U K=KC=A,D KDF+=A,B,C U 该候选键中必定含有属性D 最后得到该关系的候选键 A,D,AD是否是唯一的候选键？,【例3】利用算法寻找候选键。模式R(U,F)，U=A,B,C,D，F=AC,CDB。,候选码及其求解方法,解：K=A,B,C,D KAF+=B,C,D U 该候选键中必定含有属性A KBF+=A,B,C,D=U K=KB=A,C,D KCF+=A,B,C,D=U K=KC=A,B,D KDF+=A,C U 该候选键中必定含有属性D 最后得到该关系的一个候选键 A,D,候选键的求解方法 方法三：先计算函数依赖集F的最小覆盖（即与F相等价的最小函数依赖集），然后采用快速判定法，以及候选键的定义来确定候选键。,候选码及其求解方法,快速判断方法：对于给定的关系R(U,F)，可将其属性分为四类：L类：仅出现在函数依赖集F的左部的属性；R类：仅出现在函数依赖集F的右部的属性；LR类：在函数依赖集F的左右两边均出现的属性；N类：在函数依赖集F的左右两边均未出现的属性。,候选码及其求解方法,快速求解候选码的一个充分条件：对于给定的关系模式R(U,F)，XU定理1：若 X是R的L类属性，则X必为R的任一候选码中的属性。定理2：若 X是R的R类属性，则X必不在R的任一候选码中。定理3：若 X是R的N类属性，则X必为R的任一候选码中的属性。,候选码及其求解方法,【例1】R(A,B,C,D)，F=BD,ABC，求解R的候选键。,候选码及其求解方法,解：F是最小函数依赖集；A、B是L类属性，必为候选码中的属性；C、D是R类属性，必不出现在候选码中；(AB)F+=ABCD,AB为候选键。,【例2】设有关系模式R(U,F)，U=A,B,C,D，F=AB,BC，求解R的候选键。,候选码及其求解方法,解：F是最小函数依赖集；A是L类属性，必为候选码中的属性；C是R类属性，必不出现在候选码中；D是N类属性，必为候选码中的属性；(AD)F+=ABCD,AD为候选键。,【例3】R(A,B,C,D)，F=AC,CDB，求解R的候选键。,候选码及其求解方法,解：F是最小函数依赖集；A、D是L类属性，必为候选码中的属性；B是R类属性，必不出现在候选码中；(AD)F+=ABCD AD为候选键。,主要内容Armstrong公理逻辑蕴含 函数依赖集F 的闭包F+Armstrong公理推理规则 属性集闭包 函数依赖集等价和最小函数依赖集 候选码及其求解方法,函数依赖的理论,