《数据库技术讲义 第5章 关系数据库理论-2.ppt》由会员分享，可在线阅读，更多相关《数据库技术讲义 第5章 关系数据库理论-2.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、5.3 数据依赖的公理系统v定义对于满足一组函数依赖的关系模式R，其任何一个关系R，若函数依赖XY都成立（即r中任意两元组t,s,若tX=sX,则tY=sY），则称F逻辑蕴涵逻辑蕴涵逻辑蕴涵逻辑蕴涵XY。5.3 数据依赖的公理系统vArmstrong公理系统 设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、系统v关于Armstrong公理正确性tX=sXYXtY=sYXY自反律5.3 数据依赖的公理系统tXZ=sXZtX=sXXYtY=sYtXZ=sXZtZ=sZtYZ=sYZXZYZ增广律5.3 数据依赖的公理系统XYtX=sXtY=sYY ZtZ=sZXZ传递律5.3 数据依赖的公理系统v由Armstrong公理导出的推理规则合并律(union rule)v若XY，XZ，则XYZ分解律(decomposition rule)v若XYZ，则 XY，XZ伪传递律(pseudotransitivity rule)v若XY，WYZ，则WXZ5.3 数据依赖的公理系统XY增广律XXY合并规则XZ增广律
3、XYYZ传递律XYZ5.3 数据依赖的公理系统XY增广律WXWYWYZ传递律WXZ伪传递规则5.3 数据依赖的公理系统ZY自反律YZ分解规则XY传递律XZ5.3 数据依赖的公理系统v引理5.1 XA1A2Ak成立的充要条件XAi成立(i=1,2,k)。v定义5.12 在关系模式中为F所逻辑蕴含的函数依赖的全体叫做F的闭包闭包，记为F+5.3 数据依赖的公理系统vArmstrong公理的有效性及完备性有效性有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖必一定在F+中完备性完备性：F所蕴涵的函数依赖都能用Armstrong公理从F中导出v定义5.13设F为属性集U上的一组函数依
4、赖，X U，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集关于函数依赖集F的闭闭包包。5.3 数据依赖的公理系统v引理5.2设F为属性集U上的一组函数依赖，X,Y U，XY能由F根据Armstrong公理导出的充分必要条件是Y XF+。v由引理5.2，判定XY是否能由F根据Armstrong公理导出，可转化为求XF+，判定Y是否为XF+的子集的问题。这个 问题由算法5.1解决。5.3 数据依赖的公理系统v算法5.1步骤v1.X(0)=X,i=0v2.求B，BvA|(V)(W)(VWFV XA(i)W);v3.X(i+1)=BX(i)v4.判断X(i+1)
5、与X(i)是否相等v5.若相等或X(i+1)U则X(i+1)即XF+，算法终止。v6.否则i=i+1，返回第2步5.3 数据依赖的公理系统v定理5.3 Armstrong公理系统是有效的、完备的。v有效性可以根据定理5.1得到证明。v完备性证明,证明其逆否命题：1)V XF+XVVWXWW XF+5.3 数据依赖的公理系统2)构造张二维表r它由下列两个元组构成，可以证明r必是 R的一个关系，即R中的全部函数依赖在r上成立。5.3 数据依赖的公理系统 3)若XY不能由F从Armstrong公理导出，则Y 不是XF+的子集，因此必有Y的子集Y满足Y U-XF+，则XY在r中不成立，即XY必不为 R
6、蕴含。5.3 数据依赖的公理系统v定义5.14 如果G+=F+，就说函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖)，或F与G等价。v引理5.3 F+=G+的充分必要条件是F G+，和G F+。5.3 数据依赖的公理系统v引理5.3充分性证明5.3 数据依赖的公理系统v定义5.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。1.F中任一函数依赖的右部仅含有一个属性。2.F中不存在这样的函数依赖XA，使得F与F-XA等价。3.F中不存在这样的函数依赖XA，X有真子集Z使得F-XA)UZA与F等价。5.3 数据依赖的公理系统v 定理5.3 每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集。v 应当指出，F的最小依赖集Fm不一定是唯一的，它与对各函数依赖FDi及XA中X各属性的处置顺序有关。