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

關(guān)于函數(shù)依賴(lài)的公理系統(tǒng)

數(shù)據(jù)依賴(lài)的公理系統(tǒng)邏輯蘊(yùn)含 定義:對(duì)于滿足一組函數(shù)依賴(lài)F的關(guān)系模式R<U，F(xiàn)>，其任何一個(gè)關(guān)系r，若函數(shù)依賴(lài)X→Y都成立,

則稱(chēng)F邏輯蘊(yùn)含X→Y第2頁(yè),共30頁(yè)，2024年2月25日，星期天Armstrong公理系統(tǒng)從已知函數(shù)依賴(lài)集F要問(wèn)X→Y是否為F邏輯蘊(yùn)含，就要一套推理規(guī)則，由Armstrong在1974年提出。這套推理規(guī)則，是模式分解算法的理論基礎(chǔ)。用途從一組函數(shù)依賴(lài)求得蘊(yùn)含的函數(shù)依賴(lài)。求給定關(guān)系模式的碼。第3頁(yè),共30頁(yè)，2024年2月25日，星期天1.Armstrong公理系統(tǒng)

關(guān)系模式R<U，F(xiàn)>來(lái)說(shuō)有以下的推理規(guī)則：Al.自反律（Reflexivity）：若Y

X

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

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

注意：由自反律所得到的函數(shù)依賴(lài)均是平凡的函數(shù)依賴(lài)，自反律的使用并不依賴(lài)于F第4頁(yè),共30頁(yè)，2024年2月25日，星期天定理Armstrong推理規(guī)則是正確的（l）自反律:若Y

X

U，則X→Y為F所蘊(yùn)含證:設(shè)Y

X

U

對(duì)R<U，F(xiàn)>

的任一關(guān)系r中的任意兩個(gè)元組t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得證第5頁(yè),共30頁(yè)，2024年2月25日，星期天定理Armstrong推理規(guī)則是正確的(2)增廣律:若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。證：設(shè)X→Y為F所蘊(yùn)含，且Z

U。設(shè)R<U，F(xiàn)>

的任一關(guān)系r中任意的兩個(gè)元組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所蘊(yùn)含.增廣律得證。第6頁(yè),共30頁(yè)，2024年2月25日，星期天定理Armstrong推理規(guī)則是正確的(3)傳遞律：若X→Y及Y→Z為F所蘊(yùn)含，則

X→Z為F所蘊(yùn)含。證：設(shè)X→Y及Y→Z為F所蘊(yùn)含。對(duì)R<U，F(xiàn)>

的任一關(guān)系r中的任意兩個(gè)元組t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊(yùn)含.傳遞律得證。第7頁(yè),共30頁(yè)，2024年2月25日，星期天2.導(dǎo)出規(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及Z

Y，有X→Z。（A1，A3）第8頁(yè),共30頁(yè)，2024年2月25日，星期天導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理1

引理:X→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。第9頁(yè),共30頁(yè)，2024年2月25日，星期天總結(jié):函數(shù)依賴(lài)(FD)的推理規(guī)則函數(shù)依賴(lài)有一個(gè)正確的和完備的推理規(guī)則集——Armstrong推理規(guī)則：設(shè)有關(guān)系模式R(U)，X，Y，Z，W均是U的子集，F(xiàn)是R上只涉及到U中屬性的函數(shù)依賴(lài)集，推理規(guī)則如下：(1)自反律：如果Y

X

U,則X→Y在R上成立。(2)增廣律：如果X→Y為F所蘊(yùn)涵，Z

U，則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）第10頁(yè),共30頁(yè)，2024年2月25日，星期天函數(shù)依賴(lài)[例]關(guān)系模式R(A,B,C,G,H,I)，函數(shù)依賴(lài)集F={A

B,A

C,CG

H,CG

I,B

H}。我們可列出F中蘊(yùn)含的幾個(gè)依賴(lài)：由傳遞律可得A

H，因?yàn)锳

B且B

H；由合并律可得CG

HI，因?yàn)镃G

H，CG

I；由偽傳遞律可得AG

I，因?yàn)锳

C且CG

I。還可以使用上述規(guī)則推導(dǎo)出更多的函數(shù)依賴(lài)，讀者可自行推導(dǎo)。第11頁(yè),共30頁(yè)，2024年2月25日，星期天3.函數(shù)依賴(lài)閉包定義:在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴(lài)的全體叫作F的閉包，記為F+。定義:設(shè)F為屬性集U上的一組函數(shù)依賴(lài)，X

U，

XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱(chēng)為屬性集X關(guān)于函數(shù)依賴(lài)集F的閉包第12頁(yè),共30頁(yè)，2024年2月25日，星期天關(guān)于閉包的引理引理:

設(shè)F為屬性集U上的一組函數(shù)依賴(lài)，X，Y

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

XF+用途將判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問(wèn)題，就轉(zhuǎn)化為求出XF+

，判定Y是否為XF+的子集的問(wèn)題(簡(jiǎn)單說(shuō)，求邏輯蘊(yùn)含只要通過(guò)求閉包就可以了。）第13頁(yè),共30頁(yè)，2024年2月25日，星期天函數(shù)依賴(lài)閉包函數(shù)依賴(lài)的閉包F+是指被F邏輯蘊(yùn)涵的函數(shù)依賴(lài)的全體構(gòu)成的集合函數(shù)依賴(lài)推理規(guī)則的完備性

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

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

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

(2)F+是所有利用Amstrong推理規(guī)則從F導(dǎo)出的函數(shù)依賴(lài)的集合第14頁(yè),共30頁(yè)，2024年2月25日，星期天閉包的計(jì)算算法：求屬性集X關(guān)于函數(shù)依賴(lài)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ù)依賴(lài)（3）判斷是否有A：x(i+1)=x(i);B:若在x(i+1)已包含了F中的全部屬性；C：x(i+1)≠x(i)，但x(i+1)的左部屬性依賴(lài)已使用完出現(xiàn)A，B，C的一種即結(jié)束，否則轉(zhuǎn)（2）第15頁(yè),共30頁(yè)，2024年2月25日，星期天閉包的計(jì)算例：在關(guān)系模式R（U，F(xiàn)）中，U=ABCDEF={A→C，AC→B，B→D，C→E，EC→B}計(jì)算(EC)+。計(jì)算過(guò)程如下：

(1)x(0)=EC

(2)檢查函數(shù)依賴(lài)，因EC→B，X(1)=EC∪B=ECB(3)檢查函數(shù)依賴(lài)，因B→D，X(2)=ECB∪D=ECBD

（4）X(3)=X(2)，所以(EC)+=ECBD第16頁(yè),共30頁(yè)，2024年2月25日，星期天

屬性集閉包計(jì)算舉例練習(xí)已知R<U,F>,U=

(A,B,C,G,H,I)，F(xiàn)={A

B,A

C,CG

H,CG

I,B

H}，計(jì)算(AG)+。算法第一次循環(huán)的執(zhí)行步驟：

步驟

FD

closure

1．初值A(chǔ)G2．

A

BABG3．A

CABCG4．CG

HABCGH6．CG

IABCGHI6．B

HABCGHI

結(jié)果為closure=ABCGHI。(AG)+＝ABCGHI。（也就是說(shuō)，AG可以決定右面的每一個(gè)屬性）第17頁(yè),共30頁(yè)，2024年2月25日，星期天計(jì)算屬性集閉包的作用計(jì)算屬性集閉包的作用可歸納如下：驗(yàn)證X

Y是否在F+中：看是否有Y

X+。判斷X是否為R的超碼：通過(guò)計(jì)算X+，看其是否包含R的所有屬性。例如，(AG)+＝ABCGHI，則AG為R的超碼。判斷X是否為R的候選碼：若X是超碼，可檢驗(yàn)X包含的所有子集的閉包是否包含R的所有屬性。若不存在任何這樣的屬性子集，則X是R的候選碼。第18頁(yè),共30頁(yè)，2024年2月25日，星期天候選碼的判斷設(shè)有關(guān)系R({A1,A2,…,An},F)，F(xiàn)為R的函數(shù)依賴(lài)集，X為R的屬性組，若X滿足：1X→A1,A2,…,An，即X+={A1,A2,…,An}2不存在X的真子集Y，Y→A1,A2,…,An。則稱(chēng)X為R的碼例：關(guān)系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？還是其他？思考??！第19頁(yè),共30頁(yè)，2024年2月25日，星期天

屬性集閉包計(jì)算舉例R=(U,F),其中,U={A,B,C,D},F={AB,ACD};求A+,B+,C+,AC+;求R的侯選碼第20頁(yè),共30頁(yè)，2024年2月25日，星期天

屬性集閉包計(jì)算舉例U={A,B,C,D};F={AB,ACD};A+=AB.C+=C.(AC)+=ABCD.ACBD顯然，AC是候選碼思考：哪些屬性是L類(lèi)？（只出現(xiàn)在函數(shù)依賴(lài)左邊）哪些是R類(lèi)？哪些是LR類(lèi)？哪些是N類(lèi)？它們與候選碼有什么關(guān)系？第21頁(yè),共30頁(yè)，2024年2月25日，星期天候選碼的作用例題：已知R(X,Y,Z),F={XY→Z}，請(qǐng)問(wèn)R為第幾范式？（請(qǐng)思考：解題的思路是什么？）XY為候選碼，R屬于BCNF。練習(xí)：R(W,X,Y,Z),F={X→Z,WX→Y}，請(qǐng)問(wèn)R為第幾范式？第22頁(yè),共30頁(yè)，2024年2月25日，星期天Armstrong公理系統(tǒng)的有效性與完備性Armstrong公理的完備性及有效性說(shuō)明:“蘊(yùn)含”==“導(dǎo)出”等價(jià)的概念

F+==由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴(lài)的集合第23頁(yè),共30頁(yè)，2024年2月25日，星期天6.函數(shù)依賴(lài)集等價(jià)

定義:如果G+=F+，就說(shuō)函數(shù)依賴(lài)集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。第24頁(yè),共30頁(yè)，2024年2月25日，星期天6.最小依賴(lài)集

定義：如果函數(shù)依賴(lài)集F滿足下列條件，則稱(chēng)F為一個(gè)極小函數(shù)依賴(lài)集。亦稱(chēng)為最小依賴(lài)集或最小覆蓋。

(1)F中任一函數(shù)依賴(lài)的右部?jī)H含有一個(gè)屬性。

(2)F中不存在這樣的函數(shù)依賴(lài)X→A，使得F與

F-{X→A}等價(jià)。

(3)F中不存在這樣的函數(shù)依賴(lài)X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價(jià)。如果函數(shù)依賴(lài)集F和G等價(jià)，并且G是最小集，那么稱(chēng)G是F的一個(gè)最小覆蓋。

第25頁(yè),共30頁(yè)，2024年2月25日，星期天函數(shù)依賴(lài)集的等價(jià)和覆蓋求最小函數(shù)依賴(lài)集的方法：應(yīng)用分解規(guī)則，使F中每一個(gè)依賴(lài)的右部單一化。去掉各函數(shù)依賴(lài)左部多余的屬性。方法：檢查F中左邊是非單屬性的依賴(lài)，如：XY→A，要判定Y是否多余，只要求X閉包，若X閉包A，則Y是多余的，以X→Y代替XY→A。去掉多余的依賴(lài)。方法：從第一個(gè)依賴(lài)開(kāi)始，若要從F中去掉X→Y，則在剩下的依賴(lài)中求X閉包，若X閉包包含Y,則去掉X→Y第26頁(yè),共30頁(yè)，2024年2月25日，星期天最小依賴(lài)集