關(guān)系規(guī)范化基礎(chǔ)

1、第三章關(guān)系規(guī)范化基礎(chǔ)一、內(nèi)容提要關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)中，一個(gè)非常重要的被視為理論問題的內(nèi)容是如何構(gòu)造合理的關(guān)系，使之能準(zhǔn)確地反應(yīng)現(xiàn)實(shí)世界，有利于應(yīng)用和具體的操作。這一問題就是關(guān)系規(guī)范化要研究的問題。通過本章的學(xué)習(xí)，應(yīng)重點(diǎn)掌握：函數(shù)依賴及Armstrong公理系統(tǒng)為什么要對(duì)模式進(jìn)行分解，如何分解如何判斷關(guān)系模式達(dá)到幾范式如何求屬性的閉包及如何求最小函數(shù)依賴集判斷分解后的關(guān)系模式是不是無損連接或保持函數(shù)依賴判斷分解后的關(guān)系模式既無損連接又保持函數(shù)依賴(一)函數(shù)依賴及相關(guān)概念定義設(shè)R(U)是屬性集U上的關(guān)系模式，X,Y是U的子集。若對(duì)R(U)的任何一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相

2、等，而在Y上的屬性值不等，則稱X函數(shù)決定Y或Y函數(shù)依賴于X,記作：XY。完全函數(shù)依賴：在R(U)中，如果XY，并且對(duì)于X的任何一個(gè)真子集X、，都有X、不能決定Y，則稱Y對(duì)X完全函數(shù)依賴，記作：XY例給定一個(gè)學(xué)生選課關(guān)系SC(Sno，Cno，G)，我們可以得到F=(Sno，Cno)G，對(duì)(Sno,Cno)中的任何一個(gè)真子集Sno或Cno都不能決定G，所以，G完全依賴于Sno，Cno。平凡的函數(shù)依賴：如果XY，但Y不完全函數(shù)依賴于X，則稱Y對(duì)X部分函數(shù)依賴，記作：XY傳遞依賴：在R(U)中，如果XY，(YX)，YX，YZ則稱Z對(duì)X傳遞依賴。碼：設(shè)K為R(U，F(xiàn))中的屬性的組合，若KU，則K為R的候

3、選碼，若有多個(gè)候選碼，選一個(gè)作為主碼。注:候選碼也稱候選關(guān)鍵字。(5)主屬性和非主屬性：包含在任何一個(gè)候選碼中的屬性叫做主屬性，否則叫做非主屬性。外碼：若R(U)中的屬性或?qū)傩越MX非R的碼，但是另一關(guān)系的碼，則稱X為外碼。范式在關(guān)系數(shù)據(jù)庫(kù)中的一個(gè)非常重要的問題就是如何評(píng)價(jià)分解后的各個(gè)關(guān)系模式的好壞。通?？梢酝ㄟ^判斷分解后的模式達(dá)到幾范式來評(píng)價(jià)模式的好壞。范式有1NF、2NF、3NF、BCNF、4NF和5NF。這幾種范式之間的關(guān)系如下：1NF2NF3NFBCNF4NF5NF通過模式分解，將低一級(jí)范式的關(guān)系模式分解成了若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過程叫做規(guī)范化。下面將給出各個(gè)范式的定義。

4、1.1NF(第一范式)定義若關(guān)系模式R的每一個(gè)分量是不可再分的數(shù)據(jù)項(xiàng)，則關(guān)系模式R屬于第一范式(1NF)。例供應(yīng)者和它所提供的零件信息，關(guān)系模式如下：FIRST(Sno,Sname,Status,City,Pno,Qty)并且有F=SnoSname,SnoStatus,StatusCity,(Sno,Pno)Qty。具體的關(guān)系如圖5l所示。SnoSnameStatusCityPnoQtyS1精益20天津P1200S1精益20天津P2300S1精益20天津P3480S2盛錫10北京P2168S2盛錫10北京P3500S3東方紅30北京P1300S3東方紅30北京P2280S4泰達(dá)20上海P246

5、0從圖51中可以看出，每一個(gè)分量都是不可再分的數(shù)據(jù)項(xiàng)，所以是1NF。但是，1NF帶來四個(gè)問題：冗余度大：例如每個(gè)供應(yīng)者的Sno，Sname，Status，City要與零件的種類一樣多；引起修改操作的不一致性：例如供應(yīng)者S1從“天津”搬到“上?！?，若稍不注意，就會(huì)使一些數(shù)據(jù)被修改，另一些數(shù)據(jù)沒有被修改，導(dǎo)致數(shù)據(jù)修改的不一致性；插入異常：若某個(gè)供應(yīng)者的其它信息未提供時(shí)，如“零件號(hào)”，則不能進(jìn)行插入操作；更新異常：若供應(yīng)商S4的P2零件銷售完了，刪除后，在基本關(guān)系FIRST找不到S4，可S4又是客觀存在的。正因?yàn)樯鲜鲈蛞肓?NF。2NF(第二范式)定義若關(guān)系模式RINF，且每一個(gè)非主屬性完全依賴

6、于碼，則關(guān)系模式R2NF。即當(dāng)1NF消除了非主屬性對(duì)碼的部分函數(shù)依賴，則成為2NF。例FIRST關(guān)系中的碼是Sno、Pno,而SnoStatus，因此非主屬性Status部分函數(shù)依賴于碼，故非2NF的。若此時(shí)，將FIRST關(guān)系分解為：FIRSTl(Sno,Sname,Status，City)2NFFIRST2(Sno，Pno，Qty)2NF因?yàn)镕IRSTl和FIRST2中的碼分別為Sno和Sno,Pno每一個(gè)非主屬性完全依賴于碼。3NF(第三范式)定義若關(guān)系模式R(U，F(xiàn))中不存在這樣的碼X，屬性組Y及非主屬性Z(ZY)使得XY，(YX)YZ成立，則關(guān)系模式R3NF。即當(dāng)2NF消除了非主屬性對(duì)

7、碼的傳遞函數(shù)依賴，貝U成為3NF。例FIRSTl3NF，因?yàn)樵诜纸夂蟮年P(guān)系模式FIRSTl中有：SnoStatus，StatusCity，存在著非主屬性City傳遞依賴于碼Sno。BCNF(巴克斯范式)；定義若關(guān)系模式R1NF，若XY且YX時(shí)，X必含有碼，則關(guān)系模式RBCNF。即當(dāng)3NF消除了主屬性對(duì)碼的部分和傳遞函數(shù)依賴，則成為BCNF。結(jié)論一個(gè)滿足BCNF的關(guān)系模式，應(yīng)有如下性質(zhì)：所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴；所有非主屬性對(duì)每一個(gè)不包含它的碼，也是完全函數(shù)依賴；沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。(三)多值依賴1多值依賴定義若關(guān)系模式R(U)中，X、Y、Z是U的子集，并

8、且Z=UXY。當(dāng)且僅當(dāng)對(duì)R(U)的任何一個(gè)關(guān)系r,給定一對(duì)(x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關(guān)，則稱“Y多值依賴于X”或“X多值決定Y”成立。記為：XY。2多值依賴的性質(zhì)多值依賴具有如下六條性質(zhì)：多值依賴具有對(duì)稱性。即若XY，則XZ，其中Z=UXY多值依賴的傳遞性。即若XY，YZ，則XZY函數(shù)依賴可以看成是多值依賴的特殊情況若XY，XZ，則XYZ若XY，XZ，貝，XYZ；若XY，XZ，則XZY。34NF(第四范式)定義(4NF)若關(guān)系模式R1NF，若對(duì)于R的每個(gè)非平凡多值依賴XY且Yx時(shí)，X必含有碼，則關(guān)系模式R(U，F(xiàn))4NF。(四)函數(shù)依賴的公理系統(tǒng)Armstron

9、g公理系統(tǒng)：設(shè)關(guān)系模式R(U，F(xiàn))，其中U為屬性集，F(xiàn)是U上的一組函數(shù)依賴，那么有如下推理規(guī)則：A1自反律：若YXU，則XY為F所蘊(yùn)涵；A2增廣律：若XY為F所蘊(yùn)涵，且ZU，則XZYZ為F所蘊(yùn)涵；A3傳遞律：若XY，YZ為F所蘊(yùn)涵，則XZ為F所蘊(yùn)涵。根據(jù)上述三條推理規(guī)則又可推出下述三條推理規(guī)則：合并規(guī)則：若XY,XZ,則XYZ為F所蘊(yùn)涵偽傳遞率：若XY,WYZ，則XWZ為F所蘊(yùn)涵分解規(guī)則：若XY，ZY，則XZ為F所蘊(yùn)涵。引理：XA：A1A2A1成立的充分必要的條件是XAi成立(I=1,2,3,k)(五)函數(shù)依賴的閉包F+及屬性的閉包X+：1函數(shù)依賴的閉包定義關(guān)系模式R(U,F)中為F所邏輯蘊(yùn)含

10、的函數(shù)依賴的全體稱為F的閉包,記為：F+。2屬性的閉包X+定義設(shè)F為屬性集U上的一組函數(shù)依賴，XU,X+=AIXA能由F根據(jù)Armstrong公理導(dǎo)出,則稱X+為屬性集X關(guān)于數(shù)依賴集F的閉包。3.求屬性X的閉包X吉的算法X+算法求屬性的閉包X+輸入X,F輸出X+F步驟令X(0)=X,i=0求B,B=A1(啟)(w)(VWFVX(DAW)X(i+D=BX(i)判斷X(i+1)=X(i)嗎若相等，或X(D=U,則X(D為屬性集X關(guān)于函數(shù)依賴集F的閉包。且算法終止若不相等，則i=i+1,返回第二步例1已知關(guān)系模式R(U,F),U=A,B,C,D,E)；F=AB,DC,BCE,ACB求(AE)F+(A

11、D)F+解求(AE)+，由上述算法，設(shè)X(o)=AE計(jì)算X(1):逐一掃描F中的各個(gè)函數(shù)依賴,找到左部為A、E或AE的函數(shù)依賴，得到一個(gè)：AB。故有X=AEB。計(jì)算X：逐一掃描F中的各個(gè)函數(shù)依賴，找到左部為ABE或ABE子集的函數(shù)依賴，因?yàn)檎也坏竭@樣的函數(shù)依賴，所以，X=XQ。算法終止，(AE)+=ABE。求(AD)；,由上述算法，設(shè)XtO=AD計(jì)算X”：逐一掃描F中的各個(gè)函數(shù)依賴，找到左部為A、D或AD的函數(shù)依賴，得到兩個(gè)：A+B,D-C函數(shù)依賴。故有XCl：ADUBC。計(jì)算Xn：逐一掃描F中的各個(gè)函數(shù)依賴，找到左部為ADBC或ADBC子集的函數(shù)依賴，得到兩個(gè)：BCE,ACB函數(shù)依賴。故有X

12、2：ABCDUE。所以，X(2ABCDE：U,算法終止，(AD)吉：ABCDE。(六)最小函數(shù)依賴集1等價(jià)和覆蓋定義一個(gè)關(guān)系模式R(U,F)上的兩個(gè)依賴集F和G,如果F=G,則稱F和G是等價(jià)的，記做F三G。若F三G,則稱G是F的一個(gè)覆蓋，反之亦然。兩個(gè)等價(jià)的函數(shù)依賴集在表達(dá)能力上是完全相同的。2最小函數(shù)依賴集定義如果函數(shù)依賴集F滿足下列條件，則稱F為最小函數(shù)依賴集或最小覆蓋。；(1)F中的任何一個(gè)函數(shù)依賴的右部?jī)H含有一個(gè)屬性；”(2)F中不存在這樣一個(gè)函數(shù)依賴XA,使得F與F一XA等價(jià)；擴(kuò)(3)F中不存在這樣一個(gè)函數(shù)依賴XA,X有真子集Z使得F一XAUZ+A與F等價(jià)。；3計(jì)算最小函數(shù)依賴集的算

13、法。算法計(jì)算最小函數(shù)依賴集。輸入一個(gè)函數(shù)依賴集輸出F的一個(gè)等價(jià)的最小函數(shù)依賴集G。步驟用分解的規(guī)則，使F中的任何一個(gè)函數(shù)依賴的右部?jī)H含有一個(gè)屬性；，：(2)去掉多余的函數(shù)依賴：從第一個(gè)函數(shù)依賴X+Y開始將其從F中去掉，然在剩下的函數(shù)依賴中求X的閉包X看X是否包含Y,若是，則去掉XY；否則不能去掉，依次做下去。直到拽不到冗余的函數(shù)依賴；(3)去掉各依賴左部多余的屬性。一個(gè)一個(gè)地檢查函數(shù)依賴宏部非單個(gè)屬性的依賴。例如XY+A，若要判Y為多余的，則以醑+A代替XY+A是否等價(jià)?若AE(X),則Y是多余屬性，可以去掉。例2已知關(guān)系模式R(U，F(xiàn))，U=A,B，C，D，E，G；江F=AB+C,DEG，C

14、A，BE+C擴(kuò)BCD，CGBD，ACD-B，CEAG；請(qǐng)將F化為最小函數(shù)依賴集。解此題可以有兩種求解方法，求解過程如下：輩方法1(利用算法求解，使得其滿足三個(gè)條件)；(1)利用分解規(guī)則，將所有的函數(shù)依賴變成右邊都是單個(gè)屬：性的函數(shù)依賴，得F為：F=ABC,D+E，D+G，CA，BECBCD，CGB，CGD，ACDB，CE+A，CEG去掉F中多余的函數(shù)依賴，具體做法如下：從第一個(gè)函數(shù)依賴開始從F中去掉它(假定它為XY)，剩下的函數(shù)依賴F求X的閉包，看X是否含Y，若包含Y，則X+Y為冗余函數(shù)依賴，則去掉它，否則不去。依次下去，直到能滿足定義最小依賴的第二個(gè)條件。故有：設(shè)ABC為冗余的函數(shù)依賴，則去

15、掉AB+C得F1=D+E，DG，C+A，BECBC+D，CGB，CGD，ACD+B，CEA，CE+G因?yàn)閺腇l中找不到找到左部為AB或AB子集的函數(shù)依賴，則(AB)擊=。所以AB+C非冗余的函數(shù)依賴，不能去掉。設(shè)CGB為冗余的函數(shù)依賴，則去掉CGB得F2=AB+C，DE，D+G，C+A，BECBC+D，CG+D，ACD+B，CEA，CE+G求（CG）左設(shè)X*）：CG計(jì)算X”逐一掃描F2中的各個(gè)函數(shù)依賴，找到左部為C、（；或CG的函數(shù)依賴，得到一個(gè)：CA函數(shù)依賴。故有X“=CGA。計(jì)算X“：逐一掃描F2中的各個(gè)函數(shù)依賴，找到左部為CGA或CGA子集的函數(shù)依賴，得到一個(gè)：CG+D函數(shù)依賴。故有X9

16、=ACDG。:計(jì)算X“：逐一掃描F2中的各個(gè)函數(shù)依賴，找到左部為AC拓或ACDG子集的函數(shù)依賴，得到兩個(gè)：ACDB，D，E函數(shù)依瓤故有XCa）2ABCDEG。；：扭因?yàn)閄=ABCDEG：U,算法終止，（CG）占=ABCDE。所以CGB為冗余的函數(shù)依賴，從F2中去掉。：設(shè)CG+D為冗余的函數(shù)依賴，則去掉CGD得：捍F3=AB+C,D-*E,D+G，C-,-A,BECBC+D，ACD-B，CEA，CE+G：求（CG）占；：設(shè)XCO）：CG：計(jì)算Xm：逐一掃描F3中的各個(gè)函數(shù)依賴，找到左部為C、G城CG的函數(shù)依賴，得到一個(gè)：C+A函數(shù)依賴。故有Xu：ACG；熟計(jì)算X”：逐一掃描F3中的各個(gè)函數(shù)依賴，

17、找到左部為ACG誠(chéng)ACG子集的函數(shù)依賴，周為找不到這樣的函數(shù)依賴。故有謹(jǐn)=X”，算法終止。（CG）占=ACG。：因?yàn)锳CG芒D，所以CG+D非冗余的函數(shù)依賴，不能從F3沖去掉。；設(shè)CE+A為冗余的函數(shù)依賴，則去掉CEA得瞰F4=AB-*C,D-E，D-*G，C+A，BEC：BC-*-D，CGD,ACD-B,CE+G）：求（CZ）擊；設(shè)X（OCE芝計(jì)算X-）：逐一掃描F4中的各個(gè)函數(shù)依賴，找到左部為C、E藏CE的函數(shù)依賴，得到一個(gè)：CA函數(shù)依賴。故有：X（1，=5ACE；計(jì)算XC2）：逐一掃描F4中的各個(gè)函數(shù)依賴，找到左部為ACE:藏ACE子集的函數(shù)依賴，得到一個(gè)：CEG函數(shù)依賴；故有：騷X2）

18、=ACEG。計(jì)算X”逐一掃描F4中的各個(gè)函數(shù)依賴，找到左部為ACEG或ACEG子集的函數(shù)依賴，得到一個(gè)：CGD函數(shù)依賴。故有：X，=ACDEG。計(jì)算X“：逐一掃描F4中的各個(gè)函數(shù)依賴，找到左部為ACDEG或ACDEG子集的函數(shù)依賴，得到一個(gè)：ACDB函數(shù)依賴。故有：X=ABCDEG。因?yàn)閄“=ABCDEG=U，算法終止，（CE）占：ABCDEG。所以CE+A為冗余的函數(shù)依賴，從F4中去掉。又因?yàn)镕4中無多余函數(shù)依賴所以轉(zhuǎn)（3）。去掉F4中各函數(shù)依賴左邊多余的屬性。函數(shù)依賴ACD+B，屬性A是多余的，去掉A得CDB，因?yàn)镃A,所以可推導(dǎo)出ACDB。故最小函數(shù)依賴集為：FMIN=AB+C,DE，D

19、+G，CA，BECBC+D，CGD，CD+B，CEG方法2（利用Armstrong公理系統(tǒng)的推理規(guī)則求解）假設(shè)CGB為冗余的函數(shù)依賴，那么，從F中去掉它后能根據(jù)Armstrong公理系統(tǒng)的推理規(guī)則導(dǎo)出。因?yàn)镃G+DCA（已知）所以CGAACD（增廣律）因?yàn)锳CDB（已知）所以CGAB（傳遞律）因?yàn)镃A（已知）所以CGB（蘊(yùn)涵）同理可證：CEA是冗余的。又因CA，CDB可知，ACD-BL故去掉左邊多余的屬性得CD-B。需要注意的是，F(xiàn)的最小依賴集FMIN不一定是惟一的，它與對(duì)各函數(shù)依賴FDi及XA中X各屬性的處理順序有關(guān)。例3已知關(guān)系模式R（U，F(xiàn)），U=A，B，C；F=A+B，BA，B+C，A

20、+C，CA求最小函數(shù)依賴集。分析此題可以有兩種不同的答案，下面分別敘述如下。答案1設(shè)B一A是冗余的，將其從F中去掉，看能否根據(jù)，Armstrong公理系統(tǒng)的推理規(guī)則導(dǎo)出。因B-C,CA（已知）故BA（傳遞律）故B-,-A是冗余的，將其從F中去掉，得n為F1：A+B，B-C，A+C，C+A。又設(shè)AC為冗余，將其從F1中去掉因AB，B-C（已知）故AC（傳遞律）故A+C是冗余的，將其從n中去掉，得Fm為：FM,=AB,B+C，G+A。因?yàn)樵贔M,中的其它函數(shù)依賴是非冗余的，所以，F(xiàn)Ml為最小函數(shù)依賴集。答案2設(shè)B一C是冗余的，將其從F中去掉，看能否根據(jù)Armstrong公理系統(tǒng)的推理規(guī)則導(dǎo)出。：因

21、BA，A+C（已知）故BC（傳遞律）故B+C是冗余的，將其從F中去掉，得FM2為FM2=AB，B+C，AC，CA。i因?yàn)樵贔m中的其它函數(shù)依賴是非冗余的，所以，F(xiàn)M2為最小函數(shù)依賴集。從上分析我們可以得到兩個(gè)最小函數(shù)依賴集Fh4,和Fht。因此，F(xiàn)的最小函數(shù)依賴集不是惟一的。（七）模式分解1分解定義（分解）關(guān)系模式R（U,F）的一個(gè)分解是指，PR1（Ul,P1）,R2（U2,F2）,R。（U。F。）,其中：nU=UU，并且沒有U（U,1Wi,jWn,E是F在U上的投影。其中Fi=XYXYEF八XY三Ui對(duì)一個(gè)給定的模式進(jìn)行分解，使得分解后的模式是否與原來的模式等價(jià)有三種情況：分解具有無損連接性

22、；分解要保持函數(shù)依賴；分解既要無損連接性；又要保持函數(shù)依賴。2無損連接定義(無損連接)PR,(U1,F：),R：(U：,F2),Rh(Uk,Fk)是關(guān)系模式R(U,F)的一個(gè)分解，若對(duì)R(U,F)的任何一個(gè)關(guān)系r均有r=mP(r)成立，則成分解P具有無損連接性(簡(jiǎn)稱無損分解)。k其中，mP(r)：岡丌R：(r)。定理關(guān)系模式R(U,F)的一個(gè)分解，PR1(U：,F1),R：(U2，F(xiàn)：)具有無損連接的充分必要的條件是：U1門U2一UlU2EF或Ul門U2+U2一UlEF3保持函數(shù)依賴定義：設(shè)關(guān)系模式R(U,F)的一個(gè)分解，P=民(U：,F1),R：咖2,F2)，Rk(Uk,Pk)，如果：F=(

23、U丌Ki(F1-),則稱分解P保持函數(shù)依賴。十4.判別一個(gè)分解的無損連4匸1和保持函數(shù)依賴的算法；算法1判別一個(gè)分解的無損連接性。廣pRl(U：,F1),R。(U2,F：)，凡(UL,Fb)是關(guān)系模式R：(U,F)的一個(gè)分解,U：A1,A：,A。,F=FD1,FD2,:FDp,并設(shè)F是一個(gè)最小依賴集，記FDi為戈一Au,其步驟如下：(1)建立一張n列k行的表，每一列對(duì)應(yīng)一個(gè)屬性，每一行對(duì)：應(yīng)分解中的一個(gè)關(guān)系模式。若屬性八仨U,則在j列i行上填上鈣，否則填上、b_芝(2)對(duì)于每一個(gè)FDi做如下操作：找到Xi所對(duì)應(yīng)的列中具有：；相同符號(hào)的那些行?？疾爝@些行中1i列的元素，若其中有，則全；都改為，否

24、則全部改為bmli,m是這些行的行號(hào)最小值。i,如果在某次更改后，有一行成為：a1,a2,，an,則算法終止。：且分解p具有無損連接性，否則不具有無損連接性。:，對(duì)F中p個(gè)FD逐一進(jìn)行一次這樣的處理，稱為對(duì)F的一次；掃描。：；：(3)比較掃描前后，表有無變化，如有變化，則返回第(2)步，：否則算法終止。三斗如果發(fā)生循環(huán)，那么前次掃描至少應(yīng)使該表減少一個(gè)符號(hào),表：中符號(hào)有限,因此,循環(huán)必然終止。算法2轉(zhuǎn)換成3NF的保持函數(shù)依賴的分解。孓p=R1(U：,F1),R,(U：,F：),，Rk(Uk,Fk)是關(guān)系模式R：囊U,F)的一個(gè)分解，U：A：,A：,，An,F=FD1,FD2,FD,，并設(shè)F是一

25、個(gè)最小依賴集，記FDi為咒一，其步驟如下：；(1)對(duì)R(U,F)的函數(shù)依賴集F進(jìn)行極小化處理(處理后的：結(jié)果仍記為F)；i(2)找出不在F中出現(xiàn)的屬性，將這樣的屬性構(gòu)成一個(gè)關(guān)系模式。把這些屬性從U中去掉，剩余的屬性仍記為U；若有XA正F,且XA=U,則PR，算法終止；否則，對(duì)F按具有相同左部的原則分組(假定分為k組)，每一組函數(shù)依賴Fi所涉及的全部屬性形成一個(gè)屬性集U。若U三U(ire就去掉U。由于經(jīng)過了步驟(2),故UU9,于是PR,(Ul,F1),R2(U2,F2),Rk(Uk,Fk)構(gòu)成R(U,F)的一個(gè)保持函數(shù)依賴的分解。并且，每個(gè)Ri(Ui,E)均屬于3NF且保持函數(shù)依賴。例4關(guān)系模

26、式R(U,F),其中U=C,T,H,I,S,G),F=CSG,C+T,THI,HIC,HS1,將其分解成3NF并保持函數(shù)依賴。解根據(jù)算法2求解如下：F已為最小函數(shù)依賴集；R中的所有屬性均在F中都出現(xiàn)，所以轉(zhuǎn)(3)；對(duì)F按具有相同左部的原則分為：R1=CSG,R2；CT,R3：THI,R4：HIC,R5：HSR。所以PR1(CSG),R2(CT),R3(THl),R4(HIC),R5(HSR)算法3將一個(gè)關(guān)系模式轉(zhuǎn)換成3NF,使它既具有無損連接又保持函數(shù)依賴的分解。輸入關(guān)系模式R和R的最小函數(shù)依賴集F。輸出R(U,F)的一個(gè)分解P=R1(U,F1),R：(U：,F：),，Rk(Uk,Fk),民為

27、3NF,且P具有無損連接又保持函數(shù)依賴的分解。操作步驟如下：(1)根據(jù)算法2求出保持依賴的分解P=R1,R。，R。ii(2)判分解P是否具有無損連接性，若有，轉(zhuǎn)(4)；惑;、(3)令ppUX),其中X是R的候選關(guān)鍵字；牡.矢口(4)輸出P孫。例5對(duì)例4的關(guān)系模式R(U,F)將其分解成3NF,使P具有嘎?lián)p連接又保持函數(shù)依賴的分解。弘，解根據(jù)算法3求解如下：扒(1)據(jù)例4得3NF保持函數(shù)依賴的分解如下：杠。二RI(CSG),R2(CT),R3(TH1),R4(HIC),R5(HSR)(2)根據(jù)算法1構(gòu)造一個(gè)二維矩陣如圖52所示。;:根據(jù)F中的C一T,對(duì)上表進(jìn)行處理，由于屬性列C上第一；行、第二行及

28、第四行相同a,所以將屬性列T上b12、b2改為同一：符號(hào)a：又根據(jù)HIC將屬性列C上b“、bsl改為同一符號(hào)a1修改后如圖53所示。根據(jù)F中的CSG，對(duì)上表進(jìn)行處理，由于屬性列CS上第一行、第五行相同al、a5,所以將屬性列G上b,。改為同一符號(hào)a6。又根據(jù)CT將屬性列T上b。：改為同一符號(hào)a2,修改后如圖54所示。從上可見，找到一行(第5行)為全a,所以分解是無損的。算法4將關(guān)系模式轉(zhuǎn)換成BCNF，使它具有無損連接的分解。輸入關(guān)系模式R和函數(shù)依賴集F。輸出R(U,F)的一個(gè)分解PR,(U,F1),R。(U2,F：),Rk(Uk,Fk),民為BCNF,且P具有無損連接的分解。操作步驟如下：令P

29、=R若P中的所有模式都是BCNF,則轉(zhuǎn)(4)；若P中有一個(gè)關(guān)系模式民不是BCNF，則民中必能找到一個(gè)函數(shù)依賴XA,且X不是民的候選鍵，且A不屬于X,設(shè)Rn(XA),Ri2(民一A),用分解民，Rn代替民，轉(zhuǎn)(2)；輸出F；例6關(guān)系模式R(U,F)其中：U：C,T,H,I,S,G,F二CSC,CT,THI,HI+C,HS1,將其無損連接地分解成BCNF。解R上只有一個(gè)候選關(guān)鍵字HS(1)令PR(U,F)l：(2)p中不是所有的模式都是BCNF,轉(zhuǎn)(3)；R扭；(3)考慮CSG,這個(gè)函數(shù)依賴不滿足BCNF條件(CS不包蒙禽候選鍵HS)，所以將其分解成Ri(CSG)、R2(CTHIS)。計(jì)算法1和R

30、2的最小函數(shù)依賴集分別為：Fl=CSG,F2=C黔T,THI,HIC,HS1。R2的候選關(guān)鍵字為HS。默因R1已是BCNF,而R2的F2中存在不為碼的決定因睽素HIC駐故R2不屬于BCNF，進(jìn)一步分解R2即可。愛:.分解R2：考慮CT,將其分解成R21(CT)、R22(CHIS)。計(jì)6薯R21和R22的最小函數(shù)依賴集分別為：F21=CT,F22=：CH+I,HI+C,HS+I,.CT,TH一1,.在F22中，有CH一心。R22的候選關(guān)鍵字為HS。整因R21已是BCNF,R22不是BCNF熙故進(jìn)一步分解R22即可。默分解R22：考慮CH一1,將其分解成R221(CH1)、R222扭CHS)。計(jì)算

31、R221和R222的最小函數(shù)依賴集分別為：盼醞F221=CHI,HIC韉R：F222：HS+C。ir戴因R221,R222已是BCNF磬故將R分解后為：芝p=R1(CSG),R21(CT),R221(CHl),R222(CHS)醛算法5將關(guān)系模式分解成4NF,使它具有無損連接性。醞輸入關(guān)系模式R和函數(shù)依賴集F。黔輸出R(U,F)的一個(gè)分解P=Rl(U,F1),R2(U：,F2),F?”，Rk(U,Fk)，民為4NF,且P具有無損連接的分解。臥操作步驟如下：芝(1)令P=R若P中的所有模式都是4NF,貝峙專(4)；若P中有一個(gè)關(guān)系模式民不是4NF,則Ri中必能找到一個(gè)函數(shù)依賴X一一A,且X不包含

32、民的候選鍵，且AX乒中，XA；i民令Z=AX,由分解規(guī)則得出XZ。令R。(XZ),Ri2(民一Z),用分解vRil,Ri2代替民，由于(R,門Ri2)一一(R,一Ri。)，所以分解具有無損連接性。轉(zhuǎn)；停止分解，輸出p二、典型題解析例51對(duì)給定的關(guān)系模式R(U,F),U=A,B,C,F=vAB),如下的兩個(gè)分解：(1)F1=AB,BCp：=AB,AC判這兩個(gè)分解是否無損。解(1)根據(jù)定理判斷本題因AB門BC=BABBC=ABCAB=C故BA茫FB+C爭(zhēng)F故P,為有損連接。根據(jù)定理判斷本題因AB門AC二AABAC=BACAB=C故AB正FB+CF芝故p：為無損連接?；砝?2對(duì)給定的關(guān)系模式R(U,

33、F),U=A,B,C,D,E,F山AC,BC,CD,DEC,CEA,如下的分解：:p=R：(AD),R2(AB),R：(BE),R：(CDE),Rs(AE)捌分解P是否無損。豪解(1)構(gòu)造一個(gè)初始的二維表如圖55所示。攔臻(2)根據(jù)A+C,對(duì)上表進(jìn)行處理，由于屬性列A上第一行、汝二行及第三行相同a,所以將屬性列C上b,、b：,、b53改為同一瓢細(xì)號(hào)b13,取行號(hào)最小值。又根據(jù)BC將屬性列C上b_、b北改為粗闌一符號(hào)b13，修改后的表如圖56所示。牡(3)根據(jù)C+D,對(duì)上表進(jìn)行處理，由于屬性列C上第一行第野仁行、第三行及第五行相同b,且屬性列D上第一行為a,所以將R洄性列D上b：,、b,：、b：

34、,改為同一符號(hào)a：,修改后的表如圖57渤示。苣團(tuán)O根據(jù)DE+C,將屬性列C上第三行及第五行改為同一符號(hào)a,，修改后的表如圖58所示。田OO根據(jù)CE+A，將屬性列A上第三行及第四行改為同一符號(hào)al,修改后的表如圖59所示。通過上述更改，使第三行成為：a1,a：:a,:a4,a。，則算法終止。且分解P具有無損連接性。例53對(duì)給定的關(guān)系模式R(U:F):U=A:B:C:D:E:尸通過上述更改使第三行成為：a1a：aa4a。則算法終止。且分解P具有無損連接性。例53對(duì)給定的關(guān)系模式R(U:F):U=A:B:C:D:E:尸軋F(tuán)；AB,CP,EA,CED,如下的分解：感pR1(ABE),R2(CDEP)甄

35、。(1)求R的候選關(guān)鍵字，并判分解p是否無損；掃；(2)R1、R：屬于幾范式。瓤解(1)候選關(guān)鍵字為CE筻因(CE)=U6；十故有CE+U，并且在CE中不存在一個(gè)真子集能決定R抽全體屬性U,故CE為R的候選關(guān)鍵字。薩：根據(jù)定理判斷本題分解P是否無損舉因ABE門CDEP=E2：；蔑“ABECDEP=AB醛磬CDEPABE：CDP良因E+A,A+B(已知)莨故有E+B(傳遞律)寥“因E+A,EB豪故有E+AB(合并律)封：因E+ABEF臥：故故P為無損連接。甄.(2)R1、R：屬于幾范式?踩：R1E2NF騷；因EA,A+B良故EB,存在傳遞依賴野故R1任3NF薩R：仨1NF皂因CE+D,C+P瑟故

36、CE能惟一地確定R：中的每一個(gè)元組，故為候選關(guān)漠字。醛因CE是候選關(guān)鍵字，而CP,所以P部分函數(shù)依賴良與CE故R2手2NF例54對(duì)給定的關(guān)系模式R(U,F),U=A,B,C,D,E,P,F=AB,CP,EA,CE+D，如下的分解：p=R1(CP),R：(BE),R3(ECD),R：(AB)，判分解P是否無損。解(1)構(gòu)造一個(gè)初始的二維表如圖510所示。根據(jù)AB,對(duì)上表進(jìn)行處理，由于屬性列A上無相同元素，所以不能修改表。又根據(jù)CP將屬性列P上b：,改為a,修改后的表如圖511所示。根據(jù)E一A,對(duì)上表進(jìn)行處理，由于屬性列E上第二行、第三行相同a5,所以將屬性列A上b：,、L改為同一符號(hào)b：,修改后

37、的表如圖512所示。；(4)根據(jù)CED，對(duì)上表進(jìn)行處理，無法修改上表。因此，在輾后的表格，找不到一行全為al,a：,，an,所以P是有損的。：例5一5試證明由Armstrong公理系統(tǒng)推導(dǎo)出下面三條推理規(guī)則是正確的：l(1)合并規(guī)則：若XZXY則有XYZ偽傳遞規(guī)則：若XY,WYZ,則有XWZ分解規(guī)則：若XY,Z任Y,則有X一2三證明一.(1)合并規(guī)則:因XY(已知)器故XXY(增廣律)因XZ(已知)故XYYZ（增廣律）：因XXY，XYYZ（從上面得故XYZ（傳遞律）（2）偽傳遞規(guī)則：，因X+Y（已知）故WXWY（增廣律）因WYZ（已知）故XW一2（傳遞律）因Z(Y（已知）故YZ（自反律）因XY

38、（已知）故XZ（傳遞律）（3）分解規(guī)則：例3-6關(guān)系R(A,B,C,D,E,F,G,H,I,J)滿足下列函數(shù)依賴:ABD+E，ABG，BF，C一工，CJI，G+H該函數(shù)依賴集是最小函數(shù)依賴集嗎?給出該關(guān)系的候選碼。解該函數(shù)依賴集不是最小函數(shù)依賴集。因CJ,CJI（已知）故CJ（邏輯蘊(yùn)涵）顯然，ABCDGJ是一個(gè)超碼，即所有出現(xiàn)在函數(shù)依賴左邊的屬性的集合是超碼。但是因CJ（已知）故可將J從超碼中去掉。因ABG（已知）故可將G從超碼中去掉。此時(shí)，超碼中只剩下ABCD,由于它們都沒有在函數(shù)依賴集的任何一個(gè)函數(shù)依賴的右邊出現(xiàn)，所以它們都不能從超碼中去掉。故候選碼為：ABCD。所謂超碼是指能惟一標(biāo)識(shí)關(guān)系

39、中的每一個(gè)元組,不含多余屬性的才是候選關(guān)鍵字（或候選碼）。例37設(shè)P=R1（U1,F1）,R2（U2,F2）是R（U,F）上的一個(gè)分解，試證明P具有無損連接的充分必要的條件是：U1門U：UlU2仨F或U1門UzU2一Ul仨F。證明充分性：設(shè)U、門Uz-U：一U：,則可構(gòu)造表如圖513所示。該圖省略了a、b的下標(biāo)。如果U,門U2+U,U2在F中，則可將表的第二行U，一U：瀚韻所有符號(hào)全改為aaaa，使得該表的第二行全為a，則P具有海損連接性。同理可證U、門U：+U:一U：的情況。如果U1門U2知：一U：不在F中，但在F中，那么，它可以從Armstrong公理纂統(tǒng)的推理規(guī)則導(dǎo)出，從而也能推出U1門U2一九，且Ai三U1一巍中，所以可以將九列的b改為a，同樣，可將UlU2的其它屬醛對(duì)應(yīng)的第二行也全改為a，這樣，第二行就變成全a，所以分解是凜有無損連接性。臥(2)