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

1、關(guān)于函數(shù)依賴的公理系統(tǒng)第一張，PPT共三十頁(yè)，創(chuàng)作于2022年6月 數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含定義: 對(duì)于滿足一組函數(shù)依賴 F 的關(guān)系模式R ，其任何一個(gè)關(guān)系r，若函數(shù)依賴XY都成立, 則稱F 邏輯蘊(yùn)含X Y第二張，PPT共三十頁(yè)，創(chuàng)作于2022年6月Armstrong公理系統(tǒng)從已知函數(shù)依賴集F要問(wèn)X Y是否為F邏輯蘊(yùn)含，就要一套推理規(guī)則，由Armstrong在1974年提出。這套推理規(guī)則，是模式分解算法的理論基礎(chǔ)。用途從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴。求給定關(guān)系模式的碼。第三張，PPT共三十頁(yè)，創(chuàng)作于2022年6月1. Armstrong公理系統(tǒng) 關(guān)系模式R 來(lái)說(shuō)有以下的推理規(guī)則：Al.自反

2、律（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第四張，PPT共三十頁(yè)，創(chuàng)作于2022年6月定理 Armstrong推理規(guī)則是正確的（l）自反律:若Y X U，則X Y為F所蘊(yùn)含證: 設(shè)Y X U 對(duì)R 的任一關(guān)系r中的任意兩個(gè)元組t，s：若tX=sX，由于Y X，有ty=sy，所以XY成立.自反律得證第五張，PPT共三十頁(yè)，創(chuàng)作

3、于2022年6月定理 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中任意的兩個(gè)元組t，s；若tXZ=sXZ，則有tX=sX和tZ=sZ；由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ為F所蘊(yùn)含.增廣律得證。第六張，PPT共三十頁(yè)，創(chuàng)作于2022年6月定理 Armstrong推理規(guī)則是正確的(3) 傳遞律：若XY及YZ為F所蘊(yùn)含，則 XZ為 F所蘊(yùn)含。證：設(shè)XY及YZ為F所蘊(yùn)含。對(duì)R 的任一關(guān)系 r中的任意兩個(gè)元組 t，s。若tX=sX，由于XY，有 tY=sY；再由YZ，

4、有tZ=sZ，所以XZ為F所蘊(yùn)含.傳遞律得證。第七張，PPT共三十頁(yè)，創(chuàng)作于2022年6月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）第八張，PPT共三十頁(yè)，創(chuàng)作于2022年6月導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理1 引理: XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）。第九張，PPT共三十頁(yè)，創(chuàng)作于2022年6月總結(jié):函數(shù)依賴(FD)的推理規(guī)則函數(shù)依賴有一個(gè)正確的和完

5、備的推理規(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成立，那么WXZ成立。 (6)分解律：如果XYZ成立， 那么XY,X Z成立。引理：X A1A2Ak成立的充分必要條件是X Ai(i=1,2K） 第十張，PPT共三

6、十頁(yè)，創(chuàng)作于2022年6月函數(shù)依賴?yán)P(guān)系模式R(A, B, C, G, H, I)，函數(shù)依賴集F=AB, AC, CGH, CGI, BH。我們可列出F中蘊(yùn)含的幾個(gè)依賴：由傳遞律可得AH，因?yàn)锳B且BH；由合并律可得CGHI，因?yàn)镃GH，CGI；由偽傳遞律可得AGI，因?yàn)锳C且CGI。還可以使用上述規(guī)則推導(dǎo)出更多的函數(shù)依賴，讀者可自行推導(dǎo)。第十一張，PPT共三十頁(yè)，創(chuàng)作于2022年6月3. 函數(shù)依賴閉包定義: 在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包，記為F+。定義: 設(shè)F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+

7、稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包第十二張，PPT共三十頁(yè)，創(chuàng)作于2022年6月關(guān)于閉包的引理引理: 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+用途 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問(wèn)題，就轉(zhuǎn)化為求出XF+ ，判定Y是否為XF+的子集的問(wèn)題(簡(jiǎn)單說(shuō)，求邏輯蘊(yùn)含只要通過(guò)求閉包就可以了。）第十三張，PPT共三十頁(yè)，創(chuàng)作于2022年6月函數(shù)依賴閉包函數(shù)依賴的閉包F+是指被F邏輯蘊(yùn)涵的函數(shù)依賴的全體構(gòu)成的集合函數(shù)依賴推理規(guī)則的完備性 函數(shù)依賴推理規(guī)則系統(tǒng)(自反律、增廣律和傳遞律)是完備的。由推理規(guī)則的完備性可得

8、到兩個(gè)重要結(jié)論： (1)屬性集X+ 中的每個(gè)屬性A，都有XA被F邏輯蘊(yùn)涵，即X+是所有由F邏輯蘊(yùn)含XA的屬性A的集合。 (2)F+是所有利用Amstrong推理規(guī)則從F導(dǎo)出的函數(shù)依賴的集合第十四張，PPT共三十頁(yè)，創(chuàng)作于2022年6月閉包的計(jì)算算法：求屬性集X關(guān)于函數(shù)依賴F的閉包X+方法：計(jì)算x（i）（I=0,1,）(1)x(0)=x;(2)x(i+1)=x(i)A其中A是這樣的屬性，在F中尋找尚未用過(guò)的左邊是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，

9、C 的一種即結(jié)束，否則轉(zhuǎn)（2） 第十五張，PPT共三十頁(yè)，創(chuàng)作于2022年6月閉包的計(jì)算例：在關(guān)系模式R（U，F(xiàn)）中，U=ABCDEF=AC，ACB，BD，CE，ECB 計(jì)算(EC)+ 。計(jì)算過(guò)程如下：(1) x(0)=EC(2) 檢查函數(shù)依賴，因 ECB ， X(1)=ECB=ECB (3)檢查函數(shù)依賴，因 BD，X(2)=ECBD=ECBD （4）X(3)= X(2)，所以(EC)+ =ECBD 第十六張，PPT共三十頁(yè)，創(chuàng)作于2022年6月 屬性集閉包計(jì)算舉例練習(xí) 已知R, U= (A, B, C, G, H, I)，F(xiàn)=AB, AC, CGH, CGI, BH，計(jì)算(AG)+。 算法第

10、一次循環(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。（也就是說(shuō)，AG可以決定右面的每一個(gè)屬性）第十七張，PPT共三十頁(yè)，創(chuàng)作于2022年6月計(jì)算屬性集閉包的作用計(jì)算屬性集閉包的作用可歸納如下：驗(yàn)證XY是否在F+中：看是否有YX+。判斷X是否為R的超碼：通過(guò)計(jì)算X+，看其是否包含R的所有屬性。例如，(AG)+ABCGHI，則AG為R的超碼。判斷X是否為R的候選碼：若X是超碼，可檢驗(yàn)X包含的所有子集的閉包是否包含R

11、的所有屬性。若不存在任何這樣的屬性子集，則X是R的候選碼。第十八張，PPT共三十頁(yè)，創(chuàng)作于2022年6月候選碼的判斷設(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 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？還是其他？思考！第十九張，PPT共三十頁(yè)，創(chuàng)作于2022年6月 屬性集閉包計(jì)算舉例 R=(U,F),其中,

12、U=A, B, C, D, F=A B, AC D;求A+,B+,C+,AC+;求R的侯選碼第二十張，PPT共三十頁(yè)，創(chuàng)作于2022年6月 屬性集閉包計(jì)算舉例 U=A, B, C, D; F=A B, AC D;A+ = AB.C+ = C.(AC)+ = ABCD.ACBD顯然，AC是候選碼思考：哪些屬性是L類？（只出現(xiàn)在函數(shù)依賴左邊）哪些是R類？哪些是LR類？哪些是N類？它們與候選碼有什么關(guān)系？第二十一張，PPT共三十頁(yè)，創(chuàng)作于2022年6月候選碼的作用例題：已知R(X,Y,Z),F=XYZ，請(qǐng)問(wèn)R為第幾范式？（請(qǐng)思考：解題的思路是什么？）XY為候選碼，R屬于BCNF。練習(xí)：R(W,X,Y

13、,Z),F=XZ,WXY，請(qǐng)問(wèn)R為第幾范式？第二十二張，PPT共三十頁(yè)，創(chuàng)作于2022年6月Armstrong公理系統(tǒng)的有效性與完備性Armstrong公理的完備性及有效性說(shuō)明:“蘊(yùn)含” = “導(dǎo)出” 等價(jià)的概念 F+ =由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴的集合第二十三張，PPT共三十頁(yè)，創(chuàng)作于2022年6月6. 函數(shù)依賴集等價(jià)定義: 如果G+=F+，就說(shuō)函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。第二十四張，PPT共三十頁(yè)，創(chuàng)作于2022年6月6. 最小依賴集 定義： 如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。

14、(1) F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價(jià)。 (3) F中不存在這樣的函數(shù)依賴XA， X有真 子集Z使得F-XAZA與F等價(jià)。 如果函數(shù)依賴集F和G等價(jià)，并且G是最小集，那么稱G是F的一個(gè)最小覆蓋。 第二十五張，PPT共三十頁(yè)，創(chuàng)作于2022年6月函數(shù)依賴集的等價(jià)和覆蓋求最小函數(shù)依賴集的方法：應(yīng)用分解規(guī)則，使F中每一個(gè)依賴的右部單一化。去掉各函數(shù)依賴左部多余的屬性。方法：檢查F中左邊是非單屬性的依賴，如： XYA，要判定Y是否多余，只要求X閉包，若X閉包A，則Y是多余的，以X Y 代替XYA。去掉多余的依賴。方法：從第一個(gè)依賴開(kāi)始

15、，若要從F中去掉X Y ，則在剩下的依賴中求X閉包，若X閉包包含Y,則去掉X Y 第二十六張，PPT共三十頁(yè)，創(chuàng)作于2022年6月最小依賴集或者：1。將函數(shù)依賴的右部分解為一個(gè)屬性；2。確保函數(shù)依賴左邊是不可分的；3。將具傳遞性的函數(shù)依賴去掉；如：假設(shè)一個(gè)關(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第二十七張，PPT共三十頁(yè)，創(chuàng)作于2022年6月求最小函數(shù)依賴集練習(xí)1 關(guān)系RA,B,C,D，有FD如下： F=ABC,C B,BC