数据依赖的公理系统课件.ppt

1、6.3 数据依赖的公理系统v在以上的学习中，我们知道了一个关系模式之所以存在一些问题，是因为它的属性组之间存在一些不好的数据依赖关系，通过规范化，逐步消除数据依赖中的不合适部分，可以使关系模式达到某种范式的要求，解决关系模式存在的问题。v现在的问题是，这个规范化过程怎样实现，也就是说，对一个关系模式进行怎样的模式分解，才能使它达到3NF，BCNF或4NF的要求。这就是我们继续要学习的内容模式分解。1v在讲模式分解之前，我们还需要学习函数依赖的公理系统Armstrong 公理系统，它是模式分解算法的理论基础。26.3 数据依赖的公理系统v逻辑蕴含逻辑蕴含定义定义5.11 对于满足一组对于满足一组

2、函数依赖函数依赖 F 的关系的关系模式模式R，其任何一个关系其任何一个关系r，若函数若函数依赖依赖XY都成立都成立,则称则称 F逻辑蕴含逻辑蕴含X Y。(即即XY可以由可以由F推出推出)3v例1：已知关系模式R（ABC），F=AB，B C，判断A C是否为F逻辑蕴含？4v当已知关系模式R满足一组函数依赖F，怎么还能知道R中还有哪些函数依赖，或由F还能推导出哪些函数依赖呢？Armstorng公理系统就是解决这个问题的。5Armstrong公理系统v一套推理规则，是模式分解算法的理论基础一套推理规则，是模式分解算法的理论基础v用途用途求给定关系模式的码求给定关系模式的码从一组函数依赖求得蕴含的函数

3、依赖从一组函数依赖求得蕴含的函数依赖61.Armstrong公理系统 关系模式关系模式R 来说有以下的推理规则：来说有以下的推理规则：Al.自反律自反律（Reflexivity）：）：若若Y X U，则，则X Y为为F所蕴含。所蕴含。A2.增广律增广律（Augmentation）：若）：若XY为为F所蕴含，所蕴含，且且Z U，则，则XZYZ为为F所蕴含。所蕴含。A3.传递律传递律（Transitivity）：若）：若XY及及YZ为为F所蕴所蕴含，则含，则XZ为为F所蕴含。所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律

4、的使用并不依赖于用并不依赖于F7定理 6.l Armstrong推理规则是正确的（l）自反律自反律:若若Y X U，则，则X Y为为F所蕴含所蕴含证证:设设Y X U 对对R 的任一关系的任一关系r中的任意两个元组中的任意两个元组t，s：若若tX=sX，由于由于Y X，有，有ty=sy，所以所以XY成立成立.自反律得证自反律得证8(2)增广增广律律:若若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ 为为F所所蕴含。蕴含。证：证：设设XY为为F所蕴含，且所蕴含，且Z U。设设R 的任一关系的任一关系r中任意的两个元组中任意的两个元组t，s；若若tXZ=sXZ，则有则有tX=sX和和tZ=

5、sZ；由由XY，于是有于是有tY=sY，所以所以tYZ=sYZ，所以所以XZYZ为为F所蕴含所蕴含.增广律得证。增广律得证。9(3)传递律：传递律：若若XY及及YZ为为F所蕴含，则所蕴含，则 XZ为为 F所蕴含。所蕴含。证：证：设设XY及及YZ为为F所蕴含。所蕴含。对对R 的任一关系的任一关系 r中的任意两个元组中的任意两个元组 t，s。若若tX=sX，由于由于XY，有有 tY=sY；再由再由YZ，有，有tZ=sZ，所以所以XZ为为F所蕴含所蕴含.传递律得证。传递律得证。102.导出规则1.根据根据A1，A2，A3这三条推理规则可以得到下这三条推理规则可以得到下面三条推理规则：面三条推理规则：

6、合并规则合并规则：由：由XY，XZ，有，有XYZ。（重要）重要）（A2，A3）伪传递规则伪传递规则：由：由XY，WYZ，有，有XWZ。（A2，A3）分解规则：分解规则：由由XY及及 Z Y，有，有XZ。（重要）重要）（A1，A3）11导出规则2.根据合并规则和分解规则，可得引理6.1 引理引理6.l XA1 A2Ak成立的充分必要条件成立的充分必要条件是是XAi成立（成立（i=l，2，k）。）。合并、分解是对右边而言，对左边分解规则不成立。12v例1：已知关系模式R（ABC），F=AB，B C，判断A C是否为F逻辑蕴含？v现在我们就可以回答这个问题了.v根据Armstrong公理的传递律就可

7、以得出vAB，B C,A C,v所以A C为F逻辑蕴含13v例：已知关系模式R中 U=A，B，C，D,E,G,F=ABC,CA,BCD,ACDB,DEG,BEC,CGBD,CEAG,判断BDAC是否属于F+v解：由DEG知DE，BDBE 又知BEC，CA 所以BEA,BEAC 由、知，BDAC，所以BDAC被F所蕴涵，即BDAC属于F+14v例：已知关系模式R中 U=A，B，C，E,H,P,G,F=ACPE,PGA,BCE,AP,GAB,GCA,PABG,AEGB,ABCPH,证明BGHE属于F+v证：由BCE知BC，BE,BGGC 又知GCA，AP 所以BGA,BGABCP 又ABCPH，由

8、、知BGHE，所以BGHE被F所蕴涵，即BGHE属于F+15v这是一种判断XY是否为F逻辑蕴含的方法,即直接由公理的推理规则来推导,但是很多时候这样直接推导是比较困难的.16v另外一种方法就是根据Armstrong公理先推导出能被F所逻辑蕴含的所有函数依赖,然后看XY是否是其中的一个函数依赖,若是,则XY为F所逻辑蕴含.v这种方法就是求F闭包的方法.173.函数依赖闭包函数依赖闭包定义定义6.l2 在关系模式在关系模式R中为中为F所逻辑蕴所逻辑蕴含的函数依赖的全体叫作含的函数依赖的全体叫作 F的闭包，记为的闭包，记为F+。注意：注意：F+的的元素是函数依赖。元素是函数依赖。F包含于包含于F+，

9、若若X为为U的子集，的子集，X 属于属于F+。不要小看了这个不要小看了这个F+,一个小小的一个小小的F+常常有一个常常有一个很大的闭包。闭包中的函数依赖都是可由很大的闭包。闭包中的函数依赖都是可由F导导出的。出的。18v例1：已知关系模式R（XYZ），F=XY，Y Z，根据推理规则求出F+v提示：诸如X（表示空属性集）也属于F+，一共有42个函数依赖。19F的闭包 F+=X ,Y ,Z,XY ,XZ ,YZ ,XYZ ,X X,Y Y,Z Z,XY X,XZ X,YZ Y,XYZ X,X Y,Y Z,XY Y,XZ Y,YZ Z,XYZ Y,X Z,Y YZ,XY Z,XZ Z,YZ YZ,X

10、YZ Z,X XY,XY XY,XZ XY,XYZ XY,X XZ,XY YZ,XZ XZ,XYZ YZX YZ,XY XZ,XZ XY,XYZ XZ,X ZYZ,XY XYZ,XZ XYZ,XYZ XYZ 20v从上一个例题中可以看出，求F+是一个复杂而且困难的问题,所以这种方法也不太理想.v但是,在实际使用中，要经常要判断能否从已知的FD集F推导出函数依赖XY，经过分析,可以看出以上两种方法（即从公理直接推导和求F+方法）都不太合适,所以我们必须另想办法.21定义定义6.13 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U，XF+=A|XA能能由由F 根据根据Armst

11、rong公理导出公理导出，XF+称称为属性集为属性集X关于函数依赖集关于函数依赖集F 的闭包，的闭包，实质是由公理实质是由公理推导出的所有推导出的所有 XAi所形成的属性集。所形成的属性集。注意：注意：XF+中的元素是属性中的元素是属性,而而F+中的元素是函数依赖中的元素是函数依赖.22关于闭包的引理v引理6.2 设F为属性集U上的一组函数依赖，X，Y U，XY能由F 根据Armstrong公理导出的充分必要条件是Y XF+.23证明：设证明：设Y=AY=A1 1A A2 2AAn n （1 1）充分条件：当充分条件：当Y Y属于属于X X+时时,对于每个对于每个i,XAi,XAi i可由公理

12、导出。再用合并可由公理导出。再用合并 规则可得规则可得XYXY。（2 2）必要条件：若必要条件：若XYXY能够由公理导出能够由公理导出,则根据分解规则根据分解规,XAXAi i|i=1,2,n|i=1,2,n 成立，所以成立，所以Y Y属于属于XF+。24v用途用途 将判定将判定XY是否能由是否能由F根据根据Armstrong公理导出的公理导出的问题，问题，就转化为求出就转化为求出XF+，判定判定Y是否为是否为XF+的子集的子集的问题的问题,使复杂问题简单化了使复杂问题简单化了.25求闭包的算法算法6.l 求属性集X（X U）关于U上的函数依 赖集F 的闭包XF+输入：X，F输出：XF+步骤：

13、（1）令X（0）=X，i=0（2）求B，这里B=A|(V)(W)(VWF V X（i）A W)；（3）X（i+1）=BX（i）26（4）判断X（i+1）=X（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。（6）若否，则 i=i+l，返回第（2）步。对于算法6.l，令ai=|X（i）|，ai 形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多|U|-|X|次循环就会终止。27课本例1:已知关系模式R，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（AB）F+。解 设X（0）=AB；(1)计算X（1）:逐一的扫描F集合中各个函数依赖

14、，找左部为A，B或AB的函数依赖。得到两个：ABC，BD。于是X（1）=ABCD=ABCD。28(2)因为X（0）X（1），所以再找出左部为ABCD子集的那些函数依赖，又得到ABC，BD，CE，ACB，于是X（2）=X（1）BCDE=ABCDE。(3)因为X（2）=U，算法终止所以（AB）F+=ABCDE。29v例：设R=ABC,F=AB,BC当X分别为A,B,C是求XF+。解：当X=A时，XF+=ABC 当X=B时，XF+=BC 当X=C时，XF+=C30v练习：已知关系模式R中 U=A，B，C，D,E,G,F=ABC,CA,BCD,ACDB,DEG,BEC,CGBD,CEAG,求(BD)+

15、，判断BDAC是否属于F+v结论：(BD)+=ABCDEG,BDAC可由F导出，即BDAC属于F+31侯选码v求侯选码问题可转化为求属性集闭包问题，因为X XF+,若U=XF+,则XU，即X为侯选码。32练习已知关系模式R，其中U=A，B，C，D，E,G；F=ACB，BCD，ABE，EGC。求AB,BC,AC 是否为关系R的侯选码。334.Armstrong公理系统的有效性与完备性v有效性有效性：由F 出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中./*Armstrong正确v完备性：完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来./*A

16、rmstrong公理够用，完全34有效性与完备性的证明证明：证明：1.有效性有效性 可由定理可由定理6.l得证得证2.完备性完备性只需证明只需证明逆否命题逆否命题:若函数依赖若函数依赖XY不能由不能由F从从Armstrong公理导出，那么它必然不为公理导出，那么它必然不为F 所蕴含所蕴含分三步证明：分三步证明：35有效性与完备性的证明(1)引理引理:若若VW 成立，且成立，且V XF+，则，则W XF+证证 因为因为 V XF+，所以有所以有XV 成立；成立；因为因为X V，VW，于是于是XW 成立成立 所以所以W XF+36(2)/*若若 f 不能用不能用Armstrong公理推导出来，公理

17、推导出来，f F+/*若存在若存在r，F+中的全部函数依赖在中的全部函数依赖在 r上成立。上成立。/*而不能用而不能用Armstrong公理推导出来的公理推导出来的f,在在r上不成立。上不成立。构造一张二维表构造一张二维表r，它由下列两个元组构成，可以证明它由下列两个元组构成，可以证明r 必是必是R（U，F）的一个关系的一个关系，即，即F+中的全部函数依赖在中的全部函数依赖在 r上成立。上成立。37Armstrong公理系统的有效性与完备性(续)XF+U-XF+11.1 00.0 11.1 11.1 若r不是R 的关系，则必由于F中有函数依赖VW在r上不成立所致。由r的构成可知，V必定是XF+

18、的子集，而W不是XF+的子集，可是由第（1）步，W XF+，矛盾。所以r必是R的一个关系。38Armstrong公理系统的有效性与完备性(续)(3)/*若若 f 不能用不能用Armstrong公理推导出来，公理推导出来，f F+/*而不能用而不能用Armstrong公理推导出来的公理推导出来的 f,在在r上不成立。上不成立。若若XY 不能由不能由F从从Armstrong公理导出，则公理导出，则Y 不是不是XF+的的子集。（引理子集。（引理6.2）因此必有因此必有Y 的子集的子集Y 满足满足 Y U-XF+，则则XY在在 r 中不成立，即中不成立，即XY必不为必不为 R 蕴含蕴含 /*因为因为

19、F+中的全部函数依赖在中的全部函数依赖在 r上成立上成立。39Armstrong公理系统完备性证明(小结）(1)引理:若VW成立，且V XF+，则W XF+(2)构造一张二维表r，它由下列两个元组构成，可以证明r必是R（U，F）的一个关系，即F+中的全部函数依赖在 r上成立。XF+U-XF+11.1 00.0 11.1 11.1 (3)若XY 不能由F从Armstrong公理导出，则Y 不是XF+的子集。40Armstrong公理系统的有效性与完备性(续)Armstrong公理的完备性及有效性说明:“蕴含”=“导出”等价的概念 F+=由F出发借助Armstrong公理导出的函数依赖的集合F+=

20、XY|由F出发借助Armstrong公理导出的函数依赖的415.函数依赖集等价定义6.14 如果G+=F+，就说函数依赖集F 覆盖G（F是G的覆盖，或G是F的覆盖），或F与G 等价。42函数依赖集等价的充要条件引理6.3 F+=G+的充分必要条件是 F G+，和G F+证:必要性显然，只证充分性。（1）若F G+，则XF+XG+。（2）任取XYF+则有 Y XF+XG+。所以XY (G+）+=G+。即F+G+。（3）同理可证G+F+，所以F+=G+。43函数依赖集等价v因此引理6.3 给出了判断两个函数依赖集等价的可行算法。即只需判定F G+,G F+是否成立.v要判定F G+，只须逐一对F

21、中的函数依赖XY，考察 Y 是否属于XG+就行了.。44例v关系模式R（ABC），F=AB，B C，vG=A B，AB C，判断F与G是否等价。v解:先验证F G+vAG+=ABC,B AG+，所以AB G+vBG+=B，C BG+，所以B C G+v所以，F G+v所以F与G不等价456.最小依赖集 定义6.15 如果函数依赖集如果函数依赖集F 满足下列条件，则满足下列条件，则称称F为一个为一个极小函数依赖集极小函数依赖集。亦称为。亦称为最小依赖最小依赖集或最小覆盖。集或最小覆盖。(1)F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。(2)F中不存在这样的函数依赖中

22、不存在这样的函数依赖XA，使得使得F与与F-XA等价。等价。(3)F中不存在这样的函数依赖中不存在这样的函数依赖XA，X有真有真 子集子集Z使得使得F-XAZA与与F等价。等价。46最小依赖集例例2 对于对于6.l节中的关系模式节中的关系模式S，其中：其中：U=SNO，SDEPT，MN，CNAME，G，F=SNOSDEPT，SDEPTMN，（，（SNO，CNAMEG 设设F=SNOSDEPT，SNOMN，SDEPTMN，(SNO，CNAME)G，(SNO，SDEPT)SDEPTF是最小覆盖，而是最小覆盖，而F 不是。不是。因为：因为：F-SNOMN与与F 等价等价 F-(SNO，SDEPT)S

23、DEPT SNOSDEPT也与也与F 等价等价47v例:判断下列函数依赖集是否为最小集vF1=AD BC,BE C,C HvF2=A D,B A,A C,BD,D CvF3=A C,AD B,C D,D BF1不是最小集不是最小集,因为因为AD BC右边不是单个属性右边不是单个属性F2不是最小集不是最小集,因为因为A C可以由可以由A D和和D C推推 出出,所以所以F2-A C仍然等价于仍然等价于F2F3不是最小集不是最小集,因为因为F3-AD B D B仍仍然等价于然等价于F3;487.极小化过程定理6.3 每一个函数依赖集F均等价于一个极小 函数依赖集Fm。此Fm称为F的最小依赖集证:构

24、造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集。(1)逐一检查F中各函数依赖FDi：XY，若Y=A1A2 Ak，k 2，则用 XAj|j=1，2，k 来取代XY。引理6.1保证了F变换前后的等价性。49极小化过程(2)逐一检查F中各函数依赖FDi：XA，令G=F-XA，若AXG+，则从F中去掉此函数依赖。由于F与G=F-XA等价的充要条件是AXG+因此F变换前后是等价的。50极小化过程(3)逐一取出F 中各函数依赖FDi：XA，设X=B1B2Bm，逐一考查Bi（i=l，2，m），若A（X-Bi）F+，则以X-Bi 取代X。由于F与F-XAZA等价的充要条件是AZF+，其

25、中Z=X-Bi 因此F变换前后是等价的。51极小化过程由定义，最后剩下的F就一定是极小依赖集。因为对F 的每一次“改造”都保证了改造前后的两个函数依赖集等价，因此剩下的F与原来的F等价。证毕v定理6.3的证明过程 也是求F 极小依赖集的过程52例例2 设设F=ABC,BAC,CA,对对F进行极小化处理进行极小化处理解：(1)根据分解规则，把F中的函数依赖转化成右部都是单属性的函数依赖集合，分解后的函数依赖集仍用F表示F=AB,AC,BA,BC,CA(2)去掉F中的冗余函数依赖判断AB是否冗余。设G1=AC,BA,BC,CA,得 AG1+=AC因，所以AB不冗余。判断AC是否冗余。设G2=AB,

26、BA,BC,CA,得 AG2+=ABC因，所以AC冗余（以后得检查不再考虑AC）。53 v判断BA是否冗余v设G3=AB,BC,CA,得 BG3+=ABCv因，所以BA冗余（以后得检查不再考虑BA）。v判断BC是否冗余。v设G4=AB,CA,得 BG4+=Bv因，所以BC不冗余。v判断CA是否冗余。v设G5=AB,BC,得 CG5+=Cv因，所以CA不冗余。v由于该例中的函数依赖表达式的左部均为单属性，因而不需要进行第三步的检查。上述结果为最小函数依赖集，用Fm表示：FmAB,BC,CA54v若依次按AB，BC的顺序判定函数依赖是否冗余，则得到最小依赖集：Fm2AB,BA,AC,CA。这说明最

27、小依赖集不唯一，与对各函数依赖FDi及XA中X各属性的处置顺序有关。同时注意到，在此例中A、B、C是一一对应的。55极小化过程v极小化过程(定理6.3的证明)也是检验F是否为极小依赖集的一个算法若改造后的F与原来的F相同，说明F本身就是一个最小依赖集56计算函数依赖集F的最小依赖集的算法v1 根据推理规则的分解性，使每个FD的右边属性均为单属性；v2 消除冗余的FD；v3消除每个FD中左边冗余的属性；57练习v设关系模式R（ABC），vF=ABC，B C，A B，AB C，求Fm.v1 使FD右边都是单属性形式，去掉重复的FD。v F=AB，A C，B C，A B，AB C；v2 去掉F中冗余

28、的FDv F=AB，A C，B C，AB Cv3 消除FD中左边冗余的属性；v Fm=AB，B C58v例:R(A,B,C)vF=BC,CB,v C A,A B,v A C,BC Av求F的最小集Fmin解：解：（1）右端皆为单个属性）右端皆为单个属性 （2）去掉多余函数依赖）去掉多余函数依赖 CB（它可以由它可以由C A，A B 导出）导出）A C（它可以由它可以由AB，BC 导出导出）BC A（可以由可以由C A导出）导出）Fmin=BC，C A，A B59小结v逻辑蕴含vArmstrong公理系统v如何判断一个X Y是否被已知的函数依赖集逻辑蕴含运用Armstrong公理系统直接推导；求出F+，然后判断是否包含这个函数依赖；求出XF+,然后判断Y是否是XF+的子集；v如何判断两个函数依赖集等价；v如何求一个函数依赖的最小函数依赖集；60