函數(shù)依賴的公理系統(tǒng)

1、1 函數(shù)依賴的公理系統(tǒng)函數(shù)依賴的公理系統(tǒng)n建立函數(shù)依賴推理系統(tǒng)建立函數(shù)依賴推理系統(tǒng)的目的的目的:(1) 求關(guān)系模式的求關(guān)系模式的候選碼候選碼(2) 判斷關(guān)系模式的判斷關(guān)系模式的范式級別范式級別(3) 給定一組函數(shù)依賴，需要導(dǎo)出另外一些函數(shù)依賴，給定一組函數(shù)依賴，需要導(dǎo)出另外一些函數(shù)依賴， 或判斷另外的函數(shù)依賴是否成立。例如：或判斷另外的函數(shù)依賴是否成立。例如： FD=A B，B C，判斷，判斷 A C是否成立？是否成立？n本節(jié)內(nèi)容本節(jié)內(nèi)容:1. 1. 邏輯蘊涵；邏輯蘊涵； 2.2. ArmstrongArmstrong函數(shù)依賴公理系統(tǒng)；函數(shù)依賴公理系統(tǒng)；3.3. 函數(shù)依賴集的閉包；函數(shù)依賴集的

2、閉包； 4.4. 屬性集閉包；屬性集閉包；5.5. 函數(shù)依賴集的等價和覆蓋；函數(shù)依賴集的等價和覆蓋； 6. 6. 最小函數(shù)依賴集。最小函數(shù)依賴集。2邏輯蘊涵邏輯蘊涵n定義定義6.1 關(guān)系模式關(guān)系模式R，F(xiàn)是其函數(shù)依賴是其函數(shù)依賴集集，X、Y是是U的屬性子集，的屬性子集，r是是R的任何一個關(guān)的任何一個關(guān)系，如果從系，如果從F的函數(shù)依賴能夠推出的函數(shù)依賴能夠推出XY，則稱則稱 F邏輯蘊涵邏輯蘊涵 XY，記作記作F XY 。n示例示例:R, U=X, Y, F = XY則則 F邏輯蘊涵以下函數(shù)依賴邏輯蘊涵以下函數(shù)依賴: XX， XY， YY, XYX，XYY，XYXY3函數(shù)依賴集的閉包函數(shù)依賴集的閉

3、包F+n定義定義6.2 在關(guān)系模式在關(guān)系模式R中，中，被被F所邏輯蘊所邏輯蘊 涵的函數(shù)依賴的全體所構(gòu)成的集合稱作涵的函數(shù)依賴的全體所構(gòu)成的集合稱作F的的閉包閉包， 記作記作 F+ = XY | F XYu顯顯然，然，F(xiàn) F F F+ + 。uF+的計算很麻煩，的計算很麻煩，F(xiàn)不大，但不大，但F+也可能很大。也可能很大。 例如：例如：設(shè)設(shè) R, U=X, Y, Z, F = XR, U=X, Y, Z, F = XY, YY, YZZ F F+ + = = X XX X， X XY Y，X X Z, Z, Y YY, Y, Y YZ, Z Z, Z Z, Z, XYXYX X，XYXYY Y，X

4、YXYXY, XZX, XY, XZX, Armstrong公理系統(tǒng)公理系統(tǒng)n函數(shù)依賴公理系統(tǒng)由函數(shù)依賴公理系統(tǒng)由ArmstrongArmstrong于于19741974年首先提出。年首先提出。n設(shè)關(guān)系模式設(shè)關(guān)系模式 RR，U U為屬性全集，為屬性全集，F(xiàn) F是是U U上的一上的一組函數(shù)依賴，組函數(shù)依賴，X X、Y Y、Z Z是是U U的屬性子集，的屬性子集， 對對R R有以下推理規(guī)則：有以下推理規(guī)則： A1A1自反律自反律( (reflexivity)reflexivity)： 若若 Y Y X, X, 則則 X X Y Y。A2A2增廣律增廣律( (augmentation)augment

5、ation)：若若 X X Y Y ，則則 XZ XZ YZ YZ。A3A3傳遞律傳遞律( (transitivity)transitivity)：若若 X X Y Y，Y Y Z Z，則則 X X Z Z 。n注意注意: : 由由自反律自反律所得到的函數(shù)依賴是所得到的函數(shù)依賴是平凡的平凡的, , 自反律的自反律的使用并不依賴于函數(shù)依賴集使用并不依賴于函數(shù)依賴集F F。傳遞律與傳遞依賴傳遞律與傳遞依賴？所得到的函數(shù)依賴是所得到的函數(shù)依賴是不平凡的。不平凡的。5A公理系統(tǒng)的正確性和完備性公理系統(tǒng)的正確性和完備性nArmstrongArmstrong公理的正確性公理的正確性( (即有效性即有效性)

6、 )及完備性。及完備性。n正確性正確性：用用ArmstrongArmstrong公理從公理從F F中導(dǎo)出的函數(shù)依賴中導(dǎo)出的函數(shù)依賴必為必為F F所蘊涵。所蘊涵。n完備性完備性：被被F F所蘊涵的函數(shù)依賴都能用所蘊涵的函數(shù)依賴都能用ArmstrongArmstrong公理從公理從F F中導(dǎo)出。中導(dǎo)出。n公理的正確性公理的正確性: :保證由保證由F F出發(fā)根據(jù)公理推導(dǎo)出的每一出發(fā)根據(jù)公理推導(dǎo)出的每一個函數(shù)依賴一定在個函數(shù)依賴一定在F F+ +中。中。n公理的完備性：公理的完備性：F F+ +中的所有函數(shù)依賴都能由中的所有函數(shù)依賴都能由F F出發(fā)用出發(fā)用公理推導(dǎo)出來。公理推導(dǎo)出來。這個問題很重要這個

7、問題很重要, , 因為因為, , 如果如果F F+ +中有中有一個函數(shù)依賴不能用公理推導(dǎo)出來一個函數(shù)依賴不能用公理推導(dǎo)出來, , 那么那么, , 這些公理這些公理就不夠用就不夠用, , 就不完備就不完備, , 還必須補充新的公理。還必須補充新的公理。6A公理系統(tǒng)：推論公理系統(tǒng)：推論n根據(jù)根據(jù)ArmstrongArmstrong公理系統(tǒng)，可以得到以下公理系統(tǒng)，可以得到以下推理規(guī)則推理規(guī)則：合并律合并律( (union rule)union rule) 若若 X XY Y，X XZ Z，則則 X XYZYZ。分解律分解律( (decomposition rule)decomposition rul

8、e) 若若 X XYZ YZ ，則則 X XY Y，X XZ Z。偽傳遞律偽傳遞律( (pseudotransitivitypseudotransitivity rule) rule) 若若 X XY Y，W WY YZ Z，則則 W WX XZ Z。n引理引理6.16.1 X XA A1 1 A A2 2 A Ak k 成立成立 X XA Ai i 成立成立 ( (i=1, 2, i=1, 2, , ,k)k)證明：證明：用數(shù)學(xué)歸納法證明。用數(shù)學(xué)歸納法證明。 “ ”由由合并律合并律證明；證明； “”由由分解律分解律證明。證明。7A公理系統(tǒng)公理系統(tǒng): 例例n示例：示例：R, U = A, B,

9、 C, G, H, I,R, U = A, B, C, G, H, I, F=A F=AB, AB, AC, CGC, CGH, CGH, CGI, BI, BH,H, nF F邏輯蘊涵以下函數(shù)依賴嗎？邏輯蘊涵以下函數(shù)依賴嗎？ A AH H？ CG CGHIHI？ AG AGI I？是是, , A AB B，B BH H 是是, , CGCGH H，CGCGI I 是是, , A AC, C, AGAGCGCG，CGCGI I傳遞律傳遞律合并率合并率增廣律增廣律傳遞律傳遞律8A公理系統(tǒng)的完備性公理系統(tǒng)的完備性nArmstrong公理系統(tǒng)是有效的公理系統(tǒng)是有效的、完備的。完備的。n有效性即正確性

10、有效性即正確性：由：由F出發(fā)根據(jù)出發(fā)根據(jù)Armstrong公理推公理推導(dǎo)出來的每一個函數(shù)依賴一定在導(dǎo)出來的每一個函數(shù)依賴一定在F+中，中，已經(jīng)證明已經(jīng)證明n完備性完備性： F+中的每一個函數(shù)依賴中的每一個函數(shù)依賴必定可以必定可以由由F出發(fā)出發(fā)根據(jù)根據(jù)Armstrong公理推導(dǎo)出來。公理推導(dǎo)出來。n要證明完備性要證明完備性，必須要計算集合，必須要計算集合F+，但這是一但這是一個個NP完全問題。比如從完全問題。比如從F=XA1,XAn出發(fā)，出發(fā)，至少至少可以推導(dǎo)出可以推導(dǎo)出2n個不同的函數(shù)依賴。個不同的函數(shù)依賴。n尋求其他辦法證明尋求其他辦法證明 - 先引入先引入屬性集閉包。屬性集閉包。9屬性集的

11、閉包屬性集的閉包n示例：示例： 設(shè)屬性集設(shè)屬性集 U =A，B，C， 函數(shù)依賴集函數(shù)依賴集 F =AB，BC 則則 = A，B，C； = B，C = CFXFXn設(shè)設(shè)F為屬性集為屬性集U上的一組函數(shù)依賴，上的一組函數(shù)依賴，X U， = A | XA能由能由F根據(jù)根據(jù)Armstrong公理導(dǎo)出公理導(dǎo)出 稱稱 為為屬性集屬性集X關(guān)于函數(shù)依賴集關(guān)于函數(shù)依賴集F的閉包的閉包。n 是由是由X所能函數(shù)決定的所能函數(shù)決定的全體屬性全體屬性的的集合集合。n定義定義6.3 屬性集的閉包屬性集的閉包FXFXFXFBFAFC10n注意：注意：引理引理6.2給出了判斷一個函數(shù)依賴給出了判斷一個函數(shù)依賴XY能否能否從從

12、F出發(fā)由出發(fā)由A公理導(dǎo)出公理導(dǎo)出的方法的方法，即判，即判斷是否有斷是否有Y 屬性集閉包引理屬性集閉包引理n引理引理6.2 XY能從能從F出發(fā)由出發(fā)由A公理導(dǎo)出公理導(dǎo)出 Y FXFXn例：例：設(shè)設(shè)U =A，B，C，F(xiàn) =AB，BC要判斷函數(shù)依賴要判斷函數(shù)依賴AC是否成立，只要判斷是是否成立，只要判斷是否有否有C ，而而 =A，B，C，故故AC 成成立。立。FAFA11閉包閉包F F+ +的計算（通過的計算（通過計算計算屬性集閉包）屬性集閉包）n公理的有效性和完備性說明了公理的有效性和完備性說明了“導(dǎo)出導(dǎo)出”與與“蘊蘊涵涵”是兩個是兩個完全等價完全等價的概念的概念: : X XY Y為為F F所蘊

13、涵所蘊涵( (即即XYFXYF+ +) ) X XY Y可由可由F F出發(fā)根據(jù)出發(fā)根據(jù)ArmstrongArmstrong公理導(dǎo)出公理導(dǎo)出n方法：方法：要判斷要判斷 X XYYF F+ + ? ? 再判定再判定Y Y ？ FXFX 先求出先求出12屬性集閉包的計算屬性集閉包的計算: 算法算法n算法算法6.1 求屬性集求屬性集X的閉包的閉包.Input：屬性集屬性集X，函數(shù)依賴集函數(shù)依賴集FOutput： = X;while ( 發(fā)生變化發(fā)生變化) dofor each 函數(shù)依賴函數(shù)依賴 AB in F dobegin if A then = BendFXFXFXFXFXFX初始初始：FX初始閉

14、包初始閉包13屬性集閉包的計算屬性集閉包的計算: 示例示例n設(shè)設(shè) R ，U = (A, B, C, G, H, I)， F = AB, AC, CGH, CGI, BH ， 計算計算 FAG)( 最后最后 = A,G,B,C,H,I FAG)(所用依賴所用依賴 變化變化 FAG)(初始初始 =A,GFAG)( AB A,G,B AC A,G,B,C CGH A,G,B,C,H CGI A,G,B,C,H,I 另例另例 ： = A,B,C,H FA14屬性集閉包的計算屬性集閉包的計算: 候選碼的計算候選碼的計算n例：例： 設(shè)有設(shè)有 R，U = (C, T, H, R, S) F = CT, HR

15、C, HTR, HSRn計算計算 (HR)F+= H，R，C，T n計算計算 (HS)F+ = H，S，R，C，T n計算計算 HF+ = H n計算計算 CF+ =C,Tn計算計算 RF+ = R n計算計算 SF+ = S nHR是碼嗎？是碼嗎？nHS是碼嗎？是碼嗎？不是不是是。是。HSHSRCT是完全函數(shù)依賴是完全函數(shù)依賴因為因為 HSR,HRC所以所以 H(HS)C,即即 HSC15函數(shù)依賴集的等價和覆蓋函數(shù)依賴集的等價和覆蓋n定義定義6.4 函數(shù)依賴集函數(shù)依賴集F、G，若若F+= G+，則則稱稱F與與G等價等價，或者說，或者說F是是G的覆蓋，的覆蓋，G是是F的的覆蓋，覆蓋，F(xiàn)和和G互

16、相覆蓋?；ハ喔采w。n引理引理6.3 F+ = G+ F G+ 和和 G F+n證明證明: 略略n下面用下面用函數(shù)依賴集的函數(shù)依賴集的等價等價和和覆蓋覆蓋概念定義函概念定義函數(shù)依賴集的數(shù)依賴集的最小覆蓋最小覆蓋。16最小函數(shù)依賴集最小函數(shù)依賴集(最小覆蓋最小覆蓋)n定義定義6.56.5 最小覆蓋最小覆蓋. . 滿足下列條件的函數(shù)依賴集滿足下列條件的函數(shù)依賴集F F稱為最小覆蓋稱為最小覆蓋( (最最小依賴集小依賴集, , 極小依賴集極小依賴集) )，記作，記作F Fminmin：(1) 單屬性單屬性：F中任一函數(shù)依賴中任一函數(shù)依賴 XA，A必是單屬性。必是單屬性。(2) 無冗余性無冗余性：F中不存

17、在這樣的函數(shù)依賴中不存在這樣的函數(shù)依賴X A，使使得得 F與與 F X A等價。等價。(3) 既約性既約性：F中不存在這樣的函數(shù)依賴中不存在這樣的函數(shù)依賴 X A， X是是多屬性多屬性，在，在X中有真子集中有真子集 Z， 使得使得 F 與與 F X A Z A等價。等價。n定理定理6.2 每一個函數(shù)依賴集每一個函數(shù)依賴集F都等價于一個極小函數(shù)依賴集都等價于一個極小函數(shù)依賴集Fmin n證明就是證明就是算法算法: 檢查檢查Fmin 應(yīng)滿足的三個條件應(yīng)滿足的三個條件。 1. 單屬性單屬性：逐個檢查：逐個檢查 F 中的各函數(shù)依賴中的各函數(shù)依賴：XY，若若Y=A1 A2 Ak ，k2，則用諸則用諸 X

18、Ai 代替代替 XY。即即被確定的屬性為單屬被確定的屬性為單屬性性 2. 無冗余性無冗余性：逐個檢查：逐個檢查 F中各函數(shù)依賴中各函數(shù)依賴 XA, 判判XA是否冗余是否冗余，令令G = F XA ，若若 A XG+ ，則則XA是冗余是冗余, 從從 F 中去掉中去掉該函數(shù)依賴。即該函數(shù)依賴。即無多余的函數(shù)依賴無多余的函數(shù)依賴 3. 既約性既約性：逐個檢查：逐個檢查 F 中各函數(shù)依賴中各函數(shù)依賴 XA，若若X是多屬性，設(shè)是多屬性，設(shè) X=B1Bm, 逐個考查逐個考查 Bi , 判判 Bi 是否多余是否多余, 若若A (XBi)F+ ，則則 Bi 是冗余是冗余, 以以 (X Bi) 取代取代 X。即

19、確定因子是單屬性。即確定因子是單屬性。計算最小覆蓋計算最小覆蓋Fmin: 算法算法18計算最小覆蓋計算最小覆蓋Fmin: 例例1nF = AB，BA，AC，BC，求求Fmin 。F是單屬性的，既約性的，只檢查冗余性。是單屬性的，既約性的，只檢查冗余性。檢查檢查AB, G=F AB=BA, AC, BC 而而 =A, C，B A, C, AB 不冗余。不冗余。GA)(檢查檢查AC, G=F AC=AB, BA, BC =A, B, C，CA, B, C, AC冗余冗余, 從從F中刪除中刪除AC。GA)(實際上，因為有實際上，因為有A AB B，B BC C， 從而從而 A AC C冗余冗余于是：

20、于是： Fmin = AB，BA，BC19計算最小覆蓋計算最小覆蓋Fmin: 例例1(續(xù)續(xù))nF = AB，BA，AC，BC，求求Fmin已經(jīng)求出：已經(jīng)求出： Fmin = AB，BA，BC也可以是以下結(jié)果：也可以是以下結(jié)果：Fmin = AB，BA，ACn注意注意: 函數(shù)依賴集的最小依賴集可能不唯一。函數(shù)依賴集的最小依賴集可能不唯一。與考察的函數(shù)依賴的順序有關(guān)。與考察的函數(shù)依賴的順序有關(guān)。20計算最小覆蓋計算最小覆蓋Fmin: 例例2nF = CA，AG，CGB，BA，求求FminnF已是單屬性的；已是單屬性的；n判斷判斷CGB的既約性的既約性: = = GFCCG)(FG)( = = C,

21、 A, G, BFGCG)(FC)(B C不多余不多余FCCG)(B ， G冗余，去掉，以冗余，去掉，以C代替代替CGFGCG)(得得F = CA，AG，CB，BA再去掉再去掉 CA 得，得，F(xiàn)min = AG，CB，BA21計算最小覆蓋計算最小覆蓋Fmin: 例例3 F = AB, BA，BC，AC，CA，求求Fmin 。n已經(jīng)是單屬性的已經(jīng)是單屬性的, 既約性的既約性的, 只檢查冗余性。只檢查冗余性。nBC，CA, 由傳遞律有由傳遞律有BA, BA多余多余, 從從F中刪除中刪除, F變?yōu)樽優(yōu)锳B, BC, AC, CA；n有有AB，BC, 由傳遞律有由傳遞律有AC, AC多余多余, 從從F

22、中刪除中刪除, F變?yōu)樽優(yōu)锳B, BC，CA； 于是于是, Fmin = AB，BC，CA。n注意注意: 如果先檢查如果先檢查 BC, BA，AB, 由傳遞律有由傳遞律有BC, BC多余多余, 從從F中刪除中刪除, F變?yōu)樽優(yōu)锳B, BA，AC，CA, 則：則： Fmin = AB，BA，AC，CA22計算最小覆蓋計算最小覆蓋Fmin: 練習(xí)練習(xí)n設(shè)設(shè) F = AC, CA, BAC, DAC, BDA，n求求Fmin n檢查單屬性化檢查單屬性化 Fmin= AC, CA, BA, DC 或或 Fmin= AC, CA, BC, DA F= AC, CA, BA, BC , DA , DC ，

23、 BDA F= AC, CA, BA, BC , DA , DC n檢查既約性檢查既約性n檢查冗余性檢查冗余性23候選碼的求解算法候選碼的求解算法 設(shè)關(guān)系模式設(shè)關(guān)系模式RRn(1) (1) 將將R R的所有屬性分為的所有屬性分為 L L、 R R、NN和和 LRLR四類，四類，并令并令X X代表代表L L、NN兩類，兩類，Y Y代表代表LRLR類。類。 L類類: 僅出現(xiàn)在僅出現(xiàn)在F的函數(shù)依賴左部的屬性；的函數(shù)依賴左部的屬性； R類類: .右右； N類類: 在在F的函數(shù)依賴左右兩邊都不出現(xiàn)的屬性；的函數(shù)依賴左右兩邊都不出現(xiàn)的屬性； LR類類: 都出現(xiàn)的屬性都出現(xiàn)的屬性 。 n(2) (2) 求屬

24、性集閉包求屬性集閉包X X+ +，若若 X X+ +包含了包含了R R的全部屬的全部屬性則性則X X即為即為R R的唯一候選碼的唯一候選碼, , 轉(zhuǎn)轉(zhuǎn)(5);(5);24候選碼的求解算法候選碼的求解算法(續(xù)續(xù)) (3) (3) 否則否則, , 在在Y Y中取一屬性中取一屬性A A，求求屬性集閉包屬性集閉包( (XA)XA)+ +，若，若( (XA)XA)+ +包含了包含了R R的全部屬性，則轉(zhuǎn)的全部屬性，則轉(zhuǎn)(4)(4)；否則，調(diào)換一屬性反復(fù)進行這一過程，直到否則，調(diào)換一屬性反復(fù)進行這一過程，直到試完所有試完所有Y Y中的屬性。中的屬性。 (4) (4) 如果已找出了所有的候選碼，則轉(zhuǎn)如果已找

25、出了所有的候選碼，則轉(zhuǎn)(5)(5)；否；否則在則在Y Y中依次取中依次取2 2個、個、3 3個、個、屬性，求屬性，求X X與它與它們的屬性集閉包，直到其閉包包含們的屬性集閉包，直到其閉包包含R R的全部屬的全部屬性。性。 (5) (5) 停止，輸出結(jié)果。停止，輸出結(jié)果。25候選碼的求解：例候選碼的求解：例1n設(shè)關(guān)系模式設(shè)關(guān)系模式R(A, B, C, D), R(A, B, C, D), 其函數(shù)依賴集：其函數(shù)依賴集： F=DB, BD, ADB, ACD F=DB, BD, ADB, ACD 求求R R的所有候選碼。的所有候選碼。n解解: : L L類類: : A, CA, C R R類類: :

26、 NN類類: : LR LR類類: : B, DB, Dn因為因為( (AC)AC)F F+ +=ACDB=ACDB，所以所以ACAC是是R R的唯一候選的唯一候選碼。碼。26候選碼的求解：例候選碼的求解：例2設(shè)設(shè)關(guān)系模式關(guān)系模式R(A, B, C, D, E, P), R(A, B, C, D, E, P), 其函數(shù)依賴集：其函數(shù)依賴集： F=AD, ED, DB, BCD, DCAF=AD, ED, DB, BCD, DCA求求R R的所有候選碼。的所有候選碼。解解: : L L類類: : C, E C, E R R類類: : N N類類: : P P LR LR類類: : A, B, D

27、A, B, Dn因為因為( (CEP)CEP)F F+ +=CEPDBA=CEPDBA，所以所以CEPCEP是是R R的唯一候選碼的唯一候選碼。27候選碼的求解：例候選碼的求解：例3設(shè)設(shè)關(guān)系模式關(guān)系模式R(S, D, I, B, O, Q), 其函數(shù)依賴集其函數(shù)依賴集: F = SD, IB, BO, OQ, QI 求求R的所有候選碼。的所有候選碼。解解: L類類(S); R類類(D) ; N類類(無無) ; LR類類(I, B, O, Q) 因為因為S+=SD, 所以所以S不是不是R的候選碼；的候選碼； 因為因為(SI)+=SIDBOQ， 所以所以SI是一個候選碼；是一個候選碼； 因為因為(

28、SB)+=SBDOQI，所以所以SB也是一個候選碼；也是一個候選碼； 因為因為(SO)+=SODQIB，所以所以SO也是一個候選碼；也是一個候選碼； 因為因為(SQ)+=SQDIBO，所以所以SQ也是一個候選碼。也是一個候選碼。*6.4 模式的分解模式的分解6.4.1 模式分解的三個定義模式分解的三個定義n分解的目標(biāo)：無損連接分解、保持函數(shù)依賴、達分解的目標(biāo)：無損連接分解、保持函數(shù)依賴、達到更高級范式到更高級范式6.4.2 分解的無損連接性和保持函數(shù)依賴性分解的無損連接性和保持函數(shù)依賴性n判別無損連接的充要條件判別無損連接的充要條件n判別分解是否保持函數(shù)依賴的方法判別分解是否保持函數(shù)依賴的方法

29、6.4.3 模式分解的算法模式分解的算法n轉(zhuǎn)換為轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解的保持函數(shù)依賴的分解n轉(zhuǎn)換為轉(zhuǎn)換為3NF的既無損連接又保持函數(shù)依賴的分解的既無損連接又保持函數(shù)依賴的分解n轉(zhuǎn)換為轉(zhuǎn)換為BCNF的無損連接分解的無損連接分解n達到達到4NF的具有無損連接性的分解的具有無損連接性的分解29模式的分解：兩個記號模式的分解：兩個記號 定義定義6 6.16.16 關(guān)系模式關(guān)系模式RR的一個分解是指：的一個分解是指： = = R R1 1U, R, R2 2U, , ,R Rn nU其中其中U = U = U Ui i ，并且沒有并且沒有U Ui i U Uj j ， 1i 1i，j nj n

30、， F Fi i是是F F在在U Ui i上的投影。上的投影。定義定義6 6.17.17 函數(shù)依賴集合函數(shù)依賴集合F Fi i=X=XY | XY | XY Y F F+ + XY XY U Ui i ，稱為稱為F F在在U Ui i上上的投影。的投影。1in= =306.4.1 模式分解的三個定義模式分解的三個定義n對一個模式的對一個模式的分解是不唯一分解是不唯一的，但是的，但是分解前分解前后的兩個模式應(yīng)等價。后的兩個模式應(yīng)等價。n對對“等價等價”的概念有三種不同的定義的概念有三種不同的定義( (也稱分也稱分解的標(biāo)準(zhǔn)、分解的特性或分解的目標(biāo)解的標(biāo)準(zhǔn)、分解的特性或分解的目標(biāo)): ):(1)(1

31、)分解具有分解具有無損連接性無損連接性( (Lossless join)Lossless join)；(2)(2)分解要分解要保持函數(shù)依賴保持函數(shù)依賴( (Preserve dependency)Preserve dependency)(3)(3)分解既要保持函數(shù)依賴，又要具有無損連接分解既要保持函數(shù)依賴，又要具有無損連接性。性。31模式分解的三個定義模式分解的三個定義n按照不同的分解準(zhǔn)則，模式所能達到的分離程度各不按照不同的分解準(zhǔn)則，模式所能達到的分離程度各不相同，相同，各種范式就是對分離程度的測度各種范式就是對分離程度的測度。n進一步討論進一步討論: :(1) “(1) “無損連接性無損連

32、接性”和和“保持函數(shù)依賴保持函數(shù)依賴”的含義的含義? ? 如如何判斷何判斷? ?(2) (2) 對不同的分解等價定義，分離后的關(guān)系模式的范對不同的分解等價定義，分離后的關(guān)系模式的范式級別。式級別。(3) (3) 如何實現(xiàn)分離，分解的算法。如何實現(xiàn)分離，分解的算法。模式分解中的問題模式分解中的問題: 有損分解有損分解R(A, B, C)ABC112221AB1122BC1221ABC112221AB(R)BC(R)AB(R)BC(R)R(A, B, C)ABC111212AB1121BC1112ABC111112211212AB(R)BC(R)AB(R)BC(R)無損無損分解分解有損有損分解分解

33、模式分解中的問題模式分解中的問題: 不保持函數(shù)依賴不保持函數(shù)依賴ABCa1b1c1a2b1c1a3b2c2a4b3c1A B, B CAa1a2a3a4Bb1b2b3Cc1c2各列值A(chǔ)Ba1b1a2b1a3b2a4b3ACa1c1a2c1a3c2a4c1=ABCa1b1c1a2b1c1a3b2c2a4b3c1分解若插入若插入將違反將違反B B C C該分解保該分解保持持A A B B，而不保持而不保持 B B C C，但是是無但是是無損分解損分解 A B a5b3a5c3a5b3c334模式分解中存在的問題模式分解中存在的問題: 例例ABa1b1a2b1a3b2a4b3BCb1c1b2c2b3

34、c1ACa1c1a2c1a3c2a4c1BCb1c1b2c2b3c1=ABCa1b1c1a1b3c1a2b1c1a2b3c1a3b2c2a4b1c1a4b3c1ABCa1b1c1a2b1c1a3b2c2a4b3c1該分解保持該分解保持B B C C，而而不保持不保持A A B, B, 且是有損分且是有損分解解該分解保該分解保持函數(shù)依持函數(shù)依賴賴, , 且是無且是無損分解損分解 B C A B B C 356.4.2 分解的無損連接性分解的無損連接性和保持函數(shù)依賴性和保持函數(shù)依賴性n如果如果一個分解一個分解具有具有無損連接性無損連接性，則它能夠保證，則它能夠保證不丟失信息。不丟失信息。n如果一個

35、分解如果一個分解保持了函數(shù)依賴保持了函數(shù)依賴，則它可以減輕，則它可以減輕或解決或解決各種異常情況各種異常情況。n分解具有無損連接性和分解保持函數(shù)依賴是兩分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨立的標(biāo)準(zhǔn)個互相獨立的標(biāo)準(zhǔn)。具有無損連接性的分解不。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。的分解也不一定具有無損連接性。36分解的無損連接性定義分解的無損連接性定義n定義記號定義記號 mm ( r)( r)關(guān)系模式關(guān)系模式 R ，U = Ui ， =R1,R2, ,Rn是是R的一個分解，的一個分解，r 是是

36、R的一個關(guān)系的一個關(guān)系, 定義：定義： m (r) = Ri(r) 是是r在在中各關(guān)系模式上中各關(guān)系模式上投影的連接投影的連接。這里，。這里， Ri(r) =tUi|trn定義定義6.186.18 R(U,F) R(U,F)的一個分解的一個分解 是是無損連接分解：無損連接分解： r = m r = m (r) (r) ni1=1in= =37判無損連接性的方法判無損連接性的方法(chasechase過程過程) n算法算法6.2 6.2 判別一個分解的無損連接性。判別一個分解的無損連接性。n定理定理6.7 6.7 無損連接分解的充分必要條件無損連接分解的充分必要條件 ( (chasechase過

37、程過程) ) 。n方法：方法：構(gòu)造一個表格，根據(jù)函數(shù)依賴變化表構(gòu)造一個表格，根據(jù)函數(shù)依賴變化表格，格，能夠變出一行全為能夠變出一行全為a a，則是無損連接。則是無損連接。n例例5:5: 設(shè)設(shè) U=A,B,C,D,E, U=A,B,C,D,E, F=AB F=ABC, CC, CD, DD, DEE =(A, B, C), (C, D), (D, E) =(A, B, C), (C, D), (D, E) 是無損分解。是無損分解。ABCDEABCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5考察考察C CD DABCDEABCa1a2a3a4a5CDb21b2

38、2a3a4a5DEb31b32b33a4a5考察考察D DE EABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5考察考察ABABC C制作制作3 3行行5 5列的表列的表 例例5：U=A, B, C, D, E, F=ABC, CD, DE =(A, B, C), (C, D), (D, E) 是無損分解。是無損分解。判無損連接分解判無損連接分解chasechase過程過程: 示例示例n設(shè)設(shè) U=A, B, C, D, E, F=AC, BC,

39、 CD,DEC ,CEA =(A, D), (A, B), (B, E), (C, D, E), (A, E) 是無損連接分解。是無損連接分解。ABCDEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53b54a5考察考察A AC CABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b33b34a5CDE b41b42a3a4a5AEa1b52b13b54a5制作制作5 5列列5 5行的表行的表下頁下頁40判無損連接分解判無損連接分解chasechase過程過程: 示例示

40、例2續(xù)續(xù)考察考察B BC CABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b13b34a5CDEb41b42a3a4a5AEa1b52b13b54a5考察考察C CD DABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2b13a4a5CDEb41b42a3a4a5AEa1b52b13a4a5F=AC, BC, CD,DEC ,CEA是無損連接分解是無損連接分解上頁上頁下頁下頁41判無損連接分解判無損連接分解chasechase過程過程: 示例示例2續(xù)續(xù)考察考察DEDEC CABCDEADa1b12b13a4b15ABa1a2

41、b13a4b25BEb31a2a3a4a5CDEb41b42a3a4a5AEa1b52a3a4a5考察考察CECEA AABCDEADa1b12b13a4b15ABa1a2b13a4b25BEa1a2a3a4a5CDEa1b42a3a4a5AEa1b52a3a4a5F=AC, BC, CD,DEC ,CEA是無損連接分解是無損連接分解上頁上頁42判無損連接分解判無損連接分解chasechase過程過程: 練習(xí)練習(xí)n設(shè)關(guān)系模式設(shè)關(guān)系模式R(A, B, C, D), FR(A, B, C, D), F是是R R上成立的上成立的FDFD集集, , F=AB, CD , DBF=AB, CD , DB

42、 分解分解=AD=AD，BCBC，BDBD。 問：問：相對于相對于F F是否無損連接分解是否無損連接分解?(?(需畫出需畫出chasechase過程的示意圖過程的示意圖) )n答案：不是答案：不是無損連接分解。無損連接分解。n大家現(xiàn)場練習(xí)一下大家現(xiàn)場練習(xí)一下, ,判斷其結(jié)果。判斷其結(jié)果。43ABCDADa1b12b13a4BCb21a2a3b24BDb31a2b33a4ABCDADa1b12b13a4BCb21a2a3b24BDb31a2b33a4考察考察ABABCDADa1b12b13a4BCb21a2a3a4BDb31a2a3a4考察考察CDABCDADa1a2b13a4BCb21a2a3

43、a4BDb31a2a3a4考察考察DB根據(jù)分解造表根據(jù)分解造表判無損連接分解判無損連接分解chasechase過程過程: 練習(xí)練習(xí)分解為兩個關(guān)系模式的無損連接性判別分解為兩個關(guān)系模式的無損連接性判別n定理定理6.56.5. . 關(guān)系模式關(guān)系模式RR的分解的分解 =R R1 1U, R, R2 2U， 則則 是是一個無損連接分解的一個無損連接分解的充要條件充要條件是是: : U U1 1UU2 2U U1 1 U U2 2 或或 U U1 1UU2 2U U2 2 U U1 1 成立。成立。n注注: : 對于定理對于定理4.54.5，有的課本上是這樣敘述：，有的課本上是這樣敘述： 如果如果R R

44、有一個分解有一個分解=R=R1 1, R, R2 2, , 則分解則分解具有無損連接具有無損連接的的充分必要條件充分必要條件為：為： R R1 1RR2 2(R(R1 1-R-R2 2) ) 或或 R R1 1RR2 2(R(R2 2-R-R1 1) ) 成立。成立。45分解為兩個關(guān)系模式的無損連接分解為兩個關(guān)系模式的無損連接: 例例n例：例：設(shè)設(shè)R, U=A, B, C, F=AR, U=A, B, C, F=AB, B, 1. 1. 1 1 =R=R1 1(A, B), R(A, B), R2 2(A, C)(A, C) 則則 R R1 1RR2 2 = A, R= A, R1 1R R2

45、 2 = B = B 由由 A A B B ，得到得到 1 1是無損連接分解。是無損連接分解。 2. 2. 2 2 = = R R1 1(A, B), R(A, B), R2 2(B, C)(B, C) 則則 R R1 1RR2 2 = B, R = B, R1 1R R2 2 = A, R = A, R2 2R R1 1 = C = C 由于由于B BA, BA, BC C均不成立，所以均不成立，所以 2 2不是無損連不是無損連接分解。接分解。46分解為兩個關(guān)系模式的無損連接分解為兩個關(guān)系模式的無損連接: 練習(xí)練習(xí)n設(shè)關(guān)系模式設(shè)關(guān)系模式R(AR(A，B B，C C，D D，E E，P)P)，

46、F F是是R R上成上成立的立的FDFD集，集，F(xiàn)=ABF=AB，CPCP，EAEA，CEDCED。設(shè)有分解：設(shè)有分解： =R1(A =R1(A，B B，E)E)，R2(CR2(C，D D，E E，P)P) 判斷分解判斷分解是否無損連接分解。是否無損連接分解。n解：解：因為因為 R R1 1RR2 2 = E = E， R R1 1R R2 2 = AB = AB，而而 E EA A和和E EB B均成立均成立( 即即 R1R2 R1R2成立成立) ，所，所以以 是無損連接分解。是無損連接分解。47n定義定義6.19 保持函數(shù)依賴的模式分解。保持函數(shù)依賴的模式分解。 設(shè)設(shè)Z是是U的子集，函數(shù)依

47、賴集合的子集，函數(shù)依賴集合F在在Z上的投影上的投影定義為：定義為：Z(F) = XY | XY F+ XY Z 設(shè)設(shè) = R1,R2,Rn 是關(guān)系模式是關(guān)系模式R的一個分解，的一個分解，如果如果 F+= ( Ri (F)+ ，則稱則稱 是保持函數(shù)依賴的分解。是保持函數(shù)依賴的分解。保持函數(shù)依賴的分解定義保持函數(shù)依賴的分解定義 n i =148保持函數(shù)依賴的分解保持函數(shù)依賴的分解: 例例n例：設(shè)關(guān)系模式例：設(shè)關(guān)系模式R，U = C, S, Z, F = CS Z, Z C， = R1(S, Z), R2(C, Z) nR1R2 = Z, R2R1 = C R1R2 R2R1 ( 即即 Z C) 分

48、解是無損的。分解是無損的。nR1(F) = ， R2(F) = Z C R1 (F) R2 (F) = Z C 丟失了函數(shù)依賴丟失了函數(shù)依賴 CS Z, 分解不保持函數(shù)依賴分解不保持函數(shù)依賴49保持函數(shù)依賴的分解保持函數(shù)依賴的分解: 判別法判別法n如何判斷分解保持函數(shù)依賴？如何判斷分解保持函數(shù)依賴？n引理引理4.3 給出了判別一個分解給出了判別一個分解是否保持函數(shù)依賴的方是否保持函數(shù)依賴的方法法 - FD集的覆蓋集的覆蓋n例如，對于例如，對于(A, B, C)，AB , BC的分解的分解 ，顯然顯然, 丟失了函數(shù)依賴丟失了函數(shù)依賴: BCF+= ( Ri (F)+ n i =1504.4.3

49、關(guān)系模式分解的算法關(guān)系模式分解的算法n關(guān)于模式分解的幾個關(guān)于模式分解的幾個重要事實重要事實:.n(1) 若要求分解保持函數(shù)依賴，則分解可以若要求分解保持函數(shù)依賴，則分解可以達到達到3NF，但不一定能達到但不一定能達到BCNF。n(2) 若要求分解既保持函數(shù)依賴若要求分解既保持函數(shù)依賴, 又具有無損又具有無損連接連接, 則可以達到則可以達到3NF, 但不一定能達到但不一定能達到BCNF。n(3) 若只要求分解無損連接性若只要求分解無損連接性, 那一定可以達那一定可以達到到4NF。51關(guān)系模式分解的算法關(guān)系模式分解的算法nP191P191. . 算法算法6.36.3 ( (合成法合成法) ) 轉(zhuǎn)換

50、為轉(zhuǎn)換為3 3NFNF的保持函的保持函數(shù)依賴的分解。數(shù)依賴的分解。nP191P191. . 算法算法6.46.4 轉(zhuǎn)換為轉(zhuǎn)換為3 3NFNF既有無損連接性又既有無損連接性又保持函數(shù)依賴的分解。保持函數(shù)依賴的分解。nP192P192. . 算法算法6.56.5 轉(zhuǎn)換為轉(zhuǎn)換為BCNFBCNF的無損連接分解的無損連接分解( (分解法分解法) )。nP192P192. . 算法算法6.66.6 達到達到4 4NFNF的具有無損連接性的的具有無損連接性的分解分解n后面用例說明。后面用例說明。52達到達到3NF保持依賴的分解保持依賴的分解: 例例1n設(shè)設(shè) U=S#，SD，MN，C#，G F=S#SD,S#MN,SDMN,(S#,C#)Gn1. Fmin=S#SD，SDMN ，(S#,C#)Gn2. 分解：分解：(S#，SD)， S#SD (SD，MN)， SDMN (S#，C#，G)，