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

3.9（關系）模式的分解分解的定義：關系模式R<U，F(xiàn)>的一個分解是指ρ＝{R1<U1，F(xiàn)1>，R2<U2，F(xiàn)2>，…，Rn<Un，F(xiàn)n>}其中U＝U1∪U2∪…∪Un

，并且不存在Ui

Uj,1≤i,j≤n，F(xiàn)i是F在Ui上的投影。函數(shù)依賴集合{X→Y|X→Y∈F＋∧XYUi}的一個覆蓋(等價)Fi叫做F在屬性Ui上的投影。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9

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

無損分解定義：關系模式R<U,F>的一個分解ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}，對于R的任一關系r，都有r為其在各Ui(1=1,…,n)上的投影的(自然)連接,即r=πU1(r)?πU2(r)?…?πUn(r)，則稱關系模式R的這個分解ρ具有無損連接性（Losslessjoin）。具有無損連接性的分解保證不丟失信息。無損連接性不一定能解決插入異常、刪除異常、修改復雜、數(shù)據(jù)冗余等問題。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.2無損分解（續(xù)）例：S-L（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}S-L∈2NF，分解方法可以有多種：1.S-L分解為三個關系模式：SN(Sno)，SD(Sdept)，SL(Sloc)2.SL分解為下面二個關系模式：NL(Sno,Sloc)， DL(Sdept,Sloc)3.將SL分解為下面二個關系模式： ND(Sno,Sdept)，NL(Sno,Sloc)數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.2無損分解（續(xù)）第3種分解方法具有無損連接性。問題:（1）沒有保持原關系中的函數(shù)依賴，即S-L中的函數(shù)依賴Sdept→Sloc沒有投影到關系模式ND、NL上。（2）存在冗余和操作異常。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.2無損分解（續(xù)）4.將SL分解為下面二個關系模式：

ND(Sno,Sdept)，DL(Sdept,Sloc)該分解保持了函數(shù)依賴(且具有無損連接性)。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.3保持函數(shù)依賴的模式分解定義：設關系模式R<U,F>被分解為若干個關系模式R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>其中U=U1∪U2∪…∪Un，且不存在Ui

Uj，F(xiàn)i為F在Ui上的投影），若F所邏輯蘊含的函數(shù)依賴一定也由分解得到的某個關系模式中的函數(shù)依賴Fi所邏輯蘊含，則稱關系模式R的這個分解是保持函數(shù)依賴的（Preservedependency）。

數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.3保持函數(shù)依賴的模式分解（續(xù)）例如，將S－L（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}分解為下面二個關系模式(第四種分解)：ND(Sno,Sdept)，DL(Sdept,Sloc)該分解保持了函數(shù)依賴(具有無損連接性)。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.3保持函數(shù)依賴的模式分解(續(xù))如果一個分解具有無損連接性，則它能夠保證不丟失信息。如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨立的標準。具有無損連接性的分解不一定能夠保持函數(shù)依賴；同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.3保持函數(shù)依賴的模式分解(續(xù))對于關系模式S-L：第1種分解方法既不具有無損連接性，也未保持函數(shù)依賴。第2種分解方法未保持函數(shù)依賴，也不具有無損連接性。第3種分解方法具有無損連接性，但未保持函數(shù)依賴。第4種分解方法既具有無損連接性，又保持了函數(shù)依賴。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.4模式分解算法算法1判別一個二元分解的無損連接性算法2判別一個分解的無損連接性算法3（合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解。算法4轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解。算法5（分解法）轉(zhuǎn)換為BCNF的無損連接分解算法6達到4NF的具有無損連接性的分解。數(shù)據(jù)庫,模式的分解,無損連接性,教案算法1判別一個二元分解的無損連接性。若F＋中至少存在如下函數(shù)依賴中的一個：（1）（U1∩U2）→U1－U2（2）（U1∩U2）→U2－U1則ρ={R1<U1>，R2<U2>}是R的無損分解。反之也成立。如：模式S-L（Sno，Sdept，Sloc）分解為2個模式： ND(Sno,Sdept)，NL(Sno,Sloc)

則是無損分解。3.9.4模式分解算法數(shù)據(jù)庫,模式的分解,無損連接性,教案算法2判別一個分解的無損連接性

設ρ＝{R1<U1，F(xiàn)1>，R2<U2，F(xiàn)2>，…，Rk<Uk，F(xiàn)k>}是R<U，F(xiàn)>的一個分解，U＝{A1,…,An}①構(gòu)造一張k行n列的表格。每列對應一個屬性Aj，每行對應一個模式Ri。如果Aj屬于Ui，那么在表格的第i行第j列處填上符號aj，否則填上bij。數(shù)據(jù)庫,模式的分解,無損連接性,教案算法2判別一個分解的無損連接性②逐一檢查F中的每個函數(shù)依賴，并修改元素，方法是：取F中一函數(shù)依賴X→Y，找出X所對應的列中具有相同符號的行，考察這些行中Y列的元素，若其中有aj，則全部改為aj，否則全部改bmj，其中m是這些行的行號最小值。若在某次更改后，有一行是a1a2…an，那么ρ相對于F是無損分解，算法結(jié)束。對F中的每個函數(shù)依賴進行一次上述的處置，稱對F的一次掃描。數(shù)據(jù)庫,模式的分解,無損連接性,教案算法2判別一個分解的無損連接性③比較掃描前后，表有無變化。如有變化，則返回第②步處理，否則，算法結(jié)束，則ρ相對于F是有損分解。如果發(fā)生循環(huán)，那么前次掃描至少應使該表減少一個符號，表中符號有限，因此循環(huán)必然會終止。數(shù)據(jù)庫,模式的分解,無損連接性,教案算法2判別一個分解的無損連接性例1，設關系模式R(ABCDE)，F(xiàn)={AB→C，C→D，D→E}，R分解成ρ={R1(ABC),R2(CD),R3(DE)}。那么ρ相對于F是否無損分解？數(shù)據(jù)庫,模式的分解,無損連接性,教案算法2判別一個分解的無損連接性

R1(ABC),R2(CD),R3(DE)

F={AB→C，C→D，D→E}ABCDEa1a2a3b14b15b21b22a3a4b25b31b32b33a4a5ABCDEa1a2a3a4a5b21b22a3a4a5b31b32b33a4a5初始表：最后結(jié)果：R1R2R3R1R2R3122ρ相對于F是無損分解數(shù)據(jù)庫,模式的分解,無損連接性,教案算法2判別一個分解的無損連接性例2，R(A，B，C)，F(xiàn)={AB，CB}分解ρ1={R1(A,B)，R2(A,C)}分解ρ2={R1(A,B)，R1(B,C)}分析兩種分解的無損連接性？分解1只具有無損連接性,分解2不具有無損連接性。ABCa1a2a1a2a3ABACABCa1a2a2a3ABBC數(shù)據(jù)庫,模式的分解,無損連接性,教案算法2判別一個分解的無損連接性例3，設關系模式R(ABCD)，R分解成ρ={R1(AB),R2(BC),R3(CD)}。如果R上成立的函數(shù)依賴集F={A→B，C→D}，那么ρ相對于F是否無損分解？數(shù)據(jù)庫,模式的分解,無損連接性,教案算法2判別一個分解的無損連接性

F={A→B，C→D}ABCDABa1a2b13b14

BCb21a2a3b24

CDb31b32a3a4

ρ是有損分解ABCDABa1a2b13b14

BCb21a2a3a4

CDb31b32a3a4

數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.4模式分解算法算法3（合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解。（1）對關系模式R中的函數(shù)依賴集F進行“極小化”處理，處理后的函數(shù)依賴集仍記為F；（2）若有X→AF，且XA=U，則ρ={R}，算法終止；（3）找出不在F中出現(xiàn)的屬性，將它們構(gòu)成一個關系模式，并把這些屬性從R中去掉，把剩余的屬性仍記為U。數(shù)據(jù)庫,模式的分解,無損連接性,教案算法3轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解（4）對F按具有相同左部的原則分組(假定分為k組)，每一組函數(shù)依賴Fi所涉及的全部屬性形成一個屬性集Ui。若Ui

Uj(i≠j)，就去掉Ui。于是ρ={R1<U1，F(xiàn)1>，R2<U2，F(xiàn)2>，…，Rk<Uk，F(xiàn)k>}構(gòu)成R<U，F(xiàn)>的一個保持函數(shù)依賴的分解，并且每個Ri(Ui,Fi)均屬于3NF且保持函數(shù)依賴。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.4模式分解算法例，設R（A,B,C,D,E），F(xiàn)min={A→B，C→D}。則，ρ＝{R1（A,B)，R2（C,D）,R3（E）}是保持函數(shù)依賴的分解。數(shù)據(jù)庫,模式的分解,無損連接性,教案算法4轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解。（1）對關系模式R中的函數(shù)依賴集F進行“極小化”處理，然后把最小依賴集中那些左部相同的FD用合并性合并起來，處理后的函數(shù)依賴集仍記為F；（2）對F中的每個一函數(shù)依賴X→Y，構(gòu)成一個關系模式Ri(X,Y)，Ri為3NF,ρ＝{R1,R2,…,Rn}（3）如果每個Ri不包含R的候選鍵，那么把候選鍵作為一個模式放入ρ中。ρ即為所求。3.9.4模式分解算法數(shù)據(jù)庫,模式的分解,無損連接性,教案例，設有關系R(F,G,H,I,J)，F(xiàn)D={F→I,J→I,I→G,GH→I,IH→F}，將分解為3NF,并具有無損連接性和保持依賴性。解：HJ是L類屬性，所以候選鍵至少包含HJ，另外，(HJ)＋

＝{FGHIJ}，所以HJ是唯一的候選鍵。（1）求出最小依賴集Fmin=F={F→I,J→I,I→G,GH→I,IH→F}3.9.4模式分解算法數(shù)據(jù)庫,模式的分解,無損連接性,教案(2)將關系分解為：ρ＝{R1(FI),R2(JI),R3(IG),R4(GHI),R5(IHF)}(3)ρ并上候選鍵：ρ＝{R1（FI）,R2(JI),R3(IG),R4(GHI),R5(IHF)，R6（HJ）}3.9.4模式分解算法數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.4模式分解算法

課后習題：已知，關系模式R(A,B,C,D,E)，R的最小依賴集Fmin={A→B，C→D}。試將R分解為3NF,并具有無損連接性和保持函數(shù)依賴性。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.4模式分解算法算法5轉(zhuǎn)換為BCNF的無損連接分解。(1)關系模式R的分解ρ，初始時ρ={R<U,F>}。(2)檢查ρ中各關系模式是否均屬于BCNF。若是，則算法終止。(3)設ρ中Ri<Ui,Fi>不屬于BCNF，那么必有X→AFi＋(AX)，且X非Ri的超碼。對Ri進行分解：σ＝{S1,S2}，US1＝XA，US2＝Ui－{A}，以σ代替Ri<Ui,Fi>返回第(2)步。由于U中屬性有限，因而有限次循環(huán)后算法5一定會終止。

數(shù)據(jù)庫,模式的分解,無損連接性,教案算法5轉(zhuǎn)換為BCNF的無損連接分解。

這是一個自項向下的算法。它自然地形成一棵對R<U,F>的二又分解樹。R<U,F>的分解樹不一定是唯一的。這與步驟(3)中具體選定的X→A有關。數(shù)據(jù)庫,模式的分解,無損連接性,教案算法5轉(zhuǎn)換為BCNF的無損連接分解。例，設關系模式W(CTHRSG)的屬性分別表示課程名、任課教師名、上課時間、上課教室、選修的學生學號、成績等含義。W上的函數(shù)依賴集F：{C→T，HR→C，TH→R，CS→G，HS→R}顯然，模式W上只有一個鍵，是HS。解：要把W分解成BCNF模式集，可以首先考慮CS→G，據(jù)算法，應把CTHRSG分解成CSG和CTHRS。為進一步分解，計算出πCSG(F)＝{CS→G}，πCTHRS(F)＝{C→T，HR→C，TH→R，HS→R}。模式CTHRS的鍵是HS。

數(shù)據(jù)庫,模式的分解,無損連接性,教案算法5轉(zhuǎn)換為BCNF的無損連接分解。顯然CSG已是BCNF，而CTHRS必須進一步分解。如考慮C→T，則把CTHRS分解成CT和CHRS，πCT(F)＝{C→T}，πCHRS(F)＝{CH→R，HS→R，HR→C}。HS是CHRS的鍵。CHRS再分解一次，利用CH→R分解成CHR和CHS，2模式均滿足BCNF。分解結(jié)束。數(shù)據(jù)庫,模式的分解,無損連接性,教案分解樹數(shù)據(jù)庫,模式的分解,無損連接性,教案算法5轉(zhuǎn)換為BCNF的無損連接分解。

W分解成ρ＝{CSG，CT，CHR，CHS}，其中四個關系模式分別描述：①學生的各門課程成績(CSG)②每門課程的任課教師(CT)③每門課程的上課時間和教室(CHR)④每個學生的上課時間表(CHS)ρ是轉(zhuǎn)換為BCNF的無損連接分解，但分解中有一個問題，TH→R在分解時未能保持。在CTHRS分解成CT和CHRS時，TH→R丟失了。數(shù)據(jù)庫,模式的分解,無損連接性,教案3.9.4模式分解算法算法6達到4NF的具有無損連接性的分解首先使用算法5得到R的一個達到了BCNF的無損連接分解ρ。然后對某一Ri<Ui,Di>，若不屬于4NF，則可按下述定理的作法進行分解。直到每個關系模式均屬于4NF為止。定理若R<U,D>中X→→Y成立，則R的分解ρ={R1(X,Y),R2(X,Z)}具有無損連接性。其中Z＝U－X－Y。數(shù)據(jù)庫,模式的分解,無損連接性,教案算法6達到4NF的具有無損連接性的分解例，TEACHING(C,T,B)的碼是A1l_Key。TEACHING∈BCNF，但TEACHING∈4NF將模式TEACHING分解為：CT(C,T)和CB(C,B)，均滿足4NF數(shù)據(jù)庫,模式的分解,無損連接性,教案數(shù)據(jù)依賴的一個有效且完備的公理系統(tǒng)關系模式R<U,D>，U是屬性總體集，D是U上的一組數(shù)據(jù)依賴(函數(shù)依賴和多值依賴)，對于包含函數(shù)依賴和多值依賴的數(shù)據(jù)依賴有—個有效且完備的公理系統(tǒng)。A1：若YXU，則X→Y；A2：若X→Y為F所蘊含，且ZU，則XZ→YZ。A3：若X→Y，Y→Z，則X→Z

A4：若X→→Y，VWU