数据库技术讲义 第5章 关系数据库理论-2.pptVIP

5.3 数据依赖的公理系统 定义 对于满足一组函数依赖的关系模式RU, F，其任何一个关系R，若函数依赖XY都成立（即r中任意两元组t, s, 若t[X]=s[X],则t[Y]=s[Y]），则称F逻辑蕴涵X—Y。 5.3 数据依赖的公理系统 Armstrong公理系统 设U为属性集总体，F是U上的一组函数依赖，于是有关系模式RU,F。对RU,F 来说有以下的推理规则： 自反律(reflexivity)：若Y ? X U， 则X－Y为F所蕴含。 增广律(augmentation)：若X－Y为F所蕴含，且Z U，则 XZ－YZ为F所蕴含。 传递律(transitivity)：若X－Y，Y－Z为F所蕴含，则X－Z为F所蕴含。 5.3 数据依赖的公理系统 关于Armstrong公理正确性 5.3 数据依赖的公理系统 5.3 数据依赖的公理系统 5.3 数据依赖的公理系统 由Armstrong公理导出的推理规则 合并律(union rule) 若X－Y，X－Z，则X－YZ 分解律(decomposition rule) 若X－YZ ，则－ X－Y，X－Z 伪传递律(pseudotransitivity rule) 若X－Y，WY－Z，则WX－Z 5.3 数据依赖的公理系统 5.3 数据依赖的公理系统 5.3 数据依赖的公理系统 5.3 数据依赖的公理系统 引理5.1 X－A1A2···Ak成立的充要条件X－Ai成立(i=1,2,···,k)。 定义5.12 在关系模式中为F所逻辑蕴含的函数依赖的全体 叫做F的闭包，记为F+ 5.3 数据依赖的公理系统 Armstrong公理的有效性及完备性 有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖必一定在F+中 完备性：F所蕴涵的函数依赖都能用Armstrong公理从F中导出 定义5.13 设F为属性集U上的一组函数依赖，X U，XF+ = {A | X－A能由F根据Armstrong公理导出}， XF+称为属性集X关于函数依赖集F的闭包。 5.3 数据依赖的公理系统 引理5.2 设F为属性集U上的一组函数依赖，X,Y U，X－Y能由F根据Armstrong公理导出的充分必要条件是Y XF+。 由引理5.2，判定X－Y是否能由F根据Armstrong公理导出，可转化为求XF+，判定Y是否为XF+的子集的问题。这个 问题由算法5.1解决。 5.3 数据依赖的公理系统 算法5.1步骤 1.X(0)=X, i=0 2.求B，B＝ {A|(V)(W)(V→W∈F∧V X∧A(i)∈W)}; 3.X(i+1)=B∪X(i) 4.判断X(i+1)与X(i)是否相等 5.若相等或X(i+1)＝U则X(i+1) 即XF+，算法终止。 6.否则i=i+1，返回第2步 5.3 数据依赖的公理系统 定理5.3 Armstrong公理系统是有效的、完备的。 有效性可以根据定理5.1得到证明。 完备性证明,证明其逆否命题： 1) 5.3 数据依赖的公理系统 2)构造—张二维表r它由下列两个元组构成，可以证明r必是 RU,F的一个关系，即R中的全部函数依赖在r上成立。 5.3 数据依赖的公理系统 3)若X→Y不能由F从Armstrong公理导出，则Y 不是XF+的子集，因此必有Y的子集Y‘满足Y U-XF+ ，则X→Y在r中不成立，即X→Y必不为 RU,F蕴含。 5.3 数据依赖的公理系统 定义5.14 如果G+=F+，就说函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖)，或F与G等价。 引理5.3 F+=G+的充分必要条件是F G+，和G F+。 5.3 数据依赖的公理系统 引理5.3充分性证明 5.3 数据依赖的公理系统 定义5.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 F中任一函数依赖的右部仅含有一个属性。 F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。 F中不存在这样的函数依赖X→A， X有真子集Z使得F-{X→A)U{Z→A}与F等价。 5.3 数据依赖的公理系统 定理5.3 每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集。 应当指出，F的最小依赖集Fm不一定是唯一的，它与对各函数依赖FDi及X→A中X各属性的处置顺序有关。 * * t[X] = s[X] Y?X t[Y] = s[Y] X－Y 自反律 t[XZ] = s[XZ] t[X] = s[X] X－Y t[Y] = s[Y] t[XZ] = s[XZ] t[Z] = s[Z] t[YZ] = s[YZ] XZ