一、逻辑蕴涵定义：设有关系模式R(U)及其函数依赖集F，如果对于R的任一个满足F的关系r函数依赖X→Y都成立，则称F逻辑蕴涵X→Y，或称X→Y可以由F推出。例：关系模式R=(A,B,C),函数依赖集F={A→B,B→C},F逻辑蕴涵A→C。证：设u,v为r中任意两个元组：若A→C不成立，则有u[A]=v[A],而u[C]≠v[C]而且A→B,B→C,知u[A]=v[A],u[B]=v[B],u[C]=v[C],即若u[A]=v[A]则u[C]=v[C]，和假设矛盾。故F逻辑蕴涵A→C。满足F依赖集的所有元组都函数依赖X→Y（X→Y不属于F集），则称F逻辑蕴涵X→Y（X→Y由F依赖集中所有依赖关系推断而出）二、Armstrong公理1、定理：若U为关系模式R的属性全集，F为U上的一组函数依赖，设X、Y、Z、W均为R的子集，对R(U,F)有：F1(自反性)：若X≥Y(表X包含Y），则X→Y为F所蕴涵；(F1':X→X)F2(增广性):若X→Y为F所蕴涵，则XZ→YZ为F所蕴涵；(F2':XZ→Y)F3(传递性):若X→Y,Y→Z为F所蕴涵，则X→Z为F所蕴涵；F4(伪增性)：若X→Y，W≥Z(表W包含Z）为F所蕴涵，则XW→YZ为F所蕴涵；F5(伪传性):若X→Y，YW→Z为F所蕴涵,则XW→Z为F所蕴涵；F6(合成性):若X→Y,X→Z为F所蕴涵，则X→YZ为F所蕴涵；F7(分解性):若X→Y,Z≤Y(表Z包含于Y）为F所蕴涵，则X→Z为F所蕴涵。函数依赖推理规则F1∽F7都是正确的。2、Armstrong公理：推理规则F1、F2、F3合称Armstrong公理；F4∽F7可由F1、F2、F3推得，是Armstrong公理的推论部分。三、函数依赖的闭包定义：若F为关系模式R(U)的函数依赖集，我们把F以及所有被F逻辑蕴涵的函数依赖的集合称为F的闭包，记为F。即：F={X→Y|X→Y∈F∨“应用Armstong公理从F中导出的任何X→Y”}△F包含于F，如果F=F，则F为函数依赖的一个完备集。△规定：若X为U的子集，X→Φ属于F。例：R=ABC,F={A→B,B→C},求F解：F={A→Φ,AB→Φ,AC→Φ,ABC→Φ,B→Φ,C→Φ,A→A,AB→A,AC→A,ABC→A,B→B,C→C,A→B,AB→B,AC→B,ABC→B,B→C,A→C,AB→C,AC→C,ABC→C,B→BC,A→AB,AB→AB,AC→AB,ABC→AB,BC→Φ,A→AC,AB→AC,AC→AC,ABC→AC,BC→B,A→BC,AB→BC,AC→BC,ABC→BC,BC→C,A→ABC,AB→ABC,AC→ABC,ABC→A,BC→BC}例：已知关系模式R中U={A，B，C，D,E,G},F={AB→C,C→A,BC→D,ACD→B,D→EG,BE→C,CG→BD,CE→AG},判断BD→AC是否属于F解：由D→EG知D→E，BD→BE …①又知BE→C，C→A所以BE→A,BE→AC…②由①、②知，BD→AC，所以BD→AC被F所蕴涵，即BD→AC属于F例：已知关系模式R中U={A，B，C，E,H,P,G},F={AC→PE,PG→A,B→CE,A→P,GA→B,GC→A,PAB→G,AE→GB,ABCP→H},证明BG→HE属于F证：由B→CE知B→C，B→E,BG→GC …①又知GC→A，A→P所以BG→A,BG→ABCP…②又ABCP→H，由①、②知BG→HE，所以BG→HE被F所蕴涵，即BG→HE属于F四、属性集闭包1、定义：若F为关系模式R(U)的函数依赖集，X是U的子集，则由Armstrong公理推导出的所有X→Ai所形成的属性集例：设R=ABC,F={A→B,B→C}当X分别为A,B,C是求X。解：当X=A时，X=ABC当X=B时，X=BC当X=C时，X=C*X代表的属性集可以决定的属性集（包括本身）2、定理：当且仅当Y属于X时，X→Y能根据Armstron公理由F导出。证：设Y=A1,A2,…,An①充分条件：当Y属于X时,对于每个i,X→Ai可由公理导出。再用合并规则可得X→Y。②必要条件：若X→Y能够由公理导出,则根据分解规,X→Ai(i=1,2,…,n)成立，所以Y属于X。3、计算X(1)算法依据：若F为关系模式R(U)的函数依赖集,X,Z,W是U的子集,对于任意的Z→W∈F,若X≥Z（表X包含Z）,则X→XW。(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中的每个函数依赖W→Z){if(news包含W){news=news∪Z;从G中删除函数依赖W→Z;}}}returnnews;}例：已知关系模式R中U={A，B，C，D,E,G},F={AB→C,C→A,BC→D,ACD→B,D→EG,BE→C,CG→BD,CE→AG},求(BD)，判断BD→AC是否属于F解：X=BDEGCA结论：(BD)=ABCDEG,BD→AC可由F导出，即BD→AC属于F例：已知关系模式R中U={A，B，C，E,H,P,G},F={AC→PE,PG→A,B→CE,A→P,GA→B,GC→A,PAB→G,AE→GB,ABCP→H},证明BG→HE属于F证：因为,(BG)=ABCEHPG,所以BG→HE可由F导出，即BG→HE属于F4、结论判定函数依赖X→Y是否能由F导出的问题，可转化为求X并判定Y是否是X子集的问题。即求闭包问题可转化为求属性集问题。判定给定函数依赖X→Y是否蕴涵于函数依赖集F算法实现：输入：函数依赖集合F,函数依赖X→Y输出：若X→Y∈F输出真，否则输出假算法伪语言描述：number(F,X→Y){if(Y包含于close(X,F))return真elsereturn假}{Ai|i=1,2,…}称为X对于F的闭包，记为X。五、等价和覆盖定义：关系模式R上的两个依赖集F和G，如果F=G，则称F和G是等价的，记做F≡G。若F≡G，则称G是F的一个覆盖，反之亦然。两个等价的函数依赖集在表达能力上是完全相同的。六、最小函数依赖集定义：如果函数依赖集F满足下列条件，则称F为最小函数依赖集或最小覆盖。①F中的任何一个函数依赖的右部仅含有一个属性；②F中不存在这样一个函数依赖X→A，使得F与F-{X→A}等价；③F中不存在这样一个函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z→A}与F等价。算法：计算最小函数依赖集。输入一个函数依赖集输出F的一个等价的最小函数依赖集G步骤：①用分解的法则，使F中的任何一个函数依赖的右部仅含有一个属性；②去掉多余的函数依赖：从第一个函数依赖X→Y开始将其从F中去掉，然后在剩下的函数依赖中求X的闭包X，看X是否包含Y，若是，则去掉X→Y；否则不能去掉，依次做下去。直到找不到冗余的函数依赖；③去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如XY→A，若要判Y为多余的，则以X→A代替XY→A是否等价？若A(X)，则Y是多余属性，可以去掉。举例：已知关系模式R，U={A,B,C,D,E,G}，F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG}，求F的最小函数依赖集。解1：利用算法求解，使得其满足三个条件①利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖，得F为：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}②去掉F中多余的函数依赖A．设AB→C为冗余的函数依赖，则去掉AB→C，得：F1={D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}计算(AB)F1：设X(0)=AB计算X(1)：扫描F1中各个函数依赖，找到左部为AB或AB子集的函数依赖，因为找不到这样的函数依赖。故有X(1)=X(0)=AB，算法终止。(AB)F1=AB不包含C，故AB→C不是冗余的函数依赖，不能从F1中去掉。B．设CG→B为冗余的函数依赖，则去掉CG→B，得：F2={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→A,CE→G}计算(CG)F2：设X(0)=CG计算X(1)：扫描F2中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个C→A函数依赖。故有X(1)=X(0)∪A=CGA=ACG。计算X(2)：扫描F2中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，得到一个CG→D函数依赖。故有X(2)=X(1)∪D=ACDG。计算X(3)：扫描F2中的各个函数依赖，找到左部为ACDG或ACDG子集的函数依赖，得到两个ACD→B和D→E函数依赖。故有X(3)=X(2)∪BE=ABCDEG，因为X(3)=U，算法终止。(CG)F2=ABCDEG包含B，故CG→B是冗余的函数依赖，从F2中去掉。C．设CG→D为冗余的函数依赖，则去掉CG→D，得：F3={AB→C,D→E,D→G,C→A,BE→C,BC→D,ACD→B,CE→A,CE→G}计算(CG)F3：设X(0)=CG计算X(1)：扫描F3中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个C→A函数依赖。故有X(1)=X(0)∪A=CGA=ACG。计算X(2)：扫描F3中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，因为找不到这样的函数依赖。故有X(2)=X(1)，算法终止。(CG)F3=ACG。(CG)F3=ACG不包含D，故CG→D不是冗余的函数依赖，不能从F3中去掉。D．设CE→A为冗余的函数依赖，则去掉CE→A，得：F4={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→G}计算(CG)F4：设X(0)=CE计算X(1)：扫描F4中的各个函数依赖，找到左部为CE或CE子集的函数依赖，得到一个C→A函数依赖。故有X(1)=X(0)∪A=CEA=ACE。计算X(2)：扫描F4中的各个函数依赖，找到左部为ACE或ACE子集的函数依赖，得到一个CE→G函数依赖。故有X(2)=X(1)∪G=ACEG。计算X(3)：扫描F4中的各个函数依赖，找到左部为ACEG或ACEG子集的函数依赖，得到一个CG→D函数依赖。故有X(3)=X(2)∪D=ACDEG。计算X(4)：扫描F4中的各个函数依赖，找到左部为ACDEG或ACDEG子集的函数依赖，得到一个ACD→B函数依赖。故有X(4)=X(3)∪B=ABCDEG。因为X(4)=U，算法终止。(CE)F4=ABCDEG包含A，故CE→A是冗余的函数依赖，从F4中去掉。③去掉F4中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）由于C→A，函数依赖ACD→B中的属性A是多余的，去掉A得CD→B。故最小函数依赖集为：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,CD→B,CE→G}解2：利用Armstrong公理系统的推理规则求解①假设CG→B为冗余的函数依赖，那么，从F中去掉它后能根据Armstrong公理系统的推理规则导出。因为CG→D（已知）所以CGA→AD，CGA→ACD（增广律）因为ACD→B（已知）所以CGA→B（传递律）因为C→A（已知）所以CG→B（伪传递律）故CG→B是冗余的。②同理可证：CE→A是多余的。③又因C→A，可知函数依赖ACD→B中的属性A是多余的，去掉A得CD→B。故最小函数依赖集为：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,CD→B,CE→G}七、候选码算法定义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={AB→C,C→D,BE→A,E→DB}，求所有候选码。解：E不在F中右边出现，R的候选码必含E，E0=E,有E→DB，所以E1=EDB,再找到BE→A，所以E2=EDBA,再找到AB→C，所以E3=EDBAC所以E=EDBAC=U，所以E是R的唯一候选码。例4b.3设关系模式R=(U,F),U={ABCDE},F={AB→CD,E→D,D→E,AE→BC,B→E}，求所有候选码。解：A不在F中右边出现，R的候选码必含A，A=A,所以A不是候选码；(AB)0=AB,AB→CD,B→E所以(AB)1=ABCDE(AB)=ABCDE=U,所以，AB是候选码；(AC)=AC,所以，AC不是候选码(AD)0=AD,D→E,所以(AD)1=ADE,E→D,AE→BC所以(AD)2=ADEBC(AD)=ADEBC=U,所以，AD是候选码(AE)0=AE,AE→BC,E→D，(AE)=AEDBC=U,所以，AE是候选码；3个及以上属性的含A的子集都含AB或AD或AE，都是超码，不能是候选码。所以，R的候选码有AB,AD,AE。
本文档为【函数依赖的逻辑蕴涵(1)】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483