数据库原理——模式分解中无损链接的判别

最近重新复习数据库的时候再次被范式这一块搞晕了，跟之前期末考试的时候一摸一样，弄了大半天可算是有点小明白，记录一下。

无损链接的判定

无损链接的判定书上给的方法是画图，但是没有例题详细讲解。书上的算法如下。

ρ={R1<U1,F1>,R2<U2,F2>,…,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解，U={A1,A2,…,An}，F={FD1,FD2,…,FDp}，并设F是一个最小依赖集，记FDi为Xi→Alj，其步骤如下：

① 建立一张n列k行的表，每一列对应一个属性，每一行对应分解中的一个关系模式。若属性Aj Ui，则在j列i行上真上aj，否则填上bij；

②
对于每一个FDi做如下操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有aj，则全部改为aj，否则全部改为bmli，m是这些行的行号最小值。

如果在某次更改后，有一行成为：a1,a2,…,an，则算法终止。且分解ρ具有无损连接性，否则不具有无损连接性。

对F中p个FD逐一进行一次这样的处理，称为对F的一次扫描。

③ 比较扫描前后，表有无变化，如有变化，则返回第②
步，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此，循环必然终止

但算法过于复杂难以理解，结合例题去理解较为简单。例题如下

已知R<U,F>, U={A,B,C,D,E}, F={AB->C,C->D,D->E},R的一个分解为R1{A,B,C}, R2{C,D}, R3{D,E},判断该分解是否具有无损链接性。

1 首先建立一个n列k行的表格，其中n为属性个数(n=5),k为分解个数(k=3)。每一列对应一个属性。

分解模式R1包含ABC三个属性则在第一行的ABC三列上面填写a1,a2,a3
分解模式R2包含CD两个属性，则在第二行CD两列上面填写a3,a4，
分解模式R3包含DE两个属性，则在第三行DE两列上面填写a4,a5
aj分别对应属性在U中的位置如A-a1,B-a2,C-a3,D-a4,E-a5。

2 观察每一个函数依赖FDi（X->Y），找到其Xi所对应的列中具有相同符号的那些行，考察这些行中Y列的元素。

观察 AB->C， 观察表中AB两列是否具有相同的符号。

显然并没有相同的符号。

观察C->D，观察表中C列是否具有相同的符号。

显然前两行都为a3，故观察此两行中D列的值，一个为a4，一个为b14，根据算法将此两行D列的值全部更改为a4，则有

观察D->E，观察表中D列是否有相同的符号，显然D列值全部为a4，故观察E列三行中的值是否有aj，若有(最后一行为a5)，则全部更改为aj，否则全部改为bij(i为行数最小值,若要修改则为b15)。故将E列全部修改为a5。

此时图表如下

此时表中已有一行被修改为a1,a2,a3,…an。故算法终止，该分解具有无损链接。否则不具有无损链接性。