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

數(shù)據(jù)庫(kù)原理

計(jì)算機(jī)系軟件教研室2023/2/31數(shù)據(jù)庫(kù)原理第六章第三節(jié)數(shù)據(jù)依賴的公理系統(tǒng)2023/2/32第6章關(guān)系數(shù)據(jù)理論6.1數(shù)據(jù)依賴6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解6.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含 定義6.11對(duì)于滿足一組函數(shù)依賴F的關(guān)系模式R<U，F(xiàn)>，其任何一個(gè)關(guān)系r，若函數(shù)依賴X→Y都成立（即r中任意兩元組t，s，若t[X]=s[X]，則t[Y]=s[Y]）,則稱

F邏輯蘊(yùn)含X→YArmstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼（候選碼）從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴1.Armstrong公理系統(tǒng)

對(duì)關(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ù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F定理6.lArmstrong推理規(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成立.自反律得證定理6.l(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.l(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)含.傳遞律得證。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及ZY，有X→Z。（A1，A3）導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1

引理6.lX→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。3.函數(shù)依賴閉包定義6.l2在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作F的閉包，記為F+。定義6.13設(shè)F為屬性集U上的一組函數(shù)依賴，X

U，

XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包F的閉包

F={XY,YZ},F+計(jì)算是NP完全問(wèn)題，XA1A2...An

F+={Xφ,Yφ,Zφ,XYφ,XZφ,YZφ,XYZφ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZXYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ}關(guān)于閉包的引理引理6.2

設(shè)F為屬性集U上的一組函數(shù)依賴，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)題求閉包的算法算法6.l求屬性集X（X

U）關(guān)于U上的函數(shù)依賴集F的閉包XF+

輸入：X，F(xiàn)輸出：XF+步驟：（1）令X（0）=X，i=0（2）求B，這里B={A|(

V)(

W)(V→WF∧VX（i）∧A

W)}；（3）X（i+1）=B∪X（i）

算法6.l（4）判斷X（i+1）=X

（i）嗎?（5）若相等或X（i）=U,則X（i）就是XF+,

算法終止。（6）若否，則i=i+l，返回第（2）步。對(duì)于算法6.l，令ai=|X（i）|，{ai

}形成一個(gè)步長(zhǎng)大于1的嚴(yán)格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會(huì)終止。函數(shù)依賴閉包[例1]已知關(guān)系模式R<U，F(xiàn)>，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+

。解設(shè)X（0）=AB；(1)計(jì)算X（1）:逐一的掃描F集合中各個(gè)函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個(gè)：

AB→C，B→D。于是X（1）=AB∪CD=ABCD。函數(shù)依賴閉包(2)因?yàn)閄（0）≠X（1），所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到AB→C，B→D，C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(3)因?yàn)閄（2）=U，算法終止所以（AB）F+=ABCDE。4.Armstrong公理系統(tǒng)的有效性與完備性建立公理系統(tǒng)體系目的：從已知的f推導(dǎo)出未知的f明確：1.公理系統(tǒng)推導(dǎo)出來(lái)的f正確？2.F+中的每一個(gè)f都能推導(dǎo)出來(lái)？/f不能由F導(dǎo)出,f∈F+

FF+f4.Armstrong公理系統(tǒng)的有效性與完備性有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)的每一個(gè)函數(shù)依賴一定在F+中(可由定理6.1得到證明）

/*Armstrong正確完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)

/*Armstrong公理夠用，完全完備性：所有不能用Armstrong公理推導(dǎo)出來(lái)f,都不為真

若

f不能用Armstrong公理推導(dǎo)出來(lái)，

f∈F+有效性與完備性的證明證明： 1.有效性可由定理6.l得證2.完備性 只需證明逆否命題:

若函數(shù)依賴X→Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含分三步證明：有效性與完備性的證明(1)

若V→W成立，且V

XF+，則W

XF+

（引理)

證因?yàn)閂

XF+，所以有X→V成立；因?yàn)閄→V，V→W，于是X→W成立所以W

XF+(2)/*若

f不能用Armstrong公理推導(dǎo)出來(lái)，

f∈F+/*若存在r，F(xiàn)+中的全部函數(shù)依賴在r上成立。/*而不能用Armstrong公理推導(dǎo)出來(lái)的f,在r上不成立。構(gòu)造一張二維表r，它由下列兩個(gè)元組構(gòu)成，可以證明r必是R（U，F(xiàn)）的一個(gè)關(guān)系，即F+中的全部函數(shù)依賴在r上成立。

Armstrong公理系統(tǒng)的有效性與完備性(續(xù))

XF+

U-XF+

11......100......0

11......111......1

若r不是R<U，F(xiàn)>的關(guān)系，則必由于F中有函數(shù)依賴V→W在r上不成立所致。由r的構(gòu)成可知，V必定是XF+的子集，而W不是XF+的子集，可是由第（1）步，W

XF+，矛盾。所以r必是R<U，F(xiàn)>的一個(gè)關(guān)系。Armstrong公理系統(tǒng)的有效性與完備性(續(xù))(3))/*若

f不能用Armstrong公理推導(dǎo)出來(lái)，

f∈F+/*而不能用Armstrong公理推導(dǎo)出來(lái)的f,在r上不成立。若X→Y不能由F從Armstrong公理導(dǎo)出，則Y不是XF+的子集。（引理6.2）因此必有Y的子集Y’滿足Y’U-XF+，則X→Y在r中不成立，即X→Y必不為R<U，F(xiàn)>蘊(yùn)含/*因?yàn)镕+中的全部函數(shù)依賴在r上成立。Armstrong公理系統(tǒng)的有效性與完備性(續(xù))Armstrong公理的完備性及有效性說(shuō)明:“蘊(yùn)含”==“導(dǎo)出”等價(jià)的概念

F+==由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴的集合5.函數(shù)依賴集等價(jià) 定義6.14如果G+=F+，就說(shuō)函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。函數(shù)依賴集等價(jià)的充要條件 引理6.3F+=G+的充分必要條件是

F

G+，和G

F+證:必要性顯然，只證充分性。（1）若FG+，則XF+

XG++。（2）任取X→YF+則有Y

XF+

XG++。 所以X→Y(G+）+=G+。即F+

G+。（3）同理可證G+

F+，所以F+=G+。函數(shù)依賴集等價(jià)要判定F

G+，只須逐一對(duì)F中的函數(shù)依賴X→Y，考察Y是否屬于XG++

就行了。因此引理6.3給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。6.最小依賴集定義6.15如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。

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

(2)F中不存在這樣的函數(shù)依賴X→A，使得F與F-{X→A}等價(jià)。

(3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價(jià)。最小依賴集[例2]對(duì)于6.l節(jié)中的關(guān)系模式S<U，F(xiàn)>，其中：

U={SNO，SDEPT，MN，CNAME，G}，

F={SNO→SDEPT，SDEPT→MN，（SNO，CNAME）→G}

設(shè)F’={SNO→SDEPT，SNO→MN，

SDEPT→MN，(SNO，CNAME)→G，

(SNO，SDEPT)→SDEPT}F是最小覆蓋，而F’不是。因?yàn)椋篎’-{SNO→MN}與F’等價(jià)

F’-{(SNO，SDEPT)→SDEPT}也與F’等價(jià)

F’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也與F’等價(jià)7.極小化過(guò)程定理6.3每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集證:構(gòu)造性證明，依據(jù)定義分三步對(duì)F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2…Ak，k>2，則用{X→Aj

|j=1，2，…，k}來(lái)取代X→Y。

引理6.1保證了F變換前后的等價(jià)性。極小化過(guò)程(2)逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若AXG+，則從F中去掉此函數(shù)依賴。

（由于F與G=F-{X→A}等價(jià)的充要條件是AXG+

因此F變換前后是等價(jià)的。）極小化過(guò)程(3)逐一取出F中各函數(shù)依賴FDi：X→A，設(shè)X=B1B2…Bm，逐一考查Bi

（i=l，2