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

關于函數(shù)依賴的公理系統(tǒng)第一頁，共三十頁，2022年，8月28日數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊含 定義:對于滿足一組函數(shù)依賴F的關系模式R<U，F(xiàn)>，其任何一個關系r，若函數(shù)依賴X→Y都成立,則稱F邏輯蘊含X→Y第二頁，共三十頁，2022年，8月28日Armstrong公理系統(tǒng)從已知函數(shù)依賴集F要問X→Y是否為F邏輯蘊含，就要一套推理規(guī)則，由Armstrong在1974年提出。這套推理規(guī)則，是模式分解算法的理論基礎。用途從一組函數(shù)依賴求得蘊含的函數(shù)依賴。求給定關系模式的碼。第三頁，共三十頁，2022年，8月28日1.Armstrong公理系統(tǒng)關系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：Al.自反律（Reflexivity）：若Y

X

U，則X→Y為F所蘊含。A2.增廣律（Augmentation）：若X→Y為F所蘊含，且Z

U，則XZ→YZ為F所蘊含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含。

注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F第四頁，共三十頁，2022年，8月28日定理Armstrong推理規(guī)則是正確的（l）自反律:若Y

X

U，則X→Y為F所蘊含證:設Y

X

U

對R<U，F(xiàn)>的任一關系r中的任意兩個元組t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得證第五頁，共三十頁，2022年，8月28日定理Armstrong推理規(guī)則是正確的(2)增廣律:若X→Y為F所蘊含，且Z

U，則XZ→YZ為F所蘊含。證：設X→Y為F所蘊含，且Z

U。設R<U，F(xiàn)>的任一關系r中任意的兩個元組t，s；若t[XZ]=s[XZ]，則有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ為F所蘊含.增廣律得證。第六頁，共三十頁，2022年，8月28日定理Armstrong推理規(guī)則是正確的(3)傳遞律：若X→Y及Y→Z為F所蘊含，則

X→Z為F所蘊含。證：設X→Y及Y→Z為F所蘊含。對R<U，F(xiàn)>的任一關系r中的任意兩個元組t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊含.傳遞律得證。第七頁，共三十頁，2022年，8月28日2.導出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則：

合并規(guī)則：由X→Y，X→Z，有X→YZ。（A2，A3）

偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。（A2，A3）

分解規(guī)則：由X→Y及ZY，有X→Z。（A1，A3）第八頁，共三十頁，2022年，8月28日導出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理1

引理:X→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。第九頁，共三十頁，2022年，8月28日總結(jié):函數(shù)依賴(FD)的推理規(guī)則函數(shù)依賴有一個正確的和完備的推理規(guī)則集——Armstrong推理規(guī)則：設有關系模式R(U)，X，Y，Z，W均是U的子集，F(xiàn)是R上只涉及到U中屬性的函數(shù)依賴集，推理規(guī)則如下：(1)自反律：如果YXU,則X→Y在R上成立。(2)增廣律：如果X→Y為F所蘊涵，ZU，則XZ→YZ在R上成立。(XZ表示X∪Z，下同)(3)傳遞律：如果X→Y和Y→Z在R上成立，則X→Z在R上成立。(4)合并律：如果X→Y和X→Z成立，那么X→YZ成立。(5)偽傳遞律：如果X→Y和WY→Z成立，那么WX→Z成立。(6)分解律：如果X→YZ成立，那么X→Y,X→Z成立。引理：X→A1A2……Ak成立的充分必要條件是X→Ai(i=1,2……K）第十頁，共三十頁，2022年，8月28日函數(shù)依賴[例]關系模式R(A,B,C,G,H,I)，函數(shù)依賴集F={AB,AC,CGH,CGI,BH}。我們可列出F中蘊含的幾個依賴：由傳遞律可得AH，因為AB且BH；由合并律可得CGHI，因為CGH，CGI；由偽傳遞律可得AGI，因為AC且CGI。還可以使用上述規(guī)則推導出更多的函數(shù)依賴，讀者可自行推導。第十一頁，共三十頁，2022年，8月28日3.函數(shù)依賴閉包定義:在關系模式R<U，F(xiàn)>中為F所邏輯蘊含的函數(shù)依賴的全體叫作F的閉包，記為F+。定義:設F為屬性集U上的一組函數(shù)依賴，X

U，

XF+={A|X→A能由F根據(jù)Armstrong公理導出}，XF+稱為屬性集X關于函數(shù)依賴集F的閉包第十二頁，共三十頁，2022年，8月28日關于閉包的引理引理:設F為屬性集U上的一組函數(shù)依賴，X，Y

U，X→Y能由F根據(jù)Armstrong公理導出的充分必要條件是Y

XF+用途將判定X→Y是否能由F根據(jù)Armstrong公理導出的問題，就轉(zhuǎn)化為求出XF+，判定Y是否為XF+的子集的問題(簡單說，求邏輯蘊含只要通過求閉包就可以了。）第十三頁，共三十頁，2022年，8月28日函數(shù)依賴閉包函數(shù)依賴的閉包F+是指被F邏輯蘊涵的函數(shù)依賴的全體構(gòu)成的集合函數(shù)依賴推理規(guī)則的完備性

函數(shù)依賴推理規(guī)則系統(tǒng)(自反律、增廣律和傳遞律)是完備的。

由推理規(guī)則的完備性可得到兩個重要結(jié)論：

(1)屬性集X+中的每個屬性A，都有X→A被F邏輯蘊涵，即X+是所有由F邏輯蘊含X→A的屬性A的集合。

(2)F+是所有利用Amstrong推理規(guī)則從F導出的函數(shù)依賴的集合第十四頁，共三十頁，2022年，8月28日閉包的計算算法：求屬性集X關于函數(shù)依賴F的閉包X+方法：計算x（i）（I=0,1,……）(1)x(0)=x;(2)x(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）第十五頁，共三十頁，2022年，8月28日閉包的計算例：在關系模式R（U，F(xiàn)）中，U=ABCDEF={A→C，AC→B，B→D，C→E，EC→B}計算(EC)+。計算過程如下：

(1)x(0)=EC

(2)檢查函數(shù)依賴，因EC→B，X(1)=EC∪B=ECB(3)檢查函數(shù)依賴，因B→D，X(2)=ECB∪D=ECBD（4）X(3)=X(2)，所以(EC)+=ECBD第十六頁，共三十頁，2022年，8月28日屬性集閉包計算舉例練習已知R<U,F>,U=

(A,B,C,G,H,I)，F(xiàn)={AB,AC,CGH,CGI,BH}，計算(AG)+。算法第一次循環(huán)的執(zhí)行步驟：

步驟

FD

closure

1．初值AG2．ABABG3．ACABCG4．CGHABCGH6．CGIABCGHI6．BHABCGHI結(jié)果為closure=ABCGHI。(AG)+＝ABCGHI。（也就是說，AG可以決定右面的每一個屬性）第十七頁，共三十頁，2022年，8月28日計算屬性集閉包的作用計算屬性集閉包的作用可歸納如下：驗證XY是否在F+中：看是否有YX+。判斷X是否為R的超碼：通過計算X+，看其是否包含R的所有屬性。例如，(AG)+＝ABCGHI，則AG為R的超碼。判斷X是否為R的候選碼：若X是超碼，可檢驗X包含的所有子集的閉包是否包含R的所有屬性。若不存在任何這樣的屬性子集，則X是R的候選碼。第十八頁，共三十頁，2022年，8月28日候選碼的判斷設有關系R({A1,A2,…,An},F)，F(xiàn)為R的函數(shù)依賴集，X為R的屬性組，若X滿足：1X→A1,A2,…,An，即X+={A1,A2,…,An}2不存在X的真子集Y，Y→A1,A2,…,An。則稱X為R的碼例：關系R{A,B,C,D}，有FD如下：F={AB→C,C→B,BC→D,ACD→B}，R的碼為？AB+=ABCD,AC+=ABCD,ACD+=ABCD,候選碼為：AB，ACD;還是AB,AC？還是其他？思考?。〉谑彭?，共三十頁，2022年，8月28日屬性集閉包計算舉例R=(U,F),其中,U={A,B,C,D},F={AB,ACD};求A+,B+,C+,AC+;求R的侯選碼第二十頁，共三十頁，2022年，8月28日屬性集閉包計算舉例U={A,B,C,D};F={AB,ACD};A+=AB.C+=C.(AC)+=ABCD.ACBD顯然，AC是候選碼思考：哪些屬性是L類？（只出現(xiàn)在函數(shù)依賴左邊）哪些是R類？哪些是LR類？哪些是N類？它們與候選碼有什么關系？第二十一頁，共三十頁，2022年，8月28日候選碼的作用例題：已知R(X,Y,Z),F={XY→Z}，請問R為第幾范式？（請思考：解題的思路是什么？）XY為候選碼，R屬于BCNF。練習：R(W,X,Y,Z),F={X→Z,WX→Y}，請問R為第幾范式？第二十二頁，共三十頁，2022年，8月28日Armstrong公理系統(tǒng)的有效性與完備性Armstrong公理的完備性及有效性說明:“蘊含”==“導出”等價的概念F+==由F出發(fā)借助Armstrong公理導出的函數(shù)依賴的集合第二十三頁，共三十頁，2022年，8月28日6.函數(shù)依賴集等價 定義:如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。第二十四頁，共三十頁，2022年，8月28日6.最小依賴集定義：如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。

(1)F中任一函數(shù)依賴的右部僅含有一個屬性。(2)F中不存在這樣的函數(shù)依賴X→A，使得F與 F-{X→A}等價。(3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價。如果函數(shù)依賴集F和G等價，并且G是最小集，那么稱G是F的一個最小覆蓋。

第二十五頁，共三十頁，2022年，8月28日函數(shù)依賴集的等價和覆蓋求最小函數(shù)依賴集的方法：應用分解規(guī)則，使F中每一個依賴的右部單一化。去掉各函數(shù)依賴左部多余的屬性。方法：檢查F中左邊是非單屬性的依賴，如：XY→A，要判定Y是否多余，只要求X閉包，若X閉包A，則Y是多余的，以X→Y代替XY→A。去掉多余的依賴。方法：從第一個依賴開始，若要從F中去掉X→Y，則在剩下的依賴中求X閉包，若X閉包包含Y,則去掉X→Y