第4章(讲3数据依赖公理系统)DataBase关系数据理论.ppt

第四章 关系数据理论,4.1 问题提出4.2 规范化4.3 数据依赖的公理系统4.4 模式的分解,4.3 数据依赖的公理系统,逻辑蕴含 定义4.11 对于满足一组函数依赖 F 的关系模式R ，其任何一个关系r，若函数依赖X→Y都成立, 则称： F逻辑蕴含X →Y，记作：F |= X →Y 那么如何判定F都蕴涵了哪些FD呢？用一组推导规则从F上进行推导是方便的，引出“Armstrong”公理Armstrong公理系统,一套推理规则，是模式分解算法的理论基础用途求给定关系模式的候选码从一组函数依赖求得蕴含的函数依赖,1. Armstrong公理系统,关系模式R 来说有以下的推理规则：Al.自反律（Reflexivity）： 若Y  X  U，则X →Y为F所蕴含A2.增广律（Augmentation）：若X→Y为F所蕴含，且Z  U，则XZ→YZ为F所蕴含A3.传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含 注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F,（l）自反律:若Y  X  U，则X →Y为F所蕴含证: 设Y  X  U 对R 的任一关系r中的任意两个元组t，s：若t[X]=s[X]，由于Y  X，有t[Y]=s[Y]，所以X→Y成立.自反律得证,(2)增广律: 若X→Y为F所蕴含，且Z  U，则XZ→YZ 为F所蕴含。

证：设X→Y为F所蕴含，且Z  U 设R 的任一关系r中任意的两个元组t，s；若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ为F所蕴含.增广律得证3) 传递律：若X→Y及Y→Z为F所蕴含，则 X→Z为 F所蕴含证：设X→Y及Y→Z为F所蕴含对R 的任一关系 r中的任意两个元组 t，s若t[X]=s[X]，由于X→Y，有 t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含.传递律得证2. 导出规则,1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则： 合并规则：由X→Y，X→Z，有X→YZ （A2， A3） 伪传递规则：由X→Y，WY→Z，有XW→Z （A2， A3） 分解规则：由X→Y及 ZY，有X→Z （A1， A3）,2.根据合并规则和分解规则，可得引理4.1 引理4.l X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）。

3. 函数依赖闭包,定义4.l2 在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F +用Armstrong公理及其推论可以从F上推导出很多FD，但在实际问题中我们只对某个属性或属性组所决定的FD感兴趣（例如判断候选码），引出XF+ 定义4.13 设F为属性集U上的一组函数依赖，X U， XF+ ={ A|X→A能由F 根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F 的属性闭包关于闭包的引理,引理4.2 设F为属性集U上的一组函数依赖，X，Y  U，X→Y能由F 根据Armstrong公理导出的充分必要条件是Y XF+用途 将判定X→Y是否能由F根据Armstrong公理导出的问题转化为求出XF+ ，判定Y是否为XF+的子集的问题求闭包的算法,算法4.l 求属性集X（X  U）关于U上的函数依 赖集F 的闭包XF+ 输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，这里B = { A |( V)(  W)(V→WF ∧V  X（i）∧A W)}；（3）X（i+1）=B∪X（i）,（4）判断X（i+1）= X （i）吗?（5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。

6）若否，则 i=i+l，返回第（2）步 对于算法4.l， 令ai =|X（i）|，{ai }形成一个步长大于1的严格递增的序列，序列的上界是 | U |，因此该算法最多 |U| - |X| 次循环就会终止求属性闭包举例,[例1] 已知关系模式R，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}求（AB）F+ 解：设X（0）=AB；(1)计算X（1）: 逐一的扫描F集合中各个函数依赖， 找左部为A，B或AB的函数依赖得到两个： AB→C，B→D 于是X（1）=AB∪CD=ABCD2)因为X（0）≠ X（1） ，所以再找出左部为ABCD子集的那些函数依赖，又得到AB→C，B→D， C→E，AC→B， 于是X（2）=X（1）∪BCDE=ABCDE3)因为X（2）=U，算法终止所以（AB）F+ =ABCDE4. Armstrong公理系统的有效性与完备性,建立公理系统体系目的：从已知的 f 推导出未知的f明确： 1.公理系统推导出来的 f 正确？（有效性） 2. F +中的每一个 f 都能推导出来？（完备性）,有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F +中 /* Armstrong正确完备性：F +中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来 /* Armstrong公理够用，完全,有效性与完备性的证明,证明： 1. 有效性 可由定理4.l得证2. 完备性 只需证明逆否命题: 若函数依赖X→Y不能由F从Armstrong公理导出，那么它必然不为F所蕴含分三步证明：,有效性与完备性的证明,(1)引理: 若V→W成立，且V  XF+，则W  XF+ 证 因为 V  XF+ ，所以有X→V成立； 因为X →V，V→W，于是X→W成立 所以W  XF+ (2)/* 若 f 不能用Armstrong公理推导出来， f∈ F+ /* 若存在r， F+中的全部函数依赖在 r上成立。

/* 而不能用Armstrong公理推导出来的f , 在r上不成立 构造一张二维表r，它由下列两个元组构成，可以证明r必是R（U，F）的一个关系，即F+中的全部函数依赖在 r上成立Armstrong公理系统的有效性与完备性(续),XF+ U-XF+ 11......1 00......0   11......1 11......1   若r不是R 的关系，则必由于F中有函数依赖V→W在r上不成立所致由r的构成可知，V必定是XF+ 的子集，而W不是XF+ 的子集，可是由第（1）步，W  XF+，矛盾所以r必是R的一个关系Armstrong公理系统的有效性与完备性(续),(3) )/* 若 f 不能用Armstrong公理推导出来， f∈ F+ /* 而不能用Armstrong公理推导出来的 f , 在r上不成立若X→Y 不能由F从Armstrong公理导出，则Y 不是 XF+ 的子集。

引理4.2）因此必有Y 的子集Y’ 满足 Y’ U-XF+， 则X→Y在 r 中不成立，即X→Y必不为 R 蕴含 /* 因为 F+中的全部函数依赖在 r上成立Armstrong公理系统的有效性与完备性(续),Armstrong公理的完备性及有效性说明:“蕴含” == “导出” 等价的概念 F+ ==由F出发借助Armstrong公理导出的函数依赖的集合,5. 函数依赖集等价,定义4.14 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价函数依赖集等价的充要条件,引理4.3 F+ = G+ 的充分必要条件是 F  G+ ，和G  F+ 证: 必要性显然，只证充分性1）若FG+ ，则XF+  XG++ 2）任取X→YF+ 则有 Y  XF+  XG++ 所以X→Y  (G+）+= G+即F+  G+3）同理可证G+  F+ ，所以F+ = G+函数依赖集等价,要判定F  G+，只须逐一对F中的函数依赖X→Y，考察 Y 是否属于XG++ 就行了。

因此引理4.3 给出了判断两个函数依赖集等价的可行算法6. 最小依赖集,定义4.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖 (1) F中任一函数依赖右部仅含有一个属性 (2) F中不存在这样的函数依赖X→A，使得F与 F-{X→A}等价保证F中不存在多余FD） (3) F中不存在这样的函数依赖X→A， X有真 子集Z使得F-{X→A}∪{Z→A}与F等价 （保证F中每个FD的左边没有多余的属性）,求最小依赖集举例,[例2] 对于4.l节中的关系模式S，其中： U={ SNO，SDEPT，MN，CNAME，G }， F={ SNO→SDEPT，SDEPT→MN， （SNO，CNAME）→G } 设F’={SNO→SDEPT，SNO→MN， SDEPT→MN，(SNO，CNAME)→G， (SNO，SDEPT)→SDEPT}F是最小覆盖，而F ’不是。

因为：F ’-{SNO→MN}与F ’等价 F ’-{(SNO，SDEPT)→SDEPT}也与F ’等价 F ’-{(SNO，SDEPT)→SDEPT} ∪{SNO→SDEPT}也与F ’等价,7. 极小化过程,定理4.3 每一个函数依赖集F均等价于一个极小 函数依赖集Fm此Fm称为F的最小依赖集证:构造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集1)逐一检查F中各函数依赖FDi：X→Y， 若Y=A1A2 …Ak，k > 2， 则用 { X→Aj |j=1，2，…， k} 来取代X→Y 引理4.1保证了F变换前后的等价性极小化过程,(2)逐一检查F中各函数依赖FDi：X→A， 令G=F-{X→A}， 若AXG+， 则从F中去掉此函数依赖 由于F与G =F-{X→A}等价的充要条件是AXG+ 因此F变换前后是等价的极小化过程,(3)逐一取出F中各函数依赖FDi：X→A， 设X=B1B2…Bm， 逐一考查Bi （i=l，2，…，m）， 若A （X-Bi ）F+ ， 则以X-Bi 取代X。

由于F与F-{X→A}∪{Z→A}等价的充要条件是AZF+ ，其中Z=X-Bi 因此F变换前后是等价的。