數據庫原理

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

F邏輯蘊含X→YArmstrong公理系統一套推理規則，是模式分解算法的理論基礎用途求給定關系模式的碼（候選碼）從一組函數依賴求得蘊含的函數依賴1.Armstrong公理系統

對關系模式R<U，F>來說有以下的推理規則：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所蘊含。

注意：由自反律所得到的函數依賴均是平凡的函數依賴，自反律的使用并不依賴于F定理6.lArmstrong推理規則是正確的（l）自反律:若Y

X

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

X

U

對R<U，F>

的任一關系r中的任意兩個元組t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得證定理6.l(2)增廣律:若X→Y為F所蘊含，且Z

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

U。設R<U，F>

的任一關系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所蘊含.增廣律得證。定理6.l(3)傳遞律：若X→Y及Y→Z為F所蘊含，則

X→Z為F所蘊含。證：設X→Y及Y→Z為F所蘊含。對R<U，F>

的任一關系r中的任意兩個元組t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊含.傳遞律得證。2.導出規則1.根據A1，A2，A3這三條推理規則可以得到下面三條推理規則：

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

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

分解規則：由X→Y及ZY，有X→Z。（A1，A3）導出規則2.根據合并規則和分解規則，可得引理6.1

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

U，

XF+={A|X→A能由F根據Armstrong公理導出}，XF+稱為屬性集X關于函數依賴集F的閉包F的閉包

F={XY,YZ},F+計算是NP完全問題，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}關于閉包的引理引理6.2

設F為屬性集U上的一組函數依賴，X，Y

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

XF+用途將判定X→Y是否能由F根據Armstrong公理導出的問題，就轉化為求出XF+

，判定Y是否為XF+的子集的問題求閉包的算法算法6.l求屬性集X（X

U）關于U上的函數依賴集F的閉包XF+

輸入：X，F輸出：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）步。對于算法6.l，令ai=|X（i）|，{ai

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

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

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

FF+f4.Armstrong公理系統的有效性與完備性有效性：由F出發根據Armstrong公理推導出來的每一個函數依賴一定在F+中(可由定理6.1得到證明）

/*Armstrong正確完備性：F+中的每一個函數依賴，必定可以由F出發根據Armstrong公理推導出來

/*Armstrong公理夠用，完全完備性：所有不能用Armstrong公理推導出來f,都不為真

若

f不能用Armstrong公理推導出來，

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

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

若V→W成立，且V

XF+，則W

XF+

（引理)

證因為V

XF+，所以有X→V成立；因為X→V，V→W，于是X→W成立所以W

XF+(2)/*若

f不能用Armstrong公理推導出來，

f∈F+/*若存在r，F+中的全部函數依賴在r上成立。/*而不能用Armstrong公理推導出來的f,在r上不成立。構造一張二維表r，它由下列兩個元組構成，可以證明r必是R（U，F）的一個關系，即F+中的全部函數依賴在r上成立。

Armstrong公理系統的有效性與完備性(續)

XF+

U-XF+

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

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

若r不是R<U，F>的關系，則必由于F中有函數依賴V→W在r上不成立所致。由r的構成可知，V必定是XF+的子集，而W不是XF+的子集，可是由第（1）步，W

XF+，矛盾。所以r必是R<U，F>的一個關系。Armstrong公理系統的有效性與完備性(續)(3))/*若

f不能用Armstrong公理推導出來，

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

F+==由F出發借助Armstrong公理導出的函數依賴的集合5.函數依賴集等價 定義6.14如果G+=F+，就說函數依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。函數依賴集等價的充要條件 引理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+。函數依賴集等價要判定F

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

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

(1)F中任一函數依賴的右部僅含有一個屬性。

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

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

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

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

設F’={SNO→SDEPT，SNO→MN，

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

(SNO，SDEPT)→SDEPT}F是最小覆蓋，而F’不是。因為：F’-{SNO→MN}與F’等價

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

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

|j=1，2，…，k}來取代X→Y。

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

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

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

（i=l，2