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

1、關(guān)于函數(shù)依賴的公理系統(tǒng)第1頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四 數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含定義: 對于滿足一組函數(shù)依賴 F 的關(guān)系模式R ，其任何一個關(guān)系r，若函數(shù)依賴XY都成立, 則稱F 邏輯蘊(yùn)含X Y第2頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四Armstrong公理系統(tǒng)從已知函數(shù)依賴集F要問X Y是否為F邏輯蘊(yùn)含，就要一套推理規(guī)則，由Armstrong在1974年提出。這套推理規(guī)則，是模式分解算法的理論基礎(chǔ)。用途從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴。求給定關(guān)系模式的碼。第3頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四1. Armstrong

2、公理系統(tǒng) 關(guān)系模式R 來說有以下的推理規(guī)則：Al.自反律（Reflexivity）： 若Y X U，則X Y為F所蘊(yùn)含。A2.增廣律（Augmentation）：若XY為F所蘊(yùn)含，且Z U，則XZYZ為F所蘊(yùn)含。A3.傳遞律（Transitivity）：若XY及YZ為F所蘊(yùn)含，則XZ為F所蘊(yùn)含。注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F第4頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四定理 Armstrong推理規(guī)則是正確的（l）自反律:若Y X U，則X Y為F所蘊(yùn)含證: 設(shè)Y X U 對R 的任一關(guān)系r中的任意兩個元組t，s：若tX=sX，由于Y

3、 X，有ty=sy，所以XY成立.自反律得證第5頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四定理 Armstrong推理規(guī)則是正確的(2)增廣律: 若XY為F所蘊(yùn)含，且Z U，則XZYZ 為F所蘊(yùn)含。 證：設(shè)XY為F所蘊(yùn)含，且Z U。 設(shè)R 的任一關(guān)系r中任意的兩個元組t，s；若tXZ=sXZ，則有tX=sX和tZ=sZ；由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ為F所蘊(yùn)含.增廣律得證。第6頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四定理 Armstrong推理規(guī)則是正確的(3) 傳遞律：若XY及YZ為F所蘊(yùn)含，則 XZ為 F所蘊(yùn)含。證：設(shè)XY及YZ

4、為F所蘊(yùn)含。對R 的任一關(guān)系 r中的任意兩個元組 t，s。若tX=sX，由于XY，有 tY=sY；再由YZ，有tZ=sZ，所以XZ為F所蘊(yùn)含.傳遞律得證。第7頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四2. 導(dǎo)出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有XYZ。 （A2， A3） 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 （A2， A3） 分解規(guī)則：由XY及 ZY，有XZ。 （A1， A3）第8頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理1 引理: XA1 A2Ak成立的

5、充分必要條件是XAi成立（i=l，2，k）。第9頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四總結(jié):函數(shù)依賴(FD)的推理規(guī)則函數(shù)依賴有一個正確的和完備的推理規(guī)則集Armstrong 推理規(guī)則： 設(shè)有關(guān)系模式R(U)，X，Y，Z，W均是U的子集，F(xiàn)是R上只涉及到U中屬性的函數(shù)依賴集， 推理規(guī)則如下： (1)自反律：如果Y X U,則XY在R上成立。 (2)增廣律：如果XY為F所蘊(yùn)涵，Z U，則XZYZ在R上成立。 (XZ表示XZ，下同) (3)傳遞律：如果XY和YZ在R上成立，則XZ在R上成立。 (4)合并律：如果XY和XZ成立，那么XYZ成立。 (5)偽傳遞律：如果XY和WYZ成

6、立，那么WXZ成立。 (6)分解律：如果XYZ成立， 那么XY,X Z成立。引理：X A1A2Ak成立的充分必要條件是X Ai(i=1,2K） 第10頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四函數(shù)依賴?yán)P(guān)系模式R(A, B, C, G, H, I)，函數(shù)依賴集F=AB, AC, CGH, CGI, BH。我們可列出F中蘊(yùn)含的幾個依賴：由傳遞律可得AH，因?yàn)锳B且BH；由合并律可得CGHI，因?yàn)镃GH，CGI；由偽傳遞律可得AGI，因?yàn)锳C且CGI。還可以使用上述規(guī)則推導(dǎo)出更多的函數(shù)依賴，讀者可自行推導(dǎo)。第11頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四3. 函數(shù)依

7、賴閉包定義: 在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包，記為F+。定義: 設(shè)F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包第12頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四關(guān)于閉包的引理引理: 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+用途 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+ ，判定Y是否為XF+的子集的問題(簡單說，求邏輯蘊(yùn)含只要通過求閉包就可以了。）第1

8、3頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四函數(shù)依賴閉包函數(shù)依賴的閉包F+是指被F邏輯蘊(yùn)涵的函數(shù)依賴的全體構(gòu)成的集合函數(shù)依賴推理規(guī)則的完備性 函數(shù)依賴推理規(guī)則系統(tǒng)(自反律、增廣律和傳遞律)是完備的。由推理規(guī)則的完備性可得到兩個重要結(jié)論： (1)屬性集X+ 中的每個屬性A，都有XA被F邏輯蘊(yùn)涵，即X+是所有由F邏輯蘊(yùn)含XA的屬性A的集合。 (2)F+是所有利用Amstrong推理規(guī)則從F導(dǎo)出的函數(shù)依賴的集合第14頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四閉包的計(jì)算算法：求屬性集X關(guān)于函數(shù)依賴F的閉包X+方法：計(jì)算x（i）（I=0,1,）(1)x(0)=x;(2)x

9、(i+1)=x(i)A其中A是這樣的屬性，在F中尋找尚未用過的左邊是x(i)子集的函數(shù)依賴（3）判斷是否有A：x(i+1)=x(i);B:若在x(i+1)已包含了F中的全部屬性；C：x(i+1) x(i)，但x(i+1)的左部屬性依賴已使用完出現(xiàn)A，B，C 的一種即結(jié)束，否則轉(zhuǎn)（2） 第15頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四閉包的計(jì)算例：在關(guān)系模式R（U，F(xiàn)）中，U=ABCDEF=AC，ACB，BD，CE，ECB 計(jì)算(EC)+ 。計(jì)算過程如下：(1) x(0)=EC(2) 檢查函數(shù)依賴，因 ECB ， X(1)=ECB=ECB (3)檢查函數(shù)依賴，因 BD，X(2)=

10、ECBD=ECBD （4）X(3)= X(2)，所以(EC)+ =ECBD 第16頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四 屬性集閉包計(jì)算舉例練習(xí) 已知R, U= (A, B, C, G, H, I)，F(xiàn)=AB, AC, CGH, CGI, BH，計(jì)算(AG)+。 算法第一次循環(huán)的執(zhí)行步驟： 步驟 FD closure 1 初值 AG 2 AB ABG 3 AC ABCG 4 CGH ABCGH 6 CGI ABCGHI 6 BH ABCGHI 結(jié)果為closure=ABCGHI。(AG)+ABCGHI。（也就是說，AG可以決定右面的每一個屬性）第17頁，共30頁，2022年

11、，5月20日，10點(diǎn)59分，星期四計(jì)算屬性集閉包的作用計(jì)算屬性集閉包的作用可歸納如下：驗(yàn)證XY是否在F+中：看是否有YX+。判斷X是否為R的超碼：通過計(jì)算X+，看其是否包含R的所有屬性。例如，(AG)+ABCGHI，則AG為R的超碼。判斷X是否為R的候選碼：若X是超碼，可檢驗(yàn)X包含的所有子集的閉包是否包含R的所有屬性。若不存在任何這樣的屬性子集，則X是R的候選碼。第18頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四候選碼的判斷設(shè)有關(guān)系R(A1,A2,An,F)，F(xiàn)為R的函數(shù)依賴集，X為R的屬性組，若X滿足：1 X A1,A2,An，即X+=A1,A2,An2 不存在X的真子集Y，Y

12、 A1,A2,An。則稱X為R的碼例：關(guān)系RA,B,C,D，有FD如下：F=ABC,C B,BC D,ACD B，R的碼為？AB+=ABCD,AC+=ABCD,ACD+=ABCD,候選碼為：AB，ACD;還是AB,AC？還是其他？思考！第19頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四 屬性集閉包計(jì)算舉例 R=(U,F),其中,U=A, B, C, D, F=A B, AC D;求A+,B+,C+,AC+;求R的侯選碼第20頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四 屬性集閉包計(jì)算舉例 U=A, B, C, D; F=A B, AC D;A+ = AB.C+ =

13、C.(AC)+ = ABCD.ACBD顯然，AC是候選碼思考：哪些屬性是L類？（只出現(xiàn)在函數(shù)依賴左邊）哪些是R類？哪些是LR類？哪些是N類？它們與候選碼有什么關(guān)系？第21頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四候選碼的作用例題：已知R(X,Y,Z),F=XYZ，請問R為第幾范式？（請思考：解題的思路是什么？）XY為候選碼，R屬于BCNF。練習(xí)：R(W,X,Y,Z),F=XZ,WXY，請問R為第幾范式？第22頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四Armstrong公理系統(tǒng)的有效性與完備性Armstrong公理的完備性及有效性說明:“蘊(yùn)含” = “導(dǎo)出” 等價

14、的概念 F+ =由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴的集合第23頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四6. 函數(shù)依賴集等價定義: 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。第24頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四6. 最小依賴集 定義： 如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部僅含有一個屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價。 (3) F中不存在這樣的函數(shù)依賴XA， X有真 子集Z使得F-X

15、AZA與F等價。 如果函數(shù)依賴集F和G等價，并且G是最小集，那么稱G是F的一個最小覆蓋。 第25頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四函數(shù)依賴集的等價和覆蓋求最小函數(shù)依賴集的方法：應(yīng)用分解規(guī)則，使F中每一個依賴的右部單一化。去掉各函數(shù)依賴左部多余的屬性。方法：檢查F中左邊是非單屬性的依賴，如： XYA，要判定Y是否多余，只要求X閉包，若X閉包A，則Y是多余的，以X Y 代替XYA。去掉多余的依賴。方法：從第一個依賴開始，若要從F中去掉X Y ，則在剩下的依賴中求X閉包，若X閉包包含Y,則去掉X Y 第26頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四最小依賴集或

16、者：1。將函數(shù)依賴的右部分解為一個屬性；2。確保函數(shù)依賴左邊是不可分的；3。將具傳遞性的函數(shù)依賴去掉；如：假設(shè)一個關(guān)系R中具有屬性A、B、C、D。 F=ABC,B C,A B,AB C,AC D解： （1）ABC分解為AB， AC； （2）由 AC知AB C是冗余的，去掉； A C得A AC，而 AC D，則A D，所以， AC D冗余。 （3） AC可由AB， BC得，所以AC要去掉。得到R的最小依賴集F=AB，BC，AD第27頁，共30頁，2022年，5月20日，10點(diǎn)59分，星期四求最小函數(shù)依賴集練習(xí)1 關(guān)系RA,B,C,D，有FD如下： F=ABC,C B,BC D,ACD B。求F的