數(shù)據(jù)庫,模式的分解,無損連接性,教案-文檔資料

1、13.9 3.9 （關(guān)系）（關(guān)系）模式的分解模式的分解分解的定義分解的定義： 關(guān)系模式關(guān)系模式RURF的一個分解是指的一個分解是指 RR1 1U ，R R2 2U ，R Rn nU 其中其中U UU U1 1UU2 2UUn n ，并且不存在，并且不存在U Ui i U Uj j,1i,jn,1i,jn，F(xiàn) Fi i是是F F在在U Ui i上的投影。上的投影。 函數(shù)依賴集合函數(shù)依賴集合XY| XY FXY| XY FXYXY U Ui i 的的一個覆蓋一個覆蓋( (等價等價)F)Fi i叫做叫做F F在屬性在屬性U Ui i上的投影。上的投影。23.9 3.9 模式的分解模式的分解3.9.1

2、 3.9.1 關(guān)系模式分解的標(biāo)準(zhǔn)關(guān)系模式分解的標(biāo)準(zhǔn) 把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的式的方法并不是唯一的 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義分解方法才有意義 “ “等價等價”概念的三種定義：概念的三種定義：（1 1）分解具有無損連接性。）分解具有無損連接性。（2 2）分解要保持函數(shù)依賴性。）分解要保持函數(shù)依賴性。（3 3）分解既要保持函數(shù)依賴，又要具有無損連接性。）分解既要保持函數(shù)依賴，又要具有無損連接性。33.9.2 3.9.2 無損分解無損分

3、解 無損分解無損分解定義：關(guān)系模式定義：關(guān)系模式RR的一個分解的一個分解 = R= R1 1U ，R R2 2U ， ，R Rn nU，對于，對于R R的任的任一關(guān)系一關(guān)系r r，都有，都有r r為其在各為其在各U Ui i(1=1,n)(1=1,n)上的投影的上的投影的( (自然自然) )連接連接, ,即即r=r=U1U1(r) (r) U2U2(r) (r) UnUn(r)(r)，則稱，則稱關(guān)系關(guān)系模式模式R R的這個分解的這個分解具有無損連接性具有無損連接性（Lossless joinLossless join）。）。 具有無損連接性的分解保證不丟失信息。具有無損連接性的分解保證不丟失信

4、息。 無損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、無損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題。數(shù)據(jù)冗余等問題。43.9.2 3.9.2 無損分解（續(xù)）無損分解（續(xù)） 例：例：S-LS-L（SnoSno， SdeptSdept， SlocSloc） F= SnoF= SnoSdept,SdeptSloc,SnoSdept,SdeptSloc,SnoSloc Sloc S-L2NFS-L2NF，分解方法可以有多種：，分解方法可以有多種： 1. S-L1. S-L分解為三個關(guān)系模式：分解為三個關(guān)系模式： SN(SN(SnoSno) ) ，SD(SD(SdeptSdep

5、t) )，SL(SL(SlocSloc) ) 2. SL 2. SL分解為下面二個關(guān)系模式：分解為下面二個關(guān)系模式： NL(NL(SnoSno, Sloc), Sloc)， DL(DL(SdeptSdept, Sloc) , Sloc) 3. 3. 將將SLSL分解為下面二個關(guān)系模式：分解為下面二個關(guān)系模式： ND(ND(SnoSno, Sdept) , Sdept) ，NL(NL(SnoSno, Sloc), Sloc)53.9.2 3.9.2 無損分解（續(xù)）無損分解（續(xù)）第第3 3種分解方法具有無損連接性。種分解方法具有無損連接性。 問題問題: :（1 1）沒有保持原關(guān)系中的函數(shù)依賴，即）

6、沒有保持原關(guān)系中的函數(shù)依賴，即S-LS-L中的函數(shù)依賴中的函數(shù)依賴SdeptSlocSdeptSloc沒有投影到關(guān)系模沒有投影到關(guān)系模式式NDND、NLNL上。上。（2 2）存在冗余和操作異常。）存在冗余和操作異常。 63.9.2 3.9.2 無損分解（續(xù)）無損分解（續(xù)）4. 將將SLSL分解為下面二個關(guān)系模式：分解為下面二個關(guān)系模式： ND(ND(SnoSno, Sdept) , Sdept) ， DL(DL(SdeptSdept, Sloc) , Sloc) 該分解保持了函數(shù)依賴該分解保持了函數(shù)依賴( (且具有無損連接性且具有無損連接性) )。73.9.3 3.9.3 保持函數(shù)依賴的模式分

7、解保持函數(shù)依賴的模式分解 定義：設(shè)關(guān)系模式定義：設(shè)關(guān)系模式RR被分解為若干個關(guān)系模被分解為若干個關(guān)系模式式 R R1 1U ，R R2 2U ，R Rn nU 其中其中U=UU=U1 1UU2 2UUn n，且不存在，且不存在U Ui i U Uj j，F(xiàn) Fi i為為F F在在U Ui i上上的投影），若的投影），若F F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到的某個關(guān)系模式中的函數(shù)依賴解得到的某個關(guān)系模式中的函數(shù)依賴F Fi i所邏輯蘊(yùn)含，所邏輯蘊(yùn)含，則稱則稱關(guān)系模式關(guān)系模式R R的這個分解是保持函數(shù)依賴的的這個分解是保持函數(shù)依賴的（Preserve depend

8、encyPreserve dependency）。）。 83.9.3 3.9.3 保持函數(shù)依賴的模式分解保持函數(shù)依賴的模式分解（續(xù)）（續(xù)） 例如，將例如，將S SL L（SnoSno， SdeptSdept， SlocSloc） F= SnoF= SnoSdept,SdeptSloc,SnoSdept,SdeptSloc,SnoSlocSloc 分解為下面二個關(guān)系模式分解為下面二個關(guān)系模式( (第四種分解第四種分解) )： ND(ND(SnoSno, Sdept) , Sdept) ， DL(DL(SdeptSdept, Sloc) , Sloc) 該分解保持了函數(shù)依賴該分解保持了函數(shù)依賴(

9、(具有無損連接性具有無損連接性) )。93.9.3 3.9.3 保持函數(shù)依賴的模式分解保持函數(shù)依賴的模式分解( (續(xù)續(xù)) ) 如果一個分解具有無損連接性，則它能夠保證不如果一個分解具有無損連接性，則它能夠保證不丟失信息。丟失信息。 如果一個分解保持了函數(shù)依賴，則它可以減輕或如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。解決各種異常情況。 分解具有無損連接性和分解保持函數(shù)依賴是兩個分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨(dú)立的標(biāo)準(zhǔn)。具有無損連接性的分解不一定互相獨(dú)立的標(biāo)準(zhǔn)。具有無損連接性的分解不一定能夠保持函數(shù)依賴；同樣，保持函數(shù)依賴的分解能夠保持函數(shù)依賴；同樣，保持函數(shù)依賴

10、的分解也不一定具有無損連接性。也不一定具有無損連接性。103.9.3 3.9.3 保持函數(shù)依賴的模式分解保持函數(shù)依賴的模式分解( (續(xù)續(xù)) ) 對于關(guān)系模式對于關(guān)系模式S-LS-L： 第第1 1種分解方法既種分解方法既不具有不具有無損連接性，也無損連接性，也未保持未保持函函數(shù)依賴。數(shù)依賴。 第第2 2種分解方法種分解方法未保持未保持函數(shù)依賴，也函數(shù)依賴，也不具有不具有無損連無損連接性。接性。 第第3 3種分解方法種分解方法具有具有無損連接性，但無損連接性，但未保持未保持函數(shù)依函數(shù)依賴。賴。 第第4 4種分解方法既種分解方法既具有具有無損連接性，又無損連接性，又保持保持了函數(shù)了函數(shù)依賴。依賴。1

11、13.9.4 3.9.4 模式分解算法模式分解算法 算法算法1 1 判別一個判別一個二元二元分解的無損連接性分解的無損連接性 算法算法2 2 判別一個分解的無損連接性判別一個分解的無損連接性 算法算法3 3（合成法）轉(zhuǎn)換為（合成法）轉(zhuǎn)換為3NF3NF的保持函數(shù)依賴的分的保持函數(shù)依賴的分解。解。 算法算法4 4 轉(zhuǎn)換為轉(zhuǎn)換為3NF3NF既有無損連接性又保持函數(shù)依既有無損連接性又保持函數(shù)依賴的分解賴的分解 。 算法算法5 5 （分解法）轉(zhuǎn)換為（分解法）轉(zhuǎn)換為BCNFBCNF的無損連接分解的無損連接分解 算法算法6 6 達(dá)到達(dá)到4NF4NF的具有無損連接性的分解。的具有無損連接性的分解。12 算法算

12、法1 1 判別一個判別一個二元分解二元分解的無損連接性。的無損連接性。若若F F中至少存在如下函數(shù)依賴中的中至少存在如下函數(shù)依賴中的一個一個：（1 1）（）（U U1 1UU2 2）UU1 1U U2 2（2 2）（）（U U1 1UU2 2）UU2 2U U1 1 則則= R= R1 1U ，R R2 2U是是R R的無損分解。反之也的無損分解。反之也 成立。成立。 如：模式如：模式S-LS-L（SnoSno， SdeptSdept， SlocSloc） 分解為分解為2 2個模式：個模式： ND(ND(SnoSno, Sdept) , Sdept) ，NL(NL(SnoSno, Sloc),

13、 Sloc) 則是無損分解。則是無損分解。 3.9.4 3.9.4 模式分解算法模式分解算法13算法算法2 2 判別一個判別一個分解分解的無損連接性的無損連接性 設(shè)設(shè)RR1 1U ，R R2 2U ，R Rk kU是是RURF的一個分解，的一個分解，U UAA1 1, A, An n 構(gòu)造一張構(gòu)造一張k k行行n n列的表格。每列對應(yīng)一個屬性列的表格。每列對應(yīng)一個屬性A Aj j，每行對應(yīng)一個模式每行對應(yīng)一個模式R Ri i。如果。如果A Aj j屬于屬于U Ui i，那么在表格，那么在表格的第的第i i行第行第j j列處填上符號列處填上符號a aj j，否則填上，否則填上b bijij。14

14、算法算法2 2 判別一個判別一個分解分解的無損連接性的無損連接性逐一檢查逐一檢查F F中的中的每個函數(shù)依賴每個函數(shù)依賴，并修改元素，方法，并修改元素，方法是：取是：取F F中一函數(shù)依賴中一函數(shù)依賴X XY Y，找出，找出X X所對應(yīng)的列中具所對應(yīng)的列中具有相同符號的行，考察這些行中有相同符號的行，考察這些行中Y Y列的元素，若其列的元素，若其中有中有a aj j，則全部改為，則全部改為a aj j，否則全部改，否則全部改b bmjmj，其中，其中m m是是這些行的行號最小值。這些行的行號最小值。 若在某次更改后，有一行是若在某次更改后，有一行是a a1 1a a2 2aan n，那么，那么相對

15、相對于于F F是無損分解，算法結(jié)束。是無損分解，算法結(jié)束。 對對F F中的每個函數(shù)依賴進(jìn)行一次上述的處置，稱對中的每個函數(shù)依賴進(jìn)行一次上述的處置，稱對F F的一次掃描。的一次掃描。15算法算法2 2 判別一個判別一個分解分解的無損連接性的無損連接性比較掃描前后，表有無變化。如有變化，比較掃描前后，表有無變化。如有變化，則返回第則返回第步處理，否則，算法結(jié)束，則步處理，否則，算法結(jié)束，則相對于相對于F F是有損分解。是有損分解。 如果發(fā)生循環(huán)，那么前次掃描至少應(yīng)使該如果發(fā)生循環(huán)，那么前次掃描至少應(yīng)使該表減少一個符號，表中符號有限，因此循表減少一個符號，表中符號有限，因此循環(huán)必然會終止。環(huán)必然會終

16、止。16算法算法2 2 判別一個分解的無損連接性判別一個分解的無損連接性 例例1 1，設(shè)關(guān)系模式，設(shè)關(guān)系模式R(ABCDE)R(ABCDE)， F=ABCF=ABC，CDCD，DEDE， R R分解成分解成 =R R1 1( (ABC), ABC), R R2 2(CD),(CD),R R3 3(DE)(DE)。 那么那么相對于相對于F F是否無損分解？是否無損分解？17算法算法2 2 判別一個分解的無損連接性判別一個分解的無損連接性R1(ABC), R2(CD),R3(DE) F=ABC，CD，DEA AB BC CD DE Ea1a1a2a2a3a3b14b14b15b15b21b21b2

17、2b22a3a3a4a4b25b25b31b31b32b32b33b33a4a4a5a5A AB BC CD DE Ea1a1a2a2a3a3a4a4a5a5b21b21b22b22a3a3a4a4a5a5b31b31b32b32b33b33a4a4a5a5初始表：初始表：最后結(jié)果：最后結(jié)果：R1R1R2R2R3R3R1R1R2R2R3R31 12 22 2相對于相對于F F是無損分解是無損分解18算法算法2 2 判別一個分解的無損連接性判別一個分解的無損連接性 例例2 2，R(AR(A，B B，C)C)， F= AF= AB B，C CBB分解分解1 1=R=R1 1(A,B)(A,B)，R

18、 R2 2(A,C)(A,C)分解分解2 2=R=R1 1(A,B)(A,B)，R R1 1(B,C)(B,C) 分析兩種分解的無損連接性？分析兩種分解的無損連接性？分解分解1 1只具有無損連接性只具有無損連接性, , 分解分解2 2不具有無損連不具有無損連接性。接性。A AB BC Ca1a1a2a2a1a1a2a2a3a3ABABACACA AB BC Ca1a1a2a2a2a2a3a3ABABBCBC19算法算法2 2 判別一個分解的無損連接性判別一個分解的無損連接性例例3 3，設(shè)關(guān)系模式，設(shè)關(guān)系模式R(ABCD)R(ABCD)，R R分解成分解成 =R R1 1( (AB), AB),

19、 R R2 2(BC),(BC),R R3 3(CD)(CD)。 如果如果R R上成立的函數(shù)依賴集上成立的函數(shù)依賴集 F=ABF=AB，CDCD， 那么那么相對于相對于F F是否無損分解？是否無損分解？20算法算法2 2 判別一個分解的無損連接性判別一個分解的無損連接性 F=AB，CDA AB BC CD DABABa a1 1a a2 2b b1313b b1414 BCBCb b2121a a2 2a a3 3b b2424 CDCDb b3131b b3232a a3 3a a4 4 是是有損分解有損分解A AB BC CD DABABa a1 1a a2 2b b1313b b1414

20、 BCBCb b2121a a2 2a a3 3a a4 4 CDCDb b3131b b3232a a3 3a a4 4 213.9.4 3.9.4 模式分解算法模式分解算法算法算法3 3（合成法）轉(zhuǎn)換為（合成法）轉(zhuǎn)換為3NF3NF的保持函數(shù)依賴的分解。的保持函數(shù)依賴的分解。（1 1）對關(guān)系模式）對關(guān)系模式R R中的函數(shù)依賴集中的函數(shù)依賴集F F進(jìn)行進(jìn)行“極小化極小化”處理，處理后的函數(shù)依賴集仍記為處理，處理后的函數(shù)依賴集仍記為F F；（2 2）若有）若有XAXA F F，且，且XA=UXA=U，則，則=R=R，算法終止；，算法終止；（3 3）找出不在）找出不在F F中出現(xiàn)的屬性，中出現(xiàn)的屬

21、性，將它們構(gòu)成一個關(guān)系將它們構(gòu)成一個關(guān)系模式模式，并把這些屬性從，并把這些屬性從R R中去掉，把剩余的屬性仍中去掉，把剩余的屬性仍記為記為U U。22算法算法3 3 轉(zhuǎn)換為轉(zhuǎn)換為3NF3NF的保持函數(shù)依賴的分解的保持函數(shù)依賴的分解（4 4）對）對F F按具有相同左部的原則分組按具有相同左部的原則分組( (假定分為假定分為k k組組) )，每一組函數(shù)依賴每一組函數(shù)依賴F Fi i所涉及的全部屬性形成一個屬性所涉及的全部屬性形成一個屬性集集U Ui i。若。若U Ui i U Uj j(ij)(ij)，就去掉，就去掉U Ui i。于是。于是=R=R1 1U ，R R2 2U ，R Rk kU 構(gòu)構(gòu)

22、成成RURF的一個保持函數(shù)依賴的分解，并且每個的一個保持函數(shù)依賴的分解，并且每個R Ri i(U(Ui i,F,Fi i) )均屬于均屬于3NF3NF且保持函數(shù)依賴。且保持函數(shù)依賴。233.9.4 3.9.4 模式分解算法模式分解算法例，設(shè)例，設(shè)R R（A,B,C,D,EA,B,C,D,E），），F(xiàn) Fminmin= AB= AB，CDCD。則，則， RR1 1（A,B)A,B)，R R2 2（C,DC,D）,R,R3 3（E E） 是保持函數(shù)依賴的分解。是保持函數(shù)依賴的分解。24算法算法4 4 轉(zhuǎn)換為轉(zhuǎn)換為3NF3NF既有無損連接性又保持函數(shù)依賴既有無損連接性又保持函數(shù)依賴的分解的分解 。

23、（1 1）對關(guān)系模式）對關(guān)系模式R R中的函數(shù)依賴集中的函數(shù)依賴集F F進(jìn)行進(jìn)行“極小極小化化”處理，然后把最小依賴集中那些左部相同的處理，然后把最小依賴集中那些左部相同的FDFD用合并性合并起來，處理后的函數(shù)依賴集仍記用合并性合并起來，處理后的函數(shù)依賴集仍記為為F F；（2 2）對）對F F中的每個一函數(shù)依賴中的每個一函數(shù)依賴XYXY，構(gòu)成一個關(guān)系，構(gòu)成一個關(guān)系模式模式R Ri i(X,Y)(X,Y)，R Ri i為為3NF,3NF,RR1 1,R,R2 2,R,Rn n （3 3）如果每個）如果每個R Ri i不包含不包含R R的候選鍵，那么把候選鍵的候選鍵，那么把候選鍵作為一個模式放入作

24、為一個模式放入中。中。 即為所求。即為所求。3.9.4 3.9.4 模式分解算法模式分解算法25 例，設(shè)有關(guān)系例，設(shè)有關(guān)系R(F,G,R(F,G,H H,I,I,J J) )，F(xiàn)D=FI,I,J JI,IG,GI,IG,GH HI,II,IH HFF，將分解為，將分解為3NF,3NF,并具有無損連接性和保持依賴性。并具有無損連接性和保持依賴性。 解：解：HJHJ是是L L類屬性，所以候選鍵至少包含類屬性，所以候選鍵至少包含HJHJ，另，另外，外，( (HJHJ) ) FGHIJFGHIJ，所以，所以HJHJ是唯一的候選鍵。是唯一的候選鍵。 （1 1）求出最小依賴集）求出最小依賴集 F Fmin

25、min=F=FI,JI,IG,GHI,IHF=F=FI,JI,IG,GHI,IHF3.9.4 3.9.4 模式分解算法模式分解算法26 (2) (2) 將關(guān)系分解為：將關(guān)系分解為： R R1 1(FI),R(FI),R2 2(JI),R(JI),R3 3(IG),R(IG),R4 4(GHI),R(GHI),R5 5(IHF)(IHF) (3) (3) 并上候選鍵：并上候選鍵： RR1 1（FIFI）,R,R2 2(JI),R(JI),R3 3(IG),R(IG),R4 4(GHI),R(GHI),R5 5(IHF)(IHF)， R R6 6（HJHJ） 3.9.4 3.9.4 模式分解算法模

26、式分解算法273.9.4 3.9.4 模式分解算法模式分解算法 課后習(xí)題：課后習(xí)題： 已知，關(guān)系模式已知，關(guān)系模式R(A,B,C,D,E)R(A,B,C,D,E)，R R的最小依的最小依賴集賴集F Fminmin=AB=AB，CDCD。 試將試將R R分解為分解為3NF,3NF,并具有無損連接性和保持并具有無損連接性和保持函數(shù)依賴性。函數(shù)依賴性。283.9.4 3.9.4 模式分解算法模式分解算法算法算法5 5 轉(zhuǎn)換為轉(zhuǎn)換為BCNFBCNF的無損連接分解。的無損連接分解。(1)(1)關(guān)系模式關(guān)系模式R R的分解的分解，初始時，初始時=R=R。(2)(2)檢查檢查中各關(guān)系模式是否均屬于中各關(guān)系模

27、式是否均屬于BCNFBCNF。若是，則。若是，則 算法終止。算法終止。(3)(3)設(shè)設(shè)中中R Ri iU 不屬于不屬于BCNFBCNF，那么必有，那么必有XAXA F Fi i ( ( A A X)X)，且且X X非非R Ri i的超碼。對的超碼。對R Ri i進(jìn)行分解：進(jìn)行分解： SS1 1,S,S2 2 ，U US1S1XAXA，U US2S2U Ui iAA，以，以代替代替 R Ri iU 返回第返回第(2)(2)步。步。 由于由于U U中屬性有限，因而有限次循環(huán)后算法中屬性有限，因而有限次循環(huán)后算法5 5一定一定 會終止。會終止。 29算法算法5 5 轉(zhuǎn)換為轉(zhuǎn)換為BCNFBCNF的無損

28、連接分解的無損連接分解。 這是一個自項(xiàng)向下的算法。它自然地形成一棵對這是一個自項(xiàng)向下的算法。它自然地形成一棵對RR的二又分解樹。的二又分解樹。RR的分解樹不一定是的分解樹不一定是唯一的。這與步驟唯一的。這與步驟(3)(3)中具體選定的中具體選定的XAXA有關(guān)。有關(guān)。30算法算法5 5 轉(zhuǎn)換為轉(zhuǎn)換為BCNFBCNF的無損連接分解。的無損連接分解。 例，例， 設(shè)關(guān)系模式設(shè)關(guān)系模式W(CTHRSG)W(CTHRSG)的屬性分別表示課程的屬性分別表示課程名、任課教師名、上課時間、上課教室、選修的名、任課教師名、上課時間、上課教室、選修的學(xué)生學(xué)號、成績等含義。學(xué)生學(xué)號、成績等含義。W W上的函數(shù)依賴集上

29、的函數(shù)依賴集F F： C TC T，HR CHR C，THRTHR，CS GCS G，HS RHS R 顯然，模式顯然，模式W W上只有一個鍵，是上只有一個鍵，是HSHS。 解：要把解：要把W W分解成分解成BCNFBCNF模式集，可以首先考慮模式集，可以首先考慮CS CS G G，據(jù)算法，應(yīng)把，據(jù)算法，應(yīng)把CTHRSGCTHRSG分解成分解成CSGCSG和和CTHRSCTHRS。為進(jìn)一步分解，計(jì)算出為進(jìn)一步分解，計(jì)算出CSGCSG (F) (F)CS G CS G ， CTHRSCTHRS (F) (F) C TC T，HR CHR C，TH RTH R，HS HS R R。模式。模式CTH

30、RSCTHRS的鍵是的鍵是HSHS。 31算法算法5 5 轉(zhuǎn)換為轉(zhuǎn)換為BCNFBCNF的無損連接分解。的無損連接分解。 顯然顯然CSGCSG已是已是BCNFBCNF，而，而CTHRSCTHRS必須進(jìn)一步分必須進(jìn)一步分解。如考慮解。如考慮CTCT，則把，則把CTHRSCTHRS分解成分解成CTCT和和CHRSCHRS， CTCT (F) (F) C TC T， CHRSCHRS (F) (F) CH RCH R，HS RHS R，HR CHR C。HSHS是是CHRSCHRS的鍵。的鍵。 CHRSCHRS再分解一次，利用再分解一次，利用CHRCHR分解成分解成CHRCHR和和CHSCHS，2 2

31、模式均滿足模式均滿足BCNFBCNF。 分解結(jié)束。分解結(jié)束。32分解樹分解樹33算法算法5 5 轉(zhuǎn)換為轉(zhuǎn)換為BCNFBCNF的無損連接分解。的無損連接分解。 W W分解成分解成CSGCSG，CTCT，CHRCHR，CHSCHS，其中，其中四個關(guān)系模式分別描述：四個關(guān)系模式分別描述： 學(xué)生的各門課程成績學(xué)生的各門課程成績(CSG)(CSG) 每門課程的任課教師每門課程的任課教師(CT)(CT) 每門課程的上課時間和教室每門課程的上課時間和教室 (CHR)(CHR) 每個學(xué)生的上課時間表每個學(xué)生的上課時間表(CHS)(CHS) 是轉(zhuǎn)換為是轉(zhuǎn)換為BCNFBCNF的無損連接分解，但分解的無損連接分解，

32、但分解中有一個問題，中有一個問題，THRTHR在分解時未能保持。在分解時未能保持。在在CTHRSCTHRS分解成分解成CTCT和和CHRSCHRS時，時， THRTHR丟失了。丟失了。343.9.4 3.9.4 模式分解算法模式分解算法算法算法6 6 達(dá)到達(dá)到4NF4NF的具有無損連接性的分解的具有無損連接性的分解 首先使用算法首先使用算法5 5得到得到R R的一個達(dá)到了的一個達(dá)到了BCNFBCNF的的無損連接分解無損連接分解。然后對某一。然后對某一R Ri iU ， 若不屬于若不屬于4NF4NF，則可按下述定理的作法進(jìn)行，則可按下述定理的作法進(jìn)行分解。直到每個關(guān)系模式均屬于分解。直到每個關(guān)系

33、模式均屬于4NF4NF為止。為止。定理定理 若若RR中中XY成立，則成立，則R R的分解的分解 =R=R1 1(X,Y),R(X,Y),R2 2(X,Z) (X,Z) 具有無損連接性。具有無損連接性。 其中其中Z ZU UX XY Y。35算法算法6 6 達(dá)到達(dá)到4NF4NF的具有無損連接性的的具有無損連接性的分解分解例，例，TEACHING(TEACHING(C C, ,T T, ,B B) )的碼是的碼是A1l_KeyA1l_Key。TEACHINGBCNFTEACHINGBCNF，但，但TEACHING4NFTEACHING4NF 將模式將模式TEACHINGTEACHING分解為：分解

34、為： CT(CT(C C, ,T T) )和和CB(CB(C C, ,B B) )，均滿足，均滿足4NF4NF36數(shù)據(jù)依賴的一個有效且完備的公理系統(tǒng)數(shù)據(jù)依賴的一個有效且完備的公理系統(tǒng) 關(guān)系模式關(guān)系模式RR，U U是屬性總體集，是屬性總體集，D D是是U U上的一上的一組數(shù)據(jù)依賴組數(shù)據(jù)依賴( (函數(shù)依賴和多值依賴函數(shù)依賴和多值依賴) )，對于包含函，對于包含函數(shù)依賴和多值依賴的數(shù)據(jù)依賴有數(shù)依賴和多值依賴的數(shù)據(jù)依賴有個有效且完備個有效且完備的公理系統(tǒng)。的公理系統(tǒng)。A1A1：若：若Y Y X X U U，則，則XYXY；A2A2：若：若XYXY為為F F所蘊(yùn)含，且所蘊(yùn)含，且Z Z U U，則，則XZYZXZYZ。A3A3：若：若XYXY，YZYZ，則，則XZXZ A4A4：若：若XYXY ，V V W W U U，則，則XW XW YV YVA5A5：若：若XYXY ，則，則XUXUX XY Y A