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

《数据库技术讲义 第5章 关系数据库理论-2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、：若X－>Y，Y－>Z为F所蕴含，则X－>Z为F所蕴含。5.3数据依赖的公理系统关于Armstrong公理正确性t[X]=s[X]YXt[Y]=s[Y]X－>Y自反律5.3数据依赖的公理系统t[XZ]=s[XZ]t[X]=s[X]X－>Yt[Y]=s[Y]t[XZ]=s[XZ]t[Z]=s[Z]t[YZ]=s[YZ]XZ－>YZ增广律5.3数据依赖的公理系统X－>Yt[X]=s[X]t[Y]=s[Y]YZt[Z]=s[Z]X－>Z传递律5.3数据依赖的公理系统由Armstrong公理导出的推理规则合并律(unionrule)若X－>Y，X－>Z，

3、则X－>YZ分解律(decompositionrule)若X－>YZ，则－>X－>Y，X－>Z伪传递律(pseudotransitivityrule)若X－>Y，WY－>Z，则WX－>Z5.3数据依赖的公理系统X－>Y增广律X－>XY合并规则X－>Z增广律XY－>YZ传递律X－>YZ5.3数据依赖的公理系统X－>Y增广律WX－>WYWY－>Z传递律WX－>Z伪传递规则5.3数据依赖的公理系统Z－>Y自反律Y－>Z分解规则X－>Y传递律X－>Z5.3数据依赖的公理系统引理5.1X－>A1A2···Ak成立的充要条件X－>Ai成立(i=1,2,···,k

4、)。定义5.12在关系模式中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为F+5.3数据依赖的公理系统Armstrong公理的有效性及完备性有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖必一定在F+中完备性：F所蕴涵的函数依赖都能用Armstrong公理从F中导出定义5.13设F为属性集U上的一组函数依赖，XU，XF+={A

5、X－>A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包。5.3数据依赖的公理系统引理5.2设F为属性集U上的一组函数依赖，X,YU，X－>Y能由F根据Armstrong公理

6、导出的充分必要条件是YXF+。由引理5.2，判定X－>Y是否能由F根据Armstrong公理导出，可转化为求XF+，判定Y是否为XF+的子集的问题。这个问题由算法5.1解决。5.3数据依赖的公理系统算法5.1步骤1.X(0)=X,i=02.求B，B＝{A

7、(V)(W)(V→W∈F∧VX∧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.3Armstrong公理系统是有效的、完备的。有效性可以根

8、据定理5.1得到证明。完备性证明,证明其逆否命题：1)VXF+X－>VV－>WX－>WWXF+5.3数据依赖的公理系统2)构造—张二维表r它由下列两个元组构成，可以证明r必是R的一个关系，即R中的全部函数依赖在r上成立。5.3数据依赖的公理系统3)若X→Y不能由F从Armstrong公理导出，则Y不是XF+的子集，因此必有Y的子集Y‘满足YU-XF+，则X→Y在r中不成立，即X→Y必不为R蕴含。5.3数据依赖的公理系统定义5.14如果G+=F+，就说函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖)，或F与G等价。引理5.3F+=

9、G+的充分必要条件是FG+，和GF+。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不一定是唯一的，它与对各函数依赖

10、FDi及X→A中X各属性的处置顺序有关。