關系系統(tǒng)及查詢優(yōu)化與范式定理

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

2、元組在X上的屬性值相等，而在Y上的屬性值不等，則稱X函數(shù)決定Y或Y函數(shù)依賴于X,記作：XYof(1)完全函數(shù)依賴：在R(U)中，如果XY,并且對于X的任何一個真子集X',都有X'不能決定Y,則稱Y對X完全函數(shù)依賴，記作：XY例給定一個學生選課關系SC(Sno,Cno,G),我們可以得到F=(Sno,Cno)G,又t(Sno,Cno)中的任何一個真子集Sno或Cno都不能決定G,所以，G完全依賴于Sno,Cno。P(2)平凡的函數(shù)依賴：如果XY,1Y不完全函數(shù)依賴于X,則稱Y對X部分函數(shù)依賴，記作：XY(3)傳遞依束在R(U)中，如果XY,(YX),YX,Y則稱Z對X傳遞依賴(4

3、)碼：設K為R(U,F)中的屬性的組合，若KU,則K為R的候選碼，若有多個候選碼，選一個作為主碼。注：候選碼也稱候選關鍵字。(5)主屬性和非主屬性：包含在任何一個候選碼中的屬性叫做主屬性，否則叫做非主屬性。(6)外碼：若R(U)中的屬性或?qū)傩越MX非R的碼，但是另一關系的碼，則稱X為外碼。范式在關系數(shù)據(jù)庫中的一個非常重要的問題就是如何評價分解后的各個關系模式的好壞。通常可以通過判斷分解后的模式達到幾范式來評價模式的好壞。范式有：1NF、2NF、3NF、BCNF、4NF和5NF。這幾種范式之間的關系如下：1NF2NF3NFBCNF4NF5NF通過模式分解，將低一級范式的關系模式分解成了若干個高一級

4、范式的關系模式的集合，這種過程叫做規(guī)范化。下面將給出各個范式的定義。1. 1NF(第一范式)定義若關系模式R的每一個分量是不可再分的數(shù)據(jù)項，則關系模式R屬于第一范式(1NF)o例供應者和它所提供的零件信息，關系模式如下：FIRST(Sno,Sname,Status,City,Pno,Qty)并且有F=SnoSname,SnoStatus,StatusCity,(Sno,Pno)Qty具體的關系如圖5l所不。SnoSnameStatusCityPnoQtyS1精益20天津P1200S1精益20天津P2300S1精益20天津P3480S2盛錫10北京P2168S2盛錫10北京P3500S3東方紅3

5、0北京P1300S3東方紅30北京P2280S4泰達20上海P2460從圖51中可以看出，每一個分量都是不可再分的數(shù)據(jù)項，所以是1NF。但是，1NF帶來四個問題：(1)冗余度大：例如每個供應者的Sno,Sname,Status,City要與零件的種類一樣多；(2)引起修改操作的不一致性：例如供應者S1從“天津”搬到“上?！保羯圆蛔⒁?，就會使一些數(shù)據(jù)被修改，另一些數(shù)據(jù)沒有被修改，導致數(shù)據(jù)修改的不一致性；(3)插入異常：若某個供應者的其它信息未提供時，如“零件號”，則不能進行插入操作；(4)更新異常：若供應商S4的P2零件銷售完了，刪除后，在基本關系FIRST找不到S4,可S4又是客觀存在的。正

6、因為上述原因引入了2NF。2. 2NF(第二范式)定義若關系模式R1NF,且每一個非主屬性完全依賴于碼，則關系模式R2NF。即當1NF消除了非主屬性對碼的部分函數(shù)依賴，則成為2NF例 FIRST關系中的碼是 Sno、Pno,而Sno Status因此非主屬性 Status部分函數(shù)依賴于碼，故非2NF的。若此時，將FIRST關系分解為:FIRSTl(Sno,Sname,Status,City)2NFFIRST2(Sno,Pno,Qty)2NF因為FIRSTl和FIRST2中的碼分別為Sno和Sno,Pno每一個非主屬性完全依賴于碼。3. 3NF(第三范式)定義若關系1K式R(U,F)中不存在這樣

7、的碼X,屬性組Y及非主屬性Z(ZY)使得XY,(YX)Y/Z成立，則關系模式R3NF。即當2NF消除了非主屬性對碼的傳遞函數(shù)依賴，則成為3NF。例FIRSTl3NF,因為在分解后的關系模式FIRSTl中有：SnoStatus,StatusCity,存在著非主屬性City傳遞依束于碼Sno。4.BCNF(巴克斯范式)；定義若關系模式R1NF,若XY且YX時，*必含有碼，則關系模式RBCNF。即當3NF消除了主屬性對碼的部分和傳遞函數(shù)依賴，則成為BCNFo結(jié)論一個滿足BCNF的關系模式，應有如下性質(zhì):(1)所有非主屬性對每一個碼都是完全函數(shù)依賴；(2)所有非主屬性對每一個不包含它的碼，也是完全函數(shù)

8、依賴;(3)沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。(三)多值依賴1 .多值依賴定義若關系模式R(U)中，X、Y、Z是U的子集，并且Z=UX丫。當且僅當對R(U)的任何一個關系r,給定一對(x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關,則稱“Y多值依賴于X”或“X多值決定Y”成立。記為：X丫。2 .多值依賴的性質(zhì)多值依賴具有如下六條性質(zhì)：(1)多值依賴具有對稱性。即若XY,則XZ,其中Z=UXY(2)多值依賴的傳遞性。即若XY,YZ,則XZY(3)函數(shù)依賴可以看成是多值依賴的特殊情況(4)若XY,XZ,則XYZ(5)若XY,XZ,貝，XYZ；(6)若XY,XZ,則XZY。3

9、 .4NF(第四范式)定義(4NF)若關系模式R1NF,若對于R的每個非平凡多值依賴XY且YX時，X必含有出,則關系模式R(U,F)4NF。(四)函數(shù)依賴的公理系統(tǒng)Armstrong公理系統(tǒng)：設關系模式R(U,F),其中U為屬性集，F(xiàn)是U上的一組函數(shù)依賴，那么有如下推理規(guī)則：(1)A1自反律：若丫XU,則X丫為F所蘊涵；(2)A2增廣律：若X丫為F所蘊涵，且ZU,則XZYZ為F所蘊涵；(3)A3傳遞律：若XY,YZ為F所蘊涵，則XZ為F所蘊涵。根據(jù)上述三條推理規(guī)則又可推出下述三條推理規(guī)則:合并規(guī)則：若XY,XZ,則XYZ為F所蘊涵(2)偽傳遞率：若XY, WY Z,則XW Z為F所蘊涵(3)分

10、解規(guī)則：若XY, Z Y,則X Z為F所蘊涵。引理：X A: A1A2A1成立的充分必要的條件是XAi成立(I=1,2,3,k)(五) 函數(shù)依賴的閉包F+及屬性的閉包X +:1 函數(shù)依賴的閉包定義 關系模式 R(U ， F) 中為 F 所邏輯蘊含的函數(shù)依賴的全體稱為F 的閉包，記為： F+屬性的閉包X +F定義 設 F 為屬性集 U 上的一組函數(shù)依賴， X U ，A | X X +FA 能由 F 根據(jù) Armstrong公理導出 ，則稱 為屬性集 X 關于數(shù)依賴集 + F 的閉包。X +F求屬性 X 的閉包 X 吉的算法X F算法求屬性的閉包 X +F輸入X ， F輸出 X + F步驟(1)令

11、 X(0)=X, i=0(2)求 B, B = A |(v)( w)(V WF V X (i) A W)(3) X(i+1) = B X(i)(4) 判斷X(i+1) = X(i) 嗎(5)若相等，或X (i)=U ，則 X(i) 為屬性集 X 關于函數(shù)依賴集F 的閉包。且算法終止(6)若不相等，則i=i+1,返回第二步例 1 已知關系模式 R(U , F), U = A, B, C, D, E);F = A B, D C, BC E, AC B求 (AE) + F (AD) + F解 求(AE)上述F法，設X(0)=AE計算 X (1) : 逐一掃描 F 中的各個函數(shù)依賴，找到左部為A 、

12、E 或 AE 的函數(shù)依賴，得到一個：A Bo 故有 X(1)=AE B計算X(2) ：逐一掃描F 中的各個函數(shù)依賴，找到左部為為找不到這樣的函數(shù)依賴，所以， X(1)=X(2)O算法終止，(AE) + = ABE。求(AD);,由上述算法，設 XtO' = AD計算X ”：逐一掃描F 中的各個函數(shù)依賴，找到左部為個： A+B ， D-C 函數(shù)依賴。故有ABE 或 ABE 子集的函數(shù)依賴，因A 、 D 或 AD 的函數(shù)依賴，得到兩XCl ： ADUBC計算 X n ：逐一掃描F 中的各個函數(shù)依賴，找到左部為ADBC 或 ADBC 子集的函數(shù)依賴，得到兩個： BC E， AC B 函數(shù)依賴

13、。故有X2，： ABCDUE 。所以， X(2 ： ABCDE ： U ，算法終止，(AD)吉：ABCDE。(六)最小函數(shù)依賴集1等價和覆蓋定義一個關系模式R(U,F)上的兩個依賴集F和G,如果F'=G',則稱F和G是等價的，記做F三G。若F三G，則稱G是F的一個覆蓋，反之亦然。兩個等價的函數(shù)依賴集在表達能力上是完全相同的。2最小函數(shù)依賴集定義如果函數(shù)依賴集F滿足下列條件，則稱F為最小函數(shù)依賴集或最小覆蓋。；(1)F中的任何一個函數(shù)依賴的右部僅含有一個屬性；”(2)F中不存在這樣一個函數(shù)依賴XA,使得F與FXA等價；擴(3)F中不存在這樣一個函數(shù)依賴X一A,X有真子集Z使得FX

14、AUZ+A與F等價。；3.計算最小函數(shù)依賴集的算法。算法計算最小函數(shù)依賴集。輸入一個函數(shù)依賴集輸出F的一個等價的最小函數(shù)依賴集步驟(1)用分解的規(guī)則，使F中的任何一個函數(shù)依賴的右部僅含有一個屬性；，：(2)去掉多余的函數(shù)依賴：從第一個函數(shù)依賴X+Y開始將其從F中去掉，然在剩下的函數(shù)依賴中求X的閉包X',看X'是否包含Y,若是，則去掉XY;否則不能去掉，依次做下去。直到拽不到冗余的函數(shù)依賴；(3) 去掉各依賴左部多余的屬性。一個一個地檢查函數(shù)依賴宏部非單個屬性的依賴。例如XY+A，若要判Y為多余的，則以醑+A代替XY+A是否等價?若AE(X)，則Y是多余屬性，可以去掉。例2已知關

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

16、函數(shù)依賴，則去掉它，否則不去。依次下去，直到能滿足定義最小依賴的第二個條件。故有：設ABC為冗余的函數(shù)依賴，則去掉AB+C得F1=D+E,DG,C+A,BECBC+D，CGB，CGD，ACD+B，CEA，CE+G因為從Fl中找不到找到左部為AB或AB子集的函數(shù)依賴，則依8)擊=。所以AB+C非冗余的函數(shù)依賴，不能去掉。設CGB為冗余的函數(shù)依賴，則去掉CGB得F2=AB+C,DE,D+G,C+A,BECBC+D，CG+D，ACD+B，CEA，CE+G求(CG)左設X*)：CG計算X”：逐一掃描F2中的各個函數(shù)依賴，找到左部為C、(；或CG的函數(shù)依賴，得到一個：CA函數(shù)依賴。故有X=CGA。計算X

17、“：逐一掃描F2中的各個函數(shù)依賴，找到左部為CGA或CGA子集的函數(shù)依賴，得到一個：CG+D函數(shù)依賴。故有X'9'=ACDG。：計算X“：逐一掃描F2中的各個函數(shù)依賴，找到左部為AC拓或ACDG子集的函數(shù)依賴，得到兩個：ACDB,D,>E函數(shù)依瓢故有XCa)2ABCDEG。；：扭因為X'''=ABCDEG;U,算法終止，(CG)占=ABCDE。所以CGB為冗余的函數(shù)依賴，從F2中去掉。：'設CG+D為冗余的函數(shù)依賴，則去掉CGD得；$F3=AB+C,D-*E,D+G，C-,-A，BECBC+D,ACD-B,CEA,CE+G:求(CG)占；設

18、XCO):CG:計算Xm:逐一掃描F3中的各個函函依賴，找到左部為C、G城CG的函函依賴，得到一個：C+A函函依賴。故有Xu：；ACG。熟計算X”：逐一掃描F3中的各個函函依賴，找到左部為ACG誠ACG子集的函數(shù)依賴，周為找不到這樣的函數(shù)依賴。故有謹=X"'，算法終止。(CG)占=ACG。：因為ACG芒D,所以CG+D非冗余的函數(shù)依賴，不能從F3沖去掉。；設CE+A為冗余的函數(shù)依賴，則去掉CEA得瞰F4=AB-*'C,D-E,D-*G,C+A,BEC;BC-*-D,CGD,ACD-B,CE+G):求(CZ)擊；設X(O':CE芝計算X-):逐一掃描F4中的各個

19、函函依賴，找到左部為C、E藏CE的函函依賴，得到一個：CA函函依賴。故有：X(1'=5ACE。計算XC2):逐一掃描F4中的各個函數(shù)依賴，找到左部為ACE；藏ACE子集的函函依賴，得到一個：CEG函函依賴。故有：騷X'2)=ACEG。計算X”：逐一掃描F4中的各個函函依賴，找到左部為ACEG或ACEG子集的函函依賴，得到一個：CGD函函依賴。故有：X'''=ACDEG。計算X“：逐一掃描F4中的各個函函依賴，找到左部為ACDEG或ACDEG子集的函函依賴，得到一個：ACDB函函依賴。故有：X'''=ABCDEG。因為X=ABCDE

20、G=U,算法終止，（CE）占：ABCDEG。所以CE+A為冗余的函數(shù)依賴，從F4中去掉。又因為F4中無多余函數(shù)依賴所以轉(zhuǎn)（3）。（3）去掉F4中各函數(shù)依賴左邊多余的屬性。函數(shù)依賴ACD+B,屬性A是多余的，去掉A得CDB,因為CA，所以可推導出ACDB。故最小函數(shù)依賴集為：FMIN=AB+C,DE,D+G,CA,BECBC+D，CGD，CD+B，CEG方法2（利用Armstrong公理系統(tǒng)的推理規(guī)則求解）假設CGB為冗余的函數(shù)依賴，那么，從F中去掉它后能根據(jù)Armstrong公理系統(tǒng)的推理規(guī)則導出。因為CG+DCA（已知）所以CGAACD（增廣律）因為ACDB（已知）所以CGAB（傳遞律）因為

21、CA（已知）所以CGB（蘊涵）同理可證：CEA是冗余的。又因CA，CDB可知，ACD-BL故去掉左邊多余的屬性得CD-B。需要注意的是，F(xiàn)的最小依賴集FMIN不一定是惟一的，它與對各函數(shù)依賴FDi及XA中X各屬性的處理順序有關。例3已知關系模式R（U,F）,U=A,B,C;F=A+B,BA,B+C,A+C,CA求最小函數(shù)依賴集。分析此題可以有兩種不同的答案，下面分別敘述如下。答案1設BA是冗余的，將其從F中去掉，看能否根據(jù)，Armstrong公理系統(tǒng)的推理規(guī)則導出。因B-C，CA（已知）故BA（傳遞律）故B-,-A是冗余的，將其從F中去掉，得n為F1：A+B，B-C，A+C，C+A。又設AC為

22、冗余，將其從F1中去掉因AB,B-C(已知)故AC(傳遞律)故A+C是冗余的，將其從n中去掉，得Fm為：FM,=AB,B+C,G+A。因為在FM，中的其它函數(shù)依賴是非冗余的，所以，F(xiàn)Ml為最小函數(shù)依賴集。答案2設BC是冗余的，將其從F中去掉，看能否根據(jù)、Armstrong公理系統(tǒng)的推理規(guī)則導出。：因BA，A+C(已知)故BC(傳遞律)故B+C是冗余的，將其從F中去掉，得FM2為FM2=AB,B+C,AC,CAo：i因為在Fm中的其它函數(shù)依賴是非冗余的，所以，F(xiàn)M2為最小函數(shù)依賴集。從上分析我們可以得到兩個最小函數(shù)依賴集Fh4，和Fht。，因此，F(xiàn)的最小函數(shù)依賴集不是惟一的。(七)模式分解1分解

23、定義(分解)關系模式R(U，F(xiàn))的一個分解是指，PRl(Ul,P1),R2(U2,F2),Ro(U。，F(xiàn)。),其中：nU=UU,并且沒有U(U,1<i,j<n,E是F在U上的投影。其中Fi=XYXYEF'八XY三Ui對一個給定的模式進行分解，使得分解后的模式是否與原來的模式等價有三種情況：(1)分解具有無損連接性；(2)分解要保持函數(shù)依賴；(3)分解既要無損連接性；又要保持函數(shù)依賴。2無損連接定義(無損連接)P'R,(U1,F:),R:(U:,F2),Rh(Uk,Fk)是關系模式R(U,F)的一個分解，若又tR(U,F)的任何一個關系r均有r=mP(r)成立，則成分

24、解P具有無損連接性(簡稱無損分解)其中，mP(r):岡開R:(r)。定理關系模式R(U,F)的一個分解，P'R1(U：,F1),R：(U2，F(xiàn)：)具有無損連接的充分必要的條件是：Ul門U2一UlU2EF或Ul門U2+U2一UlEF3保持函數(shù)依賴定義：設關系模式R(U,F)的一個分解，P=民(U:,F1),R:咖2,F2)，Rk(Uk,Pk),如果：F'=(UJTKi(F1-)',則稱分解P保持函數(shù)依賴。十4.判別一個分解的無損連4i-'1和保持函數(shù)依賴的算法；算法1判別一個分解的無損連接性。廣p'Rl(U:,F1),Ro(U2,F:),凡(UL,Fb)是

25、關系模式R:(U,F)的一個分解，U:A1,A:,，Ao,F=FDl,FD2,：FDp,并設F是一個最小依賴集，記FDi為戈一Au,其步驟如下：(1)建立一張n列k行的表，每一列對應一個屬性，每一行對：應分解中的一個關系模式。若屬性八任U,則在j列i行上填上鈣，否則填上、b.芝(2)對于每一個FDi做如下操作：找到Xi所對應的列中具有：；相同符號的那些行?？疾爝@些行中1i列的元素，若其中有，則全；都改為，否則全部改為bmli,m是這些行的行號最小值。i,如果在某次更改后，有一行成為：a1,a2,，an,則算法終止。：且分解p具有無損連接性，否則不具有無損連接性。：，對F中p個FD逐一進行一次這

26、樣的處理，稱為對F的一次；掃描。：；：(3)比較掃描前后，表有無變化，如有變化，則返回第(2)步，：否則算法終止。一斗如果發(fā)生循環(huán)，那么前次掃描至少應使該表減少一個符號，表：中符號有限，因此，循環(huán)必然終止。：算法2轉(zhuǎn)換成3NF的保持函數(shù)依賴的分解。工p=R1(U:,F1),R:(U:,F:),，Rk(Uk,Fk)是關系模式R:囊U,F)的一個分解，U:A:,A:,，An,F=FDl,FD2,'：FD,并設F是一個最小依賴集，記FDi為咒一，其步驟如下：；(1)對R(U，F(xiàn))的函數(shù)依賴集F進行極小化處理(處理后的：結(jié)果仍記為F)；i(2)找出不在F中出現(xiàn)的屬性，將這樣的屬性構成一個關系模

27、式。把這些屬性從U中去掉，剩余的屬性仍記為U；(3)若有XA正F,且XA=U,則P'R>,算法終止；(4) 否則，對F按具有相同左部的原則分組(假定分為k組)，每一組函數(shù)依賴Fi所涉及的全部屬性形成一個屬性集U。若U三U(ire就去掉Uo由于經(jīng)過了步驟(2),故U U9 ，于是P R ， （Ul ， F1） ， R2（U2 ，F(xiàn)2),Rk(Uk,Fk)構成R(U，F(xiàn))的一個保持函數(shù)依賴的分解。并且，每個Ri(Ui,E)均屬于3NF且保持函數(shù)依賴。例4關系模式R(U,F),其中U=C,T,H,I,S,G),F=CSG，C+T，THI，HIC，HSI>，將其分解成3NF并保持函

28、數(shù)依賴。解根據(jù)算法2求解如下：(1)F已為最小函數(shù)依賴集；(2)R中的所有屬性均在F中都出現(xiàn)，所以轉(zhuǎn)(3)；(3)對F按具有相同左部的原則分為：R1=CSG,R2;CT,R3':THI,R4:HIC,R5：HSR。所以PR1(CSG)，R2(CT)，R3(THl)，R4(HIC)，R5(HSR)算法3將一個關系模式轉(zhuǎn)換成3NF，使它既具有無損連接又保持函數(shù)依賴的分解。輸入關系模式R和R的最小函數(shù)依賴集F。輸出R(U,F)的一個分解P=R1(U,F1),R:(U:,F:),Rk(Uk,Fk),民為3NF,且P具有無損連接又保持函數(shù)依賴的分解。操作步驟如下：(1)根據(jù)算法2求出保持依賴的分

29、解P=R1,Ro,，Roii(2)判分解P是否具有無損連接性，若有，轉(zhuǎn)(4)；惑；、(3)令ppUX)，其中X是R的候選關鍵字；牡.知輸出P孫。例5對快J4的關系模式R(U,F)將其分解成3NF,使P具有嘎?lián)p連接又保持函數(shù)依賴的分解。弘，解根據(jù)算法3求解如下：扒(1)據(jù)例4得3NF保持函數(shù)依賴的分解如下：杠。二RI(CSG),R2(CT),R3(THl),R4(HIC),R5(HSR)(2)根據(jù)算法1構造一個二維矩陣如圖52所示。；：根據(jù)F中的CT，對上表進行處理，由于屬性列C上第一；行、第二行及第四行相同a,所以將屬性列T上b12、b'2改為同一：符號a：。又根據(jù)HIC將屬性列C上b

30、“、bsl改為同一符號a1；修改后如圖53所示。根據(jù)F中的CSG，對上表進行處理，由于屬性列CS上第一行、第五行相同al、a5,所以將屬性列G上b,。改為同一符號a6。又根據(jù)CT將屬性列T上b。：改為同一符號a2，修改后如圖54所示。從上可見，找到一行(第5彳f)為全a,所以分解是無損的。算法4將關系模式轉(zhuǎn)換成BCNF，使它具有無損連接的分解。輸入關系模式R和函數(shù)依賴集F。輸出R(U,F)的一個分解P'R,(U,F1),Ro(U2,F:),Rk(Uk,Fk),民為BCNF,且P具有無損連接的分解。操作步驟如下：(1)令P=R(2)若P中的所有模式都是BCNF，則轉(zhuǎn)(4)；(3)若P中有

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

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

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

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

35、：為無損連接?；砝?2對給定的關系模式R(U,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)構造一個初始的二維表如圖55所示。攔臻(2)根據(jù)A+C,對上表進行處理，由于屬性列A上第一行、汝二行及第三行相同a,所以將屬性列C上b,、b:,、b53改為同一瓢細號b13,取行號最小值。又根據(jù)BC將屬性列C上b、b北改為粗闌一符號b13,修改后的表如圖56所示。牡(3)根據(jù)C+D,對上表進行處理，由于屬性列C上第一行第野仁行、第三行及第五行相同b,且屬T列D上第一行

36、為a,所以將R'澗性列D上b：,、b,：、b：,改為同一符號a：,修改后的表如圖57渤示。苣團O(4)根據(jù)DE+C，將屬性列C上第三行及第五行改為同一符號a，修改后的表如圖58所示。田OO(5)根據(jù)CE+A，將屬性列A上第三行及第四行改為同一符號al,修改后的表如圖59所示。通過上述更改，使第三行成為：a1，a：，a，a4，a。，則算法終止。且分解P具有無損連接性。例53對給定的關系模式R(U,F),U=A,B,C,D,E,尸通過上述更改，使第三行成為：a1，a：，a，a4，a。，則算法終止。且分解P具有無損連接性。例53對給定的關系模式R(U,F),U=A,B,C,D,E,尸軋F;A

37、B,CP,EA，CED，如下的分解：感pR1(ABE)，R2(CDEP)甄。：(1)求R的候選關鍵字，并判分解p是否無損；掃；(2)R1、R:屬于幾范式。瓢解(1)候選關鍵字為CE童因(CE)'=U6;十故有CE+U,并且在CE中不存在一個真子集能決定R抽全體屬性U,故CE為R的候選關鍵字。薩：根據(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:屬于幾范式？踩：R1E2N

38、F騷；因EA,A+B良故EB,存在傳遞依賴野故R1任3NF薩R:任1NF皂因CE+D,C+P瑟故CE能惟一地確定R：中的每一個元組，故為候選關漠字:醛因CE是候選關鍵字，而CP，所以P部分函數(shù)依賴良與CE故R2手2NF例54對給定的關系模式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)構造一個初始的二維表如圖510所示:（2）根據(jù)AB,對上表進行處理，由于屬性列A上無相同元素，所以不能修改表。又根據(jù)C一P將屬性列P上b:,改為a,修改后的表如圖511所示。（3）根據(jù)E

39、A,對上表進行處理，由于屬性列E上第二行、第三行相同a5,所以將屬性列A上b:,、L改為同一符號b:,修改后的表如圖512所示。；（4）根據(jù)CED，對上表進行處理，無法修改上表。因此，在輾后的表格，找不到一行全為al,a：,，an,所以P是有損的。：例55試證明由Armstrong公理系統(tǒng)推導出下面三條推理規(guī)則是正確的：l（1）合并規(guī)則：若XZ，XY，則有XYZ（2）偽傳遞規(guī)則：若XY,WYZ,則有XWZ（3）分解規(guī)則：若XY,Z任Y,則有X2+證明一.（1）合并規(guī)則：因XY（已知）器故XXY（增廣律）因XZ（已知）故XYYZ（增廣律）：因XXY，XYYZ（從上面得知）故XYZ（傳遞律）（2）

40、偽傳遞規(guī)則：，因X+Y（已知）故WXWY（增廣律）因WYZ（已知）故XW2'（傳遞律）（3）分解規(guī)則：因Z（Y（已知）故YZ（自反律）因XY（已知）故XZ（傳遞律）例3-6關系R（A,B,C,D,E,F,G,H,I,J）滿足下列函數(shù)依賴：ABD+E，ABG，BF，C一工，CJI，G+H該函數(shù)依賴集是最小函數(shù)依賴集嗎?給出該關系的候選碼。解該函數(shù)依賴集不是最小函數(shù)依賴集。因CJ，CJI（已知）故CJ（邏輯蘊涵）顯然，ABCDGJ是一個超碼，即所有出現(xiàn)在函數(shù)依賴左邊的屬性的集合是超碼。但是因CJ（已知）故可將J從超碼中去掉。因ABG（已知）故可將G從超碼中去掉。此時，超碼中只剩下ABCD，

41、由于它們都沒有在函數(shù)依賴集的任何一個函數(shù)依賴的右邊出現(xiàn)，所以它們都不能從超碼中去掉。故候選碼為：ABCD。所謂超碼是指能惟一標識關系中的每一個元組，不含多余屬性的才是候選關鍵字(或候選碼)。例37設=131,F1),R2(U2,F2)是R(U,F)上的一個分解，試證明P具有無損連接的充分必要的條件是：U1門U:UlU2任F'或Ul門UzU2一Ul任F'。證明充分性：設U、門Uz-'U:一U:,則可構造表如圖513所示。該圖省略了a、b的下標。如果U，門U2+U，一U2在F中，則可將表的第二行U，一U：瀚韻所有符號全改為aaaa,使得該表的第二行全為a,則P具有海損連接性

42、。同理可證U、門U:+U:U:的情況。如果Ul門U2知：一U:不在F中，但在F'中，那么，它可以從Armstrong公理纂統(tǒng)的推理規(guī)則導出，從而也能推出Ul門U2一九，且Ai三U1一巍中，所以可以將九列的b改為a,同樣，可將UlU2的其它屬醛對應的第二行也全改為a,這樣，第二行就變成全a,所以分解是凜有無損連接性。臥(2)必要性：設構造的表中有一行全為a,例如第一行全為a'湘由函數(shù)依賴的定義可知U:門U:U:Ul;如第二行全為a,則油函數(shù)依賴的定義可知U,門U2+UlU2o黔例58試證明由關系模式中全部屬性組成的集合為候選拱鍵字的關系是3NF，同時也是BCNF。證明由于關系模式

43、中的全部屬性組成的集合為候選關鍵障，該關系中沒有非主屬性，滿足R屬于3NF的條件，即每個非主幽性即不函數(shù)依賴候選關鍵字，也不傳遞依賴于候選關鍵字。醛又因為它沒有非候選關鍵字的屬性，也滿足BCNF的三個降件：F(1)所有非主屬性對每個候選關鍵字都完全函數(shù)依賴；苣(2)沒有任何屬性都完全函數(shù)依賴于非候選關鍵字的任一組61性；因為它只是一個候選關鍵字，所以又滿足BCNF的另一個陋伍(3)所有的主屬性對每一個不包含它的候選關鍵字也是完全函數(shù)依賴。例59試證明一個關系模式R是BCNF，那么它一定是3NF。證明采用反證法。設關系模式R是BCNF，不是3NF的，則必存在非主屬性A和候選關鍵字X以及屬性組Y，

44、使得：X，Y，Y+A，其中A+X，AY，Y+X不屬于F，這就是說Y不可能包含R的候選關鍵字，但YA卻成立。根據(jù)BCNF定義，R不是BCNF，與題設矛盾，所以一個BCNF必是3NF的。例510關系R(A,B,C,D,E)滿足下列函數(shù)依賴：F=AC,CD,BC,DEC,CEA(1)給出關系R的候選關鍵字；(2)判P=AD,AB,BC,CDE,AE是否無損連接分解；(3)將R分解為BCNF，并具有無損連接性。解(1)從函數(shù)依賴集F中看，候選關鍵字至少包含BE,因為BE不依賴于誰，而(BE)'=ABCDE，所以，BE是R的候選關鍵字。(2)構造一個二維表，如圖514所示。根據(jù)A+C，對上表進行

45、處理，由于屬性列A上第1，2，5行相同，但屬性列C上對應的1,2,5行上無ai元素，所以，只能將b13b:bs,改為行號最小值b130又根據(jù)CD將屬性列D上b.改為a：,修改后的表如圖515所示。臣blb擴根據(jù)BC，對上表進行處理，由于屬性列B上第2，3行相湘，但屬性列C上對應的3行為a：元素，所以，只能將第2行b13改妝口a3。又根據(jù)DEC,CEA不能修改此表所以修改后的表如卜,i聲516所不。摹“。”：根據(jù)AC,對上表進行處理，由于屬性列A上第1,2,5府相同，但屬T列C上對應的1,2,5行上有a3元素，所以，只能將藻1,5行b13改為a3。又根據(jù)C+D將屬性列D上b2'bs：改為

46、a4,:修改后的表如圖517所示。根據(jù)CE+A，對上表進行處理，由于屬性列CE上第4，5行相伺，但屬性列A上對應的5行為al元素，所以，將第4行b41改為a,。修改后的表如圖518所示。繼續(xù)掃描F不能修改此表，由于找不到一行全為a,所以該分解是有損的。(3)考慮AC，因為AC不包含候選關鍵字，所以AC不是BCNF，故將ABCDE分解為兩個子模式R1(AC)R2(ABDE)。此時，R1正BCNF。，繼續(xù)分解R2，考慮BD，將ABDE分解為兩個子模式R21(BD)R22(ABE)，此時，R21和R22均屬于BCNF。所以R分解為BCNF，并具有無損連接性的分解如下：P=AC,BD,ABE三、習題一

47、、選擇題L設學生關系模式為：學生(學號，姓名，年齡，性別，成績，專業(yè))，則該關系模式的主鍵是()。A姓名B學號，姓名C學號D學號，姓名年齡搬2設關系模式R（U，F(xiàn)），U為R的屬性集合，F(xiàn)為U上的一種函數(shù)依甑，則對R（U，F(xiàn)）而言，如果XY為F所蘊涵，且Z巨U,則XZYZ為F所酶硒。這是函數(shù)依賴的（）。筍A.傳遞律U.合并規(guī)則巴自反律D.增廣律瓢3.X一九成立是XA1A2Ah成立的（）。終久充分條件D.必要條件隨C充要條件D.既不充分也不必要蓑4.設一關系模式為：運貨路徑（顧客姓名，顧客地址，商品名，供應商姓輻，供應商地址），則該關系模式的主鍵是（）。女兒顧客姓名，供應商姓名-冪BB顧客姓名，商

48、品名軋巴顧客姓名，商品名，供應商姓名乏D顧客姓名，顧客地址，商品名醛5設有關系模式R（U，F(xiàn)），U是R的屬性集合，X，Y是U的子集，則多灌函數(shù)依賴的傳遞律為（）。薩A.如果X+Y,且YZ,則XZ小h:,薩B.如果X一+Y,Y+Z,則X+（ZY）粒豪C.如果X一+Y,則X一+（U丫一X）鏟D.如果X+一Y,VOW,則WX一+VY嚴6.下列有關范式的敘述中正確的是（）。瓢A.如果關系模式RElNF，且R中主屬性完全函數(shù)依賴于主鍵，則R遵2NF蜂B如果關系模式RE3NF，X,YOU，若X+Y,則R是BCNFC如果關系模式REBCNF，若X+Y（Y篡X）是平凡的多值依賴，簿斕R是4NF芝D.一個關系模

49、式如果屬于4NF，則一定屬于BCNF；反之不成立釃7.關系模式學生（學號，課程號，名次），若每一名學生每門課程有一定輛名次，每門課程每一名次只有一名學生，則以下敘述中錯誤的是（）。牲A.（學號，課程號）和（課程號，名次）都可以作為候選鍵駐D.只有（學號，課程號）能作為候選鍵彈巴關系模式屬于第三范式D.關系模式屬于BCNF8 .下列敘述中正確的是（）。A.若X+一Y，其中Z二UX+Y：中，則稱X一一Y為非平凡的多疽依賴且若X，一Y，其中Z：UXY：中，則稱X一一Y為平凡的多值依賴巴對于函數(shù)依賴A1,A2,，AnB來說，如果B是A中的某一個，則稱為非平凡函數(shù)依賴D.對于函數(shù)依賴A1,A2,，AnB

50、來說，如果B是A中的某一個，則稱為平凡函數(shù)依賴9 .能消除多值依賴引起的冗余的是（）。A.2NFa3NFC.4NFaBCNF10.下列敘述中正確的是（）。丸第三范式不能保持多值依賴D第四范式肯定能保持多值依賴CBC范式可能保持函數(shù)依賴D第四范式不能保持函數(shù)依賴11 下列關于第四范式的敘述中錯誤的是()。丸第四范式條件實質(zhì)上是BC范式條件a第四范式應用與多值依賴C如果一個關系屬于第四范式，則每個非平凡多值依賴實際上就是一個左邊為超鍵碼的函數(shù)依賴D屬于BC范式的每個關系都屬于第四范式12 以下敘述中正確的是()。久函數(shù)依賴XY的有效性僅決定于兩屬性集的值；而多值依賴X一一Y的有效性與屬性集的范圍有

51、關D函數(shù)依賴XY與多值依賴X+Y的有效性都決定于兩屬性集的值C多值依賴X一一Y若在R(U)上成立，則對任何Y三Y都有X一一Y成立D對于函數(shù)依賴XY在R上成立，不能斷言對任何y'cY均有X隘r成立醛：13關系數(shù)據(jù)庫設計理論中，起核心作用的是()。蘸A范式D模式設計巳數(shù)據(jù)依賴D數(shù)據(jù)完整性醛爵二、填空題躚釅1關系數(shù)據(jù)庫是以為基礎的數(shù)據(jù)庫，利用細述現(xiàn)實世界。一個關系既可以描述，也可以描述攥l+扛2在關系數(shù)據(jù)庫中，二維表稱為一個表的每一行稱為卜：二，表的每一列稱為。芝3數(shù)據(jù)完整性約束分為和兩類。黔4關系數(shù)據(jù)庫設計理論，主要包括三個方面內(nèi)容：、：二和。其中起著核心的作用。隘5X-,-Y是模式R的一

52、個函系依賴，在當前值，的兩個不同元組中，如海X值相同，就一定要求。也就是說，對于x的每一個具體涕，都有與之對應。隘；6設F是關系模式R的一個函系依賴集，X，Y是R的屬性子集，如果熬，則稱F邏輯蘊涵XY，記為。被F邏輯蘊涵g麴函系依賴的全體構成的集合，稱為，記作。§；：7設U是關系模式R的屬性集，X，Y，Z是U的子集，則：FD的自反律泌；增廣律是；傳遞律是。函系依陽推理規(guī)則系統(tǒng)(自反律、增廣律和傳遞律)是一一的。芝8.關系模式R(U)上的兩個函數(shù)依賴集 F 和予，如果滿足醞，則稱F和G是等價的。芝9每個函系依賴集F都可以被的函數(shù)依賴集G所覆蓋。釀lo.將一個關系模式分解成多個關系模式時

53、，為了保持原模式所滿足的豪特性要求分解處理具有和811.設R是一關系模式，分解成關系模式P'R1,R2,，Rk,P是R上的一個函數(shù)依賴集，如果對R中滿足F的每一個關系，都有膽以以以以以以，N，j稱該分解P相ZF&“xN969”。臣12 .如果R的分解為P=Rl,R2,F為R所滿足的函數(shù)依賴集合，分解P具有無損聯(lián)接性的充分必要條件是或。13 ，多值依賴的合并律是以以；偽傳遞律是以以；分解律是。14 對于函數(shù)依賴X以Y，如果Y巨X，則稱X以Y是一個。15 對屬性集U上的一個多值依賴X+一Y(X，Y是U的子集)，如果以以，則稱以以是一個平凡的多值依賴。16 好的模式設計應符合、三條原

54、則。三、問答題1關系規(guī)范化一般應遵循的原則是什么?2多值依賴與函數(shù)依賴有哪些主要的區(qū)別?3低級范式的關系模式對數(shù)據(jù)存儲和數(shù)據(jù)操作產(chǎn)生的不利影響是什么?4 3NF與BCNF的區(qū)別和聯(lián)系各是什么?5設一關系為：學生(學號，姓名，年齡，所在系，出生日期)，判斷此關系屬性組屬于第幾范式。為什么?6下面的結(jié)論哪些是正確的?哪些是錯誤的?對于錯誤的請給出一個反例說明之。(1)任何一個二目關系是屬于3NF。(2)任何一個二目關系是屬于BCNF(3)任何一個二目關系是屬于4NF。(4)當且僅當函數(shù)依賴A+B在R上成立，關系R(A,B,C)等與其投影Rl(A,B)和凡(A,C)的連接。(5)若R.AR.B,R.B-"R.C,則民A'-*R.C(6)若R.AR.B,R.A+兄C,則R.A民(B,C)(7)若R.BR.A.R.C+R.A,則R.(B,C)R.A(8)若R.(B,C)R.A,則R.B'-R.A,R.CR.A四、綜合題1.對給定的關系模式R(U,F),U=A,B,C,D),F:AB,CD,BC臥燦球P、。膽：2.已知學生關系模式S(Sno,Sname,SD,Sdname,Course,Grade),其中：肛學號Sname姓名SD系名Sdname系主任名Course課程Grade成績。默(1)寫出