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

1、第四章范式定理關(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)掌握：(1) 函數(shù)依賴及Armstrong公理系統(tǒng)(2) 為什么要對(duì)模式進(jìn)行分解，如何分解(3) 如何判斷關(guān)系模式達(dá)到幾范式(4) 如何求屬性的閉包及如何求最小函數(shù)依賴集(5) 判斷分解后的關(guān)系模式是不是無損連接或保持函數(shù)依賴(6) 判斷分解后的關(guān)系模式既無損連接又保持函數(shù)依賴(一)函數(shù)依賴及相關(guān)概念定義 設(shè)R(U)是屬性集U上的關(guān)系模式，X，Y是U的子集。若對(duì)R(U)的任何一個(gè)可能的關(guān)系r，r中不

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

3、遞依賴(4)碼：設(shè)K為R(U , F)中的屬性的組合，若KU，貝U K為R的候選碼，若有多個(gè)候選碼，選一個(gè)作為主碼。注：候選碼也稱候選關(guān)鍵字。 主屬性和非主屬性：包含在任何一個(gè)候選碼中的屬性叫做主屬性，否則叫做非主屬性。(6)夕卜碼：若R(U)中的屬性或?qū)傩越M X非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)系如下：1NF 2NF 3NF BCNF 4NF 5NF通過模式分解，將低一級(jí)范

4、式的關(guān)系模式分解成了若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過程叫做 規(guī)范化。下面將給岀各個(gè)范式的定義。1. 1NF(第一范式)定義 若關(guān)系模式R的每一個(gè)分量是不可再分的數(shù)據(jù)項(xiàng)，則關(guān)系模式R屬于第一范式(1NF) o例 供應(yīng)者和它所提供的零件信息，關(guān)系模式如下：FIRST (Sno，Sname，Status, City，Pno, Qty)并且有 F= Sno Sname，Sno Status，Status City， (Sno， Pno) Qty具體的關(guān)系如圖 5 l所示。SnoSnameStatusCityPnoQtyS1精益20天津P1200S1精益20天津P2300S1精益20天津P348

5、0S2盛錫10北京P2168S2盛錫10北京P3500S3東方紅30北京P1300S3東方紅30北京P2280S4 泰達(dá)20上海P2460從圖5 1中可以看岀，每一個(gè)分量都是不可再分的數(shù)據(jù)項(xiàng)，所以是1NF。但是，1NF帶來四個(gè)問題：(1) 冗余度大：例如每個(gè)供應(yīng)者的Sno，Sname，Status， City要與零件的種類一樣多；(2) 引起修改操作的不一致性：例如供應(yīng)者S1從“天津”搬到“上海”，若稍不注意，就會(huì)使一些數(shù)據(jù)被修改，另一些數(shù)據(jù)沒有被修改，導(dǎo)致數(shù)據(jù)修改的不一致性；(3) 插入異常：若某個(gè)供應(yīng)者的其它信息未提供時(shí)，如“零件號(hào)”，則不能進(jìn)行插入操作；(4) 更新異常：若供應(yīng)商 S4的

6、P2零件銷售完了，刪除后，在基本關(guān)系FIRST找不到S4,可S4又是客觀存在的。正因?yàn)樯鲜鲈蛞肓?NF。2. 2NF(第二范式)定義 若關(guān)系模式R 1NF，且每一個(gè)非主屬性 完全依賴于碼，則關(guān)系模式 R 2NF。即當(dāng)1NF消除了非主屬性對(duì)碼的部分函數(shù)依賴，則成為2NF。例 FIRST關(guān)系中的碼是 Sno、Pno，而Sno Status，因此非主屬性 Status部分函數(shù)依賴于碼，故非2NF的。若此時(shí)，將FIRST關(guān)系分解為:FIRSTI(Sno，Sname，Status，City) 2NFFIRST2(Sno，Pno，Qty) 2NF因?yàn)镕IRSTl和FIRST2中的碼分別為 Sno和Sn

7、o，Pno每一個(gè)非主屬性完全依賴于碼。3. 3NF(第三范式)定義 若關(guān)系模式 R(U，F(xiàn))中不存在這樣的碼X，屬性組 Y及非主屬性 Z(Z Y)使得X Y，(Y X)Y . Z成立，則關(guān)系模式R 3NF。即當(dāng)2NF消除了非主屬性對(duì)碼的傳遞函數(shù)依賴，則成為3NF。例FIRSTl3NF，因?yàn)樵诜纸夂蟮年P(guān)系模式FIRSTl中有：Sno Status， StatusCity，存在著非主屬性 City傳遞依賴于碼 Sno。4. BCNF(巴克斯范式)；定義 若關(guān)系模式 R 1NF，若X Y且Y X時(shí)，.X必含有碼，則關(guān)系模式R BCNF。即當(dāng)3NF消除了主屬性對(duì)碼的部分和傳遞函數(shù)依賴，則成為BCNF。

8、結(jié)論 一個(gè)滿足BCNF的關(guān)系模式，應(yīng)有如下性質(zhì):(1) 所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴;(2) 所有非主屬性對(duì)每一個(gè)不包含它的碼，也是完全函數(shù)依賴；(3) 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。(三) 多值依賴1 多值依賴定義 若關(guān)系模式 R(U)中，X、Y、Z是U的子集，并且 Z = U X Y。當(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ì)：(1)多值依賴具有對(duì)稱性。即若XY，貝U XZ，其中Z =

9、U X Y(2)多值依賴的傳遞性。即若XY，YZ,貝U XZ Y(3)函數(shù)依賴可以看成是多值依賴的特殊情況(4)若 XY，XZ，則XYZ若XY，XZ，貝，XY Z;若XY，XZ，則XZ Y。3. 4NF(第四范式)定義(4NF)若關(guān)系模式R 1NF，若對(duì)于R的每個(gè)非平凡多值依賴X Y且Y X時(shí)，X必含有碼，則關(guān)系模式R(U，F(xiàn)) 4NF。(四) 函數(shù)依賴的公理系統(tǒng)Armstrong公理系統(tǒng)：設(shè)關(guān)系模式 R(U，F(xiàn))，其中U為屬性集，F(xiàn)是U上的一組函數(shù)依賴， 那么有如下推理規(guī)則：(1) A1自反律：若Y X U，則X Y為F所蘊(yùn)涵；(2) A2增廣律：若 X Y為F所蘊(yùn)涵，且 Z U，貝U XZ

10、 YZ為F所蘊(yùn)涵；(3)A3傳遞律：若 X Y，Y Z為F所蘊(yùn)涵，則X Z為F所蘊(yùn)涵。根據(jù)上述三條推理規(guī)則又可推出下述三條推理規(guī)則：(1)合并規(guī)則：若XY，XZ,則XYZ為F所蘊(yùn)涵偽傳遞率：若XY，WYZ,則XWZ為F所蘊(yùn)涵(3)分解規(guī)則：若XY，ZY，則XZ為F所蘊(yùn)涵。引理：X A: A1A2 A1成立的充分必要的條件是X Ai成立(1=1 , 2, 3 ，k)(五) 函數(shù)依賴的閉包F+及屬性的閉包 X +:1 函數(shù)依賴的閉包定義 關(guān)系模式R(U , F)中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體稱為F的閉包，記為：F+2 屬性的閉包定義 設(shè) F 為屬性集 U 上的一組函數(shù)依賴， XU ,= A |

11、X X A 能由 F 根據(jù) Armstrong3公理導(dǎo)出 ，則稱為屬性集 X 關(guān)于數(shù)依賴集+X +F求屬性 X 的閉包 X 吉的算法+X +FF 的閉包。算法 求屬性的閉包輸入 X ， F輸出X +F步驟(1)X(°)=X , i= 0(2)B, B = A 1(v)(w)(V(i)V X A W)(3) X(i+1)=B X(i)(4) 判斷 X(i+1)= X(i) 嗎若相等，或X(I)=U，則X為屬性集X關(guān)于函數(shù)依賴集F的閉包。且算法終止(6)若不相等，則 i= i+1 ，返回第二步例 1 已知關(guān)系模式 R(U , F), U = A , B, C , D , E);F = A

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

13、 函數(shù)依賴。故有XCl '： ADUBC 。計(jì)算X 'n：逐一掃描F中的各個(gè)函數(shù)依賴，找到左部為ADBC 或 ADBC 子集的函數(shù)依賴，得到兩個(gè)：BC E，AC B函數(shù)依賴。故有 X2，： ABCDUE 。所以， X(2'： ABCDE ： U，算法終止， (AD) 吉： ABCDE 。(六 )最小函數(shù)依賴集1 等價(jià)和覆蓋定義一個(gè)關(guān)系模式R(U，F(xiàn))上的兩個(gè)依賴集G。F ' = G '，則稱F和G是等價(jià)的，記做 F三若F三G ,則稱G是F的一個(gè)覆蓋，反之亦然兩個(gè)等價(jià)的函數(shù)依賴集在表達(dá)能力上是完全相同的。2最小函數(shù)依賴集定義 如果函數(shù)依賴集 F 滿足下列條

14、件，則稱F 為最小函數(shù)依賴集或最小覆蓋。; (1)F 中的任何一個(gè)函數(shù)依賴的右部?jī)H含有一個(gè)屬性;”(2)F 中不存在這樣一個(gè)函數(shù)依賴 X A，使得F與F 一 X A等價(jià)；擴(kuò) (3)F中不存在這樣一個(gè)函數(shù)依賴 X A,X有真子集Z使得F 一X AUZ+A與F等價(jià)。； 3 計(jì)算最小函數(shù)依賴集的算法。算法 計(jì)算最小函數(shù)依賴集。輸入 一個(gè)函數(shù)依賴集輸出 F 的一個(gè)等價(jià)的最小函數(shù)依賴集 G步驟(1) 用分解的規(guī)則，使 F 中的任何一個(gè)函數(shù)依賴的右部?jī)H含有一個(gè)屬性；，：'(2) 去掉多余的函數(shù)依賴： 從第一個(gè)函數(shù)依賴 X+Y 開始將其從 F 中去掉， 然在剩下的函數(shù)依賴中求 X 的閉包 X 

15、9;，看X '是否包含 Y，若是，則去掉 X Y ;否則不能去掉，依次做下去。直到拽不到冗余 的函數(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，D EG，C A， BE+C 擴(kuò) BCD，CGBD，ACD-B ， CEAG; 請(qǐng)將 F 化為最小函數(shù)依賴集。 ; 解 此 題可以有兩種求解方法， 求解過程如下： 輩 方法 1

16、(利用算法求解， 使得其滿足三個(gè)條件 );(1)利用分解規(guī)則，將所有的函數(shù)依賴變成右邊都是單個(gè)屬：性的函數(shù)依賴，得 F 為：F = AB C，D+E，D+G，C A，BE CBCD， CGB， CGD， ACD B，CE+A ， CEG(2) 去掉 F 中多余的函數(shù)依賴，具體做法如下：從第一個(gè)函數(shù)依賴開始從F 中去掉它 (假定它為X Y)，剩下的函數(shù)依賴 F'求X '的閉包，看 X '是否含Y，若包含 Y，則X+Y為冗余函 數(shù)依賴，則去掉它，否則不去。依次下去，直到能滿足定義最小依賴的第二個(gè)條件。故有： 設(shè) AB C 為冗余的函數(shù)依賴，則去掉AB+C 得F1 = D+E

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

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

19、 設(shè) XCO) : CG :計(jì)算 Xm :逐一掃描 F3 中的各個(gè)函數(shù)依賴，找到左部為 C、 G 城 CG 的函數(shù)依賴，得到一個(gè)： C+A 函數(shù)依賴。 故有Xu ' :; ACG。熟 計(jì)算X '”：逐一掃描 F3中的各個(gè)函數(shù)依賴，找到左部為ACG誠(chéng)ACG子集的函數(shù)依賴，周為找不到這樣的函數(shù)依賴。故有謹(jǐn)=X”，算法終止。(CG)占=ACG。： 因?yàn)锳CG芒D，所以CG+D非冗余的函數(shù)依賴，不能從F3沖去掉。；設(shè)CE+A為冗余的函數(shù)依賴，則去掉 CE A得瞰F4 = AB-*'C ，D-E，D-*G，C+A，BEC ； BC-*-D，CG D，ACD-B，CE+G):求(C

20、Z)擊；設(shè) X(O ' : CE 芝 計(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ù)依賴。故有：騷X ' 2) = ACEG。計(jì)算X ” ：逐一掃描 F4中的各個(gè)函數(shù)依賴，找到左部為ACEG 或 ACEG 子集的函數(shù)依賴，得到一個(gè)： CGD 函數(shù)依賴。故有：X ''' = ACDEG。計(jì)算X '“：逐一掃描 F4中的各個(gè)

21、函數(shù)依賴，找到左部為AC DEG 或 ACDEG 子集的函數(shù)依賴，得到一個(gè)： ACD B 函數(shù)依賴。故有：X ''' = ABCDEG。因?yàn)?XABCDEG = U，算法終止，（CE）占：ABCDEG所以 CE+A 為冗余的函數(shù)依賴，從 F4 中去掉。又因?yàn)?F4 中無多余函數(shù)依賴所以轉(zhuǎn) （3）。（3）去掉 F4 中各函數(shù)依賴左邊多余的屬性。函數(shù)依賴 ACD+B，屬性A是多余的，去掉 A得CD B,因?yàn)镃 A，所以可推導(dǎo)岀 ACD Bo故最小函數(shù)依賴集為：FMIN = AB+C，D E，D+G，C A，BE CBC+D ， CGD， CD+B， CEG方法 2 （利用

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

23、A，B+C，A+C，C A求最小函數(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è)A C為冗余，將其從 F1中去掉 因 A B, B-C(已知) 故 A C (傳遞律)故A+C是冗余的，將其從 n中去掉，得 Fm為： FM , = A B, B+C , G+A。 因 為在 FM ，中的其它函數(shù)依賴是非冗余的，所以，F(xiàn)Ml 為

24、最小函數(shù)依賴集。答案 2 設(shè) BC 是冗余的，將其從 F 中去掉，看能否根據(jù)、 Armstrong 公理系統(tǒng)的推理規(guī)則導(dǎo)出。： 因 B A， A+C (已知 )故 BC (傳遞律 )故 B+C 是冗余的，將其從 F 中去掉，得 FM2 為FM2 = A B, B+C , A C , C A。： 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è)分解是指，P ' RI(Ul , P1), R2(U2 , F

25、2)，R。(U。，F(xiàn)。)，其中：nU = UU，并且沒有 U(U , K i, j< n, E是F在U上的投影。其中 Fi = X YX YEF '八 XY 三 Ui對(duì)一個(gè)給定的模式進(jìn)行分解,使得分解后的模式是否與原來的模式等價(jià)有三種情況：(1) 分解具有無損連接性；(2) 分解要保持函數(shù)依賴；(3) 分解既要無損連接性；又要保持函數(shù)依賴。2無損連接定義 (無損連接)P' R , (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具有

26、無損連接性(簡(jiǎn)稱無損分解 )其中， mP(r) ：岡丌 R：(r) 。定理 關(guān)系模式 R(U , F)的一個(gè)分解，P' R1(U :, F1), R:(U2， F： )具有無損連接的充分必要的條件是：Ul 門 U2 一 UlU2EF '或Ul 門 U2+U2 一 UlEF '3保持函數(shù)依賴定義：設(shè)關(guān)系模式R(U , F)的一個(gè)分解，P= 民(U : , F1) , R:咖2, F2)，Rk(Uk , Pk),如果： F' = (U丌Ki(F1-)',則稱分解P保持函數(shù)依賴。十4.判 別一個(gè)分解的無損連4i-'1和保持函數(shù)依賴的算法；算法1判別一個(gè)

27、分解的無損連接性。廣 p' Rl(U : , F1), R。(U2 , F:)，凡(UL , Fb)是關(guān)系模式 R: (U , F)的一個(gè)分解，U :A1 , A :,A。 , F= FDl , 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 列的元素，若其中有，則全；都改為，否則全部改為 bmli, m是這些行的行號(hào)最

28、小值。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

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

30、F2)，Rk(Uk ,Fk)構(gòu)成R(U , F)的一個(gè)保持函數(shù)依賴的分解。并且，每個(gè)Ri(Ui , E)均屬于3NF且保持函數(shù)依賴。例 4 關(guān)系模式 R(U，F(xiàn))，其中 U = C , T, H , I, S, G), F = CSG， C+T， THI， HIC， HSI> ，將其分解成 3NF 并保持函數(shù)依賴。解 根據(jù)算法 2 求解如下：(1) F 已為最小函數(shù)依賴集；(2) R 中的所有屬性均在F 中都出現(xiàn),所以轉(zhuǎn) (3)；(3) 對(duì)F按具有相同左部的原則分為：R1 = CSG , R2 ; CT , R3THI , R4 : HIC ,R5 ： HSR 。所以 P R1(CSG)

31、 , 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)，民為 3NF , 且 P 具有無損連接又保持函數(shù)依賴的分解。操作步驟如下:(1)根據(jù)算法2求岀保持依賴的分解P = R1 , R。，R。ii (2)判分解P是否具有無損連接性，若有，轉(zhuǎn) (4);惑；、(3)令p' pUX)，其中X是R的候選關(guān)鍵字；牡 知 (

32、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(THl) , R4(HIC) , R5(HSR) (2)根據(jù)算法 1 構(gòu)造一個(gè)二維矩陣如圖52所示。;:根據(jù)F中的C T,對(duì)上表進(jìn)行處理，由于屬性列C上第一；行、第二行及第四行相同a,所以將屬性列T上b12、b 2改為同一：符號(hào) a：。又根據(jù) HI C將屬性列C上b “、bsl改為同一符號(hào) a1'修改后如圖 5 3所示。根據(jù)F中的CS G,

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

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

35、G)、R2(CTHIS) o計(jì)算法1和R2的最小函數(shù)依賴集分別為：Fl = CS G，F(xiàn)2 = C 一黔T，TH I，HI C，HS 1> o R2的候選關(guān)鍵字為 HS。默 因 R1已是BCNF，而R2的F2中存在不為 碼的決定因睽素 HI C 駐' 故 R2 不屬于 BCNF ，進(jìn)一步分解 R2 即可。愛： 分解 R2： 考慮C T,將其分解成 R21(CT)、R22(CHIS)。計(jì)6薯R21和R22的最小函數(shù)依賴集分別為：F21 = C T , F22 =§： CH+I , HI+C , HS+I>C T , TH 一 1，.在 F22 中，有CH 一心。R2

36、2的候選關(guān)鍵字為 HS。整 因 R21已是BCNF , R22不是BCNF熙故 進(jìn) 一步分解 R22即可。默 分解R22 :考慮CH 一 1,將其分解成 R221(CHl)、R222扭CHS)。計(jì) 算R221和R222的最小函數(shù)依賴集分別為：盼醞F221 = CH I, HI C韉R : F222 :HS+C o 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è)分

37、解P= Rl(U ,F1) ,R2(U :, F2), F? ” , Rk(U , , Fk),民為4NF ,且P具有無損連接的分解。 臥 操作步驟如下：芝 令 P = R(2)若P中的所有模式都是4NF，則轉(zhuǎn)(4);若P中有一個(gè)關(guān)系模式民不是4NF，則Ri中必能找到一個(gè)函數(shù)依賴 X 一一 A，且X不包含民的候選鍵，且 A X乒中，XA ； i民令Z = A X，由分解規(guī)則得岀 X 一一 Z。令R。(XZ), Ri2(民一 Z)，用分解Ril，Ri2代替民，由于(R，門Ri2)一一 (R，一 Ri。)，所以分解具有無損 連接性。轉(zhuǎn) (2)；(4)停止分解，輸岀 p二、典型題解析例5 1對(duì)給定的

38、關(guān)系模式R(U，F(xiàn))，U = A，B，C，F(xiàn)= A B)，如下的兩個(gè)分解：(1) F1 = AB，BC(2) p : = AB，AC判這兩個(gè)分解是否無損。解 ( 1 )根據(jù)定理判斷本題因 AB門BC = BAB BC = ABC AB = C故 BA 茫 F'B+C 爭(zhēng) F '故P,為有損連接。(2) 根據(jù)定理判斷本題因 AB 門 AC 二 AAB AC = BAC AB = C故 AB 正 F'B+C F'芝 故p：為無損連接?；砝? 2對(duì)給定的關(guān)系模式R(U，F(xiàn))，U = A，B，C，D，E，F(xiàn) 山A C，B C，C D，DE C，CE A，如下的分解：；p

39、 = 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ù) B C將 屬性列C上、b北改為粗闌一符號(hào) b13，修改后的表如圖 5 6所示。牡 (3)根據(jù)C+D，對(duì)上表進(jìn)行處理，由于屬性列C上第一行第野仁行、第三行及第五行相同b, -且屬性列D上第一行為a,所以將 R '洄性列D上b：,、b，:、b：,改為同一

40、符號(hào) a：, 修改后的表如圖 5 7 渤示。苣團(tuán) O (4) 根據(jù)DE+C，將屬性列C上第三行及第五行改為同一符號(hào)a,修改后的表如圖5 8所示。田 OO(5) 根據(jù)CE+A，將屬性列A上第三行及第四行改為同一符號(hào)al,修改后的表如圖 5 9所示。通過上述更改,使第三行成為： a1, a：, a, a4, a。 ,則算法終止。且分解 P 具有無損 連接性。例5 3對(duì)給定的關(guān)系模式 R(U , F), U = A , B, C, D , E，尸通過上述更改，使第三行成為：a1，a：， a， a4，a。 ，則算法終止。且分解P 具有無損連接性。例 5 3 對(duì)給定的關(guān)系模式 R(U , F), U =

41、 A , B , C, D , E，尸軋 F ; A B , C P , E A CE D 如下的分解：感 p'R1(ABE) R2(CDEP) 甄。： (1)求 R 的候選關(guān)鍵字 并判 分解p是否無損；掃； (2)R1、R :屬于幾范式。瓢解(1)候選關(guān)鍵字為 CE筻因 (CE)'=U 6 ;十故 有CE+U ,并且在CE中不存在一個(gè)真子集能決定R抽全體屬性 U,故CE為R的候選關(guān)鍵字。薩：根據(jù)定理判斷本題分解P是否無損舉 因 ABE門CDEP = E 2 :;蔑“ ABE CDEP = AB 醛 磬 CDEP ABE : CDP 良 因 E+A , A+B(已知)莨故有E+

42、B(傳遞律)寥“因 E+A , E B豪 故 有E+AB(合并律)封:因 E+ABEF '臥：故故P為無損連接。甄.R1、R :屬于幾范式？踩：R1E2NF騷；因 E A , A+B良 故 E B ,存在傳遞依賴野 故 R1任3NF薩 R :仨1NF皂 因CE+D ,C+P瑟故 CE能惟一地確定 R :中的每一個(gè)元組，故為候選關(guān)漠字。醛因 CE是候選關(guān)鍵字，而C P,所以P部分函數(shù)依賴良與 CE故 R2 手 2NF例 5 4 對(duì)給定的關(guān)系模式 R(U , F), U = A , B , C, D, E , P , F = A B , C P , E A , CE+D,如下的分解：p=

43、R1(CP) , R : (BE) , R3(ECD) , R: (AB),判分解 P 是否無損。（2）根據(jù)A B,對(duì)上表進(jìn)行處理，由于屬性列A上無相同元素，所以不能修改表。又根據(jù) CP將屬性列P上b :，改為a,修改后的表如圖511所示。（3）根據(jù)E A，對(duì)上表進(jìn)行處理，由于屬性列E上第二行、第三行相同 a5,所以將屬性列 A上b:,、L改為同一符號(hào) b：，修改后的表如圖512所示。；（4）根據(jù)CE D，對(duì)上表進(jìn)行處理，無法修改上表。因此，在輾后的表格，找不到一行全為al, a:，an，所以P是有損的。： 例5 5試證明由Armstrong公理系統(tǒng)推導(dǎo)岀下面 三條推理規(guī)則是正確的：I （1）

44、合并規(guī)則：若 X Z , X Y，則有X YZ（2）偽傳遞規(guī)則：若 X Y , WY 乙則有 XW Z分解規(guī)則：若 X Y , Z任Y，則有X 一 2- 證明一.（1）合并規(guī)則：因 XY （已知）器 故 XXY （增廣律 ）因 XZ （已知 ）故XY YZ （增廣律 ）： 因 XXY， XY YZ （從上面得知）故XYZ（傳遞律 ） （2）偽傳遞規(guī)則：， 因 X+Y （已知）故 WX WY （ 增廣律 ）因 WY Z （ 已知 ）故 XW 一 2'（傳遞律）（3）分解規(guī)則：因 Z（Y（已知 ）故 YZ （自反律 ）因 XY （已知 ）故 XZ （傳遞律 ）例3-6關(guān)系R（A , B,

45、C, D, E , F , G , H , I, J）滿足下列函數(shù)依賴：ABD+E ， AB G， BF， C 一工， CJI， G+H該函數(shù)依賴集是最小函數(shù)依賴集嗎 ?給岀該關(guān)系的候選碼。解 該函數(shù)依賴集不是最小函數(shù)依賴集。因 CJ, CJI（已知 ）故 CJ （邏輯蘊(yùn)涵 ）顯然, ABCDGJ 是一個(gè)超碼,即所有岀現(xiàn)在函數(shù)依賴左邊的屬性的集合是超碼。但是因 CJ （已知 ）故 可將 J 從超碼中去掉。因 AB G （已知 ）故 可將 G 從超碼中去掉。此時(shí)，超碼中只剩下 ABCD ，由于它們都沒有在函數(shù)依賴集的任何一個(gè)函數(shù)依賴的右邊出現(xiàn)， 所以它們都不能從超碼中去掉。故候選碼為： ABCD

46、 。所謂超碼是指能惟一標(biāo)識(shí)關(guān)系中的每一個(gè)元組，不含多余屬性的才是候選關(guān)鍵字(或候選碼 )。例3 7設(shè)P = R1(U1 , F1), R2(U2 , F2)是R(U , F)上的一個(gè)分解，試證明P具有無損連接的充分必要的條件是：U1門U :一 Ul U2仨F'或Ul門Uz U2 一 Ul仨F'。證明 充分性：設(shè) U、門Uz-'U : 一 U :，則可構(gòu)造表如圖 5 13所示。該圖省略了 a、 b 的下標(biāo)。如果U，門U2+U，一 U2在F中，則可將表的第二行 U，一 U :瀚韻所有符號(hào)全改為 aaaa，使得該表的第二行全為a，則P具有海損連接性。同理可證U、門U : +U

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

48、NF， 同時(shí)也是BCNF 。 證明 由于關(guān)系模式中的全部屬性組成的集合為候選關(guān)鍵障，該關(guān)系中沒有非主屬性，滿足 R 屬于 3NF 的條件，即每個(gè)非主幽性即不函數(shù)依賴候選關(guān)鍵字，也不傳遞依賴于候選 關(guān)鍵字。醛 又因?yàn)樗鼪]有非候選關(guān)鍵字的屬性，也滿足 BCNF 的三個(gè)降件： F (1)所有非主 屬性對(duì)每個(gè)候選關(guān)鍵字都完全函數(shù)依賴;苣(2)沒有任何屬性都完全函數(shù)依賴于非候選關(guān)鍵字的任一組 61 性;因?yàn)樗皇且粋€(gè)候選關(guān)鍵字，所以又滿足 BCNF 的另一個(gè)陋伍 (3)所有的主屬性對(duì)每一個(gè)不包含它的候選關(guān)鍵字也是完全函數(shù)依賴。例 5 9 試證明一個(gè)關(guān)系模式 R 是 BCNF ，那么它一定是3NF 。證明

49、 采用反證法。設(shè)關(guān)系模式 R 是 BCNF ，不是 3NF 的，則必存在非主屬性 A和候選關(guān)鍵字 X以及屬性組 Y，使得：X，Y，Y+A，其中A+X，A Y，Y+X不屬于F '，這就是說 Y不可能包含 R的候選關(guān)鍵 字，但 Y A 卻成立。 根據(jù) BCNF 定義， R 不是 BCNF ，與題設(shè)矛盾， 所以一個(gè) BCNF 必是 3NF的。例5 10關(guān)系R(A , B, C , D, E)滿足下列函數(shù)依賴：F = A C, C D, B C , DE C , CE A(1) 給出關(guān)系 R 的候選關(guān)鍵字；(2) 判P = AD , AB , BC, CDE , AE是否無損連接分解；(3)

50、將 R 分解為 BCNF ，并具有無損連接性。解(1)從函數(shù)依賴集 F中看，候選關(guān)鍵字至少包含BE，因?yàn)锽E不依賴于誰(shuí)，而(BE)'=ABCDE ,所以, BE 是 R 的候選關(guān)鍵字。(2) 構(gòu)造一個(gè)二維表，如圖514 所示。根據(jù) A+C ，對(duì)上表進(jìn)行處理，由于屬性列 A 上第 1， 2， 5 行相同，但屬性列 C 上對(duì)應(yīng)的1, 2, 5行上無ai元素，所以，只能將b13b: bs,改為行號(hào)最小值 b130又根據(jù)C D將屬性列D上b 改為a :，修改后的表如圖5 15所示。臣 b lb擴(kuò) 根據(jù)B C,對(duì)上表進(jìn)行處理，由于屬性列B上第2，3行相湘，但屬性列C上對(duì)應(yīng)的3行為a :元素，所以

51、，只能將第2行b13改洳a3。又根據(jù)DE C , CE A不能修改此表所以修改后的表如卜 i聲516所示。 摹 ”?！保?根據(jù)A C,對(duì)上表進(jìn)行處理，由于屬性列A上第1, 2, 5府相同，但屬性列C上對(duì)應(yīng)的1, 2, 5行上有a3元素，所以，只能將藻 1, 5行b13改為a3。又根據(jù) C+D將屬性列D上b2 ' bs：改為a4,:修改后的表如圖 5仃所示。 根據(jù)CE+A，對(duì)上表進(jìn)行處理，由于屬性列CE上第4, 5行相伺，但屬性列 A上對(duì)應(yīng)的5行為al元素，所以，將第 4行b41改為a,。修改后的表如圖 5 18所示。 繼續(xù)掃描F不能修改此表，由于找不到一行全為a,所以該分解是有損的。(

52、3) 考慮A C,因?yàn)锳C不包含候選關(guān)鍵字，所以AC不是BCNF，故將ABCDE分解為兩個(gè)子模式 R1(AC)R2(ABDE) 。此時(shí)， R1 正 BCNF 。，繼續(xù)分解 R2，考慮B D，將ABDE分解為兩個(gè)子模式 R21 (BD)R22(ABE)，此時(shí)，R21和R22 均屬于 BCNF 。所以 R 分解為 BCNF ，并具有無損連接性的分解如下:P = AC , BD , ABE三、習(xí) 題一、選擇題L 設(shè)學(xué)生關(guān)系模式為:學(xué)生 (學(xué)號(hào)，姓名，年齡，性別，成績(jī)，專業(yè))，則該關(guān)系模式的主鍵是( )。A 姓名B 學(xué)號(hào)，姓名C 學(xué)號(hào) D 學(xué)號(hào)，姓名年齡搬 2設(shè)關(guān)系模式 R（U ， F） ， U 為

53、R 的屬性集合， F 為 U 上的一種函數(shù)依甑，則對(duì)R（U ，F(xiàn)）而言，如果X Y為F所蘊(yùn)涵，且Z巨U，則XZ YZ為F所酶硒。這是函數(shù)依賴的（）。筍 A 傳 遞律 U 合并規(guī)則巴自反律D 增廣律瓢 3 X 一九成立是X A1A2Ah成立的（）。終 久充分條件D.必要條件隨C充要條件D 既不充分也不必要蒺4 設(shè)一關(guān)系模式為：運(yùn)貨路徑 （顧客姓名，顧客地址，商品名，供應(yīng)商姓輻，供應(yīng)商地址 ），則該關(guān)系模式的主鍵 是（）。女 兒顧客姓名，供應(yīng)商姓名-幕 B B顧客姓名，商品名軋巴顧客姓名，商品名，供應(yīng)商姓名乏D 顧客姓名，顧客地址，商品名醛5設(shè)有關(guān)系模式 R（U ， F）， U 是 R 的屬性集合， X， Y 是 U 的子集，則多灌函數(shù)依賴的傳遞律為（）。薩 A 如果X+Y，且Y Z,則X Z小h:，薩 B.如果X 一 +Y，Y+ 一 Z,貝U X+（Z Y）粒豪 C .如果 X 一 +