《数据库无损联结的判断方法.docx》由会员分享，可在线阅读，更多相关《数据库无损联结的判断方法.docx（3页珍藏版）》请在三一办公上搜索。
1、数据库无损联结的判断方法数据库无损连接的判断方法 算法：=R1,R2,.,Rk是关系模式R的一个分解，U=A1,A2,.,An，F=FD1,FD2,.,FDp，并设F是一个最小依赖集，记FDi为XiAlj，其步骤如下： 建立一张n列k行的表，每一列对应一个属性，每一行对应分解中的一个关系模式。若属性AjUi，则在j列i行上真上aj，否则填上bij； 对于每一个FDi做如下操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有aj，则全部改为aj，否则全部改为bmli，m是这些行的行号最小值。 如果在某次更改后，有一行成为：a1,a2,.,an，则算法终止。且分解具有
2、无损连接性，否则不具有无损连接性。 对F中p个FD逐一进行一次这样的处理，称为对F的一次扫描。 比较扫描前后，表有无变化，如有变化，则返回第步，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此，循环必然终止。 举例1：已知R，U=A,B,C，F=AB，如下的两个分解： 1=AB,BC 2=AB,AC 判断这两个分解是否具有无损连接性。 解：用无损连接的定理来解。 方法一： 因为ABBC=B，AB-BC=A，BC-AB=C 所以BAF+，BCF+ 故1是有损连接。 方法二： 因为ABAC=A，AB-AC=B，AC-AB=C 所以ABF+，ACF+ 故2是无损连
3、接。 举例2：已知R，U=A,B,C,D,E，F=AC,BC,CD,DEC,CEA，R的一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。 解：用判断无损连接的算法来解。 1 构造一个初始的二维表，若“属性”属于“模式”中的属性，则填aj，否则填bij。 根据AC，对上表进行处理，由于属性列A上第1、2、5行相同均为a1，所以将属性列C上的b13、b23、b53改为同一个符号b13。(有A的相对就的行改)相同的改成一样的 根据BC，对上表进行处理，由于属性列B上第2、3行相同均为a2，所以将属性列C上的b13、b33改为同一个符号b13。 根据CD，对上表进行处理，由于属性列C上第1、2、3、5行相同均为b13，所以将属性列D上的值均改为同一个符号a4。 2 根据DEC，对上表进行处理，由于属性列DE上第3、4、5行相同均为a4a5，所以将属性列C上的值均改为同一个符号a3。 根据CEA，对上表进行处理，由于属性列CE上第3、4、5行相同均为a3a5，所以将属性列A上的值均改为同一个符号a1。 通过上述的修改，使第三行成为a1a2a3a4a5，则算法终止。且分解具有无损连接性。 3
