求解候選碼基本算法的具體步驟
第1 步,求關系模式R < U,F > 的 最小函數依賴集F
第2 步,按照上面的定義,分别計算出UL,UR,UB (UL 表示僅在函數依賴集中各依賴關系式左邊出現的屬性的集合; UR 表示僅在函數依賴集中各依賴關系式右邊出現的屬性的集合;另記UB = U - UL - UR)
第3 步,若UL ≠Φ,計算UL的閉包,若UL+ = U,則UL 為R 的唯一的候選碼,算法結束.若UL+ ≠U,轉第4 步. 若UL = Φ,轉第5 步.
第4 步,将UL 依次與UB 中的屬性組合,利用上述的定義4 判斷該組合屬性是否是候選碼;找出所有的候選碼後,算法結束.
第5 步,對UB 中的屬性及屬性組合利用上述的定義4 依次進行判斷;找出所有的候選碼後,算法結束.
簡而言之:取最小依賴集,計算UL閉包,如果UL閉包包含全屬性,則UL為唯一侯選碼,如果不包含,則依次與UB屬性組合後再求閉包是否包含全屬性。
(UL為空時,直接取UB依次組合求閉包)
多屬性依賴集候選碼求解法
輸入:關系模式R及其函數依賴集F。
輸出:R的所有候選碼。
具體步驟:
1)把R的所有屬性分為L、R、N和LR四類,并令X代表L、N類,Y代表LR類。
2)求X+,如果X+包含了R的全部屬性,則X為R的唯一候選碼,轉⑸;否則,轉⑶。
3)在Y中取一個屬性A,求(XA)+,如果它包含了R的全部屬性,則轉⑷;否則,調換一個屬性反複進行這一過程,直到試完所有Y中的屬性。
4)如果已經找到所有的候選碼,則轉⑸;否則在Y中依次去兩個、三個……求它們的屬性閉包,直到其閉包包含R的所有屬性。
5)停止,輸出結果。
簡而言之:取一個X屬性(X為L、N類)求閉包,如果包含R全部屬性則為碼,否則取一個LR類的Y屬性A,求XA閉包,未包含R全屬性則調換A,包含R全屬性且找到所有碼則結束,否則依次取2、3個。
依次遞推法
具體方法:給出一個關系模式R及所對應的函數依賴集F,經過初步判斷,在函數依賴集中沒有屬于L的屬性,所有屬性都是屬于LR類的,此時可以在函數依賴集中找出作為确定因素在左部出現頻率最多的屬性,如X,求X閉包,若其閉包包含了R中的所有屬性,則X為R的一個候選碼;再找出能夠确定X的屬性,如Y→X,求Y的閉包,若Y的閉包包含了R中的所有屬性,則Y為R的一個候選碼,依次往下找,直到把所有的函數依賴找完;單個屬性的找完了後再找兩個屬性結合的,注意:此時不應該把原來求解出的候選碼再進行組合(可以采用一般求解法)。
如設有關系模式R(A,B,C,D,E),其上的函數依賴集F={A→BC,CD→E,B→D,E→A},求出R的所有候選碼。
根據上述方法,具體求解步驟如下:把F右部單一化後F={A→B,A→C,CD→E,B→D,E→A};根據判斷,A作為确定因素在左部出現的頻率最高,求A+=ABCDE,又有E→A,求E+=ABCDE而CD→E,求(CD)+=ABCDE,可以得出屬性A,E,CD為候選碼;除去A,E,CD外,根據一般求解法求兩個屬性組合的閉包,可以得到(BC)+=ABCDE,最後可以算出R的候選碼為:A,E,CD,BC。
簡而言之:沒有L,所有屬性都屬LR,取左邊出現頻率最多的屬性X,求X+,若包含R中所有屬性,則X為侯選碼。找能決定X的屬性Y,求Y+,說Y+包含R中所有屬性,則Y也是。單個完後找兩兩結合,依次類推。(侯選碼不參與結合)
一般的求候選碼的算法
已知關系模式R(U)屬性集是A A ...A 及R的函數依賴集F,求R(U)的一個候選碼。
算法:
KEY(X,F)
K=A1A2…An;
For i=1 to n
{求K-Ai相對于F的屬性閉包(K-Ai)F+;
if (K-Ai)F + =U then K=K-Ai
else then K=K; }
return K;
利用此算法求R(U)的候選碼時,隻能求出一個,并不能保證求出所有的碼。但可以用同樣的方法調整屬性的删除次序而把所有的候選碼都求解出來。
如此題設關系R(ABCD)及R上成立的函數依賴集為F,F={AB→C,C→D,D→A},求R的所有碼。
按照上面的算法具體步驟如下:
設K={ABCD},當K=BCD時,由于KF+=ABCD,所以根據算法可删除A;
K=CD,由于KF+=ACD又因KF+不等于ABCD,所以根據算法,B不可删除;
K=BD,由于KF+=ABCD且因KF+=AB-CD,所以根據算法C可删除;
K=B,由于KF+=B又因KF+不等于ABCD,
所以根據算法,D不可删除;最後可求出KEY=BD,用同樣的方法調整屬性的删除次序,還可以得到另外的一個候選碼AB,所以最後可以得到R的碼為BD和AB。
一般求解算法适用于在判斷了所有的屬性均是屬于在函數依賴的左部和右部都出現且在後面的幾種算法都不适合的情況下采用的。
簡而言之:算法概述——有N個屬性,從1到N循環。K初始為全部屬性,每次循環時減去第N個屬性,如果KF+包含全部屬性,則K的值重新附值為K減去第N個屬性後的值;否則K仍為上次循環後的值。(算法适于所有屬性皆為LR類且其他算法不合适時,實際算時要更換删除順序後反複計算)
快速求候選碼的方法
首先對于給定的R(U)和函數依賴集F,可以将它的屬性劃分為4類:
L類,僅出現在F的函數依賴左部的屬性。
R類,僅出現在F的函數依賴右部的屬性。
N類,在F的函數依賴左部和右部均未出現的屬性。
LR類,在F的函數依賴左部和右部兩部均出現的屬性。
根據以下定理和推論來求解候選碼。
定理1:對于給定的關系模式R及其函數依賴集F,若X(X∈R)是L類屬性,則X必為R的任一候選碼的成員。
推論1:對于給定的關系模式R及其函數依賴集F,若X(X∈R)是L類屬性,且X+包含了R的全部屬性,則X必為R的唯一候選碼。
定理2:對于給定的關系模式R及其函數依賴集F,若X(X∈R)是R類屬性,則X不在任何候選碼中。
定理3:設有關系模式R及其函數依賴集F,如果X是R的N類屬性,則X必包含在R的任一候選碼中。
推論2:對于給定的關系模式R及其函數依賴集F,如果X是R的N類和L類組成的屬性集,且X+包含了R的有屬性,則X是R的唯一候選碼。
例:如設有關系模式R(U),其函數依賴集為F,其中:
U={A,B,C,D,E},F={A→C,C→A,B→AC,D→AC}
求R的候選碼。
解:根據函數依賴可得:
屬性B、D為L類,E為N類,因此屬性B、D、E必為候選碼的成員,且此三個屬性的閉包:B+=ABC,(BD)+=ABCD,(BDE)+=ABCDE,根據推論2可得BDE是R的唯一候選碼。所以R的候選碼為BDE。
如果把例題中關系模式R(U)中的屬性E去掉,那麼再求R的候選碼的話可以根據推論1得出BD為R的唯一候選碼。
快速求解方法适用于判斷有屬性是屬于L類、N類或其中一種的情況下求解。如果有L類和N類的屬性,則求解候選碼速度非常快。
簡而言之:L、R、N、LR類。根據定理,L、N類必為侯選碼之一,如果L+包含全部R,則L為唯一侯選。R類不在任何侯選碼中。L+N類且(L+N)+包含所有R,則L+N為唯一侯選。(适于有L、N類至少一種的情況。)
圖論判定方法
左邊為單屬性的函數依賴集的候選碼成員的圖論判定方法
算法2:單屬性依賴集圖論求解法。
輸入:關系模式R,R的單屬性函數依賴集F。
輸出:R的所有候選碼。
步驟:
1、求F的最小函數依賴集;
2、構造函數依賴圖FDG;
3、從圖中找出關鍵屬性集X(X可為空);
4、查看G中有無獨立回路,如果沒有則輸出X即為R的唯一候選碼,轉6);如果有則轉5);
5、從各獨立回路中去取一結點對應的屬性與X組合成一候選碼,并重複這一過程,取盡所有可能的組合,即為R的全部候選碼;
6、結束。
如已知有關系模式R(U),其函數依賴集為F,其中:
R={A,B,C,D,E,F},F={A→B,C→D,D→E,E→F,F→C},求R的所有候選碼。
根據算法,具體步驟如下:
求最小函數依賴集Fm,Fm={ A→B,C→D,D→E,E→F,F→C };
構造函數依賴圖。
關鍵屬性為:A
在圖1中可以看到有一條獨立回路CDFE,所以M=4,因此共有4個候選碼,每個候選碼有N=1+1=2個屬性。
最後可得R的候選碼為:AC,AD,AE,AF。
此方法适用于左部是單個屬性的函數依賴求解候選碼,而且如果用快速求解法又不是能很快地求解出來候選碼來的情況。


















