BC范式判定定理及關系的規(guī)范化研究

背景關系模型是目前應用得最為廣泛的數(shù)據(jù)庫模型，關系模型的規(guī)范化理論是關系型數(shù)據(jù)庫邏輯設計的基礎，信息系統(tǒng)開發(fā)人員對關系規(guī)范化的運用能力將直接影響所設計數(shù)據(jù)庫系統(tǒng)的質量， 并進而影響整個系統(tǒng)的性能。范式的概念最早是由IBM公司的研究員E.F.Codd提出的，他于1971至1972年間發(fā)表的一系列論文中系統(tǒng)地提出了1NF,2NF和3NF的標準，并深入探討了關系進一步規(guī)范化的問題，由此奠定了關系規(guī)范化理論的基礎。1974年，E.F.Codd和Boyce又共同提出了BCNF1976年，F(xiàn)agin又提出了4NF,以后又有人提出了5NE雖然關系規(guī)范化的理論研究發(fā)展至今已經(jīng)相當完備，但仍有進一步完善和充實的必要。在函數(shù)依賴的范疇內， BC范式已達到完美的程度（已完全消除了有害的函數(shù)依賴關系），本文試圖在函數(shù)依賴的范疇內對關系規(guī)范化的理論和運用作進一步的探討?！换靖拍罨靖拍睿憾x1（BCNF）給定R和F,對F中的每個函數(shù)依賴X>A,X不包含A,若X為R的超鍵（碼），則稱R關于F是BCNF的。定義1說明，如果一個關系模式R是BCNF,則在R上關于函數(shù)依賴集F的閉包中，每一個函數(shù)依賴a>B要么是平凡的，要么其決定因素a是R的一個超碼。3NF（第三范式）已經(jīng)排除了非主屬性對候選碼的傳遞函數(shù)依賴，但仍然可能存在主屬性之間的部分或傳遞函數(shù)依賴，進而造成數(shù)據(jù)冗余度大、插入異常、刪除異常、更新異常等問題。BCNF要求對于R中的每個函數(shù)依賴XtY,如果Y不是X的真子集，則X中必含有候選碼，也就是說，每一個非平凡的函數(shù)依賴，其決定因素必須包含候選碼，這樣正是對 3NF的不足之處加以補充，所以BCNF是增強的3NF。定義2設R是1NF,若R中的每個屬性都不傳遞函數(shù)依賴于R的任一候選碼，則稱R是BC范式。定義1與定義2的意義是等價的。一方面，假設關系模式R中存在傳遞依賴于候選碼X的一組函數(shù)依賴XtyYta因為傳遞函數(shù)依賴的前提是YtX不成立，所以Y中不應包含候選碼，這使得R不能滿足定義1中的要求，R不能成為BCNF另一方面，假設關系模式R中存在一個非平凡的函數(shù)依賴XtY,其決定因素X中不包含候選碼，那么對于R的任一候選碼K，有Ktx,而XtY,也就是說Y傳遞依賴于候選碼K,這使得R不能滿足定義2的要求，R

不能成為BCNF定義3（最小覆蓋）設F和G是兩個函數(shù)依賴集，若GkF,則稱G為F的一個覆蓋.特別地，當GFa。且不存在G的真子集口作為F的覆蓋，則稱G為F的一個最小覆蓋，記為Fmin。由定義顯然有Fmin FU,且F且Fmin=F+a=F+，事實上，F(xiàn)a=UFm^。二基本性質每個BCNF關系模式都應具有如下三個性質：（1） 所有非主屬性都完全函數(shù)依賴于每個候選碼；（2） 所有主屬性都完全函數(shù)依賴于每個不包含它的候選碼；（3） 沒有任何屬性完全函數(shù)依賴于非主的任何一組屬性。由于R€BCNF按定義排除了任何屬性對碼的傳遞依賴與部分依賴所以R€3NF.但是若R€3NF,則R未必屬于BCNF三定理:定理1設Fax為Fa中僅由X中的屬性組成的函數(shù)依賴的全體，F(xiàn)x為F在X上的投影，即Fx=IIx（F）,則Fax與Fx等價。證Fax二Fx顯然成立.下面證明Fax二Fx,-Y》Z，F(xiàn)x,不失一般性，設Z為單個屬性.根據(jù)Fa的定義，有原子函數(shù)依賴Y' >Z Fa（Y' Y）.因為YZ X,所以Y' Z X,從而Y'>乙Fax。根據(jù)Armstrong公司的增廣律，有YY>Z?Fax+（注意YX）,即Y》Z?Fax+（因為Y' Y），從而Fax+=Fx。證畢。定理2（守恒定理）設X、Y和Z為R上的屬性集.對-X,Y.F+,若X不包含Y,貝SZ>AFm.，ZX;反之，對Z>AFmin,在F中（不是百中）必有X》Y,X不包含Y且ZX。定理3將Fmin分成包含A和不包含A的兩部分，即Fmin—{*,Xi>A,AYj>Bj},其中*表示不合A的函數(shù)依賴，Xi>A表示右邊為A的函數(shù)依賴，AYi>B,表示左邊含有A的函數(shù)依賴，Xi和Yj為屬性集（Yj可以為空），Bj為單個屬性.則FR-a={*,XiYj>Bj,}等價于F在R-A上的投影IIr-a（F）。四判定定理判定規(guī)則1任何一個二目關系R一定是BCNF證明假設關系模式R（A,B）是二目關系，A、B為關系模式R的兩個屬性，R的候選碼存在兩種可能：全碼，即屬性組（AE）構成一個候選碼；單屬性碼，即單屬性A或B構成R的候選碼。解釋如下：（1）全碼屬性組（AB構成一個候選碼，則R中不存在兩個元組，在A和B屬性值上均相等，此時關于R的每一個函數(shù)依賴都包含候選碼，因此R是BCNF單屬性碼A和B之間存在著函數(shù)依賴關系，A-B(或：B-A),R中不存在兩個元組，在A的屬性值上相等而在B的屬性值上不等(或：在B的屬性值上相等而在A的屬性值上不等)。因為R是一個二目關系，所以R中不存在傳遞函數(shù)依賴于候選碼的屬性，因此R是BCNF例1:關系模式DS(Department,Speciality)記錄學院專業(yè)設置情況，Department表示系別，Speciality表示專業(yè)名稱，在專業(yè)設置上不同系別設置的專業(yè)名稱應該不完全相同，所以Speciality可以作為關系模式DS的一個候選碼，DS滿足BCNF的要求。判定規(guī)則2只有一個候選碼的3NF關系模式一定是BCNF證明假設關系模式R(U,F)是一個3NF的關系模式，U為R的屬性集，F(xiàn)為關于R的函數(shù)依賴的集合，K是R唯一的候選碼。⑴因為R是3NF,所以R中的非主屬性都不傳遞依賴于R的候選碼K;⑵假設A是R中的主屬性(組),存在一個不包含候選碼K的屬性集Y(K二Y),使得Y—A成立。令K'=(K-A)UY,貝卩K'—(KA),K'-Y,因為Y-A成立，所以K'-A成立，可得：K'-(K-A)UA,即：K'—K,故關系模式R除候選碼K外還存在另一個候選碼K'，與前提矛盾。綜上所述，只有一個候選碼的3NF關系模式一定是BCNR例2:關系模式Student(Sno,NameBirthday,Gen-der,Address)記錄學生檔案，Sno表示學號，Name表示姓名，Birthday表示出生日期，Gender表示性別，Address表示住址，Sno是該關系模式唯一的候選碼，Student滿足BCNF的要求。判定規(guī)則3至多只有一個復合候選碼（多屬性候選碼）的3NF關系模式一定是BCNF證明假設關系模式R（U,F）是一個3NF的關系模式，U為R的屬性集，F(xiàn)為關于R的函數(shù)依賴的集合，K是R唯一的復合候選碼。（1） 因為R是3NF，所以R中的非主屬性都不傳遞依賴于R的候選碼K；（2） 因為R是3NF，K是R唯一的復合候選碼，所以所有主屬性都完全函數(shù)依賴于每個不包含它的候選碼。綜上所述，只有一個復合候選碼的3NF關系模式一定是BCNR例3:關系模式WPE（WnoPno,Eno,Quantity）記錄倉庫的配件管理情況，其中Wno表示倉庫號，Pno表示配件號，Eno表示職工號，Quantity表示數(shù)量。因為一個倉庫有多個職工、一個職工僅在一個倉庫工作、每個倉庫里一種型號的配件由專人負責、 一個人可以管理幾種配件、同一種型號的配件可以分放在幾個倉庫中， 所以屬性組（Wno卩門0）和（Pno,Eno）都可以構成WPE的候選碼，兩個候選碼相交，又主屬性Wno和Eno之間存在著函數(shù)依賴Eno宀Wno所以WPE不滿足BCNF的要求。綜合BCNF的性質和判定規(guī)則后，可以發(fā)現(xiàn)常出現(xiàn)BCNF的情況是：有超過兩個的復合候選碼且候選碼中屬性有相交，即多個候選碼中存在公共屬性。五BC范式的分解算法BCNF的分解算法僅具備無損連接性，不具有函數(shù)依賴保持性。算法:BCNF分解算法輸入:關系模式R,R的屬性集合U和函數(shù)依賴集F輸出：具有無損連接性的分解 p,p中的所有關系模式都是BCNF方法：p:={R};WHILEp中存在非BCNF的關系模式DO選擇一個非BCNF的模式S€p；選擇S的一個違反BCNF要求的函數(shù)依賴3Y;用兩個關系模式(S-丫)和(XUY)取代p中的S;ENDWHILE結束語目前的關系數(shù)據(jù)庫邏輯設計主要以規(guī)范化設計理論為基礎， 分析關系模式中的數(shù)據(jù)依賴，通過投影分解等方法消除不合理的數(shù)據(jù)依賴， 解決因不合理的數(shù)據(jù)依賴對關系模式帶來的異常問題等。 規(guī)范化設計理論中關于BCNF的理論和算法在實踐中不容易操作和使用，尤其對于初學者來說難以掌握。本文根據(jù)國內外多名教授學者的研究成果， 對BCNF的定義、性質、判定規(guī)則與算法進行了簡潔、準確、靈活的闡述與分析，對理解和掌握BCNF有一定的實用價值。參考文獻AbrahamSilberschatz, HenryF.Korth,S.Sudarshan,DatabaseSystemConcepts（Fourth Edition）[M].Beijing, High