第五章关系数据理论

第五章关系数据理论章节6.3数据依赖的公理系统6.4模式的分解课型新授课课时2节课班级2005级11、12班教学目标掌握数据依赖的公理系统教学重点难点1.重点掌握Armstrong公理2.掌握属性集闭包的算法3.侯选码的求解理论和算法教学关键数据依赖的公理系统。关于模式分解的算法。教学方法讲授与课件演示。教具计算机大屏幕投影。复习内容函数依赖与范式引入内容如何求出给定关系模式的所有函数依赖，如何求关系模式的码。讲解内容6.3数据依赖的公理系统1.逻辑蕴含定义6.11对于满足一组函数依赖F的关系模式RU，F，其任何一个关系r，若函数依赖X→Y都成立,(即对于r中任意两个元组s,t,若s[X]=t[X]，则s[Y]t[Y])，则称F逻辑蕴含X→Y例如R(X,Y,Z),F={X→Y,Y→Z}X→Z为了求得给定关系模式的码，为了从一组给定的函数依赖求得蕴涵的函数依赖，就需要一套推理规则。这组推理规则是Armstrong于1974年提出的，所以称为Armstrong公理系统。2.Armstrong公理系统一套推理规则，是模式分解算法的理论基础用途:求给定关系模式的码从一组函数依赖求得蕴含的函数依赖关系模式RU，F来说有以下的推理规则：自反律（Reflexivity）：若YXU，则X→Y为F所蕴含。(Sno,Sname)→Sname注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F增广律（Augmentation）：若X→Y为F所蕴含，且Z→U，则XZ→YZ为F所蕴含。传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。定理6.1Armstrong推理规则是正确的（l）自反律:若YXU，则X→Y为F所蕴含证:设YXU对RU，F的任一关系r中的任意两个元组t，s：若t[X]=s[X]，由于YX，有t[y]=s[y]，所以X→Y成立.自反律得证（2）增广律:若X→Y为F所蕴含，且ZU，则XZ→YZ为F所蕴含。证：设X→Y为F所蕴含，且ZU。设RU，F的任一关系r中任意的两个元组t，s；若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ为F所蕴含.增广律得证。（3）传递律：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。证：设X→Y及Y→Z为F所蕴含。对RU，F的任一关系r中的任意两个元组t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含.传递律得证。3.导出规则(1)根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：A4合并规则：由X→Y，X→Z，有X→YZ。（A2，A3）A5分解规则：由X→Y及ZY，有X→Z。（A1，A3）A6伪传递规则：由X→Y，WY→Z，有XW→Z。（A2，A3）证明：根据合并规则和分解规则，可得引理6.1引理6.lX→A1A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）。4.函数依赖闭包定义6.12在关系模式RU，F中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。F+={X→Y|F|=X→Y}例：已知关系模式R(XYZ)，F={X→Y,Y→Z},求F+。这里对函数依赖的定义做一下扩充。用φ表示空属性集，并定义φ→φφ函数依赖于任何属性和属性集合。则φ→φ，X→φ,Y→φXXXYYZXZ计可得到43个函数依赖。F={XY,YZ},F+计算是NP完全问题，XA1A2...AnF+={X-φ,Y-φ,Z-φ,XY-φ,XZ-φ,YZ-φ,XYZ-φ,X-X,Y-Y,Z-Z,XY-X,XZ-X,YZ-Y,XYZ-X,X-Y,Y-Z,XY-Y,XZ-Y,YZ-Z,XYZ-Y,X-Z,Y-YZ,XY-Z,XZ-Z,YZ-YZ,XYZ-Z,X-XY,XY-XY,XZ-XY,XYZ-XY,X-XZ,XY-YZ,XZ-XZ,XYZ-YZX-YZ,XY-XZ,XZ-XY,XYZ-XZ,X-ZYZ,XY-XYZ,XZ-XYZ,XYZ-XYZ}自反律、增广律和传递律称为Armstrong公理系统。Armstrong公理系统是有效的、完备的。有效性是指：由F出发根据Armstrong公理系统推导出来的每一个函数依赖一定在F+中。完备性是指：在F+中每一个函数依赖，必定可以由F出发根据Armstrong公理系统推导出来。6.属性集的闭包定义6.13设F为属性集U上的一组函数依赖，XU，XF+={A|X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包引理6.2设F为属性集U上的一组函数依赖，X，YÍU，X→Y能由F根据Armstrong公理导出的充分必要条件是YÍXF+用途将判定X→Y是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题6.求属性集闭包的算法算法6.l求属性集X（XÍU）关于U上的函数依赖集F的闭包XF+输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，这里B={A|($V)($W)(V→WÎF∧VÍX（i）∧AÎW)}；（3）X（i+1）=B∪X（i）（4）判断X（i+1）=X（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。（6）若否，则i=i+l，返回第（2）步。对于算法6.l，令ai=|X（i）|，{ai}形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多|U|-|X|次循环就会终止。[例1]已知关系模式RU，F，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+。(AC)F+(C)F+解设X（0）=AB；(1)计算X（1）:逐一的扫描F集合中各个函数依赖，找左部为A，B或AB的函数依赖。得到两个：AB→C，B→D。于是X（1）=AB∪CD=ABCD。(2)因为X（0）≠X（1），所以再找出左部为ABCD子集的那些函数依赖，又得到AB→C，B→D，C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(3)因为X（2）=U，算法终止所以（AB）F+=ABCDEU={A,B,C,D};F={AB,BCD};nA+=AB.nC+=C.n(AC)+=ABCD.7.候选码的求解理论和算法候选码求解理论给定一个关系模式RU，F，U={A1,A2,…An},F只R的函数依赖集，则属性可以分为如下四类：L类：仅出现在函数依赖集F左部的属性；R类：仅出现在函数依赖集F右部的属性；LR类：在函数依赖集F左右都出现的属性；N类：在函数依赖集F左右都不出现的属性；根据候选码的特性，可以得出如下结论：给定一个关系模式RU,F，设XU。(1)若X是L类属性，则X必为R的任一候选码的成员。若XF+=U，则X为R的唯一候选码。(2)若X是R类属性，则X不是R的任一候选码的成员。(3)若X是N类属性，则X必包含在R的任一候选码中。(4)若X是LR类属性，则X可能是也可能不是R的任一候选码的成员。输入：关系模式R及其函数依赖集F。输出：R的所有候选码。步骤：(1)将R的所有属性分为L、R、N、LR四类，令X代表L、N两类，Y代表LR类。(2)求XF+。若XF+包含R的全部属性，则X即为R的唯一候选码，转(5)；否则，转(3)。(3)在Y中任取一属性A，求(AX)F+。若它包含了R的全部属性，则转(4)；否则，调换一属性，反复进行这一过程，直到试完Y中的所有属性。(4)如果已找出所有候选码，则转(5)；否则，在Y中依次取两个、3个、…，求它们的属性闭包，直到其闭包包含R的全部属性。(5)停止，输出结果。6.3函数依赖的等价和最小函数依赖集4.Armstrong公理系统的有效性与完备性建立公理系统体系目的：从已知的f推导出未知的f明确：1.公理系统推导出来的f正确？2.F+中的每一个f都能推导出来？有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中/*Armstrong正确完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来/*Armstrong公理够用，完全完备性：所有不能用Armstrong公理推导出来f,都不为真若f不能用Armstrong公理推导出来，f∈F+6.函数依赖集等价定义6.14如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。例如，R(ABC)F1={A→B,B→C}，F2={A→B,B→C,A→C}F1等价F2函数依赖集等价的充要条件引理6.3F+=G+的充分必要条件是FÍG+，和GÍF+证:必要性显然，只证充分性。（1）若FÍG+，则XF+ÍXG++。（2）任取X→YÎF+则有YÍXF+ÍXG++。所以X→YÎ(G+）+=G+。即F+ÍG+。（3）同理可证G+ÍF+，所以F+=G+。要判定FÍG+，只须逐一对F中的函数依赖X→Y，考察Y是否属于XG++就行了。因此引理6.3给出了判断两个函数依赖集等价的可行算法。6.最小依赖集定义6.15如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。(1)F中任一函数依赖的右部仅含有一个属性。(2)F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。(3)F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z→A}与F等价。[例2]对于6.l节中的关系模式SU，F，其中：U={SNO，SDEPT，MN，CNAME，G}，F={SNO→SDEPT，SDEPT→MN，（SNO，CNAME）→G}设F’={SNO→SDEPT，SNO→MN，SDEPT→MN，(SNO，CNAME)→G，(SNO，SDEPT)→SDEPT}F是最小覆盖，而F’不是。因为：F’-{SNO→MN}与F’等价F’-{(SNO，SDEPT)→SDEPT}也与F’等价F’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也与F’等价定理6.3每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集。证:构造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集。(1)逐一检查F中各函数依赖FDi：X→Y，若Y=A1A2…Ak，k2，则用{X→Aj|j=1，2，…，k}来取代X→Y。引理6.1保证了F变换前后的等价性。(2)逐一检查F中各函数依赖FDi：X→A，令G=F-{X→A}，若AÎXG+，则从F中去掉此函数依赖。由于F与G=F-{X→A}等价的充要条件是AÎXG+因此F变换前后是等价的。(3)逐一取出F中各函数依赖FDi：X→A，设X=B1B2…Bm，逐一考查Bi（i=l，2，…，m），若AÎ（X-Bi）F+，则以X-Bi取代X。由于F与F-{X→A}∪{Z→A}等价的充要条件是AÎZF+，其中Z=X-Bi因此F变换前后是等价的。由定义，最后剩下的F就一定是极小依赖集。因为对F的每一次“改造”都保证了改造前后的两个函数依赖集等价，因此剩下的F与原来的F等价。证毕定理6.3的证明过程也是求F极小依赖集的过程[例3]F={A→B，B→A，B→C，A→C，C→A}Fm1、Fm2都是F的最小依赖集：Fm1={A→B，B→C，C→A}Fm2={A→B，B→A，A→C，C→A}的最小依赖集Fm不一定是唯一的它与对各函数依赖FDi及X→A中X各属性的处置顺序有关极小化过程(定理6.3的证明)也是检验F是否为极小依赖集的一个算法若改造后的F与原来的F相同，说明F本身就是一个最小依赖集在RU，F中可以用与F等价的依赖集G来取代F原因：两个关系模式R1U，F，R2U，G，如果F与G等价，那么R1的关系一定是R2的关系。反