第4讲函数依赖的等价和覆盖.ppt

1、1,第4讲函数依赖的等价和覆盖 3.3 函数依赖的等价和覆盖 包括函数依赖集的等价和覆盖、无冗余覆盖、化简覆盖、规范覆盖、最小覆盖等。 3.3.1 函数依赖的等价和覆盖,对于在模式R上的函数依赖集F和G，如果对G中的每一个函数依赖XY，都有F|=XY，称F是G的一个覆盖。把逻辑蕴含符号引入函数依赖集的覆盖中， 记为：F|= G 定义(等价和覆盖) 在模式R上的FDs F和G，若F+=G+，则称F和G等价。 记作FG。,2,定理4 已知模式R上的函数依赖集 F和G。当且仅当 F|=G 且 G|=F ，则 F G。,证明：如果F|=G，若有XYG，则F|=XY，即XYF +， 有GF +，(G)+

2、(F+)+ = F+， 则(G)+(F+)。 同理，如果G|=F，有F + G +。因此，F +=G +，则FG。 反之，若FG，则F|=G和G|=F是显然的。证毕。 研究函数依赖集等价和覆盖的目的是对函数依赖集的化简，比如：无冗余的覆盖、规范覆盖、最小覆盖等。,3,例: 证明F=ABC, AD, CDE和 G=ABCE, AABD, CDE等价,证明：根据前面的定理，只需证明F|=G和 G|=F （1）F|=G （a）ABCE的推导： 由 ABC, AD ，合并规则： ABCD;分解规则 ACD，又 CDE，有传递律： AE；有合并规则ABCE。 ( b）AABD 的推导： ABC, AD

3、,合并规则： ABCD;分解规则 ABD;增广律： AABD 。 (c) CDE 已有 （2） G|=F ABCE, AABD,合并规则： AABCDE, 由分解律： ABC, AD,4,3.3.2 无冗余覆盖 定义(无冗余覆盖)：如果函数依赖集F不存在真子集F使F F成立，则F是无冗余的。 如果F是G的一个覆盖且F是无冗余的，则F是G的一个无冗余覆盖。,5,算法3.3.1 计算函数依赖集F的无冗余覆盖 NONREDUN(F) begin G: =F ; for each FD XY in F do if MEMBER(GXY, XY) then G: =GXY; return(G) end.

4、,6,无冗余覆盖的例子,例: 求F=AB, BA, BC, ABC 的无冗余覆盖。 求无冗余覆盖基本过程： 用算法3.3.1 ，把计算无冗余覆盖问题转化为 用成员测试算法 MEMBER(GXY, XY)，进一步转化为属性集X的闭包X+， 即： CLOSURE(X, G XY, ) 然后判断Y是否属于CLOSURE(X, G XY, ),7,例: 求F=AB, BA, BC, ABC 的无冗余覆盖。,解:（1）G1= F- AB = BA, BC, ABC MEMBER(G1,AB)? A+=CLOSURE(A, G1 ) = A, B不属于 A+, 所以AB不是多余 （2）G2= F- BA

5、= AB, BC, ABC MEMBER(G2,BA)? B+=CLOSURE(B, G2 ) =B,C, A不属于B +,所以BA不是多余 （3）G3= F- BC = AB, BA, ABC MEMBER(G3,BC)? B+=CLOSURE(B, G3 ) =A,B,C, C属于B +,所以BC是多余 （4）G4= G3 - ABC = AB, BA MEMBER(G4,ABC)? B+=CLOSURE(AB, G4 ) =A,B, C不属于B +,所以ABC不是多余 所以G3是F的无冗余覆盖,8,另外，（1）、（2）同上，先考察ABC是否多余？ （4）G5= F- ABC = AB,

6、BA, BC MEMBER(G5,ABC)? B+=CLOSURE(AB, G5 ) =A,B,C, C属于B +,所以ABC是多余， 同时可以验证在G5中， BC 不是多余的 所以G5也是F的无冗余覆盖。 结论：无冗余覆盖不是唯一的。 无冗余覆盖是在F的覆盖集中去掉多余的函数依赖，还可以从其它角度去化简覆盖，比如：下面的化简覆盖是去掉多余的属性。,9,3.3.3 规范覆盖(canonical cover) 定义 设F是模式R上的一个FDs集，XYF。若模式R中的属性A满足下列条件，则称属性A在XY中是外部属性。 1. X=AZ, XZ，且(FXY)ZY F 或者; 2. Y=AW, YW，且

7、(FXY)XW F。,36,35,10,定义(化简覆盖) 若FD XY的左部或右部都不包含外部属性，称FD XY是化简的。 如果FDs集F中的所有FD都是化简的，称FDs集F是化简的。如果F是G的一个覆盖且F是化简的，称F是G的一个化简覆盖。 化简覆盖的算法类似于无冗余覆盖，也是用成员测试算法，不同之处在分别对F的每个函数依赖的左边和右边的属性分别进行检测，看是否存在多余的属性，去掉多余的属性。,11,定义(规范覆盖) 如果FDs集F是G的一个覆盖，F中的每个FD都具有XA形式而且F是左化简的和无冗余的，称F是G的一个规范覆盖。,计算规范覆盖： （1）将每个FD的右部化为单属性； （2）将每个

8、FD化为左简化的； （3）计算无冗余的覆盖。,12,3.3.4 最小覆盖 定义(最小覆盖) 如果FDs集F和任一等价的FDs集G相比，具有最少的函数依赖数，则称F为G的最小覆盖。,例： G=ABC, BA, ADE, BDI F=ABC, BA, ADEI,13,3.4 多值依赖 3.4.1多值依赖(Multivalued Dependency，MVD),14,下下,t1 t3 t4 t2,COURSE TEACHER COURSE CLASS,下页,15,定义(MVD) 设关系模式R，X、Y R 且 Z=R-(XY)。若对r(R)中任意元组t1、t2有t1X=t2X，则在r中存在元组t3且满

9、足： t3X=t1X，t3Y=t1Y，且t3Z=t2Z 关系r(R)满足多值依赖 (MVD) XY，称X多值决定Y或Y多值依赖于X。 关于多值依赖，还有下面等价的定义：,定义（MVD）设关系模式R，X、Y R 且Z=R-(XY)。若关系模式R满足多值依赖 (MVD) XY，当且仅当对R上的任一关系r，给定一对（x, z）的值，有一组y的值，这组值仅仅决定于x值而与z的值无关。,16,MVD的示意图： 表示已存在的元组： 可推出还应该存在的元组： x y1 z1 x y2 z1 x y2 z2 x y1 z2 引理： 设关系模式R和R上的关系r，X、YR 且Z=R-(XY)。若r满足多值依赖XY

10、，则r满足多值依赖XZ。 该引理称为多值依赖的对称性或互补性。,17,3.4.2 多值依赖的性质 定理12 设关系r(R)，X、Y和Z是R的子集且 Z=R-(XY)，当且仅当关系r无损地分解成关系模式R1 =XY和R2 =XZ，则 r满足XY。,无损分解: 设r是模式R(XYZ)上的关系，r 分解成r1 (XY)和r2(XZ)，即r1 =XY(r), r2=XZ (r)。则有：,18,测试关系r是否满足MVD ： (1). 根据多值依赖的性质； (2). r是否满足： |Y ( X=x(r)| = |Y ( XZ=xz(r)| 其中， R=XYZ, Z=R -(XY),推论： 设r是模式R上的

11、一个关系，并设X和Y是R的子集。如果r满足FD XY，则r满足MVD XY。,19,3.4.3 多值依赖的推理公理 多值依赖的推理公理M1M9 M1：自反性 若Y X 则XY。 M2：增广性 若XY，W Z，则XZYW。 M3：相加性 若XY、XZ，则XYZ。 M4：投影性 若XY、XZ，则 XYZ 、 XYZ 。 M5：传递性 若XY、YZ，则XZY。 M6：伪传递性 若XY、YWZ，则 XWZ(YW)。 M7：互补性 若XY、ZR(XY)，则XZ。 M8：重复性 若XY，则XY。 M9：结合性 若XY，ZW，其中W Y和 YZ，则XW。,20,例： 设R=ABCDE，F=ABC，DEC 求

12、证：F |= ADBE,证明：由ABC，由M7(互补性）得： ADE， 已知 DEC，由M5（传递性）得： AC， 又 A AD,由M1得： ADA ， 由M5（传递性）得:ADC 由M7 (互补性）得： ADBE。 思考：上面例子中传递性是否正确？传递性：若XY、YZ，则XZY,21,定义(依赖基) 设F是关系模式R(U)上的多值依赖集，X U。定义X关于F的依赖基是U的一个划分 Y1,Y2,.,Ym，其满足如下条件： (1) F|= XYi，1 i m； (2) Y1,Y2,.,Ym中没有任何Yi (1 i m) 使得Yi Yi而满足F|= XYi。 X的依赖基记为 DEP(X，F)：XY1 |Y2 |Ym。,* X的依赖基是唯一的。,3.4.4 依赖基,22,3.5 连接依赖,r ( A B C ) r1 ( A B ) r2 ( A C ) r3 ( B C ) a1 b1 c1 a1 b1 a1 c1 b1 c1 a1 b2 c2 a1 b2 a1 c2 b2 c2 a3 b3 c3 a3 b3 a3 c3 b3 c3 a4 b3 c4 a4 b3 a4 c4 b3 c4