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

數(shù)據(jù)庫(kù)系統(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模式的分解把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義模式的分解（續(xù)）定義6.16關(guān)系模式R<U,F>的一個(gè)分解：ρ={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}的一個(gè)覆蓋Fi

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

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

──────────────────95001CSA95002ISB95003MAC95004PH─────95005────────────模式的分解（續(xù)） 分解后的數(shù)據(jù)庫(kù)丟失了許多信息例如無(wú)法查詢95001學(xué)生所在系或所在宿舍。如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息模式的分解（續(xù)）2.SL分解為下面二個(gè)關(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個(gè)元組

無(wú)法知道95002、95004、95005究竟是哪個(gè)系的學(xué)生

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

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

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

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

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

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

第三種分解方法具有無(wú)損連接性

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

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

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

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

4.將SL分解為下面二個(gè)關(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的一個(gè)分解為R1(A,B,C),R2(C,D),R3(D,E).判斷分解是否是無(wú)損連接。保持函數(shù)依賴分解的定義定義6.19p={R1<U1,F1>，R2<U2,F2>，…，Rk<Uk,Fk>}是R<U,F>的一個(gè)分解若F+=(UFi)+則分解p保持函數(shù)依賴i=1i=k引理6.3F+=G+的充分必要條件是F

G+，和G

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

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

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

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