基本介紹
- 中文名：候選關鍵字
- 外文名：Candidate Key
- 具體步驟：5步
- 適用於：左部是單個屬性的函式
- 輸入：關係模式R及其函式依賴集F
- 輸出：R的所有候選碼
定義,具體步驟,選碼求解法,依次遞推法,一般算法,快速方法,圖論判定,
定義
如果一個超關鍵字去掉其中任何一個欄位後不再能唯一地確定記錄
具體步驟
第2 步，按照上面的定義,分別計算出UL,UR,UB （UL 表示僅在函式依賴集中各依賴關係式左邊出現的屬性的集合； UR 表示僅在函式依賴集中各依賴關係式右邊出現的屬性的集合；另記UB = U - UL - UR）
第4 步，將UL 依次與UB 中的屬性組合，利用上述的定義4 判斷該組合屬性是否是候選碼； 找出所有的候選碼後，算法結束.
第5 步，對UB 中的屬性及屬性組合利用上述的定義4 依次進行判斷；找出所有的候選碼後，算法結束.
（UL為空時，直接取UB依次組合求閉包）
選碼求解法
輸出：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個。
依次遞推法
根據上述方法，具體求解步驟如下：把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也是。單個完後找兩兩結合，依次類推。（侯選碼不參與結合）
一般算法
算法：
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的全部屬性，則X必為R的唯一候選碼。
定理2：對於給定的關係模式R及其函式依賴集F，若X(X∈R）是R類屬性，則X不在任何候選碼中。
定理3：設有關係模式R及其函式依賴集F，如果X是R的N類屬性，則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。
快速求解方法適用於判斷有屬性是屬於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
