【正文】 X={A,B}， 求 (A,B)F+ 。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 3．函數(shù)依賴集的等價和最小函數(shù)依賴集 函數(shù)依賴集等價 定義 一個關(guān)系模式 R(U,F)上的 F和 G是依賴集，若 F+=G+，則稱 F與 G等價，記為 F=G。 引理 F和 G等價的充分必要條件是： ?? FG?? GF 且 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 3．函數(shù)依賴集的等價和最小函數(shù)依賴集 定義 如果函數(shù)依賴集 F滿足下列條件，則稱 F是一個極小函數(shù)依賴集或最小覆蓋。 （ 1） F中每一個函數(shù)依賴的右部都是單個屬性。 （ 2）對 F中任一函數(shù)依賴 X→ A， F{X→ A}都不與 F等價。 （ 3）對于 F中不存在這樣的函數(shù)依賴 X→ A， Z為 X的真子集，使得 {F{X→ A}}∪{ Z → A}與 F等價。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 ?例如：關(guān)系模式 S〈 U,F〉 ,其中： U={學(xué)號，所在院系，院系負(fù)責(zé)人，課程名，成績 }, F={學(xué)號 → 所在院系，所在院系 → 院系負(fù)責(zé)人， (學(xué)號 ,課程名 )→ 成績 } ?設(shè) F1={學(xué)號 → 所在院系，學(xué)號 → 院系負(fù)責(zé)人，所在院系 → 院系負(fù)責(zé)人， (學(xué)號，課程名 )→ 成績， (學(xué)號，所在院系 )→ 所在院系 } 根據(jù) F是最小覆蓋，而 F1不是。因?yàn)?F1{學(xué)號 → 院系負(fù)責(zé)人 }與 F1等價（違背 (2)） 。 ?設(shè) F2={(學(xué)號，所在院系 )→ 所在院系，所在院系 → 院系負(fù)責(zé)人，(學(xué)號，課程名 )→ 成績 } F2也不是最小覆蓋，對 F2中 (學(xué)號 ,所在院系 )→ 所在院系， {學(xué)號 ,所在院系 }存在真子集 {學(xué)號 }，使得 F39。{(學(xué)號 ,所在院系 )→所在院系 } ∪{ 學(xué)號 → 所在院系 }與 F等價。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 3．函數(shù)依賴集的等價和最小函數(shù)依賴集 ?? GXA算法 求 F的最小覆蓋的算法 第一步： 逐一檢查 F中的每個函數(shù)依賴 X→ A，若 A=A1，A2， … ， Ak ，則根據(jù)分解規(guī)則，用 X→ Ai（ i=1，2， … ， k）取代 X→ A，即使 F中任何一個函數(shù)依賴的右邊僅含有一個屬性。 第二步： 去掉多余的函數(shù)依賴。檢查 F中的每個函數(shù)依賴 X→ A，令 G =F{X→ A}，若有 ，則從 F中去掉此函數(shù)依賴。 第三步： 去掉各依賴左部多余的屬性。檢查 F中各函數(shù)依賴 X→ A，設(shè) X=B1， B2， … ， Bm ，檢查 Bi（ i=1，2， … ， m），當(dāng) 時，即以 XBi替換 X。 ???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的最小覆蓋。 3．函數(shù)依賴集的等價和最小函數(shù)依賴集 解： 第一步： 將 F中的函數(shù)依賴的右部屬性單一化； F1＝｛ A→C ， C→A ， B→A ， B→C ， D→A ， D→B ，AC→D ， DA→C ｝ 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 3．函數(shù)依賴集的等價和最小函數(shù)依賴集 第二步： 去掉 F中多余的函數(shù)依賴，具體做法是，從第一個函數(shù)依賴 A→C 開始將它從 F中去掉，剩下的函數(shù)依賴 F1求 (A)F1+，看是否包含 C。若包含 C，則A→C 為冗余函數(shù)依賴，則去掉它，否則不去掉。依此類推，直到能滿足定義最小依賴的第二個條件。 找到冗余函數(shù)依賴是： B→A 或 B→C ， D→A ， DA→C 。 F21＝｛ A→C ， C→A ， B→A ， D→B ， AC→D ｝ F22＝｛ A→C ， C→A ， B→C ， D→B ， AC→D ｝ 可以逐一判斷出 F21和 F22中已無冗余的函數(shù)依賴，所以轉(zhuǎn)第三步。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 3．函數(shù)依賴集的等價和最小函數(shù)依賴集 第三步 ：去掉函數(shù)依賴左邊的冗余屬性。 函數(shù)依賴 AC→D ，可以去掉屬性 A或?qū)傩?C。如果去掉屬性 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 。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 3．函數(shù)依賴集的等價和最小函數(shù)依賴集 所以 F的最小函數(shù)依賴集有四個： Fm1 ＝｛ A→C ， C→A ， B→A ， D→B ， A→D ｝； F m2＝｛ A→C ， C→A ， B→A ， D→B ， C→D ｝； F m3＝｛ A→C ， C→A ， B→C ， D→B ， A→D ｝； F m4＝｛ A→C ， C→A ， B→C ， D→B ， C→D ｝； 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 第四章 關(guān)系規(guī)范化理論 問題的提出 規(guī)范化理論 關(guān)系模式的分解 本章小結(jié) 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 關(guān)系模式的分解 ?定義 關(guān)系模式 R（ U， F）的一個分解 ρ是若干個關(guān)系模式的一個集合： ?其中， ，即關(guān)系模式 R的屬性全集 U是分解后所有小關(guān)系模式的屬性集 Ui的并。每個 i， j（ 1≤i， j≤n） 有 U i ? U j 。 Fi（ i=1， 2， … ， n）是 F在 Ui上的投影，即 Fi ={X→ Y| X→ Y?F+ ∧ XY?Ui} 。 )},() , . . . ,(),({ 222111 nnn FURFURFUR??iniUU ?1??仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 關(guān)系模式的分解 ? 模式分解等價性的三個判定準(zhǔn)則 ? 分解的無損連接性和函數(shù)依賴保持性 ? 模式分解的算法 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解等價性的三個判定準(zhǔn)則 人們從不同的角度，用三個不同的準(zhǔn)則來衡量關(guān)系模式分解的 “等價”性： ?（ 1）分解具有“無損連接性”； ?（ 2）分解具有“函數(shù)依賴保持性” ?（ 3）分解既具有“無損連接性”，又具有“函數(shù)依賴保持性”。 先來看一個例子，說明如果按定義 ，只要求R（ U， F）分解后的各關(guān)系模式的屬性的“并”等于 U，是不能保證分解后與分解前模式的等價性。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解等價性的三個判定準(zhǔn)則 【 例 49】 已知關(guān)系模式 EMP_DEP（ U， F），其中 U＝｛雇員編號，部門編號，部門經(jīng)理｝， F＝｛雇員編號部門編號，部門編號部門經(jīng)理，雇員編號部門經(jīng)理｝。 EMP_DEP的一個實(shí)例見 下表 47。 雇員編號 部門編號 部門經(jīng)理 E1 D1 M1 E2 D1 M1 E3 D2 M2 E4 D3 M3 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解等價性的三個判定準(zhǔn)則 分析可知，關(guān)系模式 EMP_DEP的碼是（雇員編號），沒有其他候選碼，由于存在非主屬性（部門經(jīng)理）和主屬性（雇員編號）之間的傳遞函數(shù)依賴：雇員編號部門經(jīng)理，所以 EMP_DEP 3NF ， EMP_DEP∈ 2NF。對EMP_DEP進(jìn)行規(guī)范化，得到如下兩個分解： ?ρ1＝｛ R1（雇員編號 ,Φ）， R2（部門編號 ,Φ）， R3（ 部門經(jīng)理 ,Φ）｝ ?ρ2＝｛ R1（雇員編號 ,部門編號），｛雇員編號 → 部門編號｝， R2（雇員編號 ,部門經(jīng)理），｛雇員編號 →部門經(jīng)理｝｝ ?仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 模式分解等價性的三個判定準(zhǔn)則 經(jīng)證明可知 ， ?第一種分解 ρ1沒有實(shí)現(xiàn)無損連接； ?第二種分解 ρ2沒有實(shí)現(xiàn)函數(shù)依賴 。 最后對 R進(jìn)行如下分解： ? ρ3＝｛ R1（雇員編號 ,部門編號），｛雇員編號→ 部門編號｝ ， R2（部門編號 ,部門經(jīng)理），｛部門編號 → 部門經(jīng)理｝ ｝ 可以證明， ρ3既具有無損連接性，又保持了函數(shù)依賴，它解決了操作異常，且沒有丟失原關(guān)系模式中的信息。 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 關(guān)系模式的分解 ? 模式分解等價性的三個判定準(zhǔn)則 ? 分解的無損連接性和函數(shù)依賴保持性 ? 模式分解的算法 仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 分解的無損連接性和函數(shù)依賴保持性 1．分解的無損連接性 ?定義 ρ＝ {R1(U1,F1),R2(U2,F2),…, Rn(Un,Fn)}是關(guān)系模式 R(U,F)的一個分解，若對 R(U,F)的任何一 個關(guān)系 r均有 r=mρ(r)成立， mρ(r)＝ ，則分解 ρ具有無損連接性。 注明： 若將一個關(guān)系模式分解為兩個關(guān)系模式，比較容易判別分解是否具有無損連接性。然而，若將一個關(guān)系模式分解為三個或更多個關(guān)系模式，要判別分解是否具有無損連接性需要比較復(fù)雜的算法。下面將對分解為兩個模式的情況， i=1 n )(rqR?仲愷農(nóng)業(yè)工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 分解的無損連接性和函數(shù)依賴保持性 定理 關(guān)系模式 R(U,F)的一個分解 ρ＝ {R1(U1,F1), R2(U2,F2)}具有無損連接性的充分必要的條件是 U1∩U2 → U 1 － U2 ∈ F＋ 或 U1∩U2 → U 2 － U1 ∈ F＋ 。 【 例 410】 給定的關(guān)系模式 R(U,F)， U = {A,B,C,D}, F = {A→B, B→C, A→D } ，有如下兩個分解： ρ1 ＝ { ABC, ACD } ρ2 ＝ { ABD, BC } 檢驗(yàn)這兩個分解的無損聯(lián)接性。 仲愷農(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為有損連接。 （ 2）因?yàn)? ABD