資源描述：
《候選碼的求解理論和算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、求關(guān)系模式中的候選鍵，是軟考中的考點(diǎn)，但視頻中沒(méi)有講，所以值得一提。?求閉包給定關(guān)系模式R（U，F(xiàn)），U={A，B，C，D，E}，F(xiàn)={B->A,D->A,A->E,AC->B},其屬性AD的閉包為_(kāi)_____.解：設(shè)X(0)=AD，計(jì)算X(1)：逐一掃描F集中的各個(gè)函數(shù)依賴，找左部是A、D、AD的函數(shù)依賴，得到AE。于是X(1)=X(0)∪EA=ADE。由于X(0)!=X(1)，所以繼續(xù)掃描，于是X(2)=X(1)∪EA=ADE。由于X(2)=X(1)，所以算法到此為止，屬性AD的閉包為X(2)，即ADE。?首先來(lái)看候選鍵的定義：若關(guān)系中
2、的某一屬性組的值能唯一地標(biāo)識(shí)一個(gè)元組，則稱該屬性組為候選鍵。若W是候選鍵，則必須滿足兩個(gè)條件：W的閉包是U；W沒(méi)有冗余。設(shè)關(guān)系模式R中U=ABC.......等N個(gè)屬性，U中的屬性在FD中有四種范圍：(1)左右出現(xiàn);(2)只在左部出現(xiàn);(3)只在右部出現(xiàn);(4)不在左右出現(xiàn);算法：按以下步驟求候選鍵：1.只在FD右部出現(xiàn)的屬性，不屬于候選碼;2.只在FD左部出現(xiàn)的屬性，一定存在于某候選碼當(dāng)中;3.外部屬性一定存在于任何候選碼當(dāng)中;4.其他屬性逐個(gè)與2,3的屬性組合，求屬性閉包，直至X的閉包等于U,若等于U,則X為候選碼。例1：R,
3、U=(A,B,C,D,E,G),F={AB-->C,CD-->E,E-->A.A-->G},求候選碼。??因G只在右邊出現(xiàn),所以G一定不屬于候選碼;而B(niǎo),D只在左邊出現(xiàn),所以B,D一定屬于候選碼;BD的閉包還是BD,則對(duì)BD進(jìn)行組合,除了G以外,BD可以跟A,C,E進(jìn)行組合??先看ABD??ABD本身自包ABD,而AB-->C,CD-->E,A-->G,所以ABD的閉包為ABDCEG=U?再看BDC??CD-->E,E-->A,A-->G,BDC本身自包,所以BDC的閉包為BDCEAG=U??最后看BDE??E-->A,A-->G,AB--
4、>C,BDE本身自包,所以BDE的閉包為BDEAGC=U??因?yàn)?ABD)、(BCD)、(BDE)的閉包都是ABCDEG所以本問(wèn)題的候選碼有3個(gè)分別是ABC、BCD和BDE?例2：R,U=(A,B,C),F={AB-->C,C-->B},求候選碼。因?yàn)锳只出現(xiàn)在左邊，所以A一定是候選鍵。A的閉包還是A，則對(duì)A進(jìn)行組合，可以和B,C進(jìn)行組合。首先看AB，AB本身自包AB，而AB-->C，所以AB的閉包是ABC=U。再看AC，AC本身自包AC，而C-->B，所以AC的閉包是ABC=U。因?yàn)锳B,AC的閉包都是ABC，也就是U，所以候選
5、鍵是AB，AC。?例（1）；設(shè)有關(guān)系模式R(U，F(xiàn))，其中U={A，B，C，D，E，I}，F(xiàn)={A→D，AB→E，BI→E，CD→I，E→C}，計(jì)算(AE)+????解:?(1)?令X={AE}，X(0)=AE??????(2)在F中尋找尚未使用過(guò)的左邊是AE的子集的函數(shù)依賴，結(jié)果是:?A→D，?E→C；所以?X(1)=X(0)DC=ACDE，?顯然?X(1)≠X(0).??????(3)?在F中尋找尚未使用過(guò)的左邊是ACDE的子集的函數(shù)依賴，?結(jié)果是:?CD→I；所以?X(2)=X(1)I=ACDEI。雖然X（2）≠X(1)，但F中尋找尚
6、未使用過(guò)函數(shù)依賴的左邊已經(jīng)沒(méi)有X（2）的子集，所以不必再計(jì)算下去，即(AE)+=ACDEI?！ ≌f(shuō)白話一點(diǎn)：閉包就是由一個(gè)屬性直接或間接推導(dǎo)出的所有屬性的集合。????例如：f={a->b，b->c，a->d，e->f}；由a可直接得到b和d，間接得到c，則a的閉包就是{a，b，c，d}?候選碼的求解理論和算法 對(duì)于給定的關(guān)系R（A1，A2，…An）和函數(shù)依賴集F，可將其屬性分為4類： L類??僅出現(xiàn)在函數(shù)依賴左部的屬性?！ ?類??僅出現(xiàn)在函數(shù)依賴右部的屬性?！ ?類??在函數(shù)依賴左右兩邊均未出現(xiàn)的屬性?！ R
7、類??在函數(shù)依賴左右兩邊均出現(xiàn)的屬性?！ 《ɡ恚簩?duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X（X∈R）是L類屬性，則X必是候選碼中的成員。 推論：對(duì)于給定的關(guān)系模式R及其函數(shù)依賴集F，若X（X∈R）是L類屬性，且X+包含了R的全部屬性；則X必為R的唯一候選碼。 例（2）：設(shè)有關(guān)系模式R（A，B，C，D），其函數(shù)依賴集F={D→B，B?→D，AD?→B，AC?→D}，求R的所有候選碼解：考察F發(fā)現(xiàn)，A，C兩屬性是L類屬性，所以AC必是R的候選碼成員(A的閉包一定不是全集)，又因?yàn)椋ˋC）+=ABCD，所以AC是R的唯一候選碼?！ 《ɡ恚簩?duì)于
8、給定的關(guān)系模式R及其函數(shù)依賴集F，若X（X∈R）是R類屬性，則X元素一定不是候選碼中的?！ ?duì)于LR類，求出其閉包，若包含所有屬性，則為候選鍵；若不包含，再和LR類中的其他屬性組
