數(shù)據(jù)庫課程設(shè)計之無損連接性-文庫吧
2025-01-03 15:47 本頁面
【正文】 200。…200。Uk=U，則稱 r 是R(U,F)的一個分解(Deposition)。分解有兩個準(zhǔn)則，無損連接性和函數(shù)依賴的保持性。無損連接性的定義為設(shè)關(guān)系模式R(U,F)， r={R1，R2，…，Rk}是分解R所得的一組關(guān)系模式，對于R的滿足F的任一個關(guān)系實(shí)例r，都有：成立。即r等于它在Ri上投影的自然連接，則稱此分解為滿足F的具有無損連接性的分解。：設(shè)關(guān)系模式R(U,F)， r={R1，R2}是R的一個分解，當(dāng)且僅當(dāng)U1199。U2174。U1U2或 U1199。U2174。U2U1206。F+時，則分解r具有無損連接性。 {判斷分解r的無損連接性}輸入：R(U,F)，U=A1A2…An 。 r={R1，R2，…，Rk}輸出：如果r具有無損連接性，輸出True，否則輸出False。 (1) 構(gòu)造一個n列k行的二維表T。若Aj 206。Ri，則Tij=aj；否則Tij=bij。 (2) flag:=True。 Do While Flag Flag:=False。 For 每一個X174。Y206。F Do For T中的任意兩行tj，tm Do If tj[X]=tm[X] And tj[Y]185。tm[Y] Then EQUAY(tj，tm)；Flag:=True； (3) For T的每一行t Do If t=a1a2…an Then Return(True)； Return(False).，可以得出判斷關(guān)系模式的分解是否保持無損連接性的充分必要條件是U1199。U2174。U1U2或 U1199。U2174。U2U1206。F+時，則分解r具有無損連接性。 所以問題轉(zhuǎn)變成為集合的并差問題，就可以編寫程序來實(shí)現(xiàn)這一功能了。當(dāng)然，關(guān)系模式分解的另一個準(zhǔn)則是函數(shù)依賴的保持性，這兩個準(zhǔn)則雖然沒有什么直接的關(guān)系，卻決定了一個關(guān)系模式可以達(dá)到哪一個范式，不能單一的進(jìn)行討論，都需要進(jìn)行分析，現(xiàn)在，為簡便起見，我們只討論一個關(guān)系模式的分解是否保持著無損連接性，暫時不討論其函數(shù)依賴的保持性 ，利用表格法進(jìn)行判斷，以下是表格法的詳細(xì)步驟。算法：ρ={R1U1,F1,R2U2,F2,...,RkUk,Fk}是關(guān)系模式RU,F的一個分解，U={A1,A2,...,An}，F(xiàn)={FD1,FD2,...,FDp}，并設(shè)F是一個最小依賴集，記FDi為Xi→Alj，其步驟如下：①建立一張n列k行的表，每一列對應(yīng)一個屬性，每一行對應(yīng)分解中的一個關(guān)系模式。若屬性AjUi，則在j列i行上真上aj，否則填上bij；②對于每一個FDi做如下操作：找到Xi所對應(yīng)的列中具有相同符號的那些行?？疾爝@些行中l(wèi)i列的元素，若其中有aj，則全部改為aj，否則全部改為bmli，m是這些行的行號最小值。如果在某次更改后，有一行成為：a1,a2,...,an，則算法終止。且分解ρ具有無損連接性，否則不具有無損連接性。對F中p個FD逐一進(jìn)行一次這樣的處理，稱為對F的一次掃描。③比較掃描前后，表有無變化，如有變化，則返回第步，否則算法終止。如果發(fā)生循環(huán)，那么前次掃描至少應(yīng)使該表減少一個符號，表中符號有限，因此，循環(huán)必然終止。舉例1：已知RU,F，U={A,B,C}，F(xiàn)={A→B}，如下的兩個分解：①ρ1={AB,BC}②ρ2={AB,AC}判斷這兩個分解是否具有無損連接性。用無損連接的定理來解。方法一：因為AB∩BC=B，ABBC=A，BCAB=C所以B→AF+，B→CF+故ρ1是有損連接。方法二：因為AB∩AC=A，ABAC=B，ACAB=C所以A→BF+，A→CF+故ρ2是無損連接。下面舉個例子來說明表格法【例】已知RU,F，U={A,B,C,D,E}，F(xiàn)={A→C,B→C,C→D,DE→C,CE→A}，R的一個分解為R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判斷這個分解是否具有無損連接性。解：用判斷無損連接的算法來解。① 構(gòu)造一個初始的二維表，若“屬性”屬于“模式”中的屬性，則填aj，否則填bij。見表1. 表1.② 根據(jù)A→C，對上表進(jìn)行處理，由于屬性列A上第5行相同均為a1，所以將屬性列C上的b1b2b53改為同一個符號b13（取行號最小值）。 表2③ 根據(jù)B→C，對上表進(jìn)行處理，由于屬性列B上第3行相同均為a2，所以將屬性列C上的b1b33改為同一個符號b13（取行號最小值）。 表4.④ 根據(jù)C→D，對上表進(jìn)行處理，由于屬性列C上第5行相同均為b13，所以將屬性列D上的值均改為同一個符號a4。表5.⑤根據(jù)DE→C，對上表進(jìn)行處理，由于屬性列DE上第5行相同均為a4a5，所以將屬性列C上的值均改為同一個符號a3。 表7⑤ 根據(jù)CE→A，對上表進(jìn)行處理，由于屬性列CE上第5行相同均為a3a5，所以將屬性列A上的值均改為同一個符號a1。 表7⑦通過上述的修改，使第三行成為a1a2a3a4a5，則算法終止。且分解具有無損連接性。（2000）要使本程序正確運(yùn)行下去，需要解決的問題很多，下面，舉個例子，來演示本
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1