數據庫課程中基于圖的關系候選碼分析方法

摘 要: 在數據庫課程教學中，分析關系的候選碼是認識關系的第一步，也是進一步學習關系數據理論的基礎。本文從關系候選碼的定義出發，在分析數據依賴的基礎上，提出一種基于圖形方式的關系候選碼分析方法，并通過舉例說明該方法在實際中的運用。實踐證明，本方法在數據庫課程教學過程中具有良好效果。

關鍵詞: 數據庫 關系候選碼 數據依賴 完全函數依賴

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

1.基于圖的關系候選碼分析方法介紹

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

現在已經提出的數據依賴的類型[4]-[5]主要有:

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

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

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

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

分析具體關系的候選碼時，主要解決三個問題:

首先，確定已知關系R〈U，F〉中哪些屬性或屬性組作為候選碼的判斷對象，設判斷對象為K;

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

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

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

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

對于F中的任何一個數據依賴X→Y，稱X為函數依賴中的決定因素，Y為函數依賴中的被決定因素。故在F中出現的屬性或屬性組有兩種情況:決定因素和被決定因素，所以將候選碼的判斷對象確定為F中的決定因素和被決定因素。

1.2判斷是否滿足K→U

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

1.3判斷是否滿足KU

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

2.基于圖的關系候選碼分析方法舉例

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

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

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

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

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

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

第三步:判斷是否滿足KU

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

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

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

所以ACDU，CDU。

關系R的候選碼是AB，BC，CD。

關系候選碼的定義是抽象、簡潔的。但是對于關系數據理論的初學者，分析關系的候選碼卻常常遇到困難，尤其是對比較復雜的關系更是無從下手。運用該方法可以將抽象、簡潔的定義，轉換為形象、簡單的分析過程，從而成為認識關系和學習關系數據理論的工具和幫助。

參考文獻:

[1]嚴云洋，楊民.關系數據庫模式中候選碼的求解算法[J].現代計算機，1999，(06).

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

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

[4]施伯樂，丁寶康.數據庫技術[M].北京:科學出版社，2002.

[5]王能斌.數據庫系統教程[M](上).北京:電子工業出版社，2002.