• / 29
  • 下载费用:15 金币  

多值依赖多值依赖(Multivalued Dependency,MVD)

关 键 词:
多值依赖多值依赖(MultivaluedDependencyMVD)
资源描述:
3.4 多值依赖 3.4.1多值依赖(Multivalued Dependency,MVD)例: COURSE TEACHER CLASS 知识工程 王一平 硕士刘晓利 博士 离散数学 赵 静 硕士孟山峰 本科大专1下下例: COURSE TEACHER CLASS 知识工程 王一平 硕士知识工程 王一平 博士知识工程 刘晓利 硕士知识工程 刘晓利 博士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[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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满足MVD AB→→BC,AB∩BC=B,因此r也满足MVD AB→→C。又A  AB,则r也满足MVD AB→→AC。53.4.2 多值依赖的性质 定理12 设关系r(R),X、Y和Z是R的子集且 Z=R-(XY), 当且仅当关系r无损地分解成关系模式R1 =XY和R2 =XZ, 则 r满足X→→Y。设t1、t2∈r,且t1[X]=t2[X]。 又设t1∈r1,t2∈r 2 , t1=t1[XY]且t2=t2[XZ]。由于r=r1 r2,因此有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上成立,r1和r2如上所述。设t∈r1 r2 则一定有t ∈r。因t ∈ r1 r2 , 必有元组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。所以有r1 r2  r, 而rr1 r2是显然的, 因此r= r1 r2成立.证毕。7测试关系r是否满足MVD : (1). 根据多值依赖的性质;(2). r是否满足:|πY ( X=x(r))| = |πY ( XZ=xz(r))| 其中, R=XYZ, Z=R -(XY)推论 设r是模式R上的一个关系,并设X和Y是R的子集。如果r满足FD X→Y,则r满足MVD X→→Y。83.4.3 多值依赖的推理公理 多值依赖的推理公理M1~M9 M1:自反性 若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→→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→→Y-Z 因X→→Y,X→→Y-Z,有:X→→Y-(Y-Z) =Y∩Z,即有X→→Y∩Z成立。 证毕。10证明(公理M9): 设t1和t2是r中的元组。有t1[X]=t2[X]。因 r满足X→→Y,则必有元组 t 在 r中且满足条件:t[X]=t1[X] =t2[X], t[Y]=t1[Y],t[V]=t2[V]。 其中 V = R-[XY]因 Y∩Z=Φ,Z  XV,因此 t[Z] = t2[Z]。由FD Z→W可知:因t[Z] = t2[Z],有 t[W]=t2[W]。因W  Y,而t[Y]=t1[Y], 则 t1[W]=t[W]=t2[W],而t1[X]=t[X]=t2[X], 因此 r 满足 X→W。 证毕。11例: 设R=ABCDE,F={A→→BC,DE→→C}求证:F |= AD→→BE证明:由A→→BC,由M7得:A→→DE,已知 DE→→C,由M5得:A→→C,由M2得: AD→→C , 由M7得: AD→→BE。12定义(依赖基) 设F是关系模式R上的多值依赖集,X  R。定义X关于F的依赖基是R的一个划分{ Y1,Y2,.,Ym},其满足如下条件:(1) F|= X→→Yi,1  i  m;(2) { Y1,Y2,.,Ym}中没有任何Yi (1  i  m) 使得Yi  Yi而满足F|= X→→Yi。X的依赖基记为 DEP(X,F):X→→Y1 |Y2 |…|Ym。 ** X的依赖基是唯一的。3.4.4 依赖基13最小不相交基(minimal disjoint set basic, mdsb) 设S={S1,S2, … ,Sp}是U上的属性集且U= S1∪S2∪…∪Sp,S的最小不相交基是U的划分, 表示为:{Y1,Y2,…,Yk}。 该划分满足:(1) S中的每个Si是某些Yi的并集;(2) {Y1, Y2,…,Yk}是满足(1)的每个Yi具有最少属性数的U的划分。 例: 已知 S={ABCD, CDE, AE},U=ABCDE 计算: mdsb(S) mdsb(S)为:{A, B, CD , E}。14算法3.4.1 计算最小不相交基MDSB(G)for each Yi  Yj in G doif Yi∩Yj φ thenY:={(G-Yi-Yj)}∪{Yi∩Yj}∪{Yi-Yj }∪{Yj-Yi };G:=Yreturn(G). 15计算X的依赖基DEP(X):(1). 将F中的所有FD变为右部为单属性的MVD;(2). DEP(X)的初值为X的单属性集合和除X以外的其它属性集的并集;(3).利用MVD的传递性不断改进DEP(X)。若有W→→ZF且W包含在DEP(X)的某些属性集的并Y中,而ZY不为空或不是DEP(X)中某些属性集的并,则DEP(X)=DEP(X)∪{ZY},计算mdsb(DEP(X)).反复执行(3),直到不能改进为止。 16算法3.4.2 计算X的依赖基输入:模式R,R的多值依赖基F及X R输出:DEP(X,F)BASIS(R,F,X) 17Beginfor each FD U→V in F doF:= (F{U→V })∪{U→→Bi | V=B1…Bp,1≤i≤p};G: = { {Ai} | X=A1…Ak, 1≤i≤k }∪{ RX };T: =Ф;While T G do beginT: = G;For each MVD W→→Z in F do beginY=∪{Yi | Yi T且Yi∩Wφ}; If WY then If ZYΦ and ZYT and ZY  ∪{ Yi | Yi T } thenG: = mdsb ( G∪{ ZY } )End; End;Return(G) End. 18例: 设R=ABCDEG, F={AB→C, B→DE, DE→→G}。计算:DEP(AB, F) 解:(1). 将FD 变为右部为单属性的MVD:F={AB→→C, B→→D, B→→E, DE→→G}(2). DEP(AB)={A, B, CDEG}。(3).检查AB→→C, 有AB∩Aφ和AB∩B φ, 且 ABA∪B, 加C到DEP(AB)。DEP(AB)={ mdsb (A, B, C, CDEG)}={A, B, C, DEG}。(4). 依次检查 B→→D和B→→E, DEP(AB) = {mdsb (A, B, C, DEG, D, E)={A, B, C, D, E, G} 结果: DEP(AB)= {A, B, C, D, E, G}。19定理13 推理公理A1~A3,M1~M9对于函数依赖集和多值依赖集是完备的。证明: 构造一个关系r使r满足F但不满足X→→Y, 即X→→Y在r上不成立,若能证明以下二点则定理得证。(1). 凡是F蕴涵的MVD在r中都成立;(2). X→→Y不能用公理从F中推出,则X→→Y 在r中不成立.20A1 A2 …Am W1 W2 … Wn1 1 … 1 0…0 0 … 0 … 0…0 1 1 … 1 0…0 0 … 0 … 1…1 1 1 … 1 0…0 1 … 1 … 0…0 1 1 … 1 1…1 0 … 0 … 0…0 … … … … … … …1 1 … 1 1…1 1 … 1 … 0…0 1 1 … 1 1…1 1 … 1 … 1…1X+X→→Wi213.4.5 嵌入多值依赖 定义(嵌入MVD) 设关系模式R和其上的关系r, S R, XY S, Z=S-XY, 如果 S ( r) 满足 X→→Y,则称关系 r ( R )满足嵌入多值依赖 EMVD X→→Y|Z。 例: 设模式R(C, T, S, M, G),其中C、T、S、M、G分别表示课程、教师、学生、上课时间、成绩。 r 不满足MVD CT→→S,但满足EMVD CT→→S | M。(下页图 )22C T S M Gc1 t1 s1 m1 g1c1 t1 s2 m1 g2c1 t2 s3 m1 g3c1 t1 s1 m2 g1c1 t1 s2 m2 g4c1 t2 s3 m2 g5c2 t3 s2 m2 g2c2 t3 s2 m3 g6 r不满足MVD CT→→S,但满足EMVD CT→→S | M。 23嵌入多值依赖的几个推导规则。EM1 若X→→Y|Z,Y1 Y,Z1 Z,则X→→Y1| Z1。EM2 若X→→Y|Z, YY1, XY→→(Y1-Y)|Z, 则 X→→Y1|Z。EM3 若X1→→Y1 |Z1,X2Y2Z2=X1Y1,X2 →→Y2 |Z2,X1、Y1、Z1和 X2、Y2、Z2 都互不相交。则X2 (Y2-Y1) →→Y2∩Y1 | Z1Z2。243.5 连接依赖r ( A B C ) r1 ( A B ) r2 ( A C ) r3 ( B C )a1 b1 c1 a1 b1 a1 c1 b1 c1a1 b2 c2 a1 b2 a1 c2 b2 c2a3 b3 c3 a3 b3 a3 c3 b3 c3a4 b3 c4 a4 b3 a4 c4 b3 c4a5 b5 c5 a5 b5 a5 c5 b5 c5a6 b6 c5 a6 b6 a6 c5 b6 c5 关系r及r在AB,BC,CA上的投影分别为关系r1、r2,、 r3 。若将r1、r2,、r3两两连接,连接后的关系不等于r, 但若将r1、r2,、r3三个关系连接,则连接后的关系与r相 同。 25JD定义2: 若r满足JD*[R1,R2, …, Rp],如果r含有元 组t1,t2, … , tp且对所有的 i 和 j 等式ti [Ri∩Rj]=tj [Ri∩Rj]成立,其中tiRi, tjRj,1≤i, j≤p,则r必含有元组t,且t[Ri]=ti[Ri]。定义(连接依赖) 设R={R1,R2, …,Rp}是属性集U上的 关系模式集。若r(U)无损地分解成R1,R2,…,Rp, 那么,关系r(U)满足连接依赖,即:r = R1 (r) R2 (r) … Rp (r)。 记为:(JD)*[R1, R2,…,Rp],或 *[R1,R2,…,Rp]。26例: 设关系r(ABCDE)满足JD*[ABC,BD,CDE]。r ( A B C D E )t1 a b c d e t2 a b c d et3 a b c d e  t1[ABC∩BD]=t2[ABC∩BD]= b t2[BD∩CDE]= t3[BD∩CDE]= d, t1[ABC∩CDE] = t3[ABC∩CDE]= c, 则 r也必含元组t:t[ABC]=t1[ABC]={abc}, t[BD] = t2[BD] = {bd},t[CDE]=t3[CDE]={cde}。 元组t = {abcde}。27定义(嵌入连接依赖)设关系r(R),S  R 且 S=R1R2…Rp,若S(r)满足JD*[R1,R2,……,Rp],则称关系r(R)满足嵌入连接依赖: (EJD)*[R1,R2,…,Rp]。28连接依赖推理规则 JD1—JD5JD1 对任一X U,有(EJD)*[X]。JD2 设YR1 R2 …Rk,(JD)*[R1 ,R2 ……, Rk] |= (JD)*[R1 ,R2 ……, Rk, Y]。JD3 (JD)*[R1 ,R2 …, Rk] |= (JD)*[R1,R2 …, Rk-2 , Rk-1 Rk]JD4 {(JD)*[R1 ,R2 …, Rk, Y], (EJD)*[S1 ,S2 …, Sq]}|= (JD)*[R1,R2 …, Rp, S1 ,S2 …, Sq],Y=S1S2 …Sq JD5 设A R1 R2 …Rk,(JD)*[R1 ,R2 …, Rk,YA] |= (JD)*[R1 ,R2 …, Rk, Y]29
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:多值依赖多值依赖(Multivalued Dependency,MVD)
链接地址:https://www.maidoc.com/p-13077022.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 


收起
展开