tij=
{
aj 若AjRi bij 若AjRi
c1:=true
do while c1 {c1:=false; for 每一个XYF do for 每一对ti,tk T do
if ti[X]=tk[X] and ti[Y]tk[Y]
then { EQUY(ti,tk); c1=true }
a1
a1
b12
a2
a3
a3
a4
a4
b15
b25
a1
a1 a1
a2
b42 b52
a3
a3 a3
a4
a4 a4
a5
a5 a5
算法输出true 是无损的
定理：关系模式R(U)，分解为={R(U1),R(U2)} 是无损连接的 当且仅当 U1U2 U1-U2
或
U1 U2 U2-U1
例：关系模式 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 R4 R5
a1
a1 b31 b41 a1
b12
a2 a2 b42 b52
b13
b23 b33 a3 b53
a4
b24 b34 a4 b54
b15
b25 a5 a5 a5
由AC,做的修改
A B C D E
R1
R2 R3 R4 R5
a1
a1 b31 b41 a1
b12
a2 a2 b42 b52
b13
a4
b15
b25 a5 a5 a5
b23b13 b24 b33 a3 b34 a4
判断一个分解具有无损连接性的算法
算法的输入： 关系模式R(A1,A2,…,An), R上的函数依赖集F,
R的一个分解={R1,R2,…,Rk}
算法的输出： true 或 false
算法 LOSSLESSTEST(R,F ,)
构造一个k行n列的二维表T，第i行对应于关系模式Ri，第 j列对应于属性Aj，令
b53 b13 b54
由CD做的修改
A B C D E
R1
R2 R3 R4 R5
a1
a1 b31 b41 a1
b12
a2 a2 b42 b52
b13
b13 b13 a3 b13
a4
b24a4 b34a4 a4 b54a4
bห้องสมุดไป่ตู้5
b25 a5 a5 a5
结果二维表
A B C D E
R1
R2 R3 R4 R5
};
for 任一个tT do { if t=a1a2..an then return(true)} return(false)
EQUY (ti,tk)是使ti, tk两个元组的Y值相等的子处理过程， 处理原则如下：
若ti[Y]与tj[Y] 有一个为aj
则将另一个也改为aj
否则，tk[Y]=ti[Y] 假定i<k