函数依赖的逻辑蕴涵.doc

函数依赖的逻辑蕴涵一、逻辑蕴涵 定义：设有关系模式R(U)及其函数依赖集F，如果对于R的任一个满足F的关系r函数依赖XY都成立，则称F逻辑蕴涵XY，或称XY可以由F推出。 例：关系模式 R=(A,B,C),函数依赖集F=AB,BC, F逻辑蕴涵AC。证：设u,v为r中任意两个元组： 若AC不成立，则有uA=vA,而uCvC 而且AB, BC,知 uA=vA, uB=vB, uC=vC, 即若uA=vA则uC=vC，和假设矛盾。 故F逻辑蕴涵AC。满足F依赖集的所有元组都函数依赖XY（XY不属于F集），则称F逻辑蕴涵XY（XY由F依赖集中所有依赖关系推断而出） 二、Armstrong公理 1、定理：若U为关系模式R的属性全集，F为U上的一组函数依赖，设X、Y、Z、W均为R的子集，对R(U,F)有： F1(自反性)：若XY(表X包含Y），则XY为F所蕴涵；(F1:XX) F2(增广性): 若XY为F所蕴涵，则XZYZ为F所蕴涵；(F2:XZY) F3(传递性): 若XY,YZ为F所蕴涵，则XZ为F所蕴涵； F4(伪增性)：若XY，WZ(表W包含Z）为F所蕴涵，则XWYZ为F所蕴涵； F5(伪传性): 若XY，YWZ为F所蕴涵, 则XWZ为F所蕴涵； F6(合成性): 若XY,XZ为F所蕴涵，则XYZ为F所蕴涵； F7(分解性): 若XY,ZY (表Z包含于Y）为F所蕴涵，则XZ为F所蕴涵。 函数依赖推理规则F1F7都是正确的。 2、Armstrong公理：推理规则F1、F2、F3合称Armstrong公理；F4 F7可由F1、F2、F3推得，是Armstrong公理的推论部分。 三、函数依赖的闭包 定义：若F为关系模式R(U)的函数依赖集，我们把F以及所有被F逻辑蕴涵的函数依赖的集合称为F的闭包，记为F+。即：F+=XY|XYF“应用Armstong公理从F中导出的任何XY” F包含于F+，如果F=F+，则F为函数依赖的一个完备集。 规定：若X为U的子集，X 属于F+。 例：R=ABC,F=AB, BC, 求F+ 解： F+ =A,AB,AC,ABC,B,C, AA,ABA,ACA,ABCA,BB,CC, AB,ABB,ACB,ABCB,BC, AC,ABC,ACC,ABCC,BBC, AAB,ABAB,ACAB,ABCAB,BC, AAC,ABAC,ACAC,ABCAC,BCB, ABC,ABBC,ACBC,ABCBC,BCC, AABC,ABABC,ACABC,ABCA,BCBC 例：已知关系模式R中 U=A，B，C，D, E, G, F=ABC, CA, BCD, ACDB, DEG, BEC, CGBD, CEAG,判断BDAC是否属于F+ 解：由DEG知DE，BDBE 又知BEC，CA 所以BEA, BEAC 由、知，BDAC，所以BDAC被F所蕴涵，即BDAC属于F+ 例：已知关系模式R中 U=A，B，C，E, H, P, G, F=ACPE, PGA, BCE, AP, GAB, GCA, PABG, AEGB, ABCPH,证明BGHE属于F+ 证：由BCE知BC，BE, BGGC 又知GCA，AP 所以BGA, BGABCP 又ABCPH，由、知BGHE，所以BGHE被F所蕴涵， 即BGHE属于F+ 四、属性集闭包 1、定义：若F为关系模式R(U)的函数依赖集，X是U的子集，则由Armstrong公理推导出的所有XAi所形成的属性集 例：设R=ABC,F=AB, BC当X分别为A,B,C是求X+。解：当X=A时，X+=ABC 当X=B时，X+=BC 当X=C时，X+=C* X代表的属性集可以决定的属性集（包括本身） 2、定理：当且仅当Y属于X+时，XY能根据Armstron公理由F导出。证：设Y=A1,A2,An 充分条件：当Y属于X+时,对于每个i,XAi可由公理导出。 再用合并规则可得XY。 必要条件：若XY能够由公理导出,则根据分解规, XAi(i=1,2,n)成立，所以Y属于X+。 3、计算X+(1)算法依据：若F为关系模式R(U)的函数依赖集,X,Z,W是U的子集,对于任意的ZWF,若 XZ（表X包含Z）,则XXW。 (2)算法：a.令X+ = X;b.在F中依次查找每个没有被标记的函数依赖，若“左边属性集”包含于X+ ，则令 X+ = X+“右边属性集”,为被访问过的函数依赖设置访问标记。c.反复执行b直到X+不改变为止。（先令X+等于本身，然后在F+中依次查找左边包含于X+的属性，把其右边的对应属性并到X中） (3)算法实现 输入：关系模式R的子集X,R上的函数依赖集F。 输出：X关于F的闭包X+ 算法伪语言描述： Closure(X,F) olds=; news=X; G=F; while (olds!=news) olds=news; for (G中的每个函数依赖WZ) if (news包含W) news=newsZ; 从G中删除函数依赖WZ; return news; 例：已知关系模式R中U=A，B，C，D, E, G,F=ABC, CA, BCD, ACDB, DEG, BEC, CGBD, CEAG,求(BD)+，判断BDAC是否属于F+解：X+=BDEGCA结论：(BD)+=ABCDEG,BDAC可由F导出，即BDAC属于F+ 例：已知关系模式R中U=A，B，C，E, H, P, G,F=ACPE, PGA, BCE, AP, GAB,GCA, PABG, AEGB, ABCPH,证明BGHE属于F+证：因为,(BG)+ =ABCEHPG,所以BGHE可由F导出，即BGHE属于F+ 4、结论判定函数依赖XY是否能由F导出的问题，可转化为求X+并判定Y是否是X+子集的问题。即求闭包问题可转化为求属性集问题。判定给定函数依赖XY是否蕴涵于函数依赖集F算法实现： 输入：函数依赖集合F,函数依赖XY输出：若XYF+输出真，否则输出假 算法伪语言描述：number(F,XY) if (Y包含于close(X,F) return 真 else return 假 Ai|i=1,2,称为X对于F的闭包，记为X+。五、等价和覆盖定义：关系模式R上的两个依赖集F和G，如果F+=G+，则称F和G是等价的，记做FG。若FG，则称G是F的一个覆盖，反之亦然。两个等价的函数依赖集在表达能力上是完全相同的。六、最小函数依赖集定义：如果函数依赖集F满足下列条件，则称F为最小函数依赖集或最小覆盖。 F中的任何一个函数依赖的右部仅含有一个属性； F中不存在这样一个函数依赖XA，使得F与F-XA等价； F中不存在这样一个函数依赖XA，X有真子集Z使得F-XAZA与F等价。算法：计算最小函数依赖集。输入 一个函数依赖集输出 F的一个等价的最小函数依赖集G步骤： 用分解的法则，使F中的任何一个函数依赖的右部仅含有一个属性； 去掉多余的函数依赖：从第一个函数依赖XY开始将其从F中去掉，然后在剩下的函数依赖中求X的闭包X+，看X+是否包含Y，若是，则去掉XY；否则不能去掉，依次做下去。直到找不到冗余的函数依赖； 去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如XYA，若要判Y为多余的，则以XA代替XYA是否等价？若A (X)+，则Y是多余属性，可以去掉。举例：已知关系模式R，U=A,B,C,D,E,G，F=ABC,DEG,CA,BEC,BCD,CGBD,ACDB,CEAG，求F的最小函数依赖集。解1：利用算法求解，使得其满足三个条件 利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖，得F为：F=ABC,DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG 去掉F中多余的函数依赖A设ABC为冗余的函数依赖，则去掉ABC，得：F1=DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG计算(AB)F1+：设X(0)=AB计算X(1)：扫描F1中各个函数依赖，找到左部为AB或AB子集的函数依赖，因为找不到这样的函数依赖。故有X(1)=X(0)=AB，算法终止。(AB)F1+= AB不包含C，故ABC不是冗余的函数依赖，不能从F1中去掉。B设CGB为冗余的函数依赖，则去掉CGB，得：F2=ABC,DE,DG,CA,BEC,BCD,CGD,ACDB,CEA,CEG计算(CG)F2+：设X(0)=CG计算X(1)：扫描F2中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个CA函数依赖。故有X(1)=X(0)A=CGA=ACG。计算X(2)：扫描F2中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，得到一个CGD函数依赖。故有X(2)=X(1)D=ACDG。计算X(3)：扫描F2中的各个函数依赖，找到左部为ACDG或ACDG子集的函数依赖，得到两个ACDB和DE函数依赖。故有X(3)=X(2)BE=ABCDEG，因为X(3)=U，算法终止。(CG)F2+=ABCDEG包含B，故CGB是冗余的函数依赖，从F2中去掉。C设CGD为冗余的函数依赖，则去掉CGD，得：F3=ABC,DE,DG,CA,BEC,BCD,ACDB,CEA,CEG计算(CG)F3+：设X(0)=CG计算X(1)：扫描F3中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个CA函数依赖。故有X(1)=X(0)A=CGA=ACG。计算X(2)：扫描F3中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，因为找不到这样的函数依赖。故有X(2)=X(1)，算法终止。(CG)F3+=ACG。(CG)F3+=ACG不包含D，故CGD不是冗余的函数依赖，不能从F3中去掉。D设CEA为冗余的函数依赖，则去掉CEA，得：F4=ABC,DE,DG,CA,BEC,BCD,CGD,ACDB,CEG计算(CG)F4+：设X(0)=CE计算X(1)：扫描F4中的各个函数依赖，找到左部为CE或CE子集的函数依赖，得到一个CA函数依赖。故有X(1)=X(0)A=CEA=ACE。计算X(2)：扫描F4中的各个函数依赖，找到左部为ACE或ACE子集的函数依赖，得到一个CEG函数依赖。故有X(2)=X(1)G=ACEG。计算X(3)：扫描F4中的各个函数依赖，找到左部为ACEG或ACEG子集的函数依赖，得到一个CGD函数依赖。故有X(3)=X(2)D=ACDEG。计算X(4)：扫描F4中的各个函数依赖，找到左部为ACDEG或ACDEG子集的函数依赖，得到一个ACDB函数依赖。故有X(4)=X(3)B=ABCDEG。因为X(4)=U，算法终止。(CE)F4+=ABCDEG包含A，故CEA是冗余的函数依赖，从F4中去掉。 去掉F4中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）由于CA，函数依赖ACDB中的属性A是多余的，去掉A得CDB。故最小函数依赖集为：F=ABC,DE,DG,CA,BEC,BCD,CGD,CDB,CEG解2：利用Armstrong公理系统的推理规则求解 假设CGB为冗余的函数依赖，那么，从F中去掉它后能根据Armstrong公理系统的推理规则导出。因为CGD （已知）所以CGAAD，CGAACD （增广律）因为ACDB （已知）所以CGAB （传递律）因为CA （已知）所以CGB （伪传递律）故CGB是冗余的。 同理可证：CEA是多余的。 又因CA，可知函数依赖ACDB中的属性A是多余的，去掉A得CDB。故最小函数依赖集为：F=ABC,DE,DG,CA,BEC,BCD,CGD,CDB,CEG七、候选码算法 定义4b.6（候选码的等价定义）设F是关系模式R(U,F)的函数依赖集，K是U的一个属性子集，如果K关于F的闭包K+=U(含义？)，而K的任何真子集关于F的闭包都不为U，则K是R的一个候选码。 定义4b.6的推论：设F是关系模式R(U,F)的函数依赖集，如果属性子集X的每个属性都不出现在F中的任何一个函数依赖集的右边，则所有候选码中都一定有X。 说明：由求X+的算法可知，如果属性子集X的每个属性都不出现在F中的任何一个函数依赖集的右边，则任何不包含X的属性子集的闭包都不能包含X，当然也就不是U，这些属性子集就都不是R的码，所以R的所有候选码中都一定有X。 算法4b.2（有不出现在F中的任何一个函数依赖集的右边的属性时求候选码的算法） 找出不出现在F中的任何一个函数依赖集的右边的所有属性组成的属性子集X； 求X+，若X+=U,则X是R的候选码，且R再没有别的候选码，算法结束；否则进行； 逐个考察把不在X中的一个属性并入X得到的属性子集Yi,若Yi+=U,则Yi是一个候选码； 依次取不是候选码的Yi ，逐个考察把不在任何候选码中的一个属性并入Yi得到的属性子集Zi，若 Zi+=U,则Zi是一个候选码； 如此类推，直到再没有这样的属性子集与属性为止，就找出了R的所有候选码。 例4b.2 设关系模式 R=(U,F),U=ABCDE,F=ABC,CD,BEA, EDB，求所有候选码。 解：E不在F中右边出现，R的候选码必含E， E0=E,有EDB，所以E1=EDB,再找到BEA，所以E2=EDBA,再找到ABC，所以E3=EDBAC所以E+=EDBAC=U，所以E是R的唯一候选码。例4b.3 设关系模式 R=(U,F),U=ABCDE,F=ABCD,ED, DE,AEBC,