數(shù)據(jù)庫課程中基于圖的關(guān)系候選碼分析方法

摘 要: 在數(shù)據(jù)庫課程教學(xué)中，分析關(guān)系的候選碼是認(rèn)識關(guān)系的第一步，也是進(jìn)一步學(xué)習(xí)關(guān)系數(shù)據(jù)理論的基礎(chǔ)。本文從關(guān)系候選碼的定義出發(fā)，在分析數(shù)據(jù)依賴的基礎(chǔ)上，提出一種基于圖形方式的關(guān)系候選碼分析方法，并通過舉例說明該方法在實(shí)際中的運(yùn)用。實(shí)踐證明，本方法在數(shù)據(jù)庫課程教學(xué)過程中具有良好效果。

關(guān)鍵詞: 數(shù)據(jù)庫 關(guān)系候選碼 數(shù)據(jù)依賴 完全函數(shù)依賴

從E.E.Codd提出關(guān)系規(guī)范化理論至今，關(guān)于這一理論的研究已經(jīng)取得了很多成果。對于關(guān)系的候選碼，在規(guī)范化理論中有嚴(yán)格的定義，但是針對具體的關(guān)系，尤其當(dāng)沒有給出關(guān)于關(guān)系的具體的語義信息時(shí)，只是已知關(guān)系的屬性組及屬性組上的數(shù)據(jù)依賴的情況下，該如何分析出關(guān)系的候選碼，目前已經(jīng)有一些研究，[1]-[2]但這些方法都較為復(fù)雜，不利于學(xué)生的掌握。本文提出一種基于圖的分析方法，可以快速得到關(guān)系的候選碼。

1.基于圖的關(guān)系候選碼分析方法介紹

分析關(guān)系的候選碼的方法，主要依據(jù)的是候選碼的定義[3]，即設(shè)K為關(guān)系R〈U，F(xiàn)〉中的屬性或?qū)傩越M合，若KU，則K為R的候選碼。其中，R為關(guān)系名，U為關(guān)系R的一組屬性，F(xiàn)為屬性組U上的一組數(shù)據(jù)依賴，KU表示U對K完全函數(shù)依賴。所謂數(shù)據(jù)依賴就是通過一個關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系。

現(xiàn)在已經(jīng)提出的數(shù)據(jù)依賴的類型[4]-[5]主要有:

#8226;函數(shù)依賴(Functional Dependency，簡稱FD);

#8226;多值依賴(Multivalued Dependency，簡稱MVD);

#8226;聯(lián)接依賴(Join Dependency，簡稱JD)。

本文主要討論的是函數(shù)依賴。函數(shù)依賴的定義[3]是:設(shè)R(U)是屬性集U上的關(guān)系模式，X、Y是U的子集，若對于R(U)的任意一個可能的關(guān)系r，r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱X函數(shù)確定Y或Y函數(shù)依賴于X，記作X→Y。完全函數(shù)依賴是指在R(U)中，如果X→Y，并且對于X的任何一個真子集X′，都有X′→Y，則稱Y對X完全函數(shù)依賴，記作:XY。

分析具體關(guān)系的候選碼時(shí)，主要解決三個問題:

首先，確定已知關(guān)系R〈U，F(xiàn)〉中哪些屬性或?qū)傩越M作為候選碼的判斷對象，設(shè)判斷對象為K;

其次，對所有的判斷對象K逐一判斷是否滿足K→U;

最后，對已經(jīng)滿足K→U的判斷對象K再判斷是否滿足KU。

1.1確定候選碼的判斷對象K

確定已知關(guān)系R〈U，F(xiàn)〉中哪些屬性或?qū)傩越M作為候選碼的判斷對象(設(shè)判斷對象為K)主要根據(jù)候選碼的定義。由候選碼的定義可知K可以是關(guān)系R中的屬性，也可以是關(guān)系R中的屬性組。這似乎就使選取候選碼的判斷對象的問題變成了一個組合問題，即若U中的屬性個數(shù)為n，候選碼的判斷對象的個數(shù)就有可能是C(n，1)+C(n，2)+…+C(n，n)。在C(n，1)+C(n，2)+…+C(n，n)種可能中，是否有必要對每一種可能判斷其滿足K→U?回答是否定的。因?yàn)閷τ跊]有出現(xiàn)在F中的屬性或?qū)傩越M，我們沒有判斷其是否滿足K→U的依據(jù)，所以也就沒有判斷的必要。據(jù)此，將候選碼的判斷對象的范圍縮小為在F中出現(xiàn)的屬性或?qū)傩越M。

對于F中的任何一個數(shù)據(jù)依賴X→Y，稱X為函數(shù)依賴中的決定因素，Y為函數(shù)依賴中的被決定因素。故在F中出現(xiàn)的屬性或?qū)傩越M有兩種情況:決定因素和被決定因素，所以將候選碼的判斷對象確定為F中的決定因素和被決定因素。

1.2判斷是否滿足K→U

對所有的判斷對象K逐一判斷是否滿足K→U。采用圖示的方法，表示這一判斷過程。對于F中的任何一個數(shù)據(jù)依賴X→Y，“→”用有向邊表示，并以決定因素X為起點(diǎn)指向被決定因素Y;每一個判斷對象對應(yīng)一個U(關(guān)系R的所有屬性)，并且在U中用圓圈將判斷對象圈起，表示該判斷對象已知;然后對每一個判斷對象在F中找出與之有關(guān)的數(shù)據(jù)依賴，并用有向邊在U中一一標(biāo)出。當(dāng)某一個判斷對象所對應(yīng)的U中，除了判斷對象被圓圈圈起外，其余屬性都被有向邊所指時(shí)，就滿足K→U。否則，就不滿足K→U。

1.3判斷是否滿足KU

對已經(jīng)滿足K→U的判斷對象K，再判斷是否滿足KU。如果K為關(guān)系R中的屬性，K的任何一個真子集K1是Ф，就有K1U，即滿足KU。即如果K為關(guān)系R中的屬性，K的任何一個非空真子集K′都是不存在，所以無需再判斷K′是否滿足K′→U，該K就是關(guān)系R的候選碼。如果K為關(guān)系R中的屬性組，對于K的任何一個非空真子集K′，都要采用圖示方法討論它是否滿足K′→U。只要有一個非空真子集K′滿足K′→U，那么就不滿足U對K完全函數(shù)依賴，即該K不是關(guān)系R的候選碼。

2.基于圖的關(guān)系候選碼分析方法舉例

本節(jié)通過一個多碼的例子說明基于圖的關(guān)系候選碼的分析過程。假設(shè)已知關(guān)系R的定義如下:R<{A，B，C，D}，{AB→C，C→A，BC→D，ACD→B}>，要求分析關(guān)系R的候選碼。

第一步:確定候選碼的判斷對象K

F中的決定因素:AB，C，BC，ACD

被決定因素:A，B，C，D

第二步:判斷是否滿足K→U

所以，滿足K→U的判斷對象K有AB，BC，ACD。

第三步:判斷是否滿足KU

AB的非空真子集K′是A，B。在第二步已經(jīng)判斷過K′→U，所以ABU。

BC的非空真子集K′是B，C。在第二步已經(jīng)判斷過K′→U，所以BCU。

ACD的非空真子集K′是A，C，D，AC，CD，AD。A，C，D在第二步已經(jīng)判斷過K′→U，所以現(xiàn)在只需判斷AC，CD，AD。

所以ACDU，CDU。

關(guān)系R的候選碼是AB，BC，CD。

關(guān)系候選碼的定義是抽象、簡潔的。但是對于關(guān)系數(shù)據(jù)理論的初學(xué)者，分析關(guān)系的候選碼卻常常遇到困難，尤其是對比較復(fù)雜的關(guān)系更是無從下手。運(yùn)用該方法可以將抽象、簡潔的定義，轉(zhuǎn)換為形象、簡單的分析過程，從而成為認(rèn)識關(guān)系和學(xué)習(xí)關(guān)系數(shù)據(jù)理論的工具和幫助。

參考文獻(xiàn):

[1]嚴(yán)云洋，楊民.關(guān)系數(shù)據(jù)庫模式中候選碼的求解算法[J].現(xiàn)代計(jì)算機(jī)，1999，(06).

[2]姜翠霞.關(guān)于確定關(guān)系模式的候選碼的研究[J].齊齊哈爾大學(xué)學(xué)報(bào)，2003，(04).

[3]薩師煊，王珊.數(shù)據(jù)庫系統(tǒng)概論[M](第三版).北京:高等教育出版社，2000.

[4]施伯樂，丁寶康.數(shù)據(jù)庫技術(shù)[M].北京:科學(xué)出版社，2002.

[5]王能斌.數(shù)據(jù)庫系統(tǒng)教程[M](上).北京:電子工業(yè)出版社，2002.