第6章(3) 数据依赖的公理系统2009

1、2022-4-301数据库原理计算机系计算机系软件教研室软件教研室2022-4-302数据库原理数据库原理第六章第三节第六章第三节数据依赖的公理系统数据依赖的公理系统2022-4-303第第6章章 关系数据理论关系数据理论6.1 数据依赖数据依赖6.2 规范化规范化6.3 数据依赖的公理系统数据依赖的公理系统6.4 模式的分解模式的分解2022-4-3046.3 数据依赖的公理系统数据依赖的公理系统n逻辑蕴含逻辑蕴含定义定义6.11 对于满足一组对于满足一组函数依赖函数依赖 F 的的关系模式关系模式R ，其任何一个关系，其任何一个关系r，若函数依赖若函数依赖XY都成立（即都成立（即r中任意两中

2、任意两元组元组t，s，若，若tX=sX，则，则tY=sY ）, 则称则称 F逻辑蕴含逻辑蕴含X Y2022-4-305Armstrong公理系统n一套推理规则，是模式分解算法的理论一套推理规则，是模式分解算法的理论基础基础n用途用途n求给定关系模式求给定关系模式的码（候选码）的码（候选码）n从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖2022-4-3061. Armstrong公理系统 对关系对关系模式模式R 来说有以下的推理规则：来说有以下的推理规则：nAl.自反律自反律（Reflexivity）：）： 若若Y X U，则，则X Y为为F所蕴含。所蕴含。nA2.增广律增广

3、律（Augmentation）：若）：若XY为为F所蕴含，所蕴含，且且Z U，则，则XZYZ为为F所蕴含。所蕴含。nA3.传递律传递律（Transitivity）：若）：若XY及及YZ为为F所蕴所蕴含，则含，则XZ为为F所蕴含。所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于用并不依赖于F2022-4-307定理 6.l Armstrong推理规则是正确的（l）自反律）自反律:若若Y X U，则，则X Y为为F所蕴含所蕴含证证: 设设Y X U 对对R 的任一关系的任一关系r中的任意两个元组中的任意两个

4、元组t，s：若若tX=sX，由于，由于Y X，有，有ty=sy，所以所以XY成立成立.自反律得证自反律得证2022-4-308定理6.l(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所蕴含所蕴含.增广律得证。增广律得证。2022-4-309定理6.l(3) 传递律：若传递律：若X

5、Y及及YZ为为F所蕴含，则所蕴含，则 XZ为为 F所蕴含。所蕴含。证：证：设设XY及及YZ为为F所蕴含。所蕴含。对对R 的任一关系的任一关系 r中的任意两个元组中的任意两个元组 t，s。若若tX=sX，由于，由于XY，有，有 tY=sY；再由再由YZ，有，有tZ=sZ，所以，所以XZ为为F所蕴含所蕴含.传递律得证。传递律得证。2022-4-30102. 导出规则1.根据根据A1，A2，A3这三条推理规则可以得到下这三条推理规则可以得到下面三条推理规则：面三条推理规则：n 合并规则合并规则：由：由XY，XZ，有，有XYZ。 （A2， A3）n 伪传递规则伪传递规则：由：由XY，WYZ，有，有XW

6、Z。 （A2， A3）n 分解规则分解规则：由：由XY及及 Z Y，有，有XZ。 （A1， A3）2022-4-3011导出规则2.根据合并规则和分解规则，可得引理根据合并规则和分解规则，可得引理6.1 引理引理6.l XA1 A2Ak成立的充分必要成立的充分必要条件是条件是XAi成立（成立（i=l，2，k）。）。2022-4-30123. 函数依赖闭包定义定义6.l2 在关系模式在关系模式R中为中为F所逻辑蕴含的所逻辑蕴含的函数依赖的全体叫作函数依赖的全体叫作 F的的闭包闭包，记，记为为F+。定义定义6.13 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U， XF+ =

7、A | XA能由能由F 根据根据Armstrong公理导出公理导出，XF+称为属性集称为属性集X关于函数依赖集关于函数依赖集F 的闭包的闭包2022-4-3013F的闭包 F=X Y,Y Z, F+计算是NP完全完全问题，X A1A2.An 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, XYZ Z,X XY, XY XY, XZ XY, XYZ XY, X XZ,

8、 XY YZ, XZ XZ, XYZ YZX YZ, XY XZ, XZ XY, XYZ XZ,X ZYZ, XY XYZ, XZ XYZ, XYZ XYZ 2022-4-3014关于闭包的引理n引理引理6.2 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U，XY能由能由F 根据根据Armstrong公理导出的充分必公理导出的充分必要条件是要条件是Y XF+n用途用途 将判定将判定XY是否能由是否能由F根据根据Armstrong公理导出的问题，公理导出的问题，就转化为求出就转化为求出XF+ ，判定，判定Y是否为是否为XF+的子集的问题的子集的问题2022-4-3015求

9、闭包的算法算法算法6.l 求属性集求属性集X（X U）关于）关于U上的函数依赖集上的函数依赖集F 的闭包的闭包XF+ 输入：输入：X，F输出：输出：XF+步骤：步骤：（1）令）令X（0）=X，i=0（2）求）求B，这里，这里B = A |( V)( W)(VW F V X（i）A W)；（3）X（i+1）=BX（i） 2022-4-3016算法6.l（4）判断）判断X（i+1）= X （i）吗吗?（5）若相等或）若相等或X（i）=U , 则则X（i）就是就是XF+ , 算法终止。算法终止。（6）若否，则）若否，则 i=i+l，返回第（，返回第（2）步。）步。对于算法对于算法6.l， 令令ai

10、=|X（i）|，ai 形成一个步长大于形成一个步长大于1的严格递增的序列，序列的上界是的严格递增的序列，序列的上界是 | U |，因此该算法，因此该算法最多最多 |U| - |X| 次循环就会终止。次循环就会终止。2022-4-3017函数依赖闭包例例1 已知关系模式已知关系模式R，其中，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（求（AB）F+ 。解解 设设X（0）=AB；(1)计算计算X（1）: 逐一的扫描逐一的扫描F集合中各个函数依赖，集合中各个函数依赖， 找左部为找左部为A，B或或AB的函数依赖。得到两个：的函数依赖。得到两个： ABC，BD。 于是于是X（

11、1）=ABCD=ABCD。2022-4-3018函数依赖闭包(2)因为因为X（0） X（1） ，所以再找出左部为，所以再找出左部为ABCD子集的那些函数依赖，又得到子集的那些函数依赖，又得到ABC，BD， CE，ACB， 于是于是X（2）=X（1）BCDE=ABCDE。(3)因为因为X（2）=U，算法终止，算法终止所以（所以（AB）F+ =ABCDE。2022-4-30194. Armstrong公理系统的有效性与完备性n建立公理系统体系建立公理系统体系目的目的：从已知的：从已知的 f 推导出未知的推导出未知的fn明确：明确：1.公理系统推导出来的公理系统推导出来的 f 正确？正确？ 2. F

12、+中的每一个中的每一个 f 都能推导出来？都能推导出来？ / f不能由不能由F 导出导出, f F+ F F+ f2022-4-30204. Armstrong公理系统的有效性与完备性n有效性有效性：由：由F出发根据出发根据Armstrong公理推导出来的每公理推导出来的每一个函数依赖一定在一个函数依赖一定在F+中中(可由定理可由定理6.1得到证明）得到证明） /* Armstrong正确正确n完备性完备性：F+中的每一个函数依赖，必定可以由中的每一个函数依赖，必定可以由F出发出发根据根据Armstrong公理推导出来公理推导出来 /* Armstrong公理够用，完全公理够用，完全完备性完备

13、性：所有不能用：所有不能用Armstrong公理推导出来公理推导出来f, 都不为真都不为真 若若 f 不能用不能用Armstrong公理推导出来，公理推导出来， f F+ 2022-4-3021有效性与完备性的证明证明：证明：1. 有效性有效性 可由定理可由定理6.l得证得证2. 完备性完备性只需证明只需证明逆否命题逆否命题: 若函数依赖若函数依赖XY不能由不能由F从从Armstrong公理导出，那么它必然不为公理导出，那么它必然不为F所所蕴含蕴含分三步证明：分三步证明：2022-4-3022有效性与完备性的证明(1) 若若VW成立，且成立，且V XF+，则，则W XF+ （引理引理) 证证

14、因为因为 V XF+ ，所以有，所以有XV成立；成立； 因为因为X V，VW，于是，于是XW成立成立 所以所以W XF+ (2)/* 若若 f 不能用不能用Armstrong公理推导出来，公理推导出来， f F+ /* 若存在若存在r， F+中的全部函数依赖在中的全部函数依赖在 r上成立。上成立。 /* 而不能用而不能用Armstrong公理推导出来的公理推导出来的f , 在在r上不成立。上不成立。 构造一张二维表构造一张二维表r，它由下列两个元组构成，可以证明，它由下列两个元组构成，可以证明r必是必是R（U，F）的一）的一个关系个关系，即，即F+中的全部函数依赖在中的全部函数依赖在 r上成立

15、上成立。 2022-4-3023Armstrong公理系统的有效性与完备性(续) XF+ U-XF+ 11.1 00.0 11.1 11.1 若若r不是不是R 的关系，则必由于的关系，则必由于F中有函数依赖中有函数依赖VW在在r上不成立所致。由上不成立所致。由r的构成可知的构成可知，V必定是必定是XF+ 的子集，而的子集，而W不是不是XF+ 的子集，可是由第（的子集，可是由第（1）步，）步，W XF+，矛盾。所以，矛盾。所以r必是必是R的一个关系。的一个关系。 2022-4-3024Armstrong公理系统的有效性与完备性(续)(3) )/* 若若 f 不能用不能用Armstrong公理推导

16、出来，公理推导出来， f F+ /* 而不能用而不能用Armstrong公理推导出来的公理推导出来的 f , 在在r上不成立。上不成立。n若若XY 不能由不能由F从从Armstrong公理导出，则公理导出，则Y 不不是是XF+ 的子集。（引理的子集。（引理6.2）n因此必有因此必有Y 的子集的子集Y 满足满足 Y U-XF+， 则则XY在在 r 中不成立，即中不成立，即XY必不为必不为 R 蕴含蕴含 /* 因为因为 F+中的全部函数依赖在中的全部函数依赖在 r上成立。上成立。2022-4-3025Armstrong公理系统的有效性与完备性(续)Armstrong公理的完备性及有效性说明公理的完

17、备性及有效性说明:“蕴含蕴含” = “导出导出” 等价的概念等价的概念 F+ =由由F出发借助出发借助Armstrong公理导公理导出的函数依赖的集合出的函数依赖的集合2022-4-30265. 函数依赖集等价定义定义6.14 如果如果G+=F+，就说函数依赖，就说函数依赖集集F覆盖覆盖G（F是是G的覆盖，或的覆盖，或G是是F的覆的覆盖），或盖），或F与与G等价等价。2022-4-3027函数依赖集等价的充要条件引理引理6.3 F+ = G+ 的充分必要条件是的充分必要条件是 F G+ ，和，和G F+ 证证: 必要性显然，只证充分性。必要性显然，只证充分性。（1）若）若F G+ ，则，则XF

18、+ XG+ 。（2）任取）任取XY F+ 则有则有 Y XF+ XG+ 。 所以所以XY (G+）+= G+。即。即F+ G+。（3）同理可证）同理可证G+ F+ ，所以，所以F+ = G+。2022-4-3028函数依赖集等价n要判定要判定F G+，只须逐一对，只须逐一对F中的函数依中的函数依赖赖XY，考察，考察 Y 是否属于是否属于XG+ 就行了。就行了。因此引理因此引理6.3 给出了判断两个函数依赖给出了判断两个函数依赖集等价的可行算法。集等价的可行算法。 2022-4-30296. 最小依赖集 定义定义6.15 如果函数依赖集如果函数依赖集F满足下列条件，满足下列条件，则称则称F为一个

19、为一个极小函数依赖集极小函数依赖集。亦称为。亦称为最小依最小依赖集赖集或或最小覆盖最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得F与与F-XA等价。等价。 (3) F中不存在这样的函数依赖中不存在这样的函数依赖XA， X有真有真 子集子集Z使得使得F-XAZA与与F等价。等价。 2022-4-3030最小依赖集例例2 对于对于6.l节中的关系模式节中的关系模式S，其中：，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （S

20、NO，CNAME）G 设设F=SNOSDEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPTF是最小覆盖，而是最小覆盖，而F 不是。不是。因为：因为：F -SNOMN与与F 等价等价 F -(SNO，SDEPT)SDEPT也与也与F 等价等价 F -(SNO，SDEPT)SDEPT SNOSDEPT也与也与F 等价等价2022-4-30317. 极小化过程定理定理6.3 每一个函数依赖集每一个函数依赖集F均等价于一个极小均等价于一个极小 函数依赖集函数依赖集Fm。此。此Fm称为称为F的最小依赖集的最小依赖集证证:构造性证明，依据定义分三步对构造性证

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