候選碼

若關係中的某一屬性或屬性組的值能唯一的標識一個元組，而其任何、子集都不能再標識，則稱該屬性組為（超級碼）候選碼。

例如：在學生實體中，“學號”是能唯一的區分學生實體的，同時又假設“姓名”、“班級”的屬性組合足以區分學生實體，那麼{學號}和{姓名，班級}都是（超級碼）候選碼。

簡單的説，候選碼（超級碼）就是可以被選為主碼的屬性或屬性組。當一個關係有N個屬性或屬性組可以唯一標識時，則説明該關係有N個候選碼，可以選定其中一個作為主碼。

候選碼中出現過的屬性稱為主屬性；非主屬性就是不包含在任何候選碼中的屬性

例如：關係 工人（工號，身份證號，姓名，性別，部門）.顯然工號和身份證號都能夠唯一標示這個關係，所以都是候選碼。工號、身份證號這兩個屬性就是主屬性。如果主碼是一個屬性組，那麼屬性組中的屬性都是主屬性。

第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）屬性集是A1A2...An及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的所有候選碼。

步驟：

⒈求F的最小函數依賴集；

⒉構造函數依賴圖FDG;

⒊從圖中找出關鍵屬性集X(X可為空）；

⒋查看G中有無獨立迴路，如果沒有則輸出X即為R的唯一候選碼，轉6）；如果有則轉5）；

⒌從各獨立迴路中去取一結點對應的屬性與X組合成一候選碼，並重復這一過程，取盡所有可能的組合，即為R的全部候選碼；

⒍結束。

如已知有關係模式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。

此方法適用於左部是單個屬性的函數依賴求解候選碼，而且如果用快速求解法又不是能很快地求解出來候選碼來的情況。