數(shù)據(jù)庫 第六章 模式的分解(續(xù))

數(shù)據(jù)庫系統(tǒng)原理AnIntroductiontoDatabaseSystem第六章關(guān)系數(shù)據(jù)理論第六章關(guān)系數(shù)據(jù)理論6.1數(shù)據(jù)依賴6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解6.4模式的分解把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義模式的分解（續(xù)）定義6.16關(guān)系模式R<U,F>的一個分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=U1∪U2∪…∪Un，且不存在Ui

Uj，F(xiàn)i為F在Ui上的投影定義6.17函數(shù)依賴集合{X→Y|X→Y

F+∧XY

Ui}的一個覆蓋Fi

叫作F在屬性Ui上的投影m模式的分解（續(xù)）例:SL（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入異常、刪除異常、冗余度大和修改復雜等問題分解方法可以有多種模式的分解（續(xù)）SL──────────────────Sno Sdept Sloc──────────────────95001CSA95002ISB95003MAC95004ISB95005 PH B──────────────────模式的分解（續(xù)）1.SL分解為下面三個關(guān)系模式：SN(Sno)SD(Sdept)SO(Sloc)分解后的關(guān)系為：

SN──────SD──────SO──────SnoSdeptSloc

──────────────────95001CSA95002ISB95003MAC95004PH─────95005────────────模式的分解（續(xù)） 分解后的數(shù)據(jù)庫丟失了許多信息例如無法查詢95001學生所在系或所在宿舍。如果分解后的關(guān)系可以通過自然連接恢復為原來的關(guān)系，那么這種分解就沒有丟失信息模式的分解（續(xù)）2.SL分解為下面二個關(guān)系模式：NL(Sno,Sloc)DL(Sdept,Sloc)分解后的關(guān)系為：

NL────────────DL────────────SnoSlocSdeptSloc

────────────────────────95001A CSA95002B ISB95003C MAC95004B PHB95005B──────────────────────模式的分解（續(xù)）NLDL─────────────SnoSlocSdept─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH模式的分解（續(xù)） NLDL比原來的SL關(guān)系多了3個元組

無法知道95002、95004、95005究竟是哪個系的學生

元組增加了，信息丟失了第三種分解方法3.將SL分解為下面二個關(guān)系模式：

ND(Sno,Sdept)NL(Sno,Sloc)分解后的關(guān)系為：

模式的分解（續(xù)）ND────────────NL──────────SnoSdeptSnoSloc

──────────────────────95001CS95001A95002IS95002B95003MA95003C95004IS95004B95005PH95005B

───────────────────────模式的分解（續(xù)）NDNL──────────────SnoSdeptSloc──────────────

95001CSA95002ISB95003MAC95004CSA95005PHB──────────────與SL關(guān)系一樣，因此沒有丟失信息關(guān)系模式分解的標準三種模式分解的等價定義⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性具有無損連接性的模式分解關(guān)系模式R<U,F>的一個分解ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}若R與R1、R2、…、Rn自然連接的結(jié)果相等，則稱關(guān)系模式R的這個分解ρ具有無損連接性（Losslessjoin）具有無損連接性的分解保證不丟失信息無損連接性不一定能解決插入異常、刪除異常、修改復雜、數(shù)據(jù)冗余等問題模式的分解（續(xù)）

第三種分解方法具有無損連接性

問題:這種分解方法沒有保持原關(guān)系中的函數(shù)依賴SL中的函數(shù)依賴Sdept→Sloc沒有投影到關(guān)系模式ND、NL上保持函數(shù)依賴的模式分解設(shè)關(guān)系模式R<U,F>被分解為若干個關(guān)系模式R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>（其中U=U1∪U2∪…∪Un，且不存在UiUj，F(xiàn)i為F在Ui上的投影），若F所邏輯蘊含的函數(shù)依賴一定也由分解得到的某個關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊含，則稱關(guān)系模式R的這個分解是保持函數(shù)依賴的（Preservedependency）。第四種分解方法將SL分解為下面二個關(guān)系模式：ND(Sno,Sdept)DL(Sdept,Sloc)這種分解方法就保持了函數(shù)依賴。模式的分解（續(xù)）如果一個分解具有無損連接性，則它能夠保證不丟失信息。如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨立的標準。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。模式的分解（續(xù)）1.SL分解為下面三個關(guān)系模式：SN(Sno)SD(Sdept)SO(Sloc)2.SL分解為下面二個關(guān)系模式：NL(Sno,Sloc)DL(Sdept,Sloc)3.將SL分解為下面二個關(guān)系模式：ND(Sno,Sdept)NL(Sno,Sloc)4.將SL分解為下面二個關(guān)系模式：ND(Sno,Sdept)DL(Sdept,Sloc)模式的分解（續(xù)）第一種分解方法既不具有無損連接性，也未保持函數(shù)依賴，它不是原關(guān)系模式的一個等價分解第二種分解方法未保持了函數(shù)依賴，不具有無損連接性第三種分解方法具有無損連接性，但未持函數(shù)依賴第四種分解方法既具有無損連接性，又保持了函數(shù)依賴模式分解的定義設(shè)p={R1<U1,F1>,…,RK<UK,FK>}是R<U,F>的一個分解，r是R<U,F>的一個關(guān)系。定義mp(r)=πRi(r)Mp(r)是r在p中各關(guān)系模式上投影的連接ri=πRi(r)={t.Ui|tr}i=1k模式的分解（續(xù)）引理6.4設(shè)R<U,F>是一個關(guān)系模式，p={R1<U1,F1>，R2<U2,F2>，…，Rk<Uk,Fk>}是R的一個分解，r是R的一個關(guān)系，則（1）r

mp(r)（2）若s=mp(r),則πRi(s)=ri（3）mp(

mp(r))=mp(r)第一條說明r在p上的投影連接映射后的元組只會膨脹，不會變少。第二條說明直接投影的結(jié)果與先拆開來再連接再投影的結(jié)果一致。第三條說明無論進行多少次分解后，再連接的結(jié)果都是一致的。結(jié)論告訴我們，一個實例經(jīng)過投影，連接之后，其結(jié)果可能產(chǎn)生元組膨脹，即元組增多，本節(jié)開頭部分的引例恰好也說明了這個事實。我們并不希望類似的情況發(fā)生，因為它在多個表進行連接操作時出現(xiàn)了本身不存在的元組，產(chǎn)生了數(shù)據(jù)異常，這對保持數(shù)據(jù)的正確性是有害的。因此，我們需要對表間連接的情況進行分析，以便降低產(chǎn)生數(shù)據(jù)異常的可能性。為此，我們先引入以下的概念。無損分解的定義定義6.18p={R1<U1,F1>，R2<U2,F2>，…，Rk<Uk,Fk>}是R<U,F>的一個分解若對R中的任何一個關(guān)系r均有r=mp(r)成立，則稱分解p具有無損連接性。無損分解的判定算法算法6.2判斷一個分解的無損連接性

設(shè)p={R1<U1,F1>，R2<U2,F2>，…，Rk<Uk,Fk>}是R<U,F>的一個分解，U={A1,A2,…,An},F={FD1,FD1,…,FDp}1.建立一個n列k行的表，每列對應一個屬性，每行對應分解中的一個關(guān)系模式。若屬性Aj屬于Ui，則在j列i行的交叉處天上aj,否則填上bij;無損分解的判定算法2.對應每個FDi(FDi為Xi→Ali)做下列操作：找到Xi所對應的列中具有相同符號的那些行。考察這些行的li列，若其中有ali則全部改為ali；否則全部改為bmli;m是這些行的行號最小值如在某次更改之后，有一行成為a1,a2,…,an,則算法終止,P具有無損連接性,否則P不具有無損連接性3.比較掃描前后，表有無變化，如有變化，則返回第2步，否則算法終止分解示例SL（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}2.SL分解為下面二個關(guān)系模式：NL(Sno,Sloc)DL(Sdept,Sloc)

4.將SL分解為下面二個關(guān)系模式：

ND(Sno,Sdept)DL(Sdept,Sloc)

F1={Sno→Sloc}F2={Sdept→Sloc}F1={Sno→Sloc}F2={Sno→Sloc}分解示例例：已知關(guān)系模式R<U，F(xiàn)>，其中

U={A，B，C，D，E}；

F={AB→C，C→D，D→E}。R的一個分解為R1(A,B,C),R2(C,D),R3(D,E).判斷分解是否是無損連接。保持函數(shù)依賴分解的定義定義6.19p={R1<U1,F1>，R2<U2,F2>，…，Rk<Uk,Fk>}是R<U,F>的一個分解若F+=(UFi)+則分解p保持函數(shù)依賴i=1i=k引理6.3F+=G+的充分必要條件是F

G+，和G

F+第六章關(guān)系數(shù)據(jù)理論6.4.1模式分解的定義6.4.2分解的無損連接性和函數(shù)依賴性6.4.3模式分解的算法

模式分解的事實若要求分解保持函數(shù)依賴，則分解可以達到3NF,但不一定達到BCNF;若要求分解既要保持函數(shù)依賴，又要保持無損連接則分解可以達到3NF,但不一定達到BCNF;若要求分解保持無損連接，那一定能達到4NF;第六章關(guān)系數(shù)據(jù)理論模式分解算法[算法6.3]（合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解。（1）對R〈U，F(xiàn)〉中的函數(shù)依賴集F進行“極小化處理”（處理后得到的依賴集仍記為F）（2）找出不在F中出現(xiàn)的屬性，把這樣的的屬性構(gòu)成一個關(guān)系模式。把這些屬性從U中去掉，剩余的屬性仍記為U。（3）若有X→A∈F，且XA=U，則ρ={R}，算法終止。（4）否則，對F按具有相同左部的原則分組（假定分為k組），每一組函數(shù)依賴，所涉及的全部屬性集Ui。若Ui≤

Uj(i≠j)就去掉Ui。那么Ri一定不是最小覆蓋，與第一步整個F是最小覆蓋相矛盾舉例U＝｛Sno,Sdept,Mname,Cname,Grade｝屬性組U上的一組函數(shù)依賴F：

F＝｛Sno→Sdept,Sdept→Mname,Sno→Mname,(Sno,Cname)→G