候選碼的求解基本方法集合

1、候選碼的求解基本方法集合 一、求解候選碼基本算法的具體步驟.第1 步,求關(guān)系模式R < U , F > 的最小函數(shù)依賴集F第2 步, 按照上面的定義, 分別計(jì)算出UL ,UR , UB （UL 表示僅在函數(shù)依賴集中各依賴關(guān)系式左邊出現(xiàn)的屬性的集合; UR 表示僅在函數(shù)依賴集中各依賴關(guān)系式右邊出現(xiàn)的屬性的集合;另記UB = U - UL - UR ）第3 步,若UL ,計(jì)算UL的閉包，若UL+ = U ,則UL 為R 的唯一的候選碼,算法結(jié)束. 若UL+ U ,轉(zhuǎn)第4 步. 若UL = ,轉(zhuǎn)第5 步.第4 步,將UL 依次與UB 中的屬性組合,利用上述的定義4 判斷該組合屬性是否是候

2、選碼; 找出所有的候選碼后,算法結(jié)束.第5 步,對UB 中的屬性及屬性組合利用上述的定義4 依次進(jìn)行判斷;找出所有的候選碼后,算法結(jié)束.簡而言之：取最小依賴集，計(jì)算UL閉包，如果UL閉包包含全屬性，則UL為唯一侯選碼，如果不包含，則依次與UB屬性組合后再求閉包是否包含全屬性。（UL為空時(shí)，直接取UB依次組合求閉包）二、多屬性依賴集候選碼求解法輸入:關(guān)系模式R及其函數(shù)依賴集F。輸出:R的所有候選碼。具體步驟:1)把R的所有屬性分為L、R、N和LR四類,并令X代表L、N類,Y代表LR類。2)求X+,如果X+包含了R的全部屬性,則X為R的唯一候選碼,轉(zhuǎn)(5);否則,轉(zhuǎn)(3)。3)在Y中取一個(gè)屬性A,

3、求(XA)+,如果它包含了R的全部屬性,則轉(zhuǎn)(4);否則,調(diào)換一個(gè)屬性反復(fù)進(jìn)行這一過程,直到試完所有Y中的屬性。4)如果已經(jīng)找到所有的候選碼,則轉(zhuǎn)(5);否則在Y中依次去兩個(gè)、三個(gè)求它們的屬性閉包,直到其閉包包含R的所有屬性。5)停止,輸出結(jié)果。簡而言之：取一個(gè)X屬性（X為L、N類）求閉包，如果包含R全部屬性則為碼，否則取一個(gè)LR類的Y屬性A，求XA閉包，未包含R全屬性則調(diào)換A，包含R全屬性且找到所有碼則結(jié)束，否則依次取2、3個(gè)。三、依次遞推法：具體方法:給出一個(gè)關(guān)系模式R及所對應(yīng)的函數(shù)依賴集F,經(jīng)過初步判斷,在函數(shù)依賴集中沒有屬于L的屬性,所有屬性都是屬于LR類的,此時(shí)可以在函數(shù)依賴集中找出

4、作為確定因素在左部出現(xiàn)頻率最多的屬性,如X,求X閉包,若其閉包包含了R中的所有屬性,則X為R的一個(gè)候選碼;再找出能夠確定X的屬性,如YX,求Y的閉包,若Y的閉包包含了R中的所有屬性,則Y為R的一個(gè)候選碼,依次往下找,直到把所有的函數(shù)依賴找完;單個(gè)屬性的找完了后再找兩個(gè)屬性結(jié)合的,注意:此時(shí)不應(yīng)該把原來求解出的候選碼再進(jìn)行組合(可以采用一般求解法)。如設(shè)有關(guān)系模式R(A,B,C,D,E),其上的函數(shù)依賴集F=ABC,CDE,BD,EA,求出R的所有候選碼。根據(jù)上述方法,具體求解步驟如下:把F右部單一化后F= AB,AC,CDE,BD,EA ;根據(jù)判斷,A作為確定因素在左部出現(xiàn)的頻率最高,求A+=

5、ABCDE,又有EA,求E+=ABCDE而CDE,求(CD)+=ABCDE,可以得出屬性A,E,CD為候選碼;除去A,E,CD外,根據(jù)一般求解法求兩個(gè)屬性組合的閉包,可以得到(BC)+=ABCDE,最后可以算出R的候選碼為:A,E,CD,BC。簡而言之：沒有L，所有屬性都屬LR，取左邊出現(xiàn)頻率最多的屬性X，求X+，若包含R中所有屬性，則X為侯選碼。找能決定X的屬性Y，求Y+，說Y+包含R中所有屬性，則Y也是。單個(gè)完后找兩兩結(jié)合，依次類推。（侯選碼不參與結(jié)合）四、一般的求候選碼的算法已知關(guān)系模式R(U)屬性集是A1A2.An及R的函數(shù)依賴集F,求R(U)的一個(gè)候選碼。算法：KEY(X,F)K=A

6、1A2An;For i=1 to n求K-Ai相對于F的屬性閉包(K-Ai)F+;if (K-Ai)F + =U then K=K-Aielse then K=K; return K;利用此算法求R(U)的候選碼時(shí),只能求出一個(gè),并不能保證求出所有的碼。但可以用同樣的方法調(diào)整屬性的刪除次序而把所有的候選碼都求解出來。如此題設(shè)關(guān)系R(ABCD)及R上成立的函數(shù)依賴集為F,F=ABC,CD,DA,求R的所有碼。按照上面的算法具體步驟如下:設(shè)K=ABCD,當(dāng)K=BCD時(shí),由于KF+=ABCD，所以根據(jù)算法可刪除A;K=CD,由于KF+=ACD又因KF+不等于ABCD,所以根據(jù)算法,B不可刪除;K=B

7、D,由于KF+=ABCD且因KF+=AB-CD,所以根據(jù)算法C可刪除;K=B,由于KF+=B又因KF+不等于ABCD,所以根據(jù)算法,D不可刪除;最后可求出KEY=BD,用同樣的方法調(diào)整屬性的刪除次序,還可以得到另外的一個(gè)候選碼AB,所以最后可以得到R的碼為BD和AB。一般求解算法適用于在判斷了所有的屬性均是屬于在函數(shù)依賴的左部和右部都出現(xiàn)且在后面的幾種算法都不適合的情況下采用的。簡而言之：算法概述有N個(gè)屬性，從1到N循環(huán)。K初始為全部屬性，每次循環(huán)時(shí)減去第N個(gè)屬性，如果KF+包含全部屬性，則K的值重新附值為K減去第N個(gè)屬性后的值；否則K仍為上次循環(huán)后的值。（算法適于所有屬性皆為LR類且其他算法

8、不合適時(shí)，實(shí)際算時(shí)要更換刪除順序后反復(fù)計(jì)算）五、快速求候選碼的方法首先對于給定的R(U)和函數(shù)依賴集F,可以將它的屬性劃分為4類:L類,僅出現(xiàn)在F的函數(shù)依賴左部的屬性。R類,僅出現(xiàn)在F的函數(shù)依賴右部的屬性。N類,在F的函數(shù)依賴左部和右部均未出現(xiàn)的屬性。LR類,在F的函數(shù)依賴左部和右部兩部均出現(xiàn)的屬性。根據(jù)以下定理和推論來求解候選碼。定理1:對于給定的關(guān)系模式R及其函數(shù)依賴集F,若X(XR)是L類屬性,則X必為R的任一候選碼的成員。推論1:對于給定的關(guān)系模式R及其函數(shù)依賴集F,若X(XR)是L類屬性,且X+包含了R的全部屬性,則X必為R的唯一候選碼。定理2:對于給定的關(guān)系模式R及其函數(shù)依賴集F,

9、若X(XR)是R類屬性,則X不在任何候選碼中。定理3:設(shè)有關(guān)系模式R及其函數(shù)依賴集F,如果X是R的N類屬性,則X必包含在R的任一候選碼中。推論2:對于給定的關(guān)系模式R及其函數(shù)依賴集F,如果X是R的N類和L類組成的屬性集,且X+包含了R的有屬性,則X是R的唯一候選碼。例：如設(shè)有關(guān)系模式R(U),其函數(shù)依賴集為F,其中:U=A,B,C,D,E,F=AC,CA,BAC,DAC求R的候選碼。解:根據(jù)函數(shù)依賴可得:屬性B、D為L類,E為N類,因此屬性B、D、E必為候選碼的成員,且此三個(gè)屬性的閉包:B+=ABC,(BD)+=ABCD,(BDE)+=ABCDE,根據(jù)推論2可得BDE是R的唯一候選碼。所以R的

10、候選碼為BDE。如果把例題中關(guān)系模式R(U)中的屬性E去掉,那么再求R的候選碼的話可以根據(jù)推論1得出BD為R的唯一候選碼?？焖偾蠼夥椒ㄟm用于判斷有屬性是屬于L類、N類或其中一種的情況下求解。如果有L類和N類的屬性,則求解候選碼速度非?？臁：喍灾篖、R、N、LR類。根據(jù)定理，L、N類必為侯選碼之一，如果L+包含全部R，則L為唯一侯選。R類不在任何侯選碼中。L+N類且（L+N）+包含所有R，則L+N為唯一侯選。（適于有L、N類至少一種的情況。）六、左邊為單屬性的函數(shù)依賴集的候選碼成員的圖論判定方法算法2:單屬性依賴集圖論求解法。輸入:關(guān)系模式R,R的單屬性函數(shù)依賴集F。輸出:R的所有候選碼。步驟:1、求F的最小函數(shù)依賴集;2、構(gòu)造函數(shù)依賴圖FDG;3、從圖中找出關(guān)鍵屬性集X(X可為空);4、查看G中有無獨(dú)立回路,如果沒有則輸出X即為R的唯一候選碼,轉(zhuǎn)6);如果有則轉(zhuǎn)5);5、從各獨(dú)立回路中去取一結(jié)點(diǎn)對應(yīng)的屬性與X組合成一候選碼,并重復(fù)這一過程,取盡所有可能的組合,即為R的全部候選碼;6、結(jié)束。如已知有關(guān)系模式R(U),其函數(shù)依賴集為F,其中：R=A,B,C,D,E,F，F(xiàn)=AB,CD,DE,EF,FC,求R的所有候選碼。根據(jù)算法，具體步驟如下：求最小函數(shù)依