函數依賴的公理系統

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

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

3、閉包F+n定義定義4.12 在關系模式在關系模式R中，中，被被F所所邏輯蘊涵的函數依賴的全體所構成的集合稱邏輯蘊涵的函數依賴的全體所構成的集合稱作作F的的閉包閉包，記作，記作 F+ = XY | F XYn顯然，顯然，F F F F+ + 。nF+的計算很麻煩，的計算很麻煩，F不大，其不大，其F+也可能很大。也可能很大。 例如：例如：設設 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公理系統公理系統n函數依賴公理系統由函數依賴公理系統由ArmstrongArmstrong于于19741974年首先提出。年首先提出。n設關系模式設關系模式 RR，U U為屬性全集，為屬性全集，F F是是U U上的一上的一組函數依賴，組函數依賴，X X、Y Y、Z Z是是U U的屬性子集，對的屬性子集，對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注意注意: : 由由自反律自反律所得到的函數依賴是所得到的函數依賴是平凡的平凡的, , 自反律的自反律的使用并不依賴于函數依賴集使用并不依賴于函數依賴集F F。傳遞律與傳遞依賴傳遞律與傳遞依賴？所得到的函數依賴是所得到的函數依賴是不平凡的。不平凡的。5A公理系統的正確性和完備性公理系統的正確性和完備性nArmstrongArmstrong公理的正確性公理的正確性( (即有效

6、性即有效性) )及完備性。及完備性。n正確性正確性：用：用ArmstrongArmstrong公理從公理從F F中導出的函數依賴中導出的函數依賴必為必為F F所蘊涵。所蘊涵。n完備性完備性：被：被F F所蘊涵的函數依賴都能用所蘊涵的函數依賴都能用ArmstrongArmstrong公理從公理從F F中導出。中導出。n公理的正確性公理的正確性保證由保證由F F出發(fā)根據公理推導出的每一個出發(fā)根據公理推導出的每一個函數依賴一定在函數依賴一定在F F+ +中。中。n公理的完備性公理的完備性保證用公理能推出所有的函數依賴保證用公理能推出所有的函數依賴, , 即即F F+ +中的所有函數依賴都能由中的所有

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

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公理系統：增廣律證明公理系統：增廣律證明tXZ = sXZtX = sXXYtY = sYtXZ = sXZtZ = sZtYZ = sYZXZYZ增廣律(2) (2) 證明增廣律證明增廣律: : 若若 X X Y Y， 則則 XZ XZ YZ YZ。 設設 tXZ=sXZ, tXZ=sXZ, 則有則有tX=sXtX=sX和和tZ=sZ

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

10、tZ=sZ,tZ=sZ, 所以所以 X X Z Z 成立。成立。.9A公理系統：推論公理系統：推論n由由ArmstrongArmstrong公理導出的公理導出的推理規(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證明：用數學歸納法證明。證明：用數學歸納法證明。 “ ”由由合并律合并律證明；證明； “”由由分解律分解律證明。證明。10A公理系統公理系統: 例例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邏輯蘊涵以下函數依賴嗎？邏輯蘊涵以下函數依賴嗎？ 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公理系統的完備性公理系統的完備性nArmstrong公理系統是有效的公理系統是有效的、完備的。完備的。n有效性即正確性有效性即正確性：由：由F出發(fā)根據出發(fā)根據Armstrong公理推公理推導出來的每一個函數依賴一定在導出來的每一個函數依賴一定在F+中，中，

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

14、C； BF+ = B，C CF+ = CFXFXn設設F為屬性集為屬性集U上的一組函數依賴，上的一組函數依賴，X U， = A | XA能由能由F根據根據Armstrong公理導出公理導出 稱稱 為為屬性集屬性集X關于函數依賴集關于函數依賴集F的的閉包閉包。n 是由是由X所能函數決定的所能函數決定的全體屬性全體屬性的的集合集合。n定義定義4.13 屬性集的閉包屬性集的閉包.FXFXFX13屬性集閉包引理屬性集閉包引理n引理引理4.2 XY能從能從F出發(fā)由出發(fā)由A公理導出公理導出 Y FXFXn注意：注意：引理引理4.2給出了判斷一個函數依賴給出了判斷一個函數依賴XY能否能否從從F出發(fā)由出發(fā)由A

15、公理導出公理導出的方法的方法，即判，即判斷是否有斷是否有Y n例：例：設設U =A，B，C，F =AB，BC要判斷函數依賴要判斷函數依賴AC是否成立，只要判斷是是否成立，只要判斷是否有否有C AF+，而而AF+ =A，B，C，故故AC 成立。成立。14A公理系統公理系統: 完備性的證明完備性的證明n定理定理4.24.2 Armstrong Armstrong公理是有效的、完備的。公理是有效的、完備的。n證明：證明：n有效性的證明，見定理有效性的證明，見定理4.14.1的證明。的證明。n完備性的證明。完備性的證明。n完備性的證明是構造性的證明。完備性的證明是構造性的證明。n證明完備性的逆否命題：

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

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

18、n F dobegin if A then := BendFXFXFXFXFXFX開始開始：FX17屬性集閉包的計算屬性集閉包的計算: 示例示例n設設 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 FA18屬性集閉包的計算屬性集閉包的計算: 練習練習n設有設有 R，

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

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

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

22、. 無冗余性無冗余性：逐個檢查：逐個檢查 F中各函數依賴中各函數依賴 XA, 判判XA是否冗余是否冗余，令，令G = F XA ，若若 A XG+ ，則則XA是冗余是冗余, 從從 F 中去掉該函數依賴。中去掉該函數依賴。 3. 既約性既約性：逐個檢查：逐個檢查 F 中各函數依賴中各函數依賴 XA，X是多屬是多屬性，設性，設 X=B1Bm, 逐個考查逐個考查 Bi , 判判 Bi 是否多余是否多余, 若若A (XBi)F+ ，則則 Bi 是冗余是冗余, 以以 (X Bi) 取代取代 X。計算最小覆蓋計算最小覆蓋Fmin: 算法算法22計算最小覆蓋計算最小覆蓋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)(實際上，因為有實際上，因為有A AB B，B BC C， 從而從而 A AC C冗余冗余于是：于是： Fmin = AB，BA，BC23計算最小覆蓋計算最小覆蓋Fmin: 例例1(續(xù)續(xù))nF = AB，BA，AC，BC，求求Fmin已經求出：已

24、經求出： Fmin = AB，BA，BC也可以是以下結果：也可以是以下結果：Fmin = AB，BA，ACn注意注意: 函數依賴集的最小依賴集可能不唯一。函數依賴集的最小依賴集可能不唯一。與考察的函數依賴的順序有關。與考察的函數依賴的順序有關。24計算最小覆蓋計算最小覆蓋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 得，得，Fmin = AG，CB，BA25計算最小覆蓋計算最小覆蓋Fmin: 例例3 F = AB, BA，BC，AC，CA，求求Fmin 。n已經是單屬性的已經是單屬性的, 既約性的既約性的, 只檢查冗余性。只檢查冗余性。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計算最小覆蓋計算最小覆蓋Fmin: 練習練習n設設 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補充：候選碼的求解算法補充：候選碼的

27、求解算法 設關系模式設關系模式RRn(1) (1) 將將R R的所有屬性分為的所有屬性分為 L L、 R R、NN和和 LRLR四類，四類，并令并令X X代表代表L L、NN兩類，兩類，Y Y代表代表LRLR類。類。 L類類: 僅出現在僅出現在F的函數依賴左部的屬性；的函數依賴左部的屬性； R類類: .右右； N類類: 在在F的函數依賴左右兩邊都不出現的屬性；的函數依賴左右兩邊都不出現的屬性； LR類類: 都出現的屬性都出現的屬性 。 n(2) (2) 求屬性集閉包求屬性集閉包X X+ +，若若 X X+ +包含了包含了R R的全部屬的全部屬性則性則X X即為即為R R的唯一候選碼的唯一候選碼

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

29、集閉包，直到其閉包包含們的屬性集閉包，直到其閉包包含R R的全部屬的全部屬性。性。 (5) (5) 停止，輸出結果。停止，輸出結果。29候選碼的求解：例候選碼的求解：例1n設關系模式設關系模式R(A, B, C, D), R(A, B, C, D), 其函數依賴集：其函數依賴集： 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因為因為( (AC)AC)F F+ +=ACDB=ACDB，所以所以ACAC是是

30、R R的唯一候選的唯一候選碼。碼。30候選碼的求解：例候選碼的求解：例2n設關系模式設關系模式R(A, B, C, D, E, P), R(A, B, C, D, E, P), 其函數依賴集：其函數依賴集： 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因為因為( (CEP)CEP)F F+ +=CEPDBA=CEPDBA，所以所以CEPCEP是是R R的唯一的唯一候選碼

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

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

33、損連接又保持函數依賴的分解的既無損連接又保持函數依賴的分解n轉換為轉換為BCNF的無損連接分解的無損連接分解n達到達到4NF的具有無損連接性的分解的具有無損連接性的分解33模式的分解：兩個記號模式的分解：兩個記號 n定義定義5.165.16 關系模式關系模式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， F Fi i是是F F在在U Ui i上的投影。上的投影。n定義定義5.175.17 函數依賴集合函數依賴集合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 模式分解的三個定義模式分解的三個定義n對一個模式的對一個模式的分解是不唯一分解是不唯一的，但是的，但是分解前分解前后的兩個模式應等價。后的兩個模式應等價。n對對“等價等價”的概念有三種不同的定義的概念有三種不同的定義( (也稱分也稱分解的標準、分解的特性或分解的目標解的標準、分解的特性或分解的目標): ):1. 1. 分解具有分解具有無損連接性無損連接性( (Lossless join)Lossless join)；2. 2. 分解

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

36、義，分離后的關系對不同的分解等價定義，分離后的關系模式的范式級別。模式的范式級別。n(3) (3) 如何實現分離，分解的算法。如何實現分離，分解的算法。模式分解中的問題模式分解中的問題: 有損分解有損分解R(A, B, C)ABC112221AB1122BC1221ABC112221AB(R)BC(R)AB(R)BC(R)R(A, B, C)ABC111212AB1121BC1112ABC111112211212AB(R)BC(R)AB(R)BC(R)有損分解有損分解無損分解無損分解模式分解中的問題模式分解中的問題: 不保持函數依賴不保持函數依賴ABCa1b1c1a2b1c1a3b2c2a4b

37、3c1A B, B CAa1a2a3a4Bb1b2b3Cc1c2各列值ABa1b1a2b1a3b2a4b3ACa1c1a2c1a3c2a4c1=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, 且是有損分且是有損分解解該分解保該分解保持函數依持函數依賴賴, , 且是無且是無損分解損分解 B C A B B C 395.4.2 分解的無損連接性分解的無損連接性和保持函數依賴性和保持函數依賴性n如果一個分解具有無損連接性，則它能夠保證如果一個分解具有無損連接性，則它能夠保證不丟失信息。不丟失信息。n如果一個分解保持了函數依賴，則它可以減輕如果一個分解保持了函數依賴，則它可以減輕或解決各種異常情況?；蚪鉀Q各種異常情況。n

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

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

41、個表格，根據函數依賴變化表格，能夠變出一行全為格，能夠變出一行全為a a，則是無損連接。則是無損連接。n用例子說明。用例子說明。n例例5:5: 設設 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設設 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過程過程: 練習練習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。 問：問：相對于相對于F F是否無損連接分解是否無損連接分解?(?(需畫出需畫出chasechase過程的示意圖過程的示意圖) )n答案：不是答案：不是無損連接分解。無損連接分解。n大家現場練習一下大家現場練習一下, ,判斷其結果。判斷其結果。分解為兩個關系模式的無損連接性判別分解為兩個關系模式的無損連接性判別n定理定理4.54.5. . 關 系 模 式關 系 模 式 RR 的 分 解的 分 解 = = R R1 1 U , , R R2 2U，則則 是是一個無損連接分解的充要條件是一個無損連接分解的充要條件是 U U1 1UU2 2U U1 1 U U2 2 或或 U U1

47、 1UU2 2U U2 2 U U1 1 成立。成立。n注注: : 對于定理對于定理4.54.5，有的課本上是這樣敘述：，有的課本上是這樣敘述：P124P124 如果如果R R有一個分解有一個分解=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分解為兩個關系模式的無損連接分解為兩個關系模式的無損連接: 例例n例：設例：設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分解為兩個關系模式的無損連接分解為兩個關系模式的無損連接: 練習練習n設關系模式設關系模式R(AR(A，B B，C C，D D，E E，P)P)，F F是是R R上成上成立的立的FDFD集，集，F=ABF=AB，CPCP，EAEA，CEDCED。設有分解：設有分解： =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均成立均成立(

50、即即 R1R2 R1R2成立成立) ，所，所以以 是無損連接分解。是無損連接分解。50n定義定義4.19 保持函數依賴的模式分解。保持函數依賴的模式分解。 設設Z是是U的子集，函數依賴集合的子集，函數依賴集合F在在Z上的投影上的投影定義為：定義為：Z(F) = XY | XY F+ XY Z 設設 = R1,R2,Rn 是關系模式是關系模式R的一個分解，的一個分解，如果如果 F+= ( Ri (F)+ ，則稱則稱 是保持函數依賴的分解。是保持函數依賴的分解。保持函數依賴的分解定義保持函數依賴的分解定義 n i =151保持函數依賴的分解保持函數依賴的分解: 例例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 丟失了函數依賴丟失了函數依賴 CS Z, 分解不保持函數依賴分解不保持函數依賴52保持函數依賴的分解保持函數依賴的分解: 判別法判別法n如何判斷分解保持函數依賴？如何判斷分解保持函數依賴？n引理引理4.3 給出了判別一個分解給出了判別一個分解是否保持函數依賴的方是否保持函數依賴的方法法 - FD集的覆蓋集

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

53、性若只要求分解無損連接性, 那一定可以達那一定可以達到到4NF。54關系模式分解的算法關系模式分解的算法nP191P191. . 算法算法6.36.3 ( (合成法合成法) ) 轉換為轉換為3 3NFNF的保持函的保持函數依賴的分解。數依賴的分解。nP191P191. . 算法算法6.46.4 轉換為轉換為3 3NFNF既有無損連接性又既有無損連接性又保持函數依賴的分解。保持函數依賴的分解。nP192P192. . 算法算法6.56.5 轉換為轉換為BCNFBCNF的無損連接分解的無損連接分解( (分解法分解法) )。nP192P192. . 算法算法6.66.6 達到達到4 4NFNF的具有無損連接性的的具有無損連接性的分解分解n后面用例說明。后面用例說明。55達到達到3NF保持依賴的分解保持依賴的分解: 例例1n設設 U=S#，SD，MN，C#，G F=S