候選碼求解教材

6.1.2函數(shù)依賴1.函數(shù)依賴定義定義1：設(shè)有關(guān)系模式R（A1,A2,…,An）或簡記為R(U),X,Y是U的子集，r是R的任一具體關(guān)系。如果對于r的任意兩個元組t1,t2,由t1[X]=t2[X]導(dǎo)致(或能確定)

t1[Y]=t2[Y],則稱X函數(shù)決定Y，或Y函數(shù)依賴于X,記作X→Y。定義2：設(shè)X→Y是一個函數(shù)依賴，若YX,則稱X→Y是一個平凡函數(shù)依賴。定義3：設(shè)X→Y是一個函數(shù)依賴，并且對于任何X'X,X'→Y都不成立，則稱X→Y是一個完全函數(shù)依賴。即Y函數(shù)依賴于整個X，記作XY。定義4：設(shè)X→Y是一個函數(shù)依賴，但不是完全函數(shù)依賴，則稱X→Y是一個部分函數(shù)依賴，或稱Y函數(shù)依賴于X的某個真子集，記作XY。定義5：設(shè)R(U)是一個關(guān)系模式，X,Y,ZU,如果X→Y,Y→Z,且Y-/->X,Z-Y≠?,Y-X≠?成立，則稱Z傳遞函數(shù)依賴于X，記作XZ。定義6：設(shè)F是關(guān)系模式R的一個函數(shù)依賴集，X,Y是R的屬性子集，如果從F中的函數(shù)依賴能夠推出X→Y，則稱F邏輯蘊涵X→Y。定義7：由被F邏輯蘊涵的函數(shù)依賴的全體構(gòu)成的集合，稱為F的閉包，記為F+。2.函數(shù)依賴公理函數(shù)依賴的推導(dǎo)公理即為Armstrong公理：設(shè)有關(guān)系R(A1,A2,…,An)和屬性集U=(A1,A2,…,An),X,Y,Z,W均是U的子集，F(xiàn)是R上只涉及到U中屬性的函數(shù)依賴集，則：A1(自反律)：如果Y

X

U,則X→Y在R上成立。A2(增廣律)：如果X→Y為F所蘊涵，ZU,

則XZ→YZ在R上成立。A3(傳遞律)：如果X→Y和Y→Z在R上成立，則

X→Z在R上也成立。由Armstrong公理可以得到以下推論：(合并律)：如果X→Y和X→Z成立，則X→YZ成立。(偽傳遞律)：如果X→Y和WY→Z成立，則

WX→Z成立。(分解律)：如果X→Y和ZY成立，則

X→Z成立。3.函數(shù)依賴與屬性關(guān)系屬性之間有3種關(guān)系，但并不是每一種關(guān)系中都存在函數(shù)依賴。設(shè)有屬性集X、Y以及關(guān)系模式R：如果X和Y之間是“1:1”關(guān)系（如學(xué)校和校長），則存在函數(shù)依賴：X→Y和Y→X如果X和Y之間是“m:1”關(guān)系（如學(xué)號和姓名），則存在函數(shù)依賴：X→Y如果X和Y之間是“m:n”關(guān)系（如學(xué)生和課程），則X和Y之間不存在函數(shù)依賴。定義：設(shè)關(guān)系模式R(U),F為其函數(shù)依賴集，則稱所有用Armstrong公理從F推出的函數(shù)依賴X→Ai中，Ai的屬性集合為X的屬性閉包，記為X+。定理：設(shè)關(guān)系模式R(U),F為其函數(shù)依賴集，X,YU,則從F推出X→Y的充要條件是Y

X+。4.閉包的計算：算法：求屬性集X關(guān)于函數(shù)依賴F的屬性閉包X+。輸入：關(guān)系模式R的全部屬性集U，在U上的函數(shù)依賴F，U的子集X。輸出：X關(guān)于F的屬性閉包X+。方法：計算X(i)(i=0,1,…)。(1)X(0)=X;(2)X(i+1)=X(i)A;其中A是這樣的屬性，在F中尋找尚未用過的左邊是X(i)的子集的函數(shù)依賴：Yj→Zj(j=0,1,…,k)，

YjX(i)。即Zj在尋找X(i)中未出現(xiàn)過的屬性集合A，若無這樣的A則轉(zhuǎn)(4);(3)判斷是否有X(i+1)=X(i)A，若有則轉(zhuǎn)(4),否則轉(zhuǎn)(2);(4)輸出X(i),即為X+。對于(3)的計算停止條件，以下4種方法是等價的：X(i+1)=X(i);當(dāng)發(fā)現(xiàn)X(i)包含了全部屬性時；在F中函數(shù)依賴的右邊屬性中再也找不到X(i)中未出現(xiàn)過的屬性；在F中未用過的函數(shù)依賴的左邊屬性已沒有X(i)的子集。例：設(shè)有關(guān)系模式R(U,F),其中U={A,B,C,D,E,I},F={A→D,AB→E,BI→E,CD→I,E→C},計算(AE)+。解：令X={AE},X(0)=AE。在F中找出左邊是AE子集的函數(shù)依賴，其結(jié)果是：A→D,E→C,∴X(1)=X(0)DC=AEDC,顯然X(1)≠X(0)。在F中找出左邊是AEDC子集的函數(shù)依賴，其結(jié)果是：CD→I,∴X(2)=X(1)I=AEDCI。顯然X(2)≠X(1),但F中未用過的函數(shù)依賴的左邊屬性已沒有X(2)的子集，所以不必再計算下去，即(AE)+＝ACDEI。對于給定的關(guān)系R(A1,A2,…,An)和函數(shù)依賴集F，可將其屬性分為4類：L類：僅出現(xiàn)在F的函數(shù)依賴左部的屬性R類：僅出現(xiàn)在F的函數(shù)依賴右部的屬性N類：在F的函數(shù)依賴左右兩邊均未出現(xiàn)的屬性LR類：在F的函數(shù)依賴左右兩邊均出現(xiàn)的屬性5.候選碼的求解理論和算法函數(shù)依賴的閉包計算F+已知關(guān)系模式R(U,F),U=(A,B,C),F={A→C,B→C},求F+。解：由推理規(guī)則，可求出F+有35個函數(shù)依賴，具體如下：Φ→ΦB→ΦA(chǔ)B→ΦBC→ΦA(chǔ)BC→ΦA(chǔ)→ΦB→BAB→ABC→BABC→AA→AB→CAB→BBC→CABC→BA→CB→BCAB→CBC→BCABC→CA→ACC→ΦA(chǔ)B→ABCA→ΦA(chǔ)BC→ABC→CAB→BCCA→AABC→BCAB→CACA

→CABC→CAAB→ABCCA→CAABC→ABC定理：對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X（X∈R）是L類屬性，則X必為R的任一候選碼的成員。

(1)快速求解候選碼的一個充分條件例1設(shè)有關(guān)系模式R(A,B,C,D),其函數(shù)依賴集

F={D→B,B→D,AD→B,AC→D},求R的所有候選碼。

解：考察F發(fā)現(xiàn)，A,C兩屬性是L類屬性，由前面定理可知，AC必是R的一候選碼的成員，又

∵(AC)+=ACBD,∴AC是R的惟一候選碼。推論：對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是L類屬性，且X+包含了R的全部屬性，則X必為R的惟一候選碼定理：對于給定的關(guān)系模式R及其函數(shù)依賴集F，如果X(X∈R)是R類屬性，則X不在任何候選碼中。定理：設(shè)有關(guān)系模式R及其函數(shù)依賴集F，如果X(X∈R)是N類屬性，則X必包含在R的任一候選碼中。例：設(shè)有關(guān)系模式R(A,B,C,D,E,P)，R的函數(shù)依賴集為F={A→D,E→D,D→B,BC→D,DC→A},求R的所有候選碼。解：考察F發(fā)現(xiàn)，C、E兩屬性是L類屬性，故C、E必在R的任何候選碼中；∵P是N類屬性，∴P也必在R的任何候選碼中?！?CEP)+=ABCDEP,∴CEP是R的惟一候選碼。推論：對于給定的關(guān)系模式R及其函數(shù)依賴集F，如果X是R的N類和L類組成的屬性集，且X+包含了R的全部屬性，則X是R的惟一候選碼。定義：一個函數(shù)依賴圖G是一個有序二元組(R,F)，記作G=(R,F),簡稱依賴圖。其中：(1)R=(A1,A2,…,An)是一個有限非空集，Ai(i=1,2,…,n)是G的結(jié)點，它們表示對應(yīng)關(guān)系模式R(A1,A2,…,An)的屬性，R表示其屬性全集。(2)F是G的邊集，其元素是G的一條有向線段(即邊)，每條邊(Ai,Aj)表示一個函數(shù)依賴Ai→Aj,F是R的單屬性最小依賴集。(2)左邊為單屬性的函數(shù)依賴集的候選碼成員的圖論判定方法定義：在一個函數(shù)依賴圖中有下列術(shù)語：(1)引出線/引入線：若結(jié)點Ai到Aj是連接的，則邊(Ai,Aj)是Ai的引出線，同時也是Aj的引入線。(2)原始點：只有引出線而無引入線的結(jié)點，它表示L類屬性。(3)終結(jié)點：只有引入線而無引出線的結(jié)點，它表示R類屬性。(4)途中點：既有引入線又有引出線的結(jié)點，它表示LR類屬性。(5)孤立點：既無引入線又無引出線的結(jié)點，它表示N類屬性。(6)關(guān)鍵點：原始點(L)和孤立點(N)統(tǒng)稱為關(guān)鍵點。(7)關(guān)鍵屬性：關(guān)鍵點對應(yīng)的屬性稱為關(guān)鍵屬性。(8)獨立回路：不能被其他結(jié)點到達的回路。定理：一個關(guān)系模式R的函數(shù)依賴G中若存在關(guān)鍵結(jié)點，則關(guān)鍵結(jié)點對應(yīng)的屬性必在R的任何候選碼中，而所有終結(jié)點必不在R的任何候選碼中。定理：屬性集X是R的惟一候選碼的充要條件是X為能到達G中任一結(jié)點的關(guān)鍵屬性集。推論：在單屬性情況下，R具有惟一候選碼的充要條件是G中不存在獨立回路。定理：設(shè)Y是途中點，則Y必在某個候選碼中的充要條件是Y為某一獨立回路中的結(jié)點。定理：設(shè)F是單屬性依賴集，R的關(guān)鍵屬性集X不能到達G中的某些結(jié)點，G中存在K(≥1)個獨立回路r1,r2,…,rk，各回路的結(jié)點集分別為：

AA1={A11,A12,…,A1n1}AA2={A21,A22,…,A2n2}

……

AAk={Ak1,Ak2,…,Aknn}其中Aij(i=1,..,k;j=1,…,n)都是R的屬性，則：

(1)R的候選碼必不惟一；

(2)R的每個候選碼均由兩部分組成：

■關(guān)鍵屬性集X(包括X為空)；

■k個獨立回路中，每個獨立回路任選一個點作為候選碼的成員，候選碼的集合Y是AA1,AA2,…,AAk的笛卡爾積。

(3)候選碼的個數(shù)等于各獨立回路中結(jié)點個數(shù)的乘積，即：M=n1×n2×…×nk(4)每個候選碼所含屬性個數(shù)是一個常數(shù)，它等于關(guān)鍵屬性個數(shù)｜X｜加上獨立回路個數(shù)，即：N=｜X｜+k算法：單屬性依賴集圖論求解法。輸入：關(guān)系模式R，R的單屬性函數(shù)依賴集F。輸出：R的所有候選碼。方法：(1)求F的最小依賴集Fm。(2)構(gòu)造函數(shù)依賴圖FDG。(3)從圖中找出關(guān)鍵屬性集X(X可為空)。(4)查看G中有無獨立回路，若無則輸出X即為R的惟一候選碼，轉(zhuǎn)(6);若有，則轉(zhuǎn)(5)。(5)從各獨立回路中各取一結(jié)點對應(yīng)的屬性與X組合成一候選碼，并重復(fù)這一過程，取盡所有可能的組合，即為R的全部候選碼。(6)結(jié)束。6.最小依賴集求解定義：對于給定的函數(shù)依賴F，當(dāng)滿足下列條件時，稱為F的最小依賴集，記作Fm。

(1)Fm的每個依賴的右部都是單個屬性。

(2)對于Fm中的任何一個函數(shù)依賴X→A,Fm–{X→A}與Fm都不等價。

(3)對于Fm中的任何一個X→A和X的真子集Z，(Fm–(X→A)){Z→A}與Fm都不等價。

條件(1)保證了每一個依賴子都是單屬性；條件(2)保證了在Fm中不存在多余的函數(shù)依賴；條件(3)保證了Fm中每個函數(shù)依賴的左邊沒有多余的屬性（也就是函數(shù)依賴集F中的每個函數(shù)依賴都是完全函數(shù)依賴，沒有部分函數(shù)依賴）。定義：一個關(guān)系模式R(U)上的兩個依賴集F和G，如果F+=G+,則稱F和G是等價的，記作F≡G。如果函數(shù)依賴集F≡G，則稱G是F的一個覆蓋，反之亦然。（兩個等價的依賴集在表示能力上是完全相同的）定理：每個函數(shù)依賴集F都與它的最小依賴集Fm等價。算法：計算最小依賴集輸入：一個函數(shù)依賴集F輸出：F的一個等價最小依賴集G。方法：(1)應(yīng)用分解律，使F中每一個依賴的右部屬性單一化。(2)去掉各依賴左部多余的屬性。具體做法：一個一個地檢查F中左邊是非單屬性的依賴，例如XY→A?，F(xiàn)在要判斷Y是否為多余的，即從F-{XY→A}中求X+，若X+包含A，則Y是多余的屬性；否則Y不是多余屬性。依次判斷其他屬性即可消除各依賴左邊的多余屬性。(3)去掉多余的依賴。具體做法：從第一個依賴開始，從F中去掉它(假設(shè)該依賴為X→Y)，然后在剩下的依賴中求X+

，看X+是否包含Y，若是，則去掉X→Y

，若不包含Y，則不能去掉。這樣依次做下去。例：設(shè)有依賴集：F={AB→C,C→A,BC→D,ACD→B,D→EG,BE→C,

CG→BD,CE→AG},計算其等價的最小依賴集。解：(1)將依賴右邊屬性單一化，結(jié)果為F1={AB→C,C→A,BC→D,ACD→B,D→E,D→G,BE→C,CG→B,CG→D,CE→A,CE→G},計算其等價的最小依賴集。

(2)在F1中去掉依賴左部多余的屬性。對于CE→A,由于有C→A，則E是多余的；對于ACD→B，由于(CD)