函數(shù)依賴的邏輯蘊涵.doc

一、函數(shù)依賴的邏輯蘊涵定義：設(shè)有關(guān)系模式R(U)及其函數(shù)依賴集F，如果對于R的任一個滿足F的關(guān)系r函數(shù)依賴XY都成立，則稱F邏輯蘊涵XY，或稱XY可以由F推出。例：關(guān)系模式 R=(A,B,C),函數(shù)依賴集F=AB,BC, F邏輯蘊涵AC。證：設(shè)u,v為r中任意兩個元組： 若AC不成立，則有uA=vA,而uCvC 而且AB, BC,知 uA=vA, uB=vB, uC=vC, 即若uA=vA則uC=vC，和假設(shè)矛盾。 故F邏輯蘊涵AC。滿足F依賴集的所有元組都函數(shù)依賴XY（XY不屬于F集），則稱F邏輯蘊涵XY（XY由F依賴集中所有依賴關(guān)系推斷而出）二、Armstrong公理1、定理：若U為關(guān)系模式R的屬性全集，F(xiàn)為U上的一組函數(shù)依賴，設(shè)X、Y、Z、W均為R的子集，對R(U,F)有： F1(自反性)：若XY(表X包含Y），則XY為F所蘊涵；(F1:XX) F2(增廣性): 若XY為F所蘊涵，則XZYZ為F所蘊涵；(F2:XZY) F3(傳遞性): 若XY,YZ為F所蘊涵，則XZ為F所蘊涵； F4(偽增性)：若XY，WZ(表W包含Z）為F所蘊涵，則XWYZ為F所蘊涵； F5(偽傳性): 若XY，YWZ為F所蘊涵, 則XWZ為F所蘊涵； F6(合成性): 若XY,XZ為F所蘊涵，則XYZ為F所蘊涵； F7(分解性): 若XY,ZY (表Z包含于Y）為F所蘊涵，則XZ為F所蘊涵。 函數(shù)依賴推理規(guī)則F1F7都是正確的。2、Armstrong公理：推理規(guī)則F1、F2、F3合稱Armstrong公理；F4 F7可由F1、F2、F3推得，是Armstrong公理的推論部分。三、函數(shù)依賴的閉包定義：若F為關(guān)系模式R(U)的函數(shù)依賴集，我們把F以及所有被F邏輯蘊涵的函數(shù)依賴的集合稱為F的閉包，記為F+。即：F+=XY|XYF“應(yīng)用Armstong公理從F中導(dǎo)出的任何XY” F包含于F+，如果F=F+，則F為函數(shù)依賴的一個完備集。 規(guī)定：若X為U的子集，X 屬于F+。 例：R=ABC,F=AB, BC, 求F+ 解： F+ =A,AB,AC,ABC,B,C, AA,ABA,ACA,ABCA,BB,CC, AB,ABB,ACB,ABCB,BC, AC,ABC,ACC,ABCC,BBC, AAB,ABAB,ACAB,ABCAB,BC, AAC,ABAC,ACAC,ABCAC,BCB, ABC,ABBC,ACBC,ABCBC,BCC, AABC,ABABC,ACABC,ABCA,BCBC 例：已知關(guān)系模式R中 U=A，B，C，D, E, G, F=ABC, CA, BCD, ACDB, DEG, BEC, CGBD, CEAG,判斷BDAC是否屬于F+ 解：由DEG知DE，BDBE 又知BEC，CA 所以BEA, BEAC 由、知，BDAC，所以BDAC被F所蘊涵，即BDAC屬于F+ 例：已知關(guān)系模式R中 U=A，B，C，E, H, P, G, F=ACPE, PGA, BCE, AP, GAB, GCA, PABG, AEGB, ABCPH,證明BGHE屬于F+ 證：由BCE知BC，BE, BGGC 又知GCA，AP 所以BGA, BGABCP 又ABCPH，由、知BGHE，所以BGHE被F所蘊涵， 即BGHE屬于F+四、屬性集閉包1、定義：若F為關(guān)系模式R(U)的函數(shù)依賴集，X是U的子集，則由Armstrong公理推導(dǎo)出的所有XAi所形成的屬性集例：設(shè)R=ABC,F=AB, BC當X分別為A,B,C是求X+。解：當X=A時，X+=ABC 當X=B時，X+=BC 當X=C時，X+=C* X代表的屬性集可以決定的屬性集（包括本身）2、定理：當且僅當Y屬于X+時，XY能根據(jù)Armstron公理由F導(dǎo)出。證：設(shè)Y=A1,A2,An 充分條件：當Y屬于X+時,對于每個i,XAi可由公理導(dǎo)出。 再用合并規(guī)則可得XY。 必要條件：若XY能夠由公理導(dǎo)出,則根據(jù)分解規(guī), XAi(i=1,2,n)成立，所以Y屬于X+。3、計算X+(1)算法依據(jù)：若F為關(guān)系模式R(U)的函數(shù)依賴集,X,Z,W是U的子集,對于任意的ZWF,若 XZ（表X包含Z）,則XXW。(2)算法：a.令X+ = X;b.在F中依次查找每個沒有被標記的函數(shù)依賴，若“左邊屬性集”包含于X+ ，則令 X+ = X+“右邊屬性集”,為被訪問過的函數(shù)依賴設(shè)置訪問標記。c.反復(fù)執(zhí)行b直到X+不改變?yōu)橹?。（先令X+等于本身，然后在F+中依次查找左邊包含于X+的屬性，把其右邊的對應(yīng)屬性并到X中）(3)算法實現(xiàn) 輸入：關(guān)系模式R的子集X,R上的函數(shù)依賴集F。 輸出：X關(guān)于F的閉包X+算法偽語言描述：Closure(X,F) olds=; news=X; G=F; while (olds!=news) olds=news; for (G中的每個函數(shù)依賴WZ) if (news包含W) news=newsZ; 從G中刪除函數(shù)依賴WZ; return news;例：已知關(guān)系模式R中U=A，B，C，D, E, G,F=ABC, CA, BCD, ACDB, DEG, BEC, CGBD, CEAG,求(BD)+，判斷BDAC是否屬于F+解：X+=BDEGCA結(jié)論：(BD)+=ABCDEG,BDAC可由F導(dǎo)出，即BDAC屬于F+例：已知關(guān)系模式R中U=A，B，C，E, H, P, G,F=ACPE, PGA, BCE, AP, GAB,GCA, PABG, AEGB, ABCPH,證明BGHE屬于F+證：因為,(BG)+ =ABCEHPG,所以BGHE可由F導(dǎo)出，即BGHE屬于F+4、結(jié)論判定函數(shù)依賴XY是否能由F導(dǎo)出的問題，可轉(zhuǎn)化為求X+并判定Y是否是X+子集的問題。即求閉包問題可轉(zhuǎn)化為求屬性集問題。判定給定函數(shù)依賴XY是否蘊涵于函數(shù)依賴