多值依赖多值依赖（Multivalued Dependency,MVD）.ppt

《多值依赖多值依赖（Multivalued Dependency,MVD）.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、3.4多值依赖3.4.1多值依赖(MultivaluedDependency，MVD)例：COURSETEACHERCLASS知识工程王一平硕士刘晓利博士离散数学赵静硕士孟山峰本科大专1下下例：COURSETEACHERCLASS知识工程王一平硕士知识工程王一平博士知识工程刘晓利硕士知识工程刘晓利博士t1t3t4t2COURSE→→TEACHERCOURSE→→CLASS下页2定义(MVD)设关系模式R，X、YR且Z=R-(XY)。若对r(R)中任意元组t1、t2有t1[X]=t2[X]，则在r中存在元组t3且满足：t3[X]=t1[X]，t3

2、[Y]=t1[Y]，且t3[Z]=t2[Z]关系r(R)满足多值依赖(MVD)X→→Y，称X多值决定Y或Y多值依赖于X。定义（MVD）设关系模式R，X、YR且Z=R-(XY)。若关系模式R满足多值依赖(MVD)X→→Y，当且仅当对R上的任一关系r，给定一对（x,z）的值，有一组y的值，这组值仅仅决定于x值而与z的值无关。3引理设关系模式R和R上的关系r，X、YR且Z=R-(XY)。若r满足多值依赖X→→Y，则r满足多值依赖X→→Z。说明：(1)MVD中：X∩Y=φ或X∩Y≠φ都可以。若X∩Y≠φ，则有r满足X→→Y,(Y=Y-X)。因为Y

3、Y，则t3(Y)=t1(Y)，而Z=R-(XY)=R-(XY)，有t3(Z)=t2(Z)。(2)若X∩Y=φ且XX，则r(R)满足X→→Y也满足X→→YX。(3)若Z=φ，即R=XY，即X→→Y，X→→φ为平凡的MVD。(4)若R(XYZ)中X=φ，即MVDφ→→Y，Z=R-Y。则r是投影Y(r)和Z(r)的笛卡尔积。4例：若r满足MVDAB→→BC，AB∩BC=B，因此r也满足MVDAB→→C。又AAB，则r也满足MVDAB→→AC。53.4.2多值依赖的性质定理12设关系r(R)，X、Y和Z是R的子集且Z=R-(XY)，

4、当且仅当关系r无损地分解成关系模式R1=XY和R2=XZ，则r满足X→→Y。设t1、t2∈r，且t1[X]=t2[X]。又设t1∈r1，t2∈r2,t1=t1[XY]且t2=t2[XZ]。由于r=r1r2，因此有t∈r，使t[XY]=t1[XY]和t[XZ]=t2[XZ]，即元组t是t1和t2的连接结果。因t、t1和t2在r中，所以r满足X→→Y。证明：(1)设r是模式R(XYZ)上的关系，假定r无损分解成r1(XY)和r2(XZ)，即r1=XY(r),r2=XZ(r)。r=XY(r)XZ(r)6(2)设X→→Y在r上成立，r

5、1和r2如上所述。设t∈r1r2则一定有t∈r。因t∈r1r2,必有元组t1∈r1和t2∈r2，且满足：t[X]=t1[X]=t2[X],t[Y]=t1[Y]和t[Z]=t2[Z]。因r1和r2是r的投影，则在r中必有元组t1、t2和t3，使得t1[XY]=t1[XY],t2[XZ]=t2[XZ],且t3[X]=t1[X]=t2[X],t3[Y]=t1[Y]和t3[Z]=t2[Z]。可以看出，t3就是t,即t∈r。所以有r1r2r,而rr1r2是显然的,因此r=r1r2成立.证毕。7测试关系r是否满足MVD：(1).

6、根据多值依赖的性质；(2).r是否满足：

7、πY(X=x(r))

8、=

9、πY(XZ=xz(r))

10、其中，R=XYZ,Z=R-(XY)推论设r是模式R上的一个关系，并设X和Y是R的子集。如果r满足FDX→Y，则r满足MVDX→→Y。83.4.3多值依赖的推理公理多值依赖的推理公理M1~M9M1：自反性若YX则X→→Y。M2：增广性若X→→Y，WZ，则XZ→→YW。M3：相加性若X→→Y、X→→Z，则X→→YZ。M4：投影性若X→→Y、X→→Z，则X→→Y－Z、X→→Y∩Z。M5：传递性若X→→Y、Y→→Z，则X→→Z－Y。M6：伪传递性若X→→

11、Y、YW→→Z，则XW→→Z－(YW)。M7：互补性若X→→Y、Z＝R－(XY)，则X→→Z。M8：重复性若X→Y，则X→→Y。M9：结合性若X→→Y，Z→W，其中WY和Y∩Z＝Φ，则X→W。9证明：公理M4先证X→→Y－Z成立。若X→→Y、X→→Z，有X→→YZ，求补得：X→→V，其中V=R－(XYZ)。由X→→Z、X→→V，有X→→VZ，求补得：X→→R－(XVZ)。化简R－(XVZ)：R－(XVZ)=R－(X（R－(XYZ)）Z)=R－(X（R－Y）Z)=Y－(XZ)=(Y－Z)－X因此，r满足X→→(Y－Z)－X，又X→→X，则：X→→

12、Y－Z因X→→Y，X→→Y－Z，有：X→→Y－(Y－Z)=Y∩Z，即有X→→Y∩Z成立。证毕。10证明（公理M9）：设t1和t2是r中的