《判断一个分解具有无损连接性的算法.ppt》由会员分享，可在线阅读，更多相关《判断一个分解具有无损连接性的算法.ppt（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 do if t=a
2、1a2.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,a1,a5,a5,b13,b3
3、3,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,
