《数据库系统概论》第5版-王珊-第6章报告.ppt

* 数据依赖的公理系统（续） 定义6.12 在关系模式RU,F中为F所逻辑蕴涵的函数依赖的全体叫作F的闭包，记为F +。 定义6.13 设F为属性集U上的一组函数依赖，X、Y ?U， XF+={ A|X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包。 * 数据依赖的公理系统（续） 引理6.2 设F为属性集U上的一组函数依赖，X、Y ? U，X→Y能由F根据Armstrong公理导出的充分必要条件是Y ?XF+。 引理6.2的用途 判定X→Y是否能由F根据Armstrong公理导出的问题，就 转化为求出XF+，判定Y是否为XF+的子集的问题。 * 数据依赖的公理系统（续） 求闭包的算法 算法6.1 求属性集X（X ? U）关于U上的函数依赖集F的闭包XF+ 输入：X，F 输出：XF+ 步骤： 迭代 * 数据依赖的公理系统（续） 令X(0)=X，i=0 求B，这里B ={ A |(? V)( ? W)(V→W?F ∧V ? X(i)∧A? W)}。 X(i+1)=B∪X(i) 。 判断X(i+1)= X(i) 。 若X(i+1)与X(i)相等或X(i)=U ，则X(i)就是XF+， 算法终止。 若否，则i=i+1，返回第②步。 对X(i)中的每个元素，依次检查相应的函数依赖,将依赖它的属性加入B * 数据依赖的公理系统（续） [例6.11] 已知关系模式RU, F，其中 U={A, B, C, D, E}； F={AB→C, B→D, C→E, EC→B, AC→B}。 求(AB)F+ 。 * 数据依赖的公理系统（续） 解 ：由算法6.1，设X(0)=AB。 计算X(1)：逐一的扫描F集合中各个函数依赖，找左部为 A、B或AB的函数依赖。得到两个：AB→C，B→D。于 是X(1)=AB∪CD=ABCD。 因为X(0)≠ X(1)，所以再找出左部为ABCD子集的那些函数 依赖，又得到C→E，AC→B，于是 X(2)=X(1)∪BE=ABCDE。 因为X(2)已等于全部属性集合，所以(AB)F+ =ABCDE。 参见爱课程网数据库系统概论6.3节动画《求闭包》 * 数据依赖的公理系统（续） 有效性与完备性的含义 有效性：由F 出发根据Armstrong公理推导出来的每一个函数依赖一定在F +中 完备性：F +中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来 * 定理6.2 Armstrong公理系统是有效的、完备的。 证明： 1. 有效性 有效性实际上是“正确性” 可由定理6.1得证 数据依赖的公理系统（续） * 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）构造一张二维表r，它由下列两个元组构成，可以证明r 必是RU,F的一个关系，即F中的全部函数依赖在 r上成立。 XF+ U-XF+ 11......1 00......0 ? 11......1 11......1 ? 若r 不是RU,F 的关系，则必由于F中有某一个函数依赖V→W 在r上 不成立所致。由r 的构成可知，V 必定是XF+ 的子集，而 W 不是 XF+ 的子集，可是由第（1）步，W ??? XF+，矛盾。 所以r 必是RU,F的一个关系。 数据依赖的公理系统（续） * （3）若X→Y不能由F从Armstrong公理导出，则Y不是XF+的子集。（引理6.2） 因此必有Y的子集Y’ 满足Y’?U-XF+， 则X→Y 在r 中不成立， 即X→Y 必不为RU,F 蕴涵。 数据依赖的公理系统（续） * Armstrong公理的完备性及有效性说明: “导出”与“蕴涵”是两个完全等价的概念 F+ ：为F所逻辑蕴涵的函数依赖的全体（定义6.12 ） F+ ：可以说成由F出发借助Armstrong公理导出的函数依赖的集合 数据依赖的公理系统（续） * 定义6.14 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。 两个函数依赖集等价是指它们的闭包等价