(軟考軟件設(shè)計(jì)師)模式分解的無(wú)損連接性之深入剖析

1、模式分解的無(wú)損連接性之深入剖析1. 無(wú)損連接分解的形式定義無(wú)損連接分解的形式定義如下：設(shè)R是一個(gè)關(guān)系模式，F(xiàn)是R上的一個(gè)函數(shù)依賴(FD)集。R分解成數(shù)據(jù)庫(kù)模式=R1,Rk。如果對(duì)R中每一個(gè)滿足F的關(guān)系r都有下式成立：那么稱分解相對(duì)于F是“無(wú)損連接分解”，否則稱為“損失連接分解”。其中表示自然連接。從上述形式定義中可知，若直接根據(jù)定義來(lái)判斷某個(gè)分解是否具有無(wú)損連接性，那么就得“對(duì)R中每一個(gè)滿足F的關(guān)系r”進(jìn)行測(cè)試，看是否滿足上面的等式，這顯然不可操作，因?yàn)椤皩?duì)R中每一個(gè)滿足F的關(guān)系r”進(jìn)行測(cè)試就意味著“對(duì)R中所有滿足F的關(guān)系r”進(jìn)行測(cè)試，顯然是不可能的。這里所說(shuō)的“關(guān)系”就是指一張具體的表。因此

2、，必須尋求其它的可操作性方法來(lái)判別分解的無(wú)損連接性。2. 無(wú)損連接分解的普通判別方法表格法設(shè)關(guān)系模式R=A1,An，R上成立的FD集F，R的一個(gè)分解p=R1,Rk。無(wú)損連接分解的判斷步驟如下：(1)構(gòu)造一張k行n列的表格，每列對(duì)應(yīng)一個(gè)屬性Aj(1jn)，每行對(duì)應(yīng)一個(gè)模式Ri(1ik)。如果Aj在Ri中，那么在表格的第i行第j列處填上符號(hào)aj，否則填上符號(hào)bij。(2)把表格看成模式R的一個(gè)關(guān)系，反復(fù)檢查F中每個(gè)FD在表格中是否成立，若不成立，則修改表格中的元素。修改方法如下：對(duì)于F中一個(gè)FD：XY，如果表格中有兩行在X分量上相等，在Y分量上不相等，那么把這兩行在Y分量上改成相等。如果Y的分量中

3、有一個(gè)是aj，那么另一個(gè)也改成aj;如果沒(méi)有aj，那么用其中的一個(gè)bij替換另一個(gè)(盡量把ij改成較小的數(shù)，亦即取i值較小的那個(gè))。若在修改的過(guò)程中，發(fā)現(xiàn)表格中有一行全是a，即a1,a2,an，那么可立即斷定p相對(duì)于F是無(wú)損連接分解，此時(shí)不必再繼續(xù)修改。若經(jīng)過(guò)多次修改直到表格不能修改之后，發(fā)現(xiàn)表格中不存在有一行全是a的情況，那么分解就是有損的。特別要注意，這里有個(gè)循環(huán)反復(fù)修改的過(guò)程，因?yàn)橐淮涡薷目赡軐?dǎo)致表格能繼續(xù)修改。修改過(guò)程中要特別注意，若某個(gè)bij被改動(dòng)，那么它所在列的所有bij都需要做相應(yīng)的改動(dòng)。為了明確這一點(diǎn)，舉例說(shuō)明。例如，我們根據(jù)FD“HI”、“ KL”來(lái)修改表格之前時(shí)的表格如表1

4、所示(已經(jīng)過(guò)多次修改，非初始表，空的單元表示省略)：表1 HIJKLR1 b12  b35R2a1a2 a4b25R3a1b12 a4b35R4 b12  b35R2、R3所在行的H分量都為a1，根據(jù)FD“HI”，需要修改這兩行對(duì)應(yīng)的I分量，而R2所在行的I分量為a2，因此，要將R3所在行的I分量b12修改為a2，注意到，R1、R4所在行的H分量也為b12，因此，這兩行對(duì)應(yīng)的I分量也必須修改為a2。R2、R3所在行的K分量都為a4，根據(jù)FD“KL”，需要修改這兩行對(duì)應(yīng)的L分量，于是將R3所在行的L分量b3

5、5修改為較小的b25，同時(shí)注意到，R1、R4所在行的L分量也為b35，因此，這兩行對(duì)應(yīng)的L分量也必須修改為b25。修改后的表格如表2所示：表2 HIJKLR1 a2  b25R2a1a2 a4b25R3a1a2 a4b25R4 a2  b25【例題】(軟件設(shè)計(jì)師2002年上午試題38)設(shè)關(guān)系模式 R為 R(H,I,J,K,L)，R上的一個(gè)函數(shù)依賴集為 F=HJ,JK,IJ,JLH，分解 (38) 是無(wú)損連接的。供選擇的答案：(38) A. p=HK，HI，IJ，JKL，HL B. p=HIL，IKL，IJ

6、LC. p=HJ，IK，HL D. p=HI，JK，HL試題分析：根據(jù)上述判斷方法，我們列出選項(xiàng)B(分解成三個(gè)關(guān)系模式R1(HIL)、R2(IKL)、R3(IJL) )的初始表如表3所示：表3 選項(xiàng)B的初始表 HIJKLHILa1a2b13b14a5IKLb21a2b23a4a5IJLb31a2a3b34a5對(duì)于函數(shù)依賴集中的HJ、JK對(duì)表3進(jìn)行處理，由于屬性列H和屬性列J上無(wú)相同的元素，所以無(wú)法修改。但對(duì)于IJ在屬性列I上對(duì)應(yīng)的1、2、3行上全為a2元素，所以，將屬性列J的第一行b13和第二行b23改為a3。修改后如表4所示：【例題】(表4 選項(xiàng)B的中間表 HIJKLHI

7、La1a2a3b14a5IKLb21a2a3a4a5IJLb31a2a3b34a5對(duì)于函數(shù)依賴集中的JLH在屬性列J和L上對(duì)應(yīng)的1、2、3行上為a3、a5元素，所以，將屬性列H的第二行b21和第三行b31改為a1。修改后如表5所示：表5 選項(xiàng)B的結(jié)果表 HIJKLHILa1a2a3b14a5IKLa1a2a3a4a5IJLa1a2a3b34a5從表5可以看出，第二行為a1、a2、a3、a4、a5，所以分解p是無(wú)損的。有一種特殊情況要注意：分解后的各個(gè)關(guān)系模式兩兩均無(wú)公共屬性。由于是模式分解，那么任一一個(gè)分解后的關(guān)系模式覆蓋的屬性集不可能是分解前的整個(gè)全部屬性U，因此初始表中不存在全是

8、a的行。又注意到，分解后的各個(gè)關(guān)系模式兩兩均無(wú)公共屬性，表明任兩行在任一列上都沒(méi)有相同的分量，這導(dǎo)致整個(gè)表格無(wú)法修改，保持初始狀態(tài)。而初始狀態(tài)不存在全是a的行，因此這種特殊情況的分解是有損的。例如，函數(shù)依賴集合FD，將關(guān)系模式R(ABCDEF)分解成R1(AB)、R2(CDE)、R3(F)，那么這種分解肯定是有損的?？荚囍锌赡芘龅竭@種情況，那么一眼就可以判斷出結(jié)果，從而節(jié)省了時(shí)間。3. 無(wú)損連接分解的快捷判別方法首先要申明，這種快捷方法是有前提的，前提就是分解后的關(guān)系模式只有兩個(gè)。其內(nèi)容為：設(shè)=R1，R2是R的一個(gè)分解，F(xiàn)是R上的FD集，那么分解相對(duì)于F是無(wú)損分解的充分必要條件是：(R1R2)

9、(R1R2)或(R1R2)(R2R1)。這個(gè)“或”字很重要，這里表示(R1R2)(R1R2)、(R1R2)(R2R1)中只要有一個(gè)成立就行。這里的求交和相減運(yùn)算的對(duì)象是關(guān)系模式的屬性?！纠}】關(guān)系模式R(U，F(xiàn))，其中U=W,X,Y,Z,F=WXY,WX, XZ,YW。那么下列分解中是無(wú)損分解的是 。供選擇的答案：A.p=R1(WY),R2(XZ) B.p=R1(WZ),R2(XY)C.p=R1(WXY),R2(XZ) D.p=R1(WX),R2(YZ)試題分析：A選項(xiàng)，R1R2為空，肯定不滿足條件。B選項(xiàng)，R1R2為空，肯定不滿足條件。C選項(xiàng)，R1R2=X，R1-R2=WY，R2-R1=Z，

10、根據(jù)函數(shù)依賴集，XZ成立，所以滿足條件。D選項(xiàng)，R1R2為空，肯定不滿足條件。4. 總結(jié)模式分解無(wú)損性判別的源泉仍然是普通的表格法。這種快捷方法只不過(guò)是根據(jù)這種表格法推斷出來(lái)的而已，是它的一個(gè)特列。但是這種快捷方法卻往往非常有用。軟件設(shè)計(jì)師2002年上午試題38)設(shè)關(guān)系模式 R為 R(H,I,J,K,L)，R上的一個(gè)函數(shù)依賴集為 F=HJ,JK,IJ,JLH，分解 (38) 是無(wú)損連接的。供選擇的答案：(38) A. p=HK，HI，IJ，JKL，HL B. p=HIL，IKL，IJLC. p=HJ，IK，HL D. p=HI，JK，HL試題分析：根據(jù)上述判斷方法，我們列出選項(xiàng)B(分解成三個(gè)關(guān)系模式R1(HIL)、R2(IKL)、R3(IJL) )的初始表如表3所示：表3 選項(xiàng)B的初始表 HI