1. 無損連接分解的形式定義
無損連接分解的形式定義如下：設(shè)R是一個關(guān)系模式，F(xiàn)是R上的一個函數(shù)依賴(FD)集。R分解成數(shù)據(jù)庫模式δ={R1,……,Rk}。如果對R中每一個滿足F的關(guān)系r都有下式成立：
那么稱分解δ相對于F是“無損連接分解”，否則稱為“損失連接分解”。其中表示自然連接。
從上述形式定義中可知，若直接根據(jù)定義來判斷某個分解是否具有無損連接性，那么就得“對R中每一個滿足F的關(guān)系r”進(jìn)行測試，看是否滿足上面的等式，這顯然不可操作，因?yàn)椤皩中每一個滿足F的關(guān)系r”進(jìn)行測試就意味著“對R中所有滿足F的關(guān)系r”進(jìn)行測試，顯然是不可能的。這里所說的“關(guān)系”就是指一張具體的表。
因此，必須尋求其它的可操作性方法來判別分解的無損連接性。
2. 無損連接分解的普通判別方法——表格法
設(shè)關(guān)系模式R=A1,…,An，R上成立的FD集F，R的一個分解p={R1,…,Rk}。無損連接分解的判斷步驟如下：
(1)構(gòu)造一張k行n列的表格，每列對應(yīng)一個屬性Aj(1≤j≤n)，每行對應(yīng)一個模式Ri(1≤i≤k)。如果Aj在Ri中，那么在表格的第i行第j列處填上符號aj，否則填上符號bij。
(2)把表格看成模式R的一個關(guān)系，反復(fù)檢查F中每個FD在表格中是否成立，若不成立，則修改表格中的元素。修改方法如下：對于F中一個FD：X→Y，如果表格中有兩行在X分量上相等，在Y分量上不相等，那么把這兩行在Y分量上改成相等。如果Y的分量中有一個是aj，那么另一個也改成aj;如果沒有aj，那么用其中的一個bij替換另一個(盡量把ij改成較小的數(shù)，亦即取i值較小的那個)。
若在修改的過程中，發(fā)現(xiàn)表格中有一行全是a，即a1,a2,…,an，那么可立即斷定p相對于F是無損連接分解，此時不必再繼續(xù)修改。若經(jīng)過多次修改直到表格不能修改之后，發(fā)現(xiàn)表格中不存在有一行全是a的情況，那么分解就是有損的。特別要注意，這里有個循環(huán)反復(fù)修改的過程，因?yàn)橐淮涡薷目赡軐?dǎo)致表格能繼續(xù)修改。
修改過程中要特別注意，若某個bij被改動，那么它所在列的所有bij都需要做相應(yīng)的改動。為了明確這一點(diǎn)，舉例說明。例如，我們根據(jù)FD“H→I”、“ K→L”來修改表格之前時的表格如表1所示(已經(jīng)過多次修改，非初始表，空的單元表示省略)：
表1
H
I
J
K
L
R1
b12
b35
R2
a1
a2
a4
b25
R3
a1
b12
a4
b35
R4
b12
b35
R2、R3所在行的H分量都為a1，根據(jù)FD“H→I”，需要修改這兩行對應(yīng)的I分量，而R2所在行的I分量為a2，因此，要將R3所在行的I分量b12修改為a2，注意到，R1、R4所在行的H分量也為b12，因此，這兩行對應(yīng)的I分量也必須修改為a2。R2、R3所在行的K分量都為a4，根據(jù)FD“K→L”，需要修改這兩行對應(yīng)的L分量，于是將R3所在行的L分量b35修改為較小的b25，同時注意到，R1、R4所在行的L分量也為b35，因此，這兩行對應(yīng)的L分量也必須修改為b25。修改后的表格如表2所示：
表2
H
I
J
K
L
R1
a2
b25
R2
a1
a2
a4
b25
R3
a1
a2
a4
b25
R4
a2
b25
【例題】(軟件設(shè)計(jì)師2002年上午試題38)
設(shè)關(guān)系模式 R為 R(H,I,J,K,L)，R上的一個函數(shù)依賴集為 F={H→J,J→K,I→J,JL→H}，分解 (38) 是無損連接的。
供選擇的答案：
(38) A. p={HK，HI，IJ，JKL，HL} B. p={HIL，IKL，IJL}
C. p={HJ，IK，HL} D. p={HI，JK，HL}
試題分析：
根據(jù)上述判斷方法，我們列出選項(xiàng)B(分解成三個關(guān)系模式R1(HIL)、R2(IKL)、R3(IJL) )的初始表如表3所示：
表3 選項(xiàng)B的初始表
H I J K L
HIL a1 a2 b13 b14 a5
IKL b21 a2 b23 a4 a5
IJL b31 a2 a3 b34 a5
對于函數(shù)依賴集中的H→J、J→K對表3進(jìn)行處理，由于屬性列H和屬性列J上無相同的元素，所以無法修改。但對于I→J在屬性列I上對應(yīng)的1、2、3行上全為a2元素，所以，將屬性列J的第一行b13和第二行b23改為a3。
無損連接分解的形式定義如下：設(shè)R是一個關(guān)系模式，F(xiàn)是R上的一個函數(shù)依賴(FD)集。R分解成數(shù)據(jù)庫模式δ={R1,……,Rk}。如果對R中每一個滿足F的關(guān)系r都有下式成立：
那么稱分解δ相對于F是“無損連接分解”，否則稱為“損失連接分解”。其中表示自然連接。
從上述形式定義中可知，若直接根據(jù)定義來判斷某個分解是否具有無損連接性，那么就得“對R中每一個滿足F的關(guān)系r”進(jìn)行測試，看是否滿足上面的等式，這顯然不可操作，因?yàn)椤皩中每一個滿足F的關(guān)系r”進(jìn)行測試就意味著“對R中所有滿足F的關(guān)系r”進(jìn)行測試，顯然是不可能的。這里所說的“關(guān)系”就是指一張具體的表。
因此，必須尋求其它的可操作性方法來判別分解的無損連接性。
2. 無損連接分解的普通判別方法——表格法
設(shè)關(guān)系模式R=A1,…,An，R上成立的FD集F，R的一個分解p={R1,…,Rk}。無損連接分解的判斷步驟如下：
(1)構(gòu)造一張k行n列的表格，每列對應(yīng)一個屬性Aj(1≤j≤n)，每行對應(yīng)一個模式Ri(1≤i≤k)。如果Aj在Ri中，那么在表格的第i行第j列處填上符號aj，否則填上符號bij。
(2)把表格看成模式R的一個關(guān)系，反復(fù)檢查F中每個FD在表格中是否成立，若不成立，則修改表格中的元素。修改方法如下：對于F中一個FD：X→Y，如果表格中有兩行在X分量上相等，在Y分量上不相等，那么把這兩行在Y分量上改成相等。如果Y的分量中有一個是aj，那么另一個也改成aj;如果沒有aj，那么用其中的一個bij替換另一個(盡量把ij改成較小的數(shù)，亦即取i值較小的那個)。
若在修改的過程中，發(fā)現(xiàn)表格中有一行全是a，即a1,a2,…,an，那么可立即斷定p相對于F是無損連接分解，此時不必再繼續(xù)修改。若經(jīng)過多次修改直到表格不能修改之后，發(fā)現(xiàn)表格中不存在有一行全是a的情況，那么分解就是有損的。特別要注意，這里有個循環(huán)反復(fù)修改的過程，因?yàn)橐淮涡薷目赡軐?dǎo)致表格能繼續(xù)修改。
修改過程中要特別注意，若某個bij被改動，那么它所在列的所有bij都需要做相應(yīng)的改動。為了明確這一點(diǎn)，舉例說明。例如，我們根據(jù)FD“H→I”、“ K→L”來修改表格之前時的表格如表1所示(已經(jīng)過多次修改，非初始表，空的單元表示省略)：
表1
H
I
J
K
L
R1
b12
b35
R2
a1
a2
a4
b25
R3
a1
b12
a4
b35
R4
b12
b35
R2、R3所在行的H分量都為a1，根據(jù)FD“H→I”，需要修改這兩行對應(yīng)的I分量，而R2所在行的I分量為a2，因此，要將R3所在行的I分量b12修改為a2，注意到，R1、R4所在行的H分量也為b12，因此，這兩行對應(yīng)的I分量也必須修改為a2。R2、R3所在行的K分量都為a4，根據(jù)FD“K→L”，需要修改這兩行對應(yīng)的L分量，于是將R3所在行的L分量b35修改為較小的b25，同時注意到，R1、R4所在行的L分量也為b35，因此，這兩行對應(yīng)的L分量也必須修改為b25。修改后的表格如表2所示：
表2
H
I
J
K
L
R1
a2
b25
R2
a1
a2
a4
b25
R3
a1
a2
a4
b25
R4
a2
b25
【例題】(軟件設(shè)計(jì)師2002年上午試題38)
設(shè)關(guān)系模式 R為 R(H,I,J,K,L)，R上的一個函數(shù)依賴集為 F={H→J,J→K,I→J,JL→H}，分解 (38) 是無損連接的。
供選擇的答案：
(38) A. p={HK，HI，IJ，JKL，HL} B. p={HIL，IKL，IJL}
C. p={HJ，IK，HL} D. p={HI，JK，HL}
試題分析：
根據(jù)上述判斷方法，我們列出選項(xiàng)B(分解成三個關(guān)系模式R1(HIL)、R2(IKL)、R3(IJL) )的初始表如表3所示：
表3 選項(xiàng)B的初始表
H I J K L
HIL a1 a2 b13 b14 a5
IKL b21 a2 b23 a4 a5
IJL b31 a2 a3 b34 a5
對于函數(shù)依賴集中的H→J、J→K對表3進(jìn)行處理，由于屬性列H和屬性列J上無相同的元素，所以無法修改。但對于I→J在屬性列I上對應(yīng)的1、2、3行上全為a2元素，所以，將屬性列J的第一行b13和第二行b23改為a3。