候選關鍵字

如果一個超關鍵字去掉其中任何一個欄位後不再能唯一地確定記錄,則稱它為“候選關鍵字”(Candidate Key)。候選關鍵字既能唯一地確定記錄,它包含的欄位又是最精煉的。也就是說候選關鍵字是最簡單的超關鍵字。

在關係R中如記錄完全函式依賴屬性(組)X,則稱X為關係R中的一個候選關鍵字。

這裡給出幾個求解方法:

基本介紹

  • 中文名:候選關鍵字
  • 外文名:Candidate Key
  • 具體步驟:5步
  • 適用於:左部是單個屬性的函式
  • 輸入:關係模式R及其函式依賴集F
  • 輸出:R的所有候選碼
定義,具體步驟,選碼求解法,依次遞推法,一般算法,快速方法,圖論判定,

定義

如果一個超關鍵字去掉其中任何一個欄位後不再能唯一地確定記錄

具體步驟

第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的所有候選碼。
步驟:
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。
此方法適用於左部是單個屬性的函式依賴求解候選碼,而且如果用快速求解法又不是能很快地求解出來候選碼來的情況。

相關詞條

熱門詞條

聯絡我們