1、1 函數(shù)依賴的公理系統(tǒng)函數(shù)依賴的公理系統(tǒng)n建立函數(shù)依賴推理系統(tǒng)建立函數(shù)依賴推理系統(tǒng)的目的的目的:(1) 求關(guān)系模式的候選碼求關(guān)系模式的候選碼(2) 判斷關(guān)系模式的范式級(jí)別判斷關(guān)系模式的范式級(jí)別(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. 邏輯蘊(yùn)涵；邏輯蘊(yùn)涵； 2.2. ArmstrongArmstrong函數(shù)依賴公理系統(tǒng)；函數(shù)依賴公理系統(tǒng)；3.3. 函數(shù)依賴集的閉包；函數(shù)依賴集的

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

3、閉包F+n定義定義4.12 在關(guān)系模式在關(guān)系模式R中，中，被被F所所邏輯蘊(yùn)涵的函數(shù)依賴的全體所構(gòu)成的集合稱邏輯蘊(yùn)涵的函數(shù)依賴的全體所構(gòu)成的集合稱作作F的的閉包閉包，記作，記作 F+ = XY | F XYn顯然，顯然，F(xiàn) F F F+ + 。nF+的計(jì)算很麻煩，的計(jì)算很麻煩，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，

4、XYXYXY, 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的屬性子集，對(duì)的屬性子集，對(duì)R R有以下推有以下推理規(guī)則：理規(guī)則： A1A1自反律自反律( (reflexivity)reflexivity)：若若 Y Y X, X, 則則 X X Y Y。 A2 A2增廣律增廣律( (augmentation)augmen

5、tation)：2 2若若 X X Y Y ，則則 XZ XZ YZ YZ。 A3 A3傳遞律傳遞律( (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所蘊(yùn)涵。所蘊(yùn)涵。n完備性完備性：被：被F F所蘊(yùn)涵的函數(shù)依賴都能用所蘊(yùn)涵的函數(shù)依賴都能用ArmstrongArmstrong公理從公理從F F中導(dǎo)出。中導(dǎo)出。n公理的正確性公理的正確性保證由保證由F F出發(fā)根據(jù)公理推導(dǎo)出的每一個(gè)出發(fā)根據(jù)公理推導(dǎo)出的每一個(gè)函數(shù)依賴一定在函數(shù)依賴一定在F F+ +中。中。n公理的完備性公理的完備性保證用公理能推出所有的函數(shù)依賴保證用公理能推出所有的函數(shù)依賴, , 即即F F+ +中的所有函數(shù)依賴都能由中的所有

7、函數(shù)依賴都能由F F出發(fā)用公理推導(dǎo)出來。出發(fā)用公理推導(dǎo)出來。這個(gè)問題很重要這個(gè)問題很重要, , 因?yàn)橐驗(yàn)? , 如果如果F F+ +中有一個(gè)函數(shù)依賴不中有一個(gè)函數(shù)依賴不能用公理推導(dǎo)出來能用公理推導(dǎo)出來, , 那么那么, , 這些公理就不夠用這些公理就不夠用, , 就不完就不完備備, , 還必須補(bǔ)充新的公理還必須補(bǔ)充新的公理 。6A公理系統(tǒng)的正確性證明公理系統(tǒng)的正確性證明n定理定理4.1 Armstrong推理規(guī)則是正確的。推理規(guī)則是正確的。 按函數(shù)依賴定義，假設(shè)按函數(shù)依賴定義，假設(shè) r r 是是RR上的任一關(guān)系上的任一關(guān)系實(shí)例，實(shí)例，t t、s s 是是 r r 的任意兩個(gè)元組。的任意兩個(gè)元組

8、。（1 1）證明自反律）證明自反律: : 若若Y Y X X U U，則則 X X Y Y 若若tX=sX, tX=sX, 由于由于Y Y X X, , 有有tY=sY, tY=sY, 所以有所以有X X Y Y。tX = sXYXtY = sYX Y自反律7A公理系統(tǒng)：增廣律證明公理系統(tǒng)：增廣律證明tXZ = sXZtX = sXXYtY = sYtXZ = sXZtZ = sZtYZ = sYZXZYZ增廣律(2) (2) 證明增廣律證明增廣律: : 若若 X X Y Y， 則則 XZ XZ YZ YZ。 設(shè)設(shè) tXZ=sXZ, tXZ=sXZ, 則有則有tX=sXtX=sX和和tZ=sZ

9、, tZ=sZ, 由于由于 X XY, Y, 對(duì)對(duì)tX=sXtX=sX，就有就有tY=sY, tY=sY, 從而有從而有tYZ=sYZ, tYZ=sYZ, 所以所以 XZ XZ YZ YZ成立。成立。8A公理系統(tǒng)：傳遞律證明公理系統(tǒng)：傳遞律證明X YtX = sXtY = sYY ZtZ = sZX Z傳遞律(3) (3) 證明傳遞律證明傳遞律: : 若若 X X Y Y 及及 Y YZ Z，則則 X X Z Z。 設(shè)設(shè) tX = sX, tX = sX, 由于由于X XY, Y, 則有則有 tY = sY, tY = sY, 再由再由 Y YZ Z， 對(duì)對(duì)tY = sYtY = sY，有有

10、tZ=sZ,tZ=sZ, 所以所以 X X Z Z 成立。成立。.9A公理系統(tǒng)：推論公理系統(tǒng)：推論n由由ArmstrongArmstrong公理導(dǎo)出的公理導(dǎo)出的推理規(guī)則推理規(guī)則參見參見P184.P184.n合并律合并律( (union rule)union rule) 若若 X X Y Y，X X Z Z，則則 X X YZ YZ。n分解律分解律( (decomposition rule)decomposition rule) 若若 X X YZ YZ ，則則 X X Y Y，X X Z Z。n偽傳遞律偽傳遞律( (pseudotransitivitypseudotransitivity ru

11、le) rule) 若若 X X Y Y，WY Y Z Z，則則 WX X Z Z。n引理引理4.14.1 X X A A1 1 A A2 2 A Ak k 成立成立 X X A Ai i 成立。成立。 ( (i=1, 2, i=1, 2, , ,k)k)n證明：用數(shù)學(xué)歸納法證明。證明：用數(shù)學(xué)歸納法證明。 “ ”由由合并律合并律證明；證明； “”由由分解律分解律證明。證明。10A公理系統(tǒng)公理系統(tǒng): 例例n示例：示例：R, U = A, B, C, G, H, I,R, U = A, B, C, G, H, I, F = A F = AB, AB, AC, CGC, CGH, CGH, CGI,

12、 BI, BH,H, nF F邏輯蘊(yùn)涵以下函數(shù)依賴嗎？邏輯蘊(yùn)涵以下函數(shù)依賴嗎？ A A H H？ CG CG HI HI？ AG AG I I？是是, , A AB B，B BH H 是是, , CGCGH H，CGCGI I 是是, , A AC, C, AGAGCGCG，CGCGI I傳遞律傳遞律合并率合并率增廣律增廣律傳遞律傳遞律11A公理系統(tǒng)的完備性公理系統(tǒng)的完備性nArmstrong公理系統(tǒng)是有效的公理系統(tǒng)是有效的、完備的。完備的。n有效性即正確性有效性即正確性：由：由F出發(fā)根據(jù)出發(fā)根據(jù)Armstrong公理推公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F+中，中，

13、已經(jīng)證明已經(jīng)證明n完備性完備性： F+中的每一個(gè)函數(shù)依賴必定可以由中的每一個(gè)函數(shù)依賴必定可以由F出發(fā)出發(fā)根據(jù)根據(jù)Armstrong公理推導(dǎo)出來。公理推導(dǎo)出來。n要證明完備性要證明完備性，必須要計(jì)算集合，必須要計(jì)算集合F+，但這是一但這是一個(gè)個(gè)NP完全問題。比如從完全問題。比如從F=XA1,XAn出發(fā)，至少可以推導(dǎo)出出發(fā)，至少可以推導(dǎo)出2n個(gè)不同的函數(shù)依賴。個(gè)不同的函數(shù)依賴。n尋求其他辦法證明尋求其他辦法證明 - 先引入先引入屬性集閉包。屬性集閉包。12屬性集的閉包屬性集的閉包n示例：示例： 設(shè)屬性集設(shè)屬性集 U =A，B，C， 函數(shù)依賴集函數(shù)依賴集 F =AB，BC 則則 AF+ = A，B，

14、C； BF+ = B，C CF+ = 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定義定義4.13 屬性集的閉包屬性集的閉包.FXFXFX13屬性集閉包引理屬性集閉包引理n引理引理4.2 XY能從能從F出發(fā)由出發(fā)由A公理導(dǎo)出公理導(dǎo)出 Y FXFXn注意：注意：引理引理4.2給出了判斷一個(gè)函數(shù)依賴給出了判斷一個(gè)函數(shù)依賴XY能否能否從從F出發(fā)由出發(fā)由A

15、公理導(dǎo)出公理導(dǎo)出的方法的方法，即判，即判斷是否有斷是否有Y n例：例：設(shè)設(shè)U =A，B，C，F(xiàn) =AB，BC要判斷函數(shù)依賴要判斷函數(shù)依賴AC是否成立，只要判斷是是否成立，只要判斷是否有否有C AF+，而而AF+ =A，B，C，故故AC 成立。成立。14A公理系統(tǒng)公理系統(tǒng): 完備性的證明完備性的證明n定理定理4.24.2 Armstrong Armstrong公理是有效的、完備的。公理是有效的、完備的。n證明：證明：n有效性的證明，見定理有效性的證明，見定理4.14.1的證明。的證明。n完備性的證明。完備性的證明。n完備性的證明是構(gòu)造性的證明。完備性的證明是構(gòu)造性的證明。n證明完備性的逆否命題：

16、若證明完備性的逆否命題：若函數(shù)依賴函數(shù)依賴XYXY不能由不能由F F出發(fā)從出發(fā)從公理推導(dǎo)出來，那么它必然公理推導(dǎo)出來，那么它必然不為不為F F所蘊(yùn)涵所蘊(yùn)涵( ( 即即XYXY不屬于不屬于F F+ + ) )，證明略證明略。15閉包閉包F F+ +的計(jì)算的計(jì)算-計(jì)算屬性集閉包計(jì)算屬性集閉包n公理的有效性和完備性說明了公理的有效性和完備性說明了“導(dǎo)出導(dǎo)出”與與“蘊(yùn)蘊(yùn)涵涵”是兩個(gè)是兩個(gè)完全等價(jià)完全等價(jià)的概念的概念: : X XY Y為為F F所蘊(yùn)涵所蘊(yùn)涵( (即即XYFXYF+ +) ) X XY Y可由可由F F出發(fā)根據(jù)出發(fā)根據(jù)ArmstrongArmstrong公理導(dǎo)出公理導(dǎo)出n即：欲判即：欲判

17、 X XYYF F+ + ? ? 再判再判 Y Y ? ?FXn由 引 理由 引 理 4 . 2 , 4 . 2 , 判 定判 定 X X Y Y 是 否 能 由是 否 能 由 F F 根 據(jù)根 據(jù)ArmstrongArmstrong公理導(dǎo)出，可轉(zhuǎn)化為求公理導(dǎo)出，可轉(zhuǎn)化為求 ，判定，判定Y Y 是否成立。是否成立。FXFXFX 先求出先求出16屬性集閉包的計(jì)算屬性集閉包的計(jì)算: 算法算法n算法算法4.1 求屬性集求屬性集X的閉包的閉包.Input：屬性集屬性集X，函數(shù)依賴集函數(shù)依賴集FOutput： := X;while ( 發(fā)生變化發(fā)生變化) dofor each 函數(shù)依賴函數(shù)依賴 AB i

18、n F dobegin if A then := BendFXFXFXFXFXFX開始開始：FX17屬性集閉包的計(jì)算屬性集閉包的計(jì)算: 示例示例n設(shè)設(shè) R ，U = (A, B, C, G, H, I)， F = AB, AC, CGH, CGI, BH ， 計(jì)算計(jì)算 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 FA18屬性集閉包的計(jì)算屬性集閉包的計(jì)算: 練習(xí)練習(xí)n設(shè)有設(shè)有 R，

19、U = (C, T, H, R, S) F = CT, HRC, HTR, HSRn計(jì)算計(jì)算 (HR)F+=n計(jì)算計(jì)算 (HS)F+ =n計(jì)算計(jì)算 HF+ =n計(jì)算計(jì)算 RF+ =n計(jì)算計(jì)算 SF+ =nHR是碼嗎？是碼嗎？nHS是碼嗎？是碼嗎？H，R，C，T H，S，R，C，T H R S 不是不是是。是。HSHSRCT是完全函數(shù)依賴是完全函數(shù)依賴19函數(shù)依賴集的等價(jià)和覆蓋函數(shù)依賴集的等價(jià)和覆蓋n定義定義4.14 函數(shù)依賴集函數(shù)依賴集F、G，若若F+= G+，則稱則稱F與與G等價(jià)等價(jià)，或者說，或者說F是是G的覆蓋，的覆蓋，G是是F的覆蓋，的覆蓋，F(xiàn)和和G互相覆蓋。互相覆蓋。n引理引理4.3

20、F+ = G+ F G+ 和和 G F+n證明證明: 略略n下面用下面用函數(shù)依賴集的等價(jià)和覆蓋概念定義函函數(shù)依賴集的等價(jià)和覆蓋概念定義函數(shù)依賴集的最小覆蓋。數(shù)依賴集的最小覆蓋。20最小函數(shù)依賴集最小函數(shù)依賴集(最小覆蓋最小覆蓋)n定義定義4.154.15 最小覆蓋最小覆蓋. . 滿足下列條件的函數(shù)依賴集滿足下列條件的函數(shù)依賴集F F稱為最小覆蓋稱為最小覆蓋( (最最小依賴集小依賴集, , 極小依賴集極小依賴集) )，記作，記作F Fminmin：n(1) 單屬性單屬性：F中任一函數(shù)依賴中任一函數(shù)依賴 XA，A必是單屬必是單屬性。性。n(2) 無冗余性無冗余性：F中不存在這樣的函數(shù)依賴中不存在這

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

22、. 無冗余性無冗余性：逐個(gè)檢查：逐個(gè)檢查 F中各函數(shù)依賴中各函數(shù)依賴 XA, 判判XA是否冗余是否冗余，令，令G = F XA ，若若 A XG+ ，則則XA是冗余是冗余, 從從 F 中去掉該函數(shù)依賴。中去掉該函數(shù)依賴。 3. 既約性既約性：逐個(gè)檢查：逐個(gè)檢查 F 中各函數(shù)依賴中各函數(shù)依賴 XA，X是多屬是多屬性，設(shè)性，設(shè) X=B1Bm, 逐個(gè)考查逐個(gè)考查 Bi , 判判 Bi 是否多余是否多余, 若若A (XBi)F+ ，則則 Bi 是冗余是冗余, 以以 (X Bi) 取代取代 X。計(jì)算最小覆蓋計(jì)算最小覆蓋Fmin: 算法算法22計(jì)算最小覆蓋計(jì)算最小覆蓋Fmin: 例例1nF = AB，BA

23、，AC，BC，求求Fmin 。nF是單屬性的，既約性的，只檢查冗余性。是單屬性的，既約性的，只檢查冗余性。n檢查檢查AB, G=F AB=BA, AC, BC =A, C，B A, C, AB 不冗余。不冗余。GA)(n檢查檢查AC,G=F AC=AB, BA, BC =A, B, C，CA, B, C, AC冗余冗余, 從從F中刪中刪除除AC。GA)(實(shí)際上，因?yàn)橛袑?shí)際上，因?yàn)橛蠥 AB B，B BC C， 從而從而 A AC C冗余冗余于是：于是： Fmin = AB，BA，BC23計(jì)算最小覆蓋計(jì)算最小覆蓋Fmin: 例例1(續(xù)續(xù))nF = AB，BA，AC，BC，求求Fmin已經(jīng)求出：已

24、經(jīng)求出： Fmin = AB，BA，BC也可以是以下結(jié)果：也可以是以下結(jié)果：Fmin = AB，BA，ACn注意注意: 函數(shù)依賴集的最小依賴集可能不唯一。函數(shù)依賴集的最小依賴集可能不唯一。與考察的函數(shù)依賴的順序有關(guān)。與考察的函數(shù)依賴的順序有關(guān)。24計(jì)算最小覆蓋計(jì)算最小覆蓋Fmin: 例例2nF = CA，AG，CGB，BA，求求FminnF已是單屬性的；已是單屬性的；n判斷判斷CGB的既約性的既約性: = = GFCCG)(FG)( = = C, A, G, BFGCG)(FC)(B C不可去不可去FCCG)(B ， G冗余，去掉，以冗余，去掉，以C代替代替CGFGCG)(得得F = CA，A

25、G，CB，BA再去掉再去掉 CA 得，得，F(xiàn)min = AG，CB，BA25計(jì)算最小覆蓋計(jì)算最小覆蓋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中刪除中刪除, F變?yōu)樽優(yōu)锳B, BC，CA； 于是于是, Fmin = AB，BC，CA。n注意注意: 如果先檢查如果先檢查 BC, BA，AB,

26、由傳遞律有由傳遞律有BC, BC多余多余, 從從F中刪除中刪除, F變?yōu)樽優(yōu)锳B, BA，AC，CA, 則：則： Fmin = AB，BA，AC，CA26計(jì)算最小覆蓋計(jì)算最小覆蓋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 ， BDA F= AC, CA, BA, BC , DA , DC n檢查既約性檢查既約性n檢查冗余性檢查冗余性27補(bǔ)充：候選碼的求解算法補(bǔ)充：候選碼的

27、求解算法 設(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) 求屬性集閉包求屬性集閉包X X+ +，若若 X X+ +包含了包含了R R的全部屬的全部屬性則性則X X即為即為R R的唯一候選碼的唯一候選碼

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

29、集閉包，直到其閉包包含們的屬性集閉包，直到其閉包包含R R的全部屬的全部屬性。性。 (5) (5) 停止，輸出結(jié)果。停止，輸出結(jié)果。29候選碼的求解：例候選碼的求解：例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類類: : NN類類: : LR LR類類: : B, DB, Dn因?yàn)橐驗(yàn)? (AC)AC)F F+ +=ACDB=ACDB，所以所以ACAC是是

30、R R的唯一候選的唯一候選碼。碼。30候選碼的求解：例候選碼的求解：例2n設(shè)關(guān)系模式設(shè)關(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的所有候選碼。的所有候選碼。n解解: : L L類類: : C, E RC, E R類類: : NN類類: : P P LR LR類類: : A, B, DA, B, Dn因?yàn)橐驗(yàn)? (CEP)CEP)F F+ +=CEPDBA=CEPDBA，所以所以CEPCEP是是R R的唯一的唯一候選碼

31、。候選碼。31候選碼的求解：例候選碼的求解：例3n設(shè)關(guān)系模式設(shè)關(guān)系模式R(S, D, I, B, O, Q), 其函數(shù)依賴集其函數(shù)依賴集: F = SD, IB, BO, OQ, QI 求求R的所有候選碼。的所有候選碼。n解解: L類類(S); R類類(D) ; N類類(無無) ; LR類類(I, B, O, Q) 因?yàn)橐驗(yàn)镾+=SD, 所以所以S不是不是R的候選碼；的候選碼； 因?yàn)橐驗(yàn)?SI)+=SIDBOQ，所以所以SI是一個(gè)候選碼；是一個(gè)候選碼； 因?yàn)橐驗(yàn)?SB)+=SBDOQI，所以所以SB也是一個(gè)候選碼；也是一個(gè)候選碼； 因?yàn)橐驗(yàn)?SO)+=SODQIB，所以所以SO也是一個(gè)候選碼；

32、也是一個(gè)候選碼； 因?yàn)橐驗(yàn)?SQ)+=SQDIBO，所以所以SQ也是一個(gè)候選碼。也是一個(gè)候選碼。*5.4 模式的分解模式的分解n5.4.1 模式分解的三個(gè)定義模式分解的三個(gè)定義n分解的目標(biāo)：無損連接分解、保持函數(shù)依賴、達(dá)分解的目標(biāo)：無損連接分解、保持函數(shù)依賴、達(dá)到更高級(jí)范式到更高級(jí)范式n5.4.2 分解的無損連接性和保持函數(shù)依賴性分解的無損連接性和保持函數(shù)依賴性n判別無損連接的充要條件判別無損連接的充要條件n判別分解是否保持函數(shù)依賴的方法判別分解是否保持函數(shù)依賴的方法n5.4.3 模式分解的算法模式分解的算法n轉(zhuǎn)換為轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解的保持函數(shù)依賴的分解n轉(zhuǎn)換為轉(zhuǎn)換為3NF的既無

33、損連接又保持函數(shù)依賴的分解的既無損連接又保持函數(shù)依賴的分解n轉(zhuǎn)換為轉(zhuǎn)換為BCNF的無損連接分解的無損連接分解n達(dá)到達(dá)到4NF的具有無損連接性的分解的具有無損連接性的分解33模式的分解：兩個(gè)記號(hào)模式的分解：兩個(gè)記號(hào) n定義定義5.165.16 關(guān)系模式關(guān)系模式RR的一個(gè)分解是指：的一個(gè)分解是指： = = 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， F Fi i是是F F在在U Ui i上的投影。上的投影。n定義定義5.175.17 函數(shù)依賴集合函數(shù)依賴集合F Fi i

34、 = X = XY | XY | XY Y F F+ + XY XY U Ui i ，稱為稱為F F在在U Ui i上的投影。上的投影。1in= =345.4.1 模式分解的三個(gè)定義模式分解的三個(gè)定義n對(duì)一個(gè)模式的對(duì)一個(gè)模式的分解是不唯一分解是不唯一的，但是的，但是分解前分解前后的兩個(gè)模式應(yīng)等價(jià)。后的兩個(gè)模式應(yīng)等價(jià)。n對(duì)對(duì)“等價(jià)等價(jià)”的概念有三種不同的定義的概念有三種不同的定義( (也稱分也稱分解的標(biāo)準(zhǔn)、分解的特性或分解的目標(biāo)解的標(biāo)準(zhǔn)、分解的特性或分解的目標(biāo)): ):1. 1. 分解具有分解具有無損連接性無損連接性( (Lossless join)Lossless join)；2. 2. 分解

35、要分解要保持函數(shù)依賴保持函數(shù)依賴( (Preserve dependency)Preserve dependency)3. 3. 分解既要保持函數(shù)依賴，又要具有無損連分解既要保持函數(shù)依賴，又要具有無損連接性。接性。35模式分解的三個(gè)定義模式分解的三個(gè)定義n按照不同的分解準(zhǔn)則，模式所能達(dá)到的分離程按照不同的分解準(zhǔn)則，模式所能達(dá)到的分離程度各不相同，度各不相同，各種范式就是對(duì)分離程度的測度各種范式就是對(duì)分離程度的測度。n進(jìn)一步討論進(jìn)一步討論: :n(1) “(1) “無損連接性無損連接性”和和“保持函數(shù)依賴保持函數(shù)依賴”的含的含義義? ? 如何判斷如何判斷? ?n(2) (2) 對(duì)不同的分解等價(jià)定

36、義，分離后的關(guān)系對(duì)不同的分解等價(jià)定義，分離后的關(guān)系模式的范式級(jí)別。模式的范式級(jí)別。n(3) (3) 如何實(shí)現(xiàn)分離，分解的算法。如何實(shí)現(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)有損分解有損分解無損分解無損分解模式分解中的問題模式分解中的問題: 不保持函數(shù)依賴不保持函數(shù)依賴ABCa1b1c1a2b1c1a3b2c2a4b

37、3c1A B, B CAa1a2a3a4Bb1b2b3Cc1c2各列值A(chǔ)Ba1b1a2b1a3b2a4b3ACa1c1a2c1a3c2a4c1=ABCa1b1c1a2b1c1a3b2c2a4b3c1分解若插入若插入將違反將違反B B C C該分解保該分解保持持A A B B，而不保持而不保持B B C C，但是是無但是是無損分解損分解 A B a5b3a5c3a5b3c338模式分解中存在的問題模式分解中存在的問題: 例例ABa1b1a2b1a3b2a4b3BCb1c1b2c2b3c1ACa1c1a2c1a3c2a4c1BCb1c1b2c2b3c1=ABCa1b1c1a1b3c1a2b1c1a

38、2b3c1a3b2c2a4b1c1a4b3c1ABCa1b1c1a2b1c1a3b2c2a4b3c1該分解保持該分解保持B B C C，而而不保持不保持A A B, B, 且是有損分且是有損分解解該分解保該分解保持函數(shù)依持函數(shù)依賴賴, , 且是無且是無損分解損分解 B C A B B C 395.4.2 分解的無損連接性分解的無損連接性和保持函數(shù)依賴性和保持函數(shù)依賴性n如果一個(gè)分解具有無損連接性，則它能夠保證如果一個(gè)分解具有無損連接性，則它能夠保證不丟失信息。不丟失信息。n如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。或解決各種異常情況。n

39、分解具有無損連接性和分解保持函數(shù)依賴是兩分解具有無損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn)個(gè)互相獨(dú)立的標(biāo)準(zhǔn)。具有無損連接性的分解不。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。的分解也不一定具有無損連接性。40分解的無損連接性定義分解的無損連接性定義n定義記號(hào)定義記號(hào) mm ( r)( r)關(guān)系模式關(guān)系模式 R ，U = Ui ， =R1,R2, ,Rn是是R的一個(gè)分解，的一個(gè)分解，r 是是R的一個(gè)關(guān)系的一個(gè)關(guān)系, 定義：定義： m (r) = Ri(r) 是是r在在中各關(guān)系模式上投影的連接。這里，中

40、各關(guān)系模式上投影的連接。這里， Ri(r) =tUi|trn定義定義4.184.18 R(U, F) R(U, F)的一個(gè)分解的一個(gè)分解 是是無損連接分解：無損連接分解：r = mr = m (r) (r) 。ni1=1in= =41判無損連接性的方法判無損連接性的方法(chasechase過程過程) nP189.P189. 算法算法6.2 6.2 判別一個(gè)分解的無損連接性。判別一個(gè)分解的無損連接性。nP124P124. . 定理定理4.74.7 無損連接分解的充分必要條件無損連接分解的充分必要條件( (chasechase過程過程) ) 。n方法：構(gòu)造一個(gè)表格，根據(jù)函數(shù)依賴變化表方法：構(gòu)造一

41、個(gè)表格，根據(jù)函數(shù)依賴變化表格，能夠變出一行全為格，能夠變出一行全為a a，則是無損連接。則是無損連接。n用例子說明。用例子說明。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 DABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b

42、32b33a4a5考察考察D DE EABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5考察考察ABABC C制作制作5 5列列3 3行的表行的表 例例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, CD,DEC ,CEA

43、=(A, D), (A, B), (B, E), (C, D, E), (A, E) 是無損連接分解。是無損連接分解。ABCDEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53b54a5考察考察A AC CABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b33b34a5CDE b41b42a3a4a5AEa1b52b13b54a5制作制作5 5列列5 5行的表行的表下頁下頁44判無損連接分解判無損連接分解chasechase過程過程: 示例示例2續(xù)續(xù)考察考察B BC

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

45、a2a3a4a5CDEb41b42a3a4a5AEa1b52a3a4a5考察考察CECEA AABCDEADa1b12b13a4b15ABa1a2b13a4b25BEa1a2a3a4a5CDEa1b42a3a4a5AEa1b52a3a4a5F=AC, BC, CD,DEC ,CEA是無損連接分解是無損連接分解上頁上頁46判無損連接分解判無損連接分解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 分解分解=AD=AD，B

46、CBC，BDBD。 問：問：相對(duì)于相對(duì)于F F是否無損連接分解是否無損連接分解?(?(需畫出需畫出chasechase過程的示意圖過程的示意圖) )n答案：不是答案：不是無損連接分解。無損連接分解。n大家現(xiàn)場練習(xí)一下大家現(xiàn)場練習(xí)一下, ,判斷其結(jié)果。判斷其結(jié)果。分解為兩個(gè)關(guān)系模式的無損連接性判別分解為兩個(gè)關(guān)系模式的無損連接性判別n定理定理4.54.5. . 關(guān) 系 模 式關(guān) 系 模 式 RR 的 分 解的 分 解 = = R R1 1 U , , R R2 2U，則則 是是一個(gè)無損連接分解的充要條件是一個(gè)無損連接分解的充要條件是 U U1 1UU2 2U U1 1 U U2 2 或或 U U1

47、 1UU2 2U U2 2 U U1 1 成立。成立。n注注: : 對(duì)于定理對(duì)于定理4.54.5，有的課本上是這樣敘述：，有的課本上是這樣敘述：P124P124 如果如果R R有一個(gè)分解有一個(gè)分解=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) ) 成立。成立。48分解為兩個(gè)關(guān)系模式的無損連接分解為兩個(gè)關(guān)系模式的無損連接: 例例n例：設(shè)例：設(shè)R, U=A, B, C, F=AR, U=A, B, C, F=AB,

48、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 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不是

49、無損連不是無損連接分解。接分解。49分解為兩個(gè)關(guān)系模式的無損連接分解為兩個(gè)關(guān)系模式的無損連接: 練習(xí)練習(xí)n設(shè)關(guān)系模式設(shè)關(guān)系模式R(AR(A，B B，C C，D D，E E，P)P)，F(xiàn) 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解：因?yàn)榻猓阂驗(yàn)?R R1 1RR2 2 = E = E， R R1 1R R2 2 = AB = AB，而而 E EA A和和E EB B均成立均成立(

50、即即 R1R2 R1R2成立成立) ，所，所以以 是無損連接分解。是無損連接分解。50n定義定義4.19 保持函數(shù)依賴的模式分解。保持函數(shù)依賴的模式分解。 設(shè)設(shè)Z是是U的子集，函數(shù)依賴集合的子集，函數(shù)依賴集合F在在Z上的投影上的投影定義為：定義為：Z(F) = XY | XY F+ XY Z 設(shè)設(shè) = R1,R2,Rn 是關(guān)系模式是關(guān)系模式R的一個(gè)分解，的一個(gè)分解，如果如果 F+= ( Ri (F)+ ，則稱則稱 是保持函數(shù)依賴的分解。是保持函數(shù)依賴的分解。保持函數(shù)依賴的分解定義保持函數(shù)依賴的分解定義 n i =151保持函數(shù)依賴的分解保持函數(shù)依賴的分解: 例例n例：設(shè)關(guān)系模式例：設(shè)關(guān)系模式R

51、，U = C, S, Z, F = CS Z, Z C， = R1(S, Z), R2(C, Z) nR1R2 = Z, R2R1 = C R1R2 R2R1 ( 即即 Z C) 分解是無損的。分解是無損的。nR1(F) = ， R2(F) = Z C R1 (F) R2 (F) = Z C 丟失了函數(shù)依賴丟失了函數(shù)依賴 CS Z, 分解不保持函數(shù)依賴分解不保持函數(shù)依賴52保持函數(shù)依賴的分解保持函數(shù)依賴的分解: 判別法判別法n如何判斷分解保持函數(shù)依賴？如何判斷分解保持函數(shù)依賴？n引理引理4.3 給出了判別一個(gè)分解給出了判別一個(gè)分解是否保持函數(shù)依賴的方是否保持函數(shù)依賴的方法法 - FD集的覆蓋集

52、的覆蓋n例如，對(duì)于例如，對(duì)于(A, B, C)，AB , BC的分解的分解 ，顯然顯然, 丟失了函數(shù)依賴丟失了函數(shù)依賴: BCF+= ( Ri (F)+ n i =1534.4.3 關(guān)系模式分解的算法關(guān)系模式分解的算法n關(guān)于模式分解的幾個(gè)關(guān)于模式分解的幾個(gè)重要事實(shí)重要事實(shí):.n(1) 若要求分解保持函數(shù)依賴，則分解可以若要求分解保持函數(shù)依賴，則分解可以達(dá)到達(dá)到3NF，但不一定能達(dá)到但不一定能達(dá)到BCNF。n(2) 若要求分解既保持函數(shù)依賴若要求分解既保持函數(shù)依賴, 又具有無損又具有無損連接連接, 則可以達(dá)到則可以達(dá)到3NF, 但不一定能達(dá)到但不一定能達(dá)到BCNF。n(3) 若只要求分解無損連接

53、性若只要求分解無損連接性, 那一定可以達(dá)那一定可以達(dá)到到4NF。54關(guān)系模式分解的算法關(guān)系模式分解的算法nP191P191. . 算法算法6.36.3 ( (合成法合成法) ) 轉(zhuǎn)換為轉(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 達(dá)到達(dá)到4 4NFNF的具有無損連接性的的具有無損連接性的分解分解n后面用例說明。后面用例說明。55達(dá)到達(dá)到3NF保持依賴的分解保持依賴的分解: 例例1n設(shè)設(shè) U=S#，SD，MN，C#，G F=S