函数依赖公理系统

1、关于函数依赖的公理系统第1页，共30页，2022年，5月20日，10点59分，星期四 数据依赖的公理系统逻辑蕴含定义: 对于满足一组函数依赖 F 的关系模式R ，其任何一个关系r，若函数依赖XY都成立, 则称F 逻辑蕴含X Y第2页，共30页，2022年，5月20日，10点59分，星期四Armstrong公理系统从已知函数依赖集F要问X Y是否为F逻辑蕴含，就要一套推理规则，由Armstrong在1974年提出。这套推理规则，是模式分解算法的理论基础。用途从一组函数依赖求得蕴含的函数依赖。求给定关系模式的码。第3页，共30页，2022年，5月20日，10点59分，星期四1. Armstrong

2、公理系统 关系模式R 来说有以下的推理规则：Al.自反律（Reflexivity）： 若Y X U，则X Y为F所蕴含。A2.增广律（Augmentation）：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。A3.传递律（Transitivity）：若XY及YZ为F所蕴含，则XZ为F所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F第4页，共30页，2022年，5月20日，10点59分，星期四定理 Armstrong推理规则是正确的（l）自反律:若Y X U，则X Y为F所蕴含证: 设Y X U 对R 的任一关系r中的任意两个元组t，s：若tX=sX，由于Y

3、 X，有ty=sy，所以XY成立.自反律得证第5页，共30页，2022年，5月20日，10点59分，星期四定理 Armstrong推理规则是正确的(2)增广律: 若XY为F所蕴含，且Z U，则XZYZ 为F所蕴含。 证：设XY为F所蕴含，且Z U。 设R 的任一关系r中任意的两个元组t，s；若tXZ=sXZ，则有tX=sX和tZ=sZ；由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ为F所蕴含.增广律得证。第6页，共30页，2022年，5月20日，10点59分，星期四定理 Armstrong推理规则是正确的(3) 传递律：若XY及YZ为F所蕴含，则 XZ为 F所蕴含。证：设XY及YZ

4、为F所蕴含。对R 的任一关系 r中的任意两个元组 t，s。若tX=sX，由于XY，有 tY=sY；再由YZ，有tZ=sZ，所以XZ为F所蕴含.传递律得证。第7页，共30页，2022年，5月20日，10点59分，星期四2. 导出规则1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则： 合并规则：由XY，XZ，有XYZ。 （A2， A3） 伪传递规则：由XY，WYZ，有XWZ。 （A2， A3） 分解规则：由XY及 ZY，有XZ。 （A1， A3）第8页，共30页，2022年，5月20日，10点59分，星期四导出规则2.根据合并规则和分解规则，可得引理1 引理: XA1 A2Ak成立的

5、充分必要条件是XAi成立（i=l，2，k）。第9页，共30页，2022年，5月20日，10点59分，星期四总结:函数依赖(FD)的推理规则函数依赖有一个正确的和完备的推理规则集Armstrong 推理规则： 设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集， 推理规则如下： (1)自反律：如果Y X U,则XY在R上成立。 (2)增广律：如果XY为F所蕴涵，Z U，则XZYZ在R上成立。 (XZ表示XZ，下同) (3)传递律：如果XY和YZ在R上成立，则XZ在R上成立。 (4)合并律：如果XY和XZ成立，那么XYZ成立。 (5)伪传递律：如果XY和WYZ成

6、立，那么WXZ成立。 (6)分解律：如果XYZ成立， 那么XY,X Z成立。引理：X A1A2Ak成立的充分必要条件是X Ai(i=1,2K） 第10页，共30页，2022年，5月20日，10点59分，星期四函数依赖例关系模式R(A, B, C, G, H, I)，函数依赖集F=AB, AC, CGH, CGI, BH。我们可列出F中蕴含的几个依赖：由传递律可得AH，因为AB且BH；由合并律可得CGHI，因为CGH，CGI；由伪传递律可得AGI，因为AC且CGI。还可以使用上述规则推导出更多的函数依赖，读者可自行推导。第11页，共30页，2022年，5月20日，10点59分，星期四3. 函数依

7、赖闭包定义: 在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。定义: 设F为属性集U上的一组函数依赖，X U， XF+ = A|XA能由F 根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 的闭包第12页，共30页，2022年，5月20日，10点59分，星期四关于闭包的引理引理: 设F为属性集U上的一组函数依赖，X，Y U，XY能由F 根据Armstrong公理导出的充分必要条件是Y XF+用途 将判定XY是否能由F根据Armstrong公理导出的问题，就转化为求出XF+ ，判定Y是否为XF+的子集的问题(简单说，求逻辑蕴含只要通过求闭包就可以了。）第1

8、3页，共30页，2022年，5月20日，10点59分，星期四函数依赖闭包函数依赖的闭包F+是指被F逻辑蕴涵的函数依赖的全体构成的集合函数依赖推理规则的完备性 函数依赖推理规则系统(自反律、增广律和传递律)是完备的。由推理规则的完备性可得到两个重要结论： (1)属性集X+ 中的每个属性A，都有XA被F逻辑蕴涵，即X+是所有由F逻辑蕴含XA的属性A的集合。 (2)F+是所有利用Amstrong推理规则从F导出的函数依赖的集合第14页，共30页，2022年，5月20日，10点59分，星期四闭包的计算算法：求属性集X关于函数依赖F的闭包X+方法：计算x（i）（I=0,1,）(1)x(0)=x;(2)x

9、(i+1)=x(i)A其中A是这样的属性，在F中寻找尚未用过的左边是x(i)子集的函数依赖（3）判断是否有A：x(i+1)=x(i);B:若在x(i+1)已包含了F中的全部属性；C：x(i+1) x(i)，但x(i+1)的左部属性依赖已使用完出现A，B，C 的一种即结束，否则转（2） 第15页，共30页，2022年，5月20日，10点59分，星期四闭包的计算例：在关系模式R（U，F）中，U=ABCDEF=AC，ACB，BD，CE，ECB 计算(EC)+ 。计算过程如下：(1) x(0)=EC(2) 检查函数依赖，因 ECB ， X(1)=ECB=ECB (3)检查函数依赖，因 BD，X(2)=

10、ECBD=ECBD （4）X(3)= X(2)，所以(EC)+ =ECBD 第16页，共30页，2022年，5月20日，10点59分，星期四 属性集闭包计算举例练习 已知R, U= (A, B, C, G, H, I)，F=AB, AC, CGH, CGI, BH，计算(AG)+。 算法第一次循环的执行步骤： 步骤 FD closure 1 初值 AG 2 AB ABG 3 AC ABCG 4 CGH ABCGH 6 CGI ABCGHI 6 BH ABCGHI 结果为closure=ABCGHI。(AG)+ABCGHI。（也就是说，AG可以决定右面的每一个属性）第17页，共30页，2022年

11、，5月20日，10点59分，星期四计算属性集闭包的作用计算属性集闭包的作用可归纳如下：验证XY是否在F+中：看是否有YX+。判断X是否为R的超码：通过计算X+，看其是否包含R的所有属性。例如，(AG)+ABCGHI，则AG为R的超码。判断X是否为R的候选码：若X是超码，可检验X包含的所有子集的闭包是否包含R的所有属性。若不存在任何这样的属性子集，则X是R的候选码。第18页，共30页，2022年，5月20日，10点59分，星期四候选码的判断设有关系R(A1,A2,An,F)，F为R的函数依赖集，X为R的属性组，若X满足：1 X A1,A2,An，即X+=A1,A2,An2 不存在X的真子集Y，Y

12、 A1,A2,An。则称X为R的码例：关系RA,B,C,D，有FD如下：F=ABC,C B,BC D,ACD B，R的码为？AB+=ABCD,AC+=ABCD,ACD+=ABCD,候选码为：AB，ACD;还是AB,AC？还是其他？思考！第19页，共30页，2022年，5月20日，10点59分，星期四 属性集闭包计算举例 R=(U,F),其中,U=A, B, C, D, F=A B, AC D;求A+,B+,C+,AC+;求R的侯选码第20页，共30页，2022年，5月20日，10点59分，星期四 属性集闭包计算举例 U=A, B, C, D; F=A B, AC D;A+ = AB.C+ =

13、C.(AC)+ = ABCD.ACBD显然，AC是候选码思考：哪些属性是L类？（只出现在函数依赖左边）哪些是R类？哪些是LR类？哪些是N类？它们与候选码有什么关系？第21页，共30页，2022年，5月20日，10点59分，星期四候选码的作用例题：已知R(X,Y,Z),F=XYZ，请问R为第几范式？（请思考：解题的思路是什么？）XY为候选码，R属于BCNF。练习：R(W,X,Y,Z),F=XZ,WXY，请问R为第几范式？第22页，共30页，2022年，5月20日，10点59分，星期四Armstrong公理系统的有效性与完备性Armstrong公理的完备性及有效性说明:“蕴含” = “导出” 等价

14、的概念 F+ =由F出发借助Armstrong公理导出的函数依赖的集合第23页，共30页，2022年，5月20日，10点59分，星期四6. 函数依赖集等价定义: 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。第24页，共30页，2022年，5月20日，10点59分，星期四6. 最小依赖集 定义： 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖XA，使得F与F-XA等价。 (3) F中不存在这样的函数依赖XA， X有真 子集Z使得F-X

15、AZA与F等价。 如果函数依赖集F和G等价，并且G是最小集，那么称G是F的一个最小覆盖。 第25页，共30页，2022年，5月20日，10点59分，星期四函数依赖集的等价和覆盖求最小函数依赖集的方法：应用分解规则，使F中每一个依赖的右部单一化。去掉各函数依赖左部多余的属性。方法：检查F中左边是非单属性的依赖，如： XYA，要判定Y是否多余，只要求X闭包，若X闭包A，则Y是多余的，以X Y 代替XYA。去掉多余的依赖。方法：从第一个依赖开始，若要从F中去掉X Y ，则在剩下的依赖中求X闭包，若X闭包包含Y,则去掉X Y 第26页，共30页，2022年，5月20日，10点59分，星期四最小依赖集或

16、者：1。将函数依赖的右部分解为一个属性；2。确保函数依赖左边是不可分的；3。将具传递性的函数依赖去掉；如：假设一个关系R中具有属性A、B、C、D。 F=ABC,B C,A B,AB C,AC D解： （1）ABC分解为AB， AC； （2）由 AC知AB C是冗余的，去掉； A C得A AC，而 AC D，则A D，所以， AC D冗余。 （3） AC可由AB， BC得，所以AC要去掉。得到R的最小依赖集F=AB，BC，AD第27页，共30页，2022年，5月20日，10点59分，星期四求最小函数依赖集练习1 关系RA,B,C,D，有FD如下： F=ABC,C B,BC D,ACD B。求F的