第15講 公理系統(tǒng)

6.3數(shù)據(jù)依賴的公理系統(tǒng)Armstrong公理系統(tǒng)FD的閉包，屬性集的閉包候選碼極小函數(shù)依賴集邏輯蘊含 定義6.11對于滿足一組函數(shù)依賴F的關系模式R<U，F(xiàn)>，其任何一個關系r，假設函數(shù)依賴X→Y都成立〔即r中的任意兩元組t，s，假設t[X]=s[X]，那么t[Y]=s[Y]〕，那么稱F邏輯蘊含X→Y。1.Armstrong公理系統(tǒng)關系模式R<U，F(xiàn)>來說有以下的推理規(guī)那么：Al.自反律〔Reflexivity〕：假設YXU，那么X→Y為F所蘊含。A2.增廣律〔Augmentation〕：假設X→Y為F所蘊含，且ZU，那么XZ→YZ為F所蘊含。A3.傳遞律〔Transitivity〕：假設X→Y及Y→Z為F所蘊含，那么X→Z為F所蘊含。 可以從邏輯蘊含的定義出發(fā)證明推理規(guī)那么的正確性。2.導出規(guī)那么根據(jù)A1，A2，A3這三條推理規(guī)那么可以得到下面三條推理規(guī)那么：合并規(guī)那么：由X→Y，X→Z，有X→YZ。偽傳遞規(guī)那么：由X→Y，WY→Z，有XW→Z。分解規(guī)那么：由X→Y及ZY，有X→Z。根據(jù)推理規(guī)那么，很容易得到這樣一個重要事實：引理6.lX→A1A2…Ak成立的充分必要條件是X→Ai成立〔i=l，2，…，k〕。3.函數(shù)依賴集的閉包定義6.l2在關系模式R<U，F(xiàn)>中為F所邏輯蘊含的函數(shù)依賴的全體叫作F的閉包，記為F+。F={XY,YZ},F+計算是NP完全問題

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,XXYZ,XYXYZ,XZXYZ,XYZXYZ}定義6.13對于R<U,F>，X

U，XF+={A|X→A能由F根據(jù)Armstrong公理導出}，XF+稱為屬性集X關于函數(shù)依賴集F的閉包4.屬性集的閉包例：在R(U,F)中，U={ABC},F={A->B,B->C}那么AF+=?求屬性集閉包的用途將判定X→Y是否被F蘊含的問題，就轉(zhuǎn)化為求XF+

，判定Y是否為XF+的子集的問題求閉包的算法算法6.l求屬性集X〔XU〕關于U上的函數(shù)依賴集F的閉包XF+.輸入：X，F(xiàn)輸出：XF+步驟：1〕令X〔0〕=X，i=02〕求B,這里B={A|(V)(W)(V→WF∧VX〔i〕∧AW)}；3〕X〔i+1〕=B∪X〔i〕4〕判斷X〔i+1〕=X〔i〕嗎?假設相等或X〔i+1〕=U,那么X〔i+1〕就是XF+,算法終止。假設否，那么i=i+l，返回第〔2〕步。例:關系模式R<U，F(xiàn)>，其U={A,B,C,D,E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求〔AB〕F+。練習：關系模式R<U，F(xiàn)>，其中U={A，B，C，D，E}；F={A→B，D→C，BC→E，AC→B}。求〔AE〕F+、〔AD〕F+。5.候選碼性質(zhì)對于關系模式R(U,F)的候選碼K:1.K→U:閉包為U2.極小:不包含冗余屬性根據(jù)F分析屬性的種類:1.只出現(xiàn)在左邊:必包含在任何候選碼中

2.只出現(xiàn)在右邊:必不包含在任何候選碼中

3.兩邊都出現(xiàn):可能包含于某個候選碼中候選碼求解方法1.查找只在左邊出現(xiàn)的屬性集X;2.假設X非空:判斷X的閉包是否為U,假設是那么即為所求碼;否那么,考查兩邊都出現(xiàn)的屬性y：依次檢查X與y的各種極小組合,判斷其閉包是否為U;3.假設X為空:考查兩邊都出現(xiàn)的屬性y：依次檢查y的各種極小組合,判斷其閉包是否為U;練習:1.R(U,F),U=(ABCDEG),F={AB->C,CD->E,E->A,A->G},求候選碼，并判斷R屬于第幾范式。2.R(U,F),U=(ABCDE),F={A->BC,CD->E,B->D,E->A},求候選碼，并判斷R屬于第幾范式。回憶：函數(shù)依賴集的閉包屬性集的閉包候選碼的求解方法從蘊含〔或?qū)С觥车母拍畛霭l(fā)，引出了函數(shù)依賴集等價和最小依賴集的概念。6.函數(shù)依賴集等價定義6.14如果G+=F+，就說函數(shù)依賴集F覆蓋G〔F是G的覆蓋，或G是F的覆蓋〕，或F與G等價。引理6.3

F+=G+的充分必要條件是

F

G+，和G

F+引理給出了判斷兩個函數(shù)依賴集等價的可行算法：要判定F

G+，只須逐一對F中的函數(shù)依賴X→Y，考察Y是否屬于XG++就行了。7.最小依賴集定義6.15如果函數(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等價。右部單屬性無冗余FD左部無冗余屬性定理6.3每一個函數(shù)依賴集F均等價于一個極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集。極小化過程〔1〕對F進行“極小化處理〞，找出F的一個最小依賴集:(1)右部單屬性：逐一檢查F中各函數(shù)依賴FDi：X→Y，假設Y=A1A2…Ak，那么用{X→Aj|j=1，2，…，k}來取代X→Y。引理6.1保證了F變換前后的等價性：即使用分解規(guī)那么，使F的任一函數(shù)依賴右部僅含一個屬性。極小化過程〔2〕(2)消除冗余的函數(shù)依賴：逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，假設AXG+，那么從F中去掉此函數(shù)依賴。由于F與G=F-{X→A}等價的充要條件是AXG+，因此F變換前后是等價的。

極小化過程〔3〕(3)消除函數(shù)依賴左邊冗余的屬性：逐一取出F中各函數(shù)依賴FDi：X→A，設X=B1B2…Bm，逐一考查Bi〔i=l，2，…，m〕，假設A〔X-Bi〕F+，那么以X-Bi取代X。由于F與F-{X→A}∪{Z→A}等價的充要條件是AZF+，其中Z=X-Bi，因此F變換前后是等價的。由定義，最后剩下的F就一定是極小依賴集，并且與原來的F等價。因為對F的每一次“改造〞都保證了改造前后的兩個函數(shù)依賴集等價。注意F的最小依賴集Fm不一定是唯一的,它與對各函數(shù)依賴FDi及X→A中X各屬性的處置順序有關。[例]F={A→B，B→A，B→C，

A→C，C→A}求F的最小依賴集極小化過程也是檢驗F是否為極小依賴集的一個算法,假設改造后的F與原來的F