判断模式分解是否具有无损连接性的算法

《判断模式分解是否具有无损连接性的算法》由会员分享，可在线阅读，更多相关《判断模式分解是否具有无损连接性的算法（10页珍藏版）》请在金锄头文库上搜索。

1、判断一个分解具有无损连接性的算法,算法的输入： 关系模式R(A1,A2,An), R上的函数依赖集F, R的一个分解=R1,R2,Rk,算法的输出： true 或 false,算法 LOSSLESSTEST(R,F ,),构造一个k行n列的二维表T，第i行对应于关系模式Ri，第j列对应于属性Aj，令,tij=,aj 若AjRi,bij 若AjRi,c1:=true,do while c1 c1:=false; for 每一个XYF do for 每一对ti,tk T do if tiX=tkX and tiYtkY then EQUY(ti,tk); c1=true ;,for 任一个tT d

2、o if t=a1a2.an then return(true),return(false),EQUY (ti,tk)是使ti, tk两个元组的Y值相等的子处理过程，处理原则如下：,若tiY与tjY 有一个为aj 则将另一个也改为aj,否则，tkY=tiY 假定ik,例：关系模式 R(A,B,C,D,E) F=AC,BC,CD,DEC,CEA 分解为 =R1(A,D)，R2(A,B)，R3(B,E), R4(C,D,E),R5(A,E ),用上述算法 判断是否具有无损连接性,构造二维表,A B C D E,R1,R2,R3,a1,a3,a2,a1,b23,R4,R5,a5,a4,a2,a4,a

3、1,a5,a5,b13,b33,b53,b12,b15,b24,b25,b34,b31,b54,b52,b42,b41,由AC,做的修改,A B C D E,R1,R2,R3,a1,a3,a2,a1,b23,R4,R5,a5,a4,a2,a4,a1,a5,a5,b13,b33,b53,b12,b15,b24,b25,b34,b31,b54,b52,b42,b41,b13,b13,由CD做的修改,A B C D E,R1,R2,R3,a1,a3,a2,a1,b13,R4,R5,a5,a4,a2,a4,a1,a5,a5,b13,b13,b13,b12,b15,b24,b25,b34,b31,b54,b52,b42,b41,a4,a4,a4,结果二维表,A B C D E,R1,R2,R3,a1,a3,a2,a1,R4,R5,a5,a4,a2,a4,a1,a5,a5,b12,b15,b25,b52,b42,a3,a3,a3,a3,a1,a1,a4,a4,a4,算法输出true 是无损的,定理：关系模式R(U)，分解为=R(U1),R(U2),是无损连接的当且仅当,U1U2 U1-U2 或U1 U2 U2-U1,