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

1、5.3 数据依赖的公理系统,定义 对于满足一组函数依赖的关系模式R，其任何一个关系R，若函数依赖XY都成立（即r中任意两元组t, s, 若tX=sX,则tY=sY），则称F逻辑蕴涵XY。,5.3 数据依赖的公理系统,Armstrong公理系统 设U为属性集总体，F是U上的一组函数依赖，于是有关系模式R。对R 来说有以下的推理规则： 自反律(reflexivity)：若Y X U， 则XY为F所蕴含。 增广律(augmentation)：若XY为F所蕴含，且Z U，则 XZYZ为F所蕴含。 传递律(transitivity)：若XY，YZ为F所蕴含，则XZ为F所蕴含。,5.3 数据依赖的公理系统

2、,关于Armstrong公理正确性,tX = sX YX,tY = sY,XY,自反律,5.3 数据依赖的公理系统,tXZ = sXZ,tX = sX,XY,tY = sY,tXZ = sXZ,tZ = sZ,tYZ = sYZ,XZYZ,增广律,5.3 数据依赖的公理系统,XY tX = sX,tY = sY,Y Z,tZ = sZ,XZ,传递律,5.3 数据依赖的公理系统,由Armstrong公理导出的推理规则 合并律(union rule) 若XY，XZ，则XYZ 分解律(decomposition rule) 若XYZ ，则 XY，XZ 伪传递律(pseudotransitivity

3、rule) 若XY，WYZ，则WXZ,5.3 数据依赖的公理系统,XY 增广律,XXY,合并规则,XZ 增广律,XYYZ,传递律,XYZ,5.3 数据依赖的公理系统,XY 增广律,WXWY,WYZ,传递律,WXZ,伪传递规则,5.3 数据依赖的公理系统,ZY 自反律,YZ,分解规则,XY,传递律,XZ,5.3 数据依赖的公理系统,引理5.1 XA1A2Ak成立的充要条件XAi成立(i=1,2,k)。 定义5.12 在关系模式中为F所逻辑蕴含的函数依赖的全体 叫做F的闭包，记为F+,5.3 数据依赖的公理系统,Armstrong公理的有效性及完备性 有效性：由F出发根据Armstrong公理推导

4、出来的每一个函数依赖必一定在F+中 完备性：F所蕴涵的函数依赖都能用Armstrong公理从F中导出 定义5.13 设F为属性集U上的一组函数依赖，X U，XF+ = A | XA能由F根据Armstrong公理导出， XF+称为属性集X关于函数依赖集F的闭包。,5.3 数据依赖的公理系统,引理5.2 设F为属性集U上的一组函数依赖，X,Y U，XY能由F根据Armstrong公理导出的充分必要条件是Y XF+。 由引理5.2，判定XY是否能由F根据Armstrong公理导出，可转化为求XF+，判定Y是否为XF+的子集的问题。这个 问题由算法5.1解决。,5.3 数据依赖的公理系统,算法5.1

5、步骤 1.X(0)=X, i=0 2.求B，B A|(V)(W)(VWFV XA(i)W); 3.X(i+1)=BX(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),V XF+,XV,VW,XW,W XF+,5.3 数据依赖的公理系统,2)构造张二维表r它由下列两个元组构成，可以证明r必是 R的一个关系，即R中的全部函数依赖在r上成立。,5.3

6、数据依赖的公理系统,3)若XY不能由F从Armstrong公理导出，则Y 不是XF+的子集，因此必有Y的子集Y满足Y U-XF+ ，则XY在r中不成立，即XY必不为 R蕴含。,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中不存在这样的函数依赖XA，使得F与F-XA等价。 F中不存在这样的函数依赖XA， X有真子集Z使得F-XA)UZA与F等价。,5.3 数据依赖的公理