函数依赖公理体系PPT学习教案VIP

1、会计学1函数依赖公理体系函数依赖公理体系主要内容主要内容n阿姆斯特朗公理及推论nX关于F的闭包及其计算n最小函数依赖集n候选键的求解方法第1页/共32页一、阿姆斯特朗公理及推论一、阿姆斯特朗公理及推论是一系列推理规则最早出现在1974年W.W.Armstrong的论文里他人与1977年提出改进形式侯选键侯选键在在R中是否成中是否成立立问题引入：问题引入：第2页/共32页1 1、阿姆斯特朗阿姆斯特朗公理公理n 设有关系模式R(U,F)，U=A1,A2,An是R的属性集，F是R的属性集U上的FD集，X、Y、Z、W是U的子集。 阿姆斯特朗公理为：n A1 自反律：若YX，则XYn A2 增广律：若X

2、Y，则XZYZn A3 传递律：若XY,YZ，则XZ 第3页/共32页n Armstrong公理是正确的。n 方法：从函数依赖的定义出发n A1 自反律：若YX，则XYn证：设u、v为r的任意两个元组。n 若uX=vX，则u和v在X的任何子集上必然相等。 n 由条件YX ，所以有：uY=vY，n 由u、v的任意性，并根据函数依赖的定义，可得 XY。2 2、定理定理5.15.1第4页/共32页3 3、 阿姆斯特朗阿姆斯特朗公理的推论公理的推论n 合并规则：若XY且XZ，则XYZn 分解规则：若XY，且ZY，则XZn 伪传递规则：若XY且WYZ，则WXZ证：证：X XY YWXZWXZWXWYWX

3、WYWYZWYZ第5页/共32页4 4、定理定理5.25.2如果Ai(i=1,n)是关系模式R的属性,则XA1A2An成立的充分必要条件是XAi(i=n 1,n)均成立。 第6页/共32页二、二、X关于关于F的闭包及其计算的闭包及其计算n 例：已知关系模式R(A,B,C)，其函数依赖集为F=AB，BC，求函数依赖集F的闭包F+。 F+=A ， AB ， AC ， ABC ， B ， C A A， AB A， AC A， ABC A， B B， C CA B， AB B， AC B， ABC B， B C， A C， AB C， AC C， ABC C， B BC， A AB， AB AB， A

4、C 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 ABC，BC BC，第7页/共32页1、X关于关于F的闭包的闭包设 有 关 系 模 式 R ( U , F ) 和 属 性 集U=A1,A2,An的子集X。则称所有用阿姆斯特朗公理从F推导出的函数依赖XAi的属性Ai组成的集合称为X关于F的闭包，记为XF+，通常简记为X+。即n XF+=Ai|用公理从F推出的XAi集合元素集合元素对比对比第8页/共32页设有关系模式R(U，F)

5、，U=A1,A2,An是R的属性集，F是R的属性集U上的函数依赖集，X、Y是U的子集，则n XY能用Armstrong公理从F导出YX。2 2、定理定理5.35.3第9页/共32页n算法5.1 求属性集X关于函数依赖集F的闭包Xn输入：n 关系模式R的全部属性集U,U上的函数依赖集F，U的子集X。n输出：n X关于F的闭包X。n计算方法：3、X关于关于F的闭包的闭包X的的计算计算第10页/共32页n（1）X(0)=X。n（2）从F中找出满足条件VX(i)的所有函数依赖VW，并把所有的VW中的属性W组成的集合记为Z；也即从F中找出那些其决定因素是X(i)的子集的函数依赖，并把由所有这样的依赖的被

6、决定因素组成的集合记为Z。n（3）若ZX(i)，则转（5）。n（4）否则，X(i+1)=X(i)Z，并转（2）。n（5）停止计算，输出X(i)，即为X+。3、X关于关于F的闭包的闭包X的计算（续）的计算（续）第11页/共32页n例5.4 已知R(U),U=A,B,C,D,E,G， R上的FD集n F=ABC,CA,BCD,ACDB，DEG,BEC,n CGBD,CEAG，n X=BD，求X，BDA是否成立？n(1)X（0）=BD。n(2)X（1）=BDEGn(3)X（2）=BCDEGn(4)X（3）=ABCDEGX X=ABCDEG=ABCDEGABDABD，故，故BDABDA成立成立4、举例

7、、举例Z=EG BD=X(0)第12页/共32页一个函数依赖集F的闭包F通常包含很多函数依赖，有些函数依赖是无意义的，如平凡的函数依赖，还有一些是可以推导出的，即无关的函数依赖。如果将每一个函数依赖看作是对关系的一个约束，要检查F中的每一个函数依赖对应的约束，显然是一件很繁重的任务。如果能找出一个与F等价的、包含较少数目函数依赖的函数依赖集G，则可以简化此工作。最小函数依赖集的概念由此而提出。三、最小函数依赖集三、最小函数依赖集第13页/共32页定义5.5n 设F和G是两个函数依赖集，如果FG，则称F和G等价。如果F和G等价，则称F覆盖G，同时也称G覆盖F。1 1、函数依赖集的等价与覆盖函数依

8、赖集的等价与覆盖第14页/共32页n定理5.7 FG的充要条件是FG和GF。F F G Gu定理定理G G F F第15页/共32页u推论推论每一个函数依赖集F都被其右端只有一个属性的函数依赖组成的依赖集G所覆盖。第16页/共32页满足下列条件的函数依赖集F称为最小函数依赖集。n F中每一个FD的右端都是单个属性；n 对F中任何FD:XA，F-XA不等价于F；n 对F中的任何FD:XA和X的任何真子集Z，n (F-XA)ZA不等价于F。2 2、最小函数依赖集、最小函数依赖集第17页/共32页u求解方法求解方法n（1）用分解规则将F中的所有函数依赖分解成右端为单个属性的函数依赖；第18页/共32

9、页u求解方法（续一）求解方法（续一）n（2）去掉F中冗余的函数依赖 n 对于F中任一FD：XY n G = F-XY；n 求X关于G的闭包XG+；n 看XG+是否包含Y。如果XG+包含Y，则在G中逻辑蕴涵XY，说明XY是多余的函数依赖，所以F=G；如果X+不包含Y，则保留XY。第19页/共32页u求解方法求解方法（续二）（续二）（3）去掉左端多余的属性n 对于F中左端是非单属性的函数依赖（XYA），假设要判断Y是否是多余的属性n G = (F-XYA)XA；n 求X关于F的闭包XF+；n 如果A不属于XF+，则XA不在F+中，说明Y不是多余的属性，接着判别X是否是多余的属性；如果A属于XF+，

10、则说明Y是多余的属性，F=G。第20页/共32页ABABC C，C CA A，BCBCD D，ACDACDB B，D DEGEG，BEBEC C，CGCGBDBD，CECEAGAGF=F=ABABC C，C CA A，BCBCD D，ACDACDB,B,D DE,DE,DG G，BEBEC C，CGCGB B ，CGCGD D，CECEA,CEA,CEG G F F1 1= =n例5.5：求函数依赖集F的最小函数依赖集3、举例、举例第21页/共32页 F F2121= =ABABC C，C CA A，BCBCD D，ACDACDB,B,D DE,DE,DG G，BEBEC C，CGCGB B

11、，CGCGD D，CECEA,CEA,CEG G F F1 1= =ABABC C，C CA A，BCBCD D，ACDACDB B，D DE E，D DG G，BEBEC C，CGCGD D，CECEA,CEA,CEG G3、举例（续一）、举例（续一）n例5.5：求函数依赖集F的最小函数依赖集第22页/共32页 F F2222= =A BA B C C ， C C A A ， B CB C D D ，ACDACDB,B,D DE,DE,DG G，BEBEC C，CGCGD D，CECEA,CEA,CEG G F F2121= =ABABC C，C CA A，BCBCD D，ACDACDB B

12、，D DE E，D DG G，BEBEC C，CGCGD D，CECEG G3、举例（续二）、举例（续二）n例5.5：求函数依赖集F的最小函数依赖集第23页/共32页ABABC C，C CA A，BCBCD D，ACDACDB B，D DE E，D DG G，BEBEC C，CGCGD D，CECEG G F F2222= = F F3 3= =ABABC C，C CA A，BCBCD D，CDCDB B，D DE E，D DG G，BEBEC C，CGCGD D，CECEG G3、举例（续三）、举例（续三）n例5.5：求函数依赖集F的最小函数依赖集第24页/共32页 F F2121= =AB

13、ABC C，C CA A，BCBCD D，D DE E，D DG G，BEBEC C，CGCGB B，CECEG GABABC C，C CA A，BCBCD D，ACDACDB,B,D DE,DE,DG G，BEBEC C，CGCGB BCGCGD D，CECEA,CEA,CEG G F F1 1= =3、举例（续四）、举例（续四）n例5.5：求函数依赖集F的最小函数依赖集第25页/共32页四、候选键的求解方法四、候选键的求解方法n1、属性分类n 对于给定的关系R（U）和函数依赖集F，可将其属性分为4类：n L类：仅出现在F的函数依赖左部的属性；n R类：仅出现在F的函数依赖右部的属性；n N

14、类：在F的FD左右两边均未出现的属性；n LR类：在F的FD左右两边均出现的属性。第26页/共32页四、候选键的求解方法四、候选键的求解方法n2、快速求解候选键的一个充分条件n（1）若X是L类属性，则X必为R的某一候选键的成员；n（2）若X是L类属性，且X包含了R的全部属性，则X必为R的唯一候选键；n（3）若X是R类属性，则X不是任一候选键的成员；n（4）若X是N类属性，则X必包含在R的某一候选键中；n（5）若X是R的N类属性和L类属性组成的属性集，且X包含了R的全部属性，则X是R的唯一候选键。第27页/共32页四、候选键的求解方法四、候选键的求解方法n3、候选键的一般求解方法n 将所有属性分

15、为L、R、N和LR四类，并令X代表L和N类，Y代表LR类；n 求XF+：若XF+包含了R的全部属性，则X是R的唯一候选键，转；n 在Y中取一属性A，并求(XA)F+ ：若(XA)F+包含了R的全部属性，则XA为的一个候选键；n 重复，直到Y中的属性依次取完为止；n 从Y中除去所有已成为主属性的属性A；第28页/共32页四、候选键的求解方法四、候选键的求解方法n3、候选键的一般求解法n 在剩余的属性中依次取两个属性、三个属性，将其记为集合B，并求(XB)F+ ：若(XB)F+包含了R的全部属性，且自身不包含已求出的候选键，则XB为R的一个候选键；n 重复，直到Y中的属性按的组合依次取完为止； n 输出候选键，算法结束。第29页/共32页R R的候选键的候选键：A A、E E、BCBC和和CDCD四、候选键