第三章数据依赖.ppt

1,第三章 数 据 依 赖,2,本章的主要内容： 函数依赖的概念及函数依赖公理 函数依赖集的等价和覆盖 多值依赖及多值依赖公理 连接依赖,3,数据依赖 : 函数依赖、多值依赖、连接依赖,数据依赖 是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系 是现实世界属性间相互联系的抽象 是数据内在的性质 是语义的体现,4,3.1 函数依赖(Functional dependency FD) 定义1(FD) 设关系模式R(U)，X,Y U，r是R(U)上的任一关系，对任意t1、t2r, 如果 t1X=t2X 有t1Y=t2 Y，称X函数决定Y，或Y函数依赖于X，记为：FD XY。,定义2（FD） 对X中的任一值x，Y(X=x(r) 的值仅有一个元组，则有XY。,定义(平凡/非平凡的FD) 设FD XY，如果YX，则称 FD XY为非平凡的函数依赖；否则，若YX，称FD XY为平凡的函数依赖。,5,定义(完全FD): 设FD XY，如果对任意的XX，XY都不成立，则称XY是完全函数依赖；若对X的真子集X有XX，而XY成立，则称FD XY是部分函数依赖，即Y函数依赖于X的一部分。,函数依赖的例子,学校数据库的语义： 一个系有若干学生， 一个学生只属于一个系； 一个系只有一名主任； 一个学生可以选修多门课程， 每门课程有若干学生选修； 每个学生所学的每门课程都有一个成绩。,R(SNO,CNO,SNAME,GRADE,DEPT,MNG) SNO DEPT, DEPT MNG; SNO,CNOGRADE;,SNO,CNOSNO; SNO,CNOSNAME; SNOMNG,7,3.2 函数依赖公理 3.2.1 函数依赖公理 定义(FD的逻辑蕴涵) ： 设关系模式R(U,F)，X,YU，如果能从函数依赖集F推导出FD XY，则称 F逻辑蕴涵 FD XY，或称XY逻辑蕴涵于F。记为 F|= XY。,8,Armstrong公理： 设r是R(U)上的一个关系，X、Y、Z、WU。 A1. 自反律: 若YXU, 则 XY; A2. 增广律: 若XY且ZU，则 XZYZ; A3. 传递律: 若XY, YZ，则 XZ.,9,证明： A1. 自反律: 若YXU, 则 XY; 设r是R的关系，t1, t2是r的任意元组，X、Y、Z U (1) 对X的任意值x，有X(X=x(r)至多有一个元组， 因YX，Y(X=x(r)至多只有一个元组，则有XY,10,证明： A2. 增广律: 若XY且ZU，则 XZYZ; (2) 对任意x值，X(X=x(r)至多有一个 元组。有 ： XZ=xz (r) X=x(r)，则 Y(XZ=xz(r) Y(X=x(r)。所以， Y (XZ=xz (r)至多有一个元组， r必满足XZY。,11,证明： A3. 传递律: 若XY, YZ，则 XZ. (3) 若XY，则t1X = t2X， t1Y = t2Y 又 YZ，则有t1Y=t2Y， t1Z=t2Z。 显然，XY在r中成立。,12,推论1 若XY，XZ，则XYZ。 证明：若XY X XY XZ XYYZ,XYZ,推论2 若XY且ZY，则XZ。 证明： ZY YZ 推论3 若XY，YZW，则XZW。 证明： XY XZY Z YZ W,XZW,13,示例：SC(SNO,CNO,SNAME,GRADE,DEPT,MN) F= SNO,CNOGRADE， SNO SNAME，DEPT， DEPT MN,SNO SNAME，DEPT，MN SNO,CNO SNAME，DEPT，MN SNO,CNO SNAME,GRADE,DEPT,MN,14,定理1 如果Ai (i =1, 2, , n)是关系模式R的属性，则 X A1 A2 An 成立的充要条件是： X Ai (i =1, 2, , n) 都成立。,15,例： 设F=ABE，AGJ，BEI，EG，GIH 试证：F|= ABGH 证明：用公理系统和F中的函数依赖，推导过程如下： 1. 已知 ABE，EG 则：ABG； (传递律) 2. 已知 ABE 则：ABBE； (增广律) 3. 已知 BEI，又 ABBE 则：ABI (传递律) 4. 由1和3有ABG， ABI 则：ABGI (合成规则) 5. 由4有 ABGI，又 GIH 则：ABH (传递律) 6. 由1和5有 ABH，ABG 则：ABGH (合成规则),16,定义(使用集) 用公理从F推出 XY成立所使用的函数依赖组成的序列称F上的一个推理序列。由推理序列中出现的且包含在F中的函数依赖的集合称推理序列的使用集(use set)，记为： U(F, XY),例：U(F, ABGH) =ABE，EG， BEI， GIH,17,3.2.2 公理的完备性 定义(FDs的闭包 F +) 设F是关系r(R)上的FDs，F所蕴含的所有FD的集合称为F的闭包，记作F +。 F + = XY | 所有F |= XY ,18,例：设F=ABC，CB。 F+ 为： F+ = AA, ABA, ACA, ABCA, BB, ABB, BCB，ABCB，CC，ACC，BCC,ABCC，ABAB，ABCAB，ACAC，ABCAC，BCBC, ABCBC, ABCABC, ABC, ABAC, ABBC, ABABC，CB, CBC，ACB ，ACAB,19,定义(属性集的闭包X + ) 设关系模式R(U, F)，X U, 所有用公理推出的XAi中Ai的属性集合称X对于F的闭包，记作：X + X += Ai | 用公理推出的XAi 且Ai U,20,定理2 Armstrong公理是完备的。,证明：如果能证明XY不能由公理推出将不会被F所蕴涵，则公理得证。为此，构造一个关系r(R)。 我们将证明两点： (1). F中的所有函数依赖在 r (R)上都成立； (2). XY在r(R)上不成立。,21,22,证明： (1) 设WZF，W在r中有两种情况: (a) W X+。根据属性闭包定义，有XW，又因WZ，根据公理A3有 XZ。因此 ZX+，即 tZ= tZ= ai , 所以，WZ在r上成立。 (b) W X+。则在r中有tW tW，因此，WZ在r上总是成立的。 由(a)和(b)得：r(R)满足F。,(2) 若XY不能由公理推出。即XX+而YX+，由r的构造知，XY在r上不成立，即 XY不被F所蕴涵。,23,3.2.3 函数依赖集闭包及成员测试算法 算法1 计算属性集X的闭包X+的算法 输入：属性集X和函数依赖集F 输出：X的闭包X+,While RESULTVAR do Begin VAR:=RESULT; for every FD WZ in F do if WRESULT then RESULT:=RESULTZ end; return(RESULT) end.,CLOSURE(X, F) Begin VAR:=; RESULT:=X;,24,例： F=AD, ABE, BIE，CDI，EC 求： AE+ 解： AE0 = AE AE1 = AED AE2 = AEDC AE+ = ACDEI,F=A2A1, A3A2, A4A3，AmAm-1 算法改进：每个FD仅考察一次；每个属性仅考察一次,25,计算属性闭包的改进算法： 1. 构造一个LIST表，存放含相同左部属性的FD。 如listA，将存放左部含A的FD； 2. 构造一个计数器COUNT，计数FD的左部属性数。 如: COUNTWZ=|W|; 3. 变量UPDATE记录未考察的属性，使每个属性仅 考察一次， RESULT放中间和最后结果。,26,算法3.2.2 计算属性闭包的改进算法 LINCLOSURE(X, F) . 初始化 for each FD WZ in F do begin COUNTWZ:=W; for each attribute A in W do add WZ to listA end; RESULT:=X; UPDATE:=X.,27,. 计算 While UPDATE do begin Choose an A in UPDATE; UPDATE:=UPDATE-A; for each FD WZ in LISTA do begin COUNTWZ:=COUNTWZ-1; if COUNTWZ=0 then begin ADD:=Z-RESULT; RESULT:=RESULTADD UPDATE:=UPDATEADD end end end. . return(RESULT).,28,例: 设F=AD，ABE，BIE，CDI，EC 计算：LINCLOSURE(AE,F)。 解：(1) 初始化： RESULT=AE UPDATE=AE LISTA=AD，ABE COUNTAD=1 LISTB=BIE，ABE COUNTABE=2 LISTC=CDI COUNTBIE=2 LISTD=CDI COUNTCDI=2 LISTE=EC COUNTEC=1 LISTI=BIE (2) COUNTAD=0 COUNTABE=1 RESULT=ADE UPDATE=ED 其余不变。 (3) COUNTEC=0 RESULT=ACDE UPDATE=CD 其余不变。 最后返回结果为ACDEI。,29,定理1： LINCLOSURE算法对输入长度n而言，具有时间复杂度O(n)。,证明： (1) 初始化阶段计算COUNTWZ所用时间和|W|成正比。计算COUNT的全部初始化值为 O(n)次。 (2) 填写LIST表花费O(n)，RESULT和UPDATE能用O(n)时间进行初始化。 (3) 计算阶段，F中的属性加入到UPDATE至多一次。减COUNT所花费的时间为O(n)。算法中涉及ADD的计算与Z成正比，是O(n)的。,30,算法3.2.3 判定F是否蕴涵XY的成员测试算法 输入：函数依赖集F和FD XY。 输出：若F蕴涵XY输出为true，否则为false MEMBER(F, XY) begin if Y LINCLOSURE(X,F) then return(true) eles return(false) end.,31,3.3 函数依赖的等价和覆盖 3.3.1 函数依赖的等价和覆盖,定义(等价和覆盖) 在模式R上的FDs F和G，若F+=G+，则F和G等价。 记作FG。 若FG，称F是G的一个覆盖，也称G是F的一个覆盖。,32,定理4 已知模式R上的函数依赖集 F和G。当且仅当 F|=G 且 G|=F ，则 F G。,证明：如果F|=G，若有XYG，则F|=XY，即XYF +， 有GF +，(G)+(F+)+ = F + 。 同理，如果G|=F，有F + G +。因此，F +=G +，则FG。 反之，若FG，则F|=G和G|=F是显然的。证毕。,例: 证明F=ABC, AD, CDE和 G=ABCE, AABD, CDE等价,33,3.3.2 无冗余覆盖 定义(无冗余覆盖) 如果FDs F不存在真子集F使F F成立，则F是无冗余的。如果F是G的一个覆盖且F是无冗余的，则F是G的一个无冗余覆盖。,例: 求F=AB, BA, BC, ABC 的一个无冗余覆盖。 AB, BA, BC, ABC ,*一个函数依赖集的无冗余覆盖不是唯一的.,34,算法3.3.1 计算无冗余覆盖 NONREDUN(F) begin G: =F ; for each FD XY in F do if MEMBER(GXY, XY) then G: =GXY; return(G) end.,35,定理5 设F和G是模式R上的两个等价的、无冗余的FDs。令XY是F上的一个FD。则在G中存在一个FD VW使得XV。,定义(属性集等价) 设X、YR，若F|=XY，且F|=YX，则X和Y在F上等价。记作XY。,36,证明：若XYF，因FG，G|=XY. 则对XY有一个基于G的推理序列，其使用集为U(G,XY)。 对任一 FD SZU(G,XY)，则根据属性闭包的概念， 有：G|=XS。 又因 FG， F|= SZ. 则该函数依赖有一个基于F的推理序列。 要证明： XV 在G中一定有一个FD VW U(G,XY)，则有XV。 因FG，VW有一个基于F的推理序列且XY U(F,VW), 则有G|= VX。 ,37,否则,若XYU(F,VW)，则FD VW的使用集可写为：U(FXY，VW)。这样，由F和G等价可推出： FXY |= U(G,XY)，则XY在F中是冗余的，这与F是无冗余的相矛盾。因此，必定有 XYU(F,VW)，则F|=VX。 由以上证明可知，G|=XV ，则F|=XV，又 F|=VX。因此，在F中有XV，同理，在G中亦有XV。 证毕。 示例,38,例：设无冗余的等价的函数依赖集FG F =ABC，BA，ADE G=AABC，BA，BDE F和G中左部等价的属性集为： AA，BB，ADBD,ADE是F中的FD，在G中有BDE 使得ADBD： 在G中，U（G，ADE）=AABC，BDE 在F中，U（F，AABC ）=ABC U（F，BDE ）=BA，ADE 因此，在F和G中有 ADBD。,39,等价类：对于模式R上的FDs集F和属性集X R。设EF(X)是F中左部等价于X的函数依赖集，即： EF(X)=ZW ZWF且 XZ 令 EF 为F上所有左部等价的函数依赖的集合，即： EF = EF(X) X R且EF (X) *F上左部等价的依赖集的集合 EF 是F的一个划分。,40,例： 设F=ABC，BA，ADE， G=AB，BA， BC， BDE， F和G是无冗余的且FG 求：F和G中左部等价的依赖集。 解：EF 为：EF (A)=ABC，BA， EF (AD)=ADE EG 为：EG (A)=AB， BA， BC， EG (AD)=BDE,41,3.3.3 规范覆盖(canonical cover) 定义 设F是模式R上的一个FDs集，XYF。若模式R中的属性A满足下列条件，则称属性A在XY中是外部属性。 1. X=AZ, XZ，且(FXY)ZY F 或者; 2. Y=AW, YW，且(FXY)XW F。,36,35,42,定义(化简覆盖) 若FD XY的左部或右部都不包含外部属性，称FD XY是化简的。 如果FDs集F中的所有FD都是化简的，称FDs集F是化简的。如果F是G的一个覆盖且F是化简的，称F是G的一个化简覆盖。,例: G=ABC, BC, ABD 求：G的化简覆盖。 解：ABC、 ABD中C、B是外部属性， G1=AB, BC, AD是G的化简覆盖。,43,. 左化简 G:=F; for each FD XY in F do for each attribute A in X do if MEMBER(G, (XA)Y) then remove A from X in XY in G;,算法3.3.2 求化简覆盖 输入：函数依赖集F 输出：化简的F REDUCE(F) begin,44,. 右化简 F:=G; for each FD XY in F do for each attribute A in Y do if MEMBER(GXYX(YA), XA) then remove A from Y in XY in G;,.除去形如X的FD remove all FDs of the form X from G; F:=G return(F) end.,45,例: 已知：F=AC，ABD，AECI，ACJ, CD 求：化简F 解：(1) 左简化 检查F中的FD, 在 ABD和ACJ中分别有属性B和C为外部属性，去掉B和C： F=AC，AD，AECI，AJ, CD (2) 右简化 检查AD和AECI分别有外部属性D和C, 去掉D和C后： F=AC，A, AEI，AJ，CD (3) 去掉A 结果为：F=AC，AEI，AJ，CD。,46,* 求简化覆盖时，应该按照算法中给出的顺序： (1) 左简化 (2) 右简化 例：F=BA，DA，ABD (1) 右简化 结果为F (2) 左简化 结果为： F= BA，DA，BD (3) 右简化 结果为： F = DA，BD ,47,定义(规范覆盖) 如果FDs集F是G的一个覆盖，F中的每个FD都具有XA形式而且F是左化简的和无冗余的，称F是G的一个规范覆盖。,计算规范覆盖： （1）将每个FD的右部化为单属性； （2）将每个FD化为左简化的； （3）计算无冗余的覆盖。,48,3.3.4 最小覆盖 定义(最小覆盖) 如果FDs集F和任一等价的FDs集G相比，具有最少的函数依赖数，则称F为G的最小覆盖。,例： G=ABC, BA, ADE, BDI F=ABC, BA, ADEI,49,50,51,证明： 设F是G的一个无冗余覆盖， 因 XY，在F中有： U(F, XY)EF(X)=。 设F是G的另一个无冗余覆盖，对任一FD WZ U(F, XY), 假设在F中有:U(F, WZ) EF (X)=, 则有 U(F, XY)EF (X)=，定理得证。 如果假设不成立，即有U(F, WZ) EF (X)。 设有 VTU(F, WZ) 而且 VTEF(X)。 则有：F|=WV， XV。 有F|=WX，因而有F|=WX。 但 WZ U(F, XY)，即F|=XW。 因此，在F下有WX，即WZEF(X)。 这与 U(F, XY)EF(X)=相矛盾。 证毕,52,53,定义： eF(X)=Z | 所有 ZW EF(X) ,例：G=ACD，BEF，CEG，CBJ，EIK 有：ABCE， CE JK 则： AB JK,54,55,例：F=ADE，DEA，ACBI，ID 有：AC CDE， CDEAC,56,也就是有：YU EF(X) 而 YU U (F, YZ) 因YZ，则用ZUV 代替 YU 和 ZV， 结果为F， 且 F F 即 F |= YU 和 F |= ZV。 但F 有更少的函数依赖数，因而与F是最小函数依赖集矛盾。,57,定理10 若F和G是等价的最小函数依赖集，则对任一X， |EF(X)|EG(X)| 。,eF(X)=X1,X2,Xm eG(X)=Y1,Y2, , Yn,58,59,60,61,算法3.3.4 求最小覆盖 输入：函数依赖集G 输出：G的最小覆盖 MINIMIZE(G) begin F:=NONREDUN(G); find the set of EF ; for each EF(X) in EF do for each YU in EF(X) do for each ZV YU in EF(X) do if MEMBER(F EF(X)，YZ) then replace YU and ZV by ZUV in F return(F); end.,62,例: 设F=ABC, CA, ADE, ECGH, AEH, ED 求：F的最小覆盖,解：(1)计算F的无冗余覆盖。考察F得 FD AEH 是冗余的，去掉冗余FD，则： F=ABC, CA, ADE, ECGH, ED。,(2) 找出F中FD左部的等价类如下： EF(A)=ABC,CA EF(AD)=ADE, ECGH EF(E)=ED,