【正文】 也就是閉包，首先 X= {A1,A2,…,Am},反復(fù)尋找這樣的函數(shù)依賴： B1,B2,…,Bm → C,使得B1,B2,…,Bm 在 X中，而 C不在 X中，則把 C加入 X，并重復(fù)這個(gè)過程。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 2．函數(shù)依賴集閉包和屬性集閉包 具體而言，根據(jù)下列步驟計(jì)算一系列屬性集合 X (0)， X (1)， … ： （ 1）令 X(0)=X， i=0； （ 2）令 X(i+1) =X(i) ∪ B。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 3．函數(shù)依賴集的等價(jià)和最小函數(shù)依賴集 函數(shù)依賴集等價(jià) 定義 一個(gè)關(guān)系模式 R(U,F)上的 F和 G是依賴集，若 F+=G+，則稱 F與 G等價(jià)，記為 F=G。 （ 1） F中每一個(gè)函數(shù)依賴的右部都是單個(gè)屬性。 （ 3）對(duì)于 F中不存在這樣的函數(shù)依賴 X→ A， Z為 X的真子集，使得 {F{X→ A}}∪{ Z → A}與 F等價(jià)。因?yàn)?F1{學(xué)號(hào) → 院系負(fù)責(zé)人 }與 F1等價(jià)（違背 (2)） 。{(學(xué)號(hào) ,所在院系 )→所在院系 } ∪{ 學(xué)號(hào) → 所在院系 }與 F等價(jià)。 第二步： 去掉多余的函數(shù)依賴。 第三步： 去掉各依賴左部多余的屬性。 ???FiBXA )(仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 【 例 48】 設(shè)有關(guān)系模式 R(U， F)，其中： U＝｛ A，B， C， D｝， F＝｛ A→ C， C→ A， B→ AC，D→ AB， AC→ D， DA→ C｝求 F的最小覆蓋。若包含 C，則A→C 為冗余函數(shù)依賴，則去掉它，否則不去掉。 找到冗余函數(shù)依賴是： B→A 或 B→C ， D→A ， DA→C 。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 3．函數(shù)依賴集的等價(jià)和最小函數(shù)依賴集 第三步 ：去掉函數(shù)依賴左邊的冗余屬性。如果去掉屬性 A，函數(shù)依賴變?yōu)?C→D ，因?yàn)橛?A→C ，所以根據(jù)傳遞律可以推出 A→D ，故導(dǎo)出 AC→D ；如果去掉屬性 C，函數(shù)依賴變?yōu)?A→D ，因?yàn)橛蠧→A ，所以根據(jù)傳遞律可以推出 C→D ，故導(dǎo)出AC→D 。每個(gè) i， j（ 1≤i， j≤n） 有 U i ? U j 。 )},() , . . . ,(),({ 222111 nnn FURFURFUR??iniUU ?1??仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 關(guān)系模式的分解 ? 模式分解等價(jià)性的三個(gè)判定準(zhǔn)則 ? 分解的無損連接性和函數(shù)依賴保持性 ? 模式分解的算法 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解等價(jià)性的三個(gè)判定準(zhǔn)則 人們從不同的角度，用三個(gè)不同的準(zhǔn)則來衡量關(guān)系模式分解的 “等價(jià)”性： ?（ 1）分解具有“無損連接性”； ?（ 2）分解具有“函數(shù)依賴保持性” ?（ 3）分解既具有“無損連接性”，又具有“函數(shù)依賴保持性”。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解等價(jià)性的三個(gè)判定準(zhǔn)則 【 例 49】 已知關(guān)系模式 EMP_DEP（ U， F），其中 U＝｛雇員編號(hào)，部門編號(hào)，部門經(jīng)理｝， F＝｛雇員編號(hào)部門編號(hào)，部門編號(hào)部門經(jīng)理，雇員編號(hào)部門經(jīng)理｝。 雇員編號(hào) 部門編號(hào) 部門經(jīng)理 E1 D1 M1 E2 D1 M1 E3 D2 M2 E4 D3 M3 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解等價(jià)性的三個(gè)判定準(zhǔn)則 分析可知，關(guān)系模式 EMP_DEP的碼是（雇員編號(hào)），沒有其他候選碼，由于存在非主屬性（部門經(jīng)理）和主屬性（雇員編號(hào)）之間的傳遞函數(shù)依賴：雇員編號(hào)部門經(jīng)理，所以 EMP_DEP 3NF ， EMP_DEP∈ 2NF。 最后對(duì) R進(jìn)行如下分解： ? ρ3＝｛ R1（雇員編號(hào) ,部門編號(hào)），｛雇員編號(hào)→ 部門編號(hào)｝ ， R2（部門編號(hào) ,部門經(jīng)理），｛部門編號(hào) → 部門經(jīng)理｝ ｝ 可以證明， ρ3既具有無損連接性，又保持了函數(shù)依賴，它解決了操作異常，且沒有丟失原關(guān)系模式中的信息。 注明： 若將一個(gè)關(guān)系模式分解為兩個(gè)關(guān)系模式，比較容易判別分解是否具有無損連接性。下面將對(duì)分解為兩個(gè)模式的情況， i=1 n )(rqR?仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 分解的無損連接性和函數(shù)依賴保持性 定理 關(guān)系模式 R(U,F)的一個(gè)分解 ρ＝ {R1(U1,F1), R2(U2,F2)}具有無損連接性的充分必要的條件是 U1∩U2 → U 1 － U2 ∈ F＋ 或 U1∩U2 → U 2 － U1 ∈ F＋ 。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 分解的無損連接性和函數(shù)依賴保持性 解：根據(jù)定理 ： （ 1）因?yàn)? ABC ∩ ACD ＝ C ABC － ACD ＝ B ACD － ABC ＝ D 所以 C → B F＋ ， C → D F＋ 故 ρ1為有損連接。 根據(jù)引理 ，可以判斷一個(gè)分解是否具有函數(shù)依賴保持性。如果將 R分解成 ρ＝ {R1,R2},其中 R1＝{STREET, POSTALCODE}， R2＝ { CITY, POSTALCODE}。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 分解的無損連接性和函數(shù)依賴保持性 解：根據(jù)定理 ，由于 R1∩R2＝ POSTALCODE， R1－ R2＝ CITY，POSTALCODE → CITY 所以這個(gè)分解是無損連接的。 )(1 FR? ?仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 分解的無損連接性和函數(shù)依賴保持性 【 例 413】 設(shè)關(guān)系模式 R(A,B,C,D,E)，函數(shù)依賴集為F＝ {(A,B) → D, C → E} ， ρ＝ {R1,R2}，其中 R1＝{A,B,D}， R2＝ {C, E}。 又根據(jù)定義 F1＝ ＝ { (A,B) → D,} ， F2＝ ＝ { C → E } 則 F1∪ F2 ＝ {(A,B) → D, C → E} ＝ F 所以這個(gè)分解是保持函數(shù)依賴的。但是根據(jù)目前的研究結(jié)果，模式分解還不盡人意，存在這樣的事實(shí)： （ 1）若要求分解具有無損連接性，分解一定可達(dá)到 BCNF； （ 2）若要求函數(shù)依賴保持，則分解可達(dá)到 3NF，但不一定能達(dá)到 BCNF。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解的算法 下面介紹算法 、 算法 、 算法 ， 他們分別實(shí)現(xiàn)了符合以上范式要求的模式分解 。 算法步驟如下： (1) 令 ρ＝｛ RU， F｝ (2) 檢查 ρ中各種關(guān)系模式是否均屬于 BCNF。因此， XA是 Ui的真子集。 (5) 輸出 ρ。應(yīng)當(dāng)指出， RU， F的分解是不唯一的。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解的算法 【 例 414】 將 CTHRSG無損連接分解為一組 BCNF的關(guān)系模式，其中： C表示課程， T表示教師， H表示時(shí)間， R表示教室， S表示學(xué)生， G表示成績。 HT→R 在任一時(shí)間，一個(gè)教師只能在一個(gè)教室上課。 HS→R 在任一時(shí)間，每個(gè)學(xué)生只能在一個(gè)教室聽課。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解的算法 解： （ 1）關(guān)系模式 CTHRSG侯選關(guān)鍵字為： HS； 由于 CS不包含侯選關(guān)鍵字， CS→G ，分解 CTHRSG為 CSG和 CTHRS，并求得 CSG和 CTHRS上函數(shù)依賴最小集： F11=πCSG(F) ={ CS→G } F12=πCTHRS(F)={HS→R,HT→R,C→T,HR→C} CSR(CSG,{CS→G})(BCNF) CTHRS(CTHRS,{HS→R,HT→R,C→T,HR→C}) 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解的算法 （ 2） ρ={CSG, CTHRS} 關(guān)系模式 CTHRS侯選關(guān)鍵字為： HS； 由 C不包含侯選關(guān)鍵字， C→T ， 分解 CT為 CSG和 CHRS，并求得 CT和 CHRS上函數(shù)依賴最小集： CT(CT,{C→T})(BCNF) CHRS(CHRS,{HS→R,HT→R,HR→C}) ρ={CSG,CT, CHRS} 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解的算法 （ 3）關(guān)系模式 CHRS侯選關(guān)鍵字為： HS； 由 HR不包含侯選關(guān)鍵字， HC→R ， 分解 CT為 CSG和 CHRS，并求得 CT和 CHRS上函數(shù)依賴最小集 CHR(CH,{HC→R,HR→C})(BCNF) CHS(HS,{HS→C})(BCNF) （ 4） ρ={CSG,CT,CHR,CHS}。 步驟如下： （ 1）如果 R中有某些屬性與 F的最小覆蓋中的每個(gè)依賴的左邊和右邊都無關(guān)，原則上可由這些屬性構(gòu)成一個(gè)關(guān)系模式，并從 R中將它們消除；否則， （ 2）如果 F′中有一個(gè)依賴涉及到 R的所有屬性，則輸出 R，算法停止；否則， （ 3）輸出一個(gè)分解 ρ，它由模式 XA組成，其中X→ A∈ F+。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解的算法 【 例 415】 將 【 例 414】 中的關(guān)系模式進(jìn)行分解，要保持函數(shù)依賴達(dá)到 3NF。 該模式可以保持函數(shù)依賴地分解為如下一組 3NF的關(guān)系模式： ρ={CT， CSG， CHR， HSR， HRT}。 （ 1）根據(jù)算法 ，是函數(shù)依賴保持的 3NF分解； （ 2）判斷分解是否具有無損連接性，若有，轉(zhuǎn)(4)，否則， （ 3）設(shè) X為 R的一個(gè)候選關(guān)鍵字， =∪ {X}是 R的一個(gè)分解，且中的所有關(guān)系模式均滿足 3NF，同時(shí)，既具有連接不失真性，又具有依賴保持性； （ 4）輸出。 解： 已知 R（ C， T， H， R， S， G）， F′={C→ T， HR→ C，CS→ G， HS→ R， HT→ R}， KEY=HS，則 ={CT，CSG， HRT， CHR， HSR， HS}。關(guān)系模式的范式從低級(jí)到高級(jí)有第一范式（ 1NF ） 、 第二范式 （ 2NF ） 、 第三范式（ 3NF） 、 BCNF范式和第四范式 （ 4NF） ， 它們分別滿足某種確定的約束條件 ， 具有一定的性質(zhì) 。這些概念是模式分解的基礎(chǔ)。 模式分解的三個(gè)算法。