函数依赖公理体系课件

第2讲函数依赖的公理体系第5章关系数据库模式设计主要内容阿姆斯特朗公理及推论X关于F的闭包及其计算最小函数依赖集候选键的求解方法一、阿姆斯特朗公理及推论是一系列推理规则最早出现在1974年W.W.Armstrong的论文里他人与1977年提出改进形式F=X→YF+侯选键X→Y在R中是否成立能从F导出的所有X→Y推导工具？问题引入：

Armstrong公理是正确的。

方法：从函数依赖的定义出发A1自反律：若YX，则XY证：设u、v为r的任意两个元组。若u[X]=v[X]，则u和v在X的任何子集上必然相等。由条件YX

，所以有：u[Y]=v[Y]，由u、v的任意性，并根据函数依赖的定义，可得XY。2、定理5.13、阿姆斯特朗公理的推论合并规则：若XY且XZ，则XYZ

分解规则：若XY，且ZY，则XZ

伪传递规则：若XY且WYZ，则WXZ增广律传递律证：XYWX→ZWX→WYWY→Z作用：将一个FD分解成若干个右边是单属性的FD。用于确定关系的主键。4、定理5.2

如果Ai(i=1,…,n)是关系模式R的属性,则XA1A2…An成立的充分必要条件是XAi(i=1,…,n)均成立。

1、X关于F的闭包设有关系模式R(U,F)和属性集U={A1,A2,…,An}的子集X。则称所有用阿姆斯特朗公理从F推导出的函数依赖X→Ai的属性Ai组成的集合称为X关于F的闭包，记为XF+，通常简记为X+。即

XF+={Ai|用公理从F推出的X→Ai}集合元素对比F+和X+设有关系模式R(U，F)，U={A1,A2,…,An}是R的属性集，F是R的属性集U上的函数依赖集，X、Y是U的子集，则

XY能用Armstrong公理从F导出YX＋。该定理把判定XY是否能由F根据Armstrong公理导出的问题求出X＋，判定Y是否为X＋的子集的问题。2、定理5.3算法5.1

求属性集X关于函数依赖集F的闭包X＋输入：关系模式R的全部属性集U,U上的函数依赖集F，U的子集X。输出：X关于F的闭包X＋。计算方法：3、X关于F的闭包X＋的计算例5.4已知R(U),U={A,B,C,D,E,G}，R上的FD集F={AB→C,C→A,BC→D,ACD→B，D→EG,BE→C,CG→BD,CE→AG}，X=BD，求X＋，BD→A是否成立？(1)X（0）=BD。(2)X（1）=BDEG(3)X（2）=BCDEG(4)X（3）=ABCDEGX＋=ABCDEGA∈BD＋，故BD→A成立4、举例Z=EGBD=X(0)一个函数依赖集F的闭包F＋通常包含很多函数依赖，有些函数依赖是无意义的，如平凡的函数依赖，还有一些是可以推导出的，即无关的函数依赖。如果将每一个函数依赖看作是对关系的一个约束，要检查F＋中的每一个函数依赖对应的约束，显然是一件很繁重的任务。如果能找出一个与F等价的、包含较少数目函数依赖的函数依赖集G，则可以简化此工作。最小函数依赖集的概念由此而提出。三、最小函数依赖集

定义5.5设F和G是两个函数依赖集，如果F＋＝G＋，则称F和G等价。如果F和G等价，则称F覆盖G，同时也称G覆盖F。1、函数依赖集的等价与覆盖作用：任一函数依赖集都可转化成由右端只有单一属性的依赖组成的集合。该结论是最小函数依赖集的基础。推论每一个函数依赖集F都被其右端只有一个属性的函数依赖组成的依赖集G所覆盖。满足下列条件的函数依赖集F称为最小函数依赖集。①F中每一个FD的右端都是单个属性；②对F中任何FD:XA，F-{XA}不等价于F；③对F中的任何FD:XA和X的任何真子集Z，(F-{XA})∪{ZA}不等价于F。2、最小函数依赖集F没有多余的FD每个FD左端无多余的属性求解方法（1）用分解规则将F中的所有函数依赖分解成右端为单个属性的函数依赖；Armstrong公理的推论分解规则：若XY，且ZY，则XZ求解方法（续二）（3）去掉左端多余的属性对于F中左端是非单属性的函数依赖（XYA），假设要判断Y是否是多余的属性①G=(F-{XYA})∪{XA}；②求X关于F的闭包XF+；③如果A不属于XF+，则XA不在F+中，说明Y不是多余的属性，接着判别X是否是多余的属性；如果A属于XF+，则说明Y是多余的属性，F=G。ABC，CA，BCD，ACDB，DEG，BEC，CGBD，CEAGF=ABC，CA，BCD，ACDB,DE,DG，BEC，CGB，CGD，CEA,CEG①F1=例5.5：求函数依赖集F的最小函数依赖集法1：3、举例②F21=ABC，CA，BCD，ACDB,DE,DG，BEC，CGB，CGD，CEA,CEG①F1=ABC，CA，BCD，ACDB，DE，DG，BEC，CGD，CEA,CEG3、举例（续一）例5.5：求函数依赖集F的最小函数依赖集ABC，CA，BCD，ACDB，DE，DG，BEC，CGD，CEG②F22=③F3=ABC，CA，BCD，CDB，DE，DG，BEC，CGD，CEG3、举例（续三）例5.5：求函数依赖集F的最小函数依赖集②F21=ABC，CA，BCD，DE，DG，BEC，CGB，CEGABC，CA，BCD，ACDB,DE,DG，BEC，CGBCGD，CEA,CEG①F1=3、举例（续四）例5.5：求函数依赖集F的最小函数依赖集法2：四、候选键的求解方法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；四、候选键的求解方法3、候选键的一般求解法⑥在剩余的属性中依次取两个属性、三个属性，…，将其记为集合B，并求(XB)F+：若(XB)F+包含了R的全部属性，且自身不包含已求出的候选键，则XB为R的一个候选键；⑦重复⑥，直到Y中的属性按⑥的组合依次取完为止；⑧输出候选键，算法结束。R的候选键：A、E、BC和CD四、候选键的求解方法3、候选键的一般求解法例:设有关系模式R（A,B,C,D,E），R的函数依赖集F＝{ABC,CDE,BD,E