《函数依赖公理体系》课件.ppt

1、主要内容主要内容n阿姆斯特朗公理及推论阿姆斯特朗公理及推论nX关于关于F的闭包及其计算的闭包及其计算n最小函数依赖集最小函数依赖集n候选键的求解方法候选键的求解方法一、阿姆斯特朗公理及推论一、阿姆斯特朗公理及推论是一系列推理规则是一系列推理规则最早出现在最早出现在19741974年年W.W.ArmstrongW.W.Armstrong的论文里的论文里他人与他人与19771977年提出改进形式年提出改进形式侯选键侯选键在在R中是否成立中是否成立问题引入：问题引入：1 1、阿姆斯特朗阿姆斯特朗公理公理 设有关系模式设有关系模式R(U,F)R(U,F)，U=AU=A1 1,A,A2 2,A,An n

2、 是是R R的属性集，的属性集，F F是是R R的属性集的属性集U U上的上的FDFD集，集，X X、Y Y、Z Z、W W是是U U的子集。的子集。阿姆斯特朗阿姆斯特朗公理为：公理为：A1 A1 自反律自反律：若：若Y Y X X，则，则X XY Y A2 A2 增广律增广律：若：若X XY Y，则，则XZXZYZYZ A3 A3 传递律传递律：若：若X XY,YY,YZ Z，则，则X XZ Z ArmstrongArmstrong公理是正确的公理是正确的。方法方法：从函数依赖的定义出发从函数依赖的定义出发 A1 A1 自反律自反律：若若Y Y X X，则，则X XY Y证：证：设设u u、

3、v v为为r r的任意两个元组。的任意两个元组。若若uXuX=vXvX，则，则u u和和v v在在X X的任何子集上必然的任何子集上必然相等。相等。由条件由条件Y Y X X ，所以有：，所以有：uYuY=vYvY，由由u u、v v的任意性，并根据函数依赖的定义，的任意性，并根据函数依赖的定义，可得可得 X XY Y。2 2、定理定理5.15.13 3、阿姆斯特朗阿姆斯特朗公理的推论公理的推论 合并规则合并规则：若：若X XY Y且且X XZ Z，则，则X XYZYZ 分解规则分解规则：若：若X XY Y，且，且Z Z Y Y，则，则X XZ Z 伪传递规则伪传递规则：若：若X XY Y且且

4、WYWYZ Z，则，则WXWXZ Z证：证：X XY YWXZWXZWXWYWXWYWYZWYZ4 4、定理定理5.25.2如果如果A Ai i(i(i=1,=1,n),n)是关系模式是关系模式R R的属性的属性,则则X XA A1 1A A2 2A An n成立的充分必要条件是成立的充分必要条件是X XA Ai i(i(i=1,1,n),n)均成立。均成立。二、二、X关于关于F的闭包及其计算的闭包及其计算 例：已知关系模式例：已知关系模式R(A,B,C)R(A,B,C)，其函数依赖集为，其函数依赖集为F=ABF=AB，BCBC，求函数依赖集，求函数依赖集F F的闭包的闭包F F+。F+=A

5、，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，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 ABC，BC BC，1、X关于关于F的闭包的闭包设 有 关 系 模 式设 有 关 系 模 式 R(U,F)R(U,F)和 属 性 集和 属 性 集U=AU=A1 1,A,A2 2,A,An

6、n 的子集的子集X X。则称所有用阿姆斯特。则称所有用阿姆斯特朗公理从朗公理从F F推导出的函数依赖推导出的函数依赖X XAAi i的属性的属性A Ai i组成组成的集合称为的集合称为X X关于关于F F的闭包，记为的闭包，记为X XF F+，通常简记，通常简记为为X X+。即。即 X XF F+=A=Ai i|用公理从用公理从F F推出的推出的X XAAi i 集合元素集合元素对比对比设有关系模式设有关系模式R(UR(U，F)F)，U=AU=A1 1,A,A2 2,A An n 是是R R的属性集，的属性集，F F是是R R的属性集的属性集U U上的函数依赖集，上的函数依赖集，X X、Y Y

7、是是U U的子集，则的子集，则 X XY Y能用能用ArmstrongArmstrong公理从公理从F F导出导出Y Y X X。2 2、定理定理5.35.3算法算法5.15.1 求属性集求属性集X X关于函数依赖集关于函数依赖集F F的闭包的闭包X X输入：输入：关系模式关系模式R R的全部属性集的全部属性集U,UU,U上的函数依赖集上的函数依赖集F F，U U的子集的子集X X。输出：输出：X X关于关于F F的闭包的闭包X X。计算方法：计算方法：3、X关于关于F的闭包的闭包X的的计算计算（1 1）X X(0)(0)=X=X。（2 2）从）从F F中找出满足条件中找出满足条件V V X

8、X(i(i)的所有函数依赖的所有函数依赖VWVW，并把所有的，并把所有的VWVW中的属性中的属性W W组成的集合记组成的集合记为为Z Z；也即从；也即从F F中找出那些其决定因素是中找出那些其决定因素是X X(i(i)的子的子集的函数依赖，并把由所有这样的依赖的被决集的函数依赖，并把由所有这样的依赖的被决定因素组成的集合记为定因素组成的集合记为Z Z。（3 3）若）若Z Z X X(i(i)，则转（，则转（5 5）。）。（4 4）否则，）否则，X X(i+1)(i+1)=X X(i)(i)Z Z，并转（，并转（2 2）。）。（5 5）停止计算，输出）停止计算，输出X X(i(i)，即为，即为X

9、 X+。3、X关于关于F的闭包的闭包X的计算（续）的计算（续）例例5.4 5.4 已知已知R(U),U=A,B,C,D,E,GR(U),U=A,B,C,D,E,G，R R上的上的FDFD集集 F=ABC,CA,BCD,ACDB F=ABC,CA,BCD,ACDB，DEG,BEC,DEG,BEC,CGBD,CEAG CGBD,CEAG，X=BD X=BD，求，求X X，BDABDA是否成立？是否成立？(1)X(1)X（0 0）=BD=BD。(2)X(2)X（1 1）=BDEG=BDEG(3)X(3)X（2 2）=BCDEG=BCDEG(4)X(4)X（3 3）=ABCDEG=ABCDEGX X=

10、ABCDEG=ABCDEGABDABD，故，故BDABDA成立成立4、举例、举例Z=EG BD=X(0)一个函数依赖集一个函数依赖集F F的闭包的闭包F F通常包含很多函通常包含很多函数依赖，有些函数依赖是无意义的，如平凡的数依赖，有些函数依赖是无意义的，如平凡的函数依赖，还有一些是可以推导出的，即无关函数依赖，还有一些是可以推导出的，即无关的函数依赖。如果将每一个函数依赖看作是对的函数依赖。如果将每一个函数依赖看作是对关系的一个约束，要检查关系的一个约束，要检查F F中的每一个函数依中的每一个函数依赖对应的约束，显然是一件很繁重的任务。如赖对应的约束，显然是一件很繁重的任务。如果能找出一个与

11、果能找出一个与F F等价的、包含较少数目函数依等价的、包含较少数目函数依赖的函数依赖集赖的函数依赖集G G，则可以简化此工作。最小函，则可以简化此工作。最小函数依赖集的概念由此而提出。数依赖集的概念由此而提出。三、最小函数依赖集三、最小函数依赖集定义定义5.55.5 设设F F和和G G是两个函数依赖集，如果是两个函数依赖集，如果F FG G，则，则称称F F和和G G等价。如果等价。如果F F和和G G等价，则称等价，则称F F覆盖覆盖G G，同，同时也称时也称G G覆盖覆盖F F。1 1、函数依赖集的等价与覆盖函数依赖集的等价与覆盖定理定理5.75.7 F FG G的充要条件是的充要条件是

12、F F G G和和G G F F。F F G Gu定理定理G G F Fu推论推论每一个函数依赖集每一个函数依赖集F F都被其都被其右端只有一个属右端只有一个属性性的函数依赖组成的依赖集的函数依赖组成的依赖集G G所覆盖。所覆盖。满足下列条件的函数依赖集满足下列条件的函数依赖集F F称为最小函数依称为最小函数依赖集。赖集。F F中每一个中每一个FDFD的右端都是单个属性；的右端都是单个属性；对对F F中任何中任何FD:XFD:XA A，F-XF-XAA不等价于不等价于F F；对对F F中的任何中的任何FD:XFD:XA A和和X X的任何真子集的任何真子集Z Z，(F-X (F-XA)ZA)Z

13、AA不等价于不等价于F F。2 2、最小函数依赖集、最小函数依赖集u求解方法求解方法（1 1）用分解规则将）用分解规则将F F中的所有函数依赖分解成右中的所有函数依赖分解成右端为单个属性的函数依赖；端为单个属性的函数依赖；u求解方法（续一）求解方法（续一）（2 2）去掉）去掉F F中冗余的函数依赖中冗余的函数依赖 对于对于F F中任一中任一FDFD：X XY Y G=F-X G=F-XYY；求求X X关于关于G G的闭包的闭包XG+；看看X XG G+是否包含是否包含Y Y。如果。如果X XG G+包含包含Y Y，则在，则在G G中中逻辑蕴涵逻辑蕴涵X XY Y，说明，说明X XY Y是多余的

14、函数依赖，是多余的函数依赖，所以所以F=GF=G；如果；如果X X+不包含不包含Y Y，则保留，则保留X XY Y。u求解方法求解方法（续二）（续二）（3 3）去掉左端多余的属性）去掉左端多余的属性 对 于对 于 F F 中 左 端 是 非 单 属 性 的 函 数 依 赖中 左 端 是 非 单 属 性 的 函 数 依 赖（XYXYA A），假设要判断），假设要判断Y Y是否是多余的属性是否是多余的属性 G=(F-XY G=(F-XYA)XA)XAA；求求X X关于关于F F的闭包的闭包XF+；如果如果A A不属于不属于X XF F+，则，则X XA A不在不在F F+中，说明中，说明Y Y不是

15、多余的属性，接着判别不是多余的属性，接着判别X X是否是多余的属性；是否是多余的属性；如果如果A A属于属于X XF F+，则说明，则说明Y Y是多余的属性，是多余的属性，F=GF=G。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=例例5.55.5：求函数依赖集：求函数依赖集F F的最小函数依赖集的最小函数依赖集3、举

16、例、举例 F F2121=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=ABABC C，C CA A，BCBCD D，ACDACDB B，D DE E，D DG G，BEBEC C，CGCGD D，CECEA,CEA,CEG G3、举例（续一）、举例（续一）例例5.55.5：求函数依赖集：求函数依赖集F F的最小函数依赖集的最小函数依赖集 F F2222=ABABC C，C CA A，BCBCD D，ACDACDB,B,D DE,DE,DG G，BEBEC

17、 C，CGCGD D，CECEA,CEA,CEG G F F2121=ABABC C，C CA A，BCBCD D，ACDACDB B，D DE E，D DG G，BEBEC C，CGCGD D，CECEG G3、举例（续二）、举例（续二）例例5.55.5：求函数依赖集：求函数依赖集F F的最小函数依赖集的最小函数依赖集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，

18、CGCGD D，CECEG G3、举例（续三）、举例（续三）例例5.55.5：求函数依赖集：求函数依赖集F F的最小函数依赖集的最小函数依赖集 F F2121=ABABC 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、举例（续四）、举例（续四）例例5.55.5：求函数依赖集：求函数依赖集F F的最小函数依赖集的最小函数依赖集四、候选键的求解方法四、

19、候选键的求解方法1 1、属性分类、属性分类 对于给定的关系对于给定的关系R R（U U）和函数依赖集）和函数依赖集F F，可，可将其属性分为将其属性分为4 4类：类：L L类：仅出现在类：仅出现在F F的函数依赖的函数依赖左部左部的属性；的属性；R R类：仅出现在类：仅出现在F F的函数依赖的函数依赖右部右部的属性；的属性；N N类：在类：在F F的的FDFD左右两边均左右两边均未未出现出现的属性；的属性；LR LR类：在类：在F F的的FDFD左右两边均出现左右两边均出现的属性。的属性。四、候选键的求解方法四、候选键的求解方法2 2、快速求解候选键的一个充分条件、快速求解候选键的一个充分条件

20、（1）若）若X是是L类属性，则类属性，则X必为必为R的某一候选键的成员；的某一候选键的成员；（2）若）若X是是L类属性，且类属性，且X包含了包含了R的全部属性，则的全部属性，则X必必为为R的的唯一唯一候选键；候选键；（3）若）若X是是R类属性，则类属性，则X不是任一候选键的成员；不是任一候选键的成员；（4）若）若X是是N类属性，则类属性，则X必包含在必包含在R的某一候选键中；的某一候选键中；（5）若）若X是是R的的N类属性和类属性和L类属性组成的属性集，且类属性组成的属性集，且X包含了包含了R的全部属性，则的全部属性，则X是是R的的唯一唯一候选键。候选键。四、候选键的求解方法四、候选键的求解方

21、法3 3、候选键的一般求解方法、候选键的一般求解方法 将所有属性分为将所有属性分为L、R、N和和LR四类，并令四类，并令X代代表表L和和N类，类，Y代表代表LR类；类；求求XF+：若：若XF+包含了包含了R的全部属性，则的全部属性，则X是是R的的唯一候选键，转；唯一候选键，转；在在Y中取一属性中取一属性A，并求，并求(XA)F+：若：若(XA)F+包包含了含了R的全部属性，则的全部属性，则XA为的一个候选键；为的一个候选键；重复，直到重复，直到Y中的属性依次取完为止；中的属性依次取完为止；从从Y中除去所有已成为主属性的属性中除去所有已成为主属性的属性A；四、候选键的求解方法四、候选键的求解方法

22、3 3、候选键的一般求解法、候选键的一般求解法 在剩余的属性中依次取两个属性、三个属在剩余的属性中依次取两个属性、三个属性，性，将其记为集合，将其记为集合B，并求，并求(XB)F+：若：若(XB)F+包含了包含了R的全部属性，且的全部属性，且自身不包含已自身不包含已求出的候选键求出的候选键，则，则XB为为R的一个候选键；的一个候选键；重复，直到重复，直到Y中的属性按的组合依次取完中的属性按的组合依次取完为止；为止；输出候选键，算法结束。输出候选键，算法结束。R R的候选键的候选键：A A、E E、BCBC和和CDCD四、候选键的求解方法四、候选键的求解方法3 3、候选键的一般求解法、候选键的一般求解法例例:设有关系模式设有关系模式R R（A,B,C,D,EA,B,C,D,E），），R R的函数依赖的函数依赖集集F FAABC,CDBC,CDE,BE,BD,ED,EAA，求，求R R的所有候的所有候选键。选键。均为均为LRLR类类,令令Y=ABCDEY=ABCDE。A A+=ABCDE E=ABCDE E+=ABCDE=ABCDE BCBC+=ABCDE CD=ABCDE CD+=ABCDE=ABCDE ArmstrongArmstrong公理公理及推论及推论小结小结