最小函數(shù)依賴.ppt

1、第6章 關系模式的規(guī)范化理論,6.3 函數(shù)依賴的公理系統(tǒng),6.3.1 函數(shù)依賴的邏輯蘊涵 6.3.2 Armstrong公理系統(tǒng) 6.3.3 函數(shù)依賴集的等價與覆蓋,6.3.1 函數(shù)依賴的邏輯蘊涵,例如在上述的傳遞函數(shù)依賴中，由XY，YZ，推導出XZ，這可以表示為： XY，YZ XZ 其中: 表示邏輯蘊涵。 一般地講，函數(shù)依賴的邏輯蘊涵定義如下：,定義6.6（邏輯蘊涵）：設F是由關系模式R(U)滿足的一個函數(shù)依賴集，XY是R的一個函數(shù)依賴，且不包含在F，如果滿足F中所有函數(shù)依賴的任一具體關系r，也滿足XY，則稱函數(shù)依賴集F邏輯地蘊涵函數(shù)依賴XY，或稱XY可從F推出?？杀硎緸椋?FXY,函數(shù)依賴

2、集F的閉包F+,定義6.7：函數(shù)依賴集F所邏輯蘊涵的函數(shù)依賴的全體稱為為F的閉包（Closure），記為F+，即F+XYFXY,例如，有關系R（X，Y，Z），它的函數(shù)依賴集FXY，YZ，則其閉包F+為：,6.3.2 Armstrong公理系統(tǒng),1）獨立推理規(guī)則 即下面給出的Armstrong公理的三條推理規(guī)則是彼此獨立的。,（3） A3：傳遞律(Transitivity) 如果XY且YZ，則XZ成立。,（2） A2：增廣律(Augmentation) 如果XY，且Z W，則XWYZ成立。 根據(jù)A2可以推出XWY、XZYZ或XWYW、XXY、XYX等。,（1） A1：自反律(Reflexivit

3、y) 如果Y X，則XY成立，這是一個平凡函數(shù)依賴。 根據(jù)A1可以推出X、UX等平凡函數(shù)依賴（因為 X U）。,2）其他推理規(guī)則,推論1：合并規(guī)則(The Union Rule) XY，XZ XYZ,推論3：偽傳遞規(guī)則(The Pseudo Transitivity Rule) XY，WYZ XWZ,證：（1）XY XXY（A2增廣律） XZ XYYZ （A2增廣律） 由上可得XYZ （A3傳遞律）,（3）XYWXWY （A2增廣律） WYZ （給定條件） 由上可得XWZ（A3傳遞律）,（2）Z Y YZ （A1自反律） XY （給定條件） 由上可得XZ（A3傳遞律）,推論2：分解規(guī)則(The

4、 Decomposition Rule) 如果XY，Z Y，則XZ成立,一個重要定理,例6.2：設有關系模式R(A,B,C,D,E)及其上的函數(shù)依賴集F=ABCD,AB,DE，求證F必蘊涵AE。,定理6.1：若Ai(i=1，2，,n)是關系模式R的屬性， 則X(A1，A2，,An)成立的充分必要條件是XAi均成立。,證明： AB （給定條件） AAB （A2增廣律） ABCD （給定條件） ACD （A3傳遞律） AC，AD （分解規(guī)則） DE （給定條件） AE （A3傳遞律） 證畢。,屬性集閉包,定義6.8（屬性集閉包）:設有關系模式R(U),U= A1，A2，,An,X是U的子集,F是U

5、上的一個函數(shù)依賴集，則屬性集X關于函數(shù)依賴集F的閉包 定義為： AiAiU，且XAi可用阿氏公理從F推出,例：設關系模式R(A,B,C)的函數(shù)依賴集為F=AB,BC，分別求A、B、C的閉包。,解：若XA， AB,BC（給定條件） AC （A2傳遞律） AA （A1自反律） =A，B，C （據(jù)定義）,若X=B BB （A1自反律） BC （給定條件） =B，C （據(jù)定義）,若X=C， CC （自反律） =C （據(jù)定義）,定理6.2:設F是關系模式R(U)上的函數(shù)依賴集,U是屬性全集，X,Y U,則函數(shù)依賴XY是用阿氏公理從F推出的，充分必要條件是Y ； 反之，能用阿氏公理從F推出的所有XY的Y都

6、在 中。,這個定理告訴我們，只要Y ，則必有XY。于是，一個函數(shù)依賴XY能否用阿氏公理從F推出的問題，就變成判斷Y是否為 子集的問題。 下面介紹一下計算 的算法。,屬性集的閉包計算,方法：根據(jù)下列步驟計算一系列屬性集合X(0)，X(1)， (1) 令X(0)=X，i0； (2) 求屬性集 /*在F中尋找滿足條件V X(i)的所有函數(shù)依賴VW,并記屬性W的并集為B*/ (3) X(i+1)X(i) B (4)判斷X(i+1)= X(i)嗎？ (4)若X(i+1) X(i)，則用i+1取代i,返回(2)； (5)若X(i+1) = X(i)，則 =X(i)，結束。,算法6.1：求屬性集X(X U)

7、關于U上的函數(shù)依賴集F的閉包 。 輸入：屬性全集U,U上的函數(shù)依賴集F,以及屬性集X U。 輸出：X關于F的閉包 。,算法6.1的求解過程,例：設FAHC，CA，EHC，CHD，DEG，CGDH，CEAG，ACDH，令XDH ，求 。,最后，(DH)+=ACDEGH。,解： X(0)=X=DH 在F中找所有滿足條件V X(0)=DH的函數(shù)依賴VW，結果只有DEG，則B=EG，于是X(1)X(0)B=DEGH 。 判斷是否X(i+1)= X(i)，顯然X(1)X(0)。 在F中找所有滿足條件V X(1)=DEGH的函數(shù)依賴VW，結果為EHC，于是B=C，則X(2)X(1)B=CDEGH 。 判斷

8、是否X(i+1)= X(i)，顯然X(2)X(1)。 在F中找所有滿足條件V X(2)=CDEGH的函數(shù)依賴VW，結果為CA，CHD，CGDH，CEAG，則B=ADGH，于是X(3)X(2)B=CDEGHB=ACDEGH 。 判斷是否X(i+1)= X(i)，這時雖然X(3)X(2)。但X(3)已經包含了全部屬性，所以不必再繼續(xù)計算下去。,屬性集閉包計算結束判斷方法,在判斷計算何時結束時，可用下面四種方法： （1）X(i+1)= X(i)。 （2）X(i+1)已包含了全部屬性。 （3）在F中再也找不到函數(shù)依賴的右部屬性是X(i)中未出現(xiàn)過的屬性。 （4）在F中再也找不到滿足條件V X(i)的函

9、數(shù)依賴VW。,6.3.3 函數(shù)依賴集的等價和覆蓋,定義6.9（函數(shù)依賴集的等價、覆蓋）：設F和G是關系R（U）上的兩個依賴集，若F+=G+，則稱F與G等價，記為F=G。也可以稱F覆蓋G，或G覆蓋F；也可說F與G相互覆蓋。,檢查兩個函數(shù)依賴集F和G是否等價的方法是： 第一步：檢查F中的每個函數(shù)依賴是否屬于G+，若全部滿足，則F G+。如若有XYF,則計算 ,如果Y , 則XYG+; 第二步：同第一步，檢查是否G F+; 第三步：如果F G+，且G F+，則F與G等價。 由此可見,F和G等價的充分必要條件是：F G+，且G F+。,引理6.1：設G是一個函數(shù)依賴集，且其中所有依賴的右部都只有一個屬

10、性，則G覆蓋任一左部與G（左部）相同的函數(shù)依賴集。,一個函數(shù)依賴集F可能有若干個與其等價的函數(shù)依賴集，我們可以從中選擇一個較好以便應用的函數(shù)依賴集。標準至少是： 所有函數(shù)依賴均獨立，即該函數(shù)依賴集中不存在這樣的函數(shù)依賴，它可由這個集合中的別的函數(shù)依賴推導出來。 表示最簡單，即每個函數(shù)依賴的右部為單個屬性，左部最簡單。,證明：構造GXAXYF且AY 由AY，XYF根據(jù)分解規(guī)則導出，從而等到G F+。 反之，如果YA1A2An，而且XA1，XA2，XAn在G中可根據(jù)合并律等到F G +。 由此可見，F(xiàn)與G等價，即F被G覆蓋。,最小函數(shù)依賴集,定義6.10（最小函數(shù)依賴集）:函數(shù)依賴集F如果滿足下列

11、條件，則稱F為最小函數(shù)覆蓋，記為Fmin： (1) F中每一個函數(shù)依賴的右部都是單個屬性。 (2) 對F中任一函數(shù)依賴XA，F(xiàn)XA都不與F等價。 (3) 對于F中的任一函數(shù)依賴XA, FXAZA都不與F等價，其中Z為X的任一真子集。,求函數(shù)依賴集F的最小覆蓋的方法是： (1) 檢查F中的每個函數(shù)依賴XA,若A= A1,A2,Ak,則根據(jù)分解規(guī)則，用XAi(i=1，2，k)取代XA。 (2) 檢查F中的每個函數(shù)依賴XA,令G=FXA， 若有 A ，則從F中去掉此函數(shù)依賴。 (3) 檢查F中各函數(shù)依賴XA，設X= B1,B2,Bm,檢查Bi ， 當A 時，即以XBi替換X。,最小覆蓋的求解事例,例

12、6.5：求下列函數(shù)依賴集的最小覆蓋： FAHC，CA，CHD，CEG，EHC， CGDH， CEAG，ACDH 。,解：(1)用分解規(guī)則將F中的所有依賴的右部變成單個屬性，可以得到以下11個函數(shù)依賴： AHC，CA，CHD，ACDH （給定） CE，CG（由CEG分解得到） EHC （給定） CGH，CGD（由CGDH分解得到） CEA，CEG（由CEAG分解得到） (2) 根據(jù)阿氏公理去掉F中的冗余依賴 由于從CA可推出CEA，從CA、CGD、ACDH推出CGH，因此CEA和CGH是冗余，可從F刪除 。 (3) 用所含屬性較少的依賴代替所含屬性較多的依賴。 由于CA, ACDH中A是冗余屬性

13、，因此，可用CDH代替ACDH，故刪除ACDH。 最后得到F的最小覆蓋為： FAHC，CA，CHD，CDH，CE，CG，EHC，CGD，CEG,6.候選關鍵字的求解方法,給定一個關系模式R(U，F(xiàn))，U=A1，A2，An，F(xiàn)是R的函數(shù)依賴集，那么，可以見屬性分為如下四類： L：僅出現(xiàn)在函數(shù)依賴集F左部的屬性 R：僅出現(xiàn)在函數(shù)依賴集F右部的屬性 LR：在函數(shù)依賴集F左右部都出現(xiàn)的屬性 NLR：在函數(shù)依賴集 F左右部都未出現(xiàn)的屬性,6.候選關鍵字的求解方法,求候選碼的規(guī)則： （1）如果有屬性不在函數(shù)依賴集中出現(xiàn)，那么它必須包含在候選碼中；（2）如果有屬性不在函數(shù)依賴集中任何函數(shù)依賴的右邊出現(xiàn)，那么

14、它必須包含在候選碼中；（3）如果有屬性只在函數(shù)依賴集的左邊出現(xiàn)，則該屬性一定包含在候選碼中。（4）如果有屬性或屬性組能唯一標識元組，則它就是候選碼；,6.候選關鍵字的求解方法,設有關系模式 R（B，C，M，T，A，G），根據(jù)語義有如下函數(shù)依賴集，F(xiàn)=B-C, (M,T)-B, (M,C)-T, (M,A)-T, (A,B)-G 則求關系的候選碼？ 根據(jù)第一條，發(fā)現(xiàn)所有的屬性都在函數(shù)依賴集中出現(xiàn)了。所以不使用第一條規(guī)則根據(jù)第二條，只有M,A沒有在函數(shù)依賴的右邊出現(xiàn)，則,A,M一定是候選碼的一部分。根據(jù)第三條，只有M,A只在函數(shù)依賴的左邊出現(xiàn)，因此可以判定AM一定是候選碼的一部分。根據(jù)第四條，只有

15、（M,A）這個屬性組可以唯一確定屬性集中的每一個屬性，因此，(M,A)一定是該關系模式的候選碼。在根據(jù)第四條，沒有發(fā)現(xiàn)還有別的屬性或屬性組能夠確定屬性集中的全部屬性，因此可以確定，該關系模式只有一個候選碼，該候選碼就是（M,A）,單獨的A或M都不是候選碼，候選碼是M和A的組合。,舉例,【例2.18】設關系模式R(U，F(xiàn))，其中U=A，B，C，D，F(xiàn)=AC， CB， ADB。求R的候選碼。,舉例,解:根據(jù)結論(1)可以求得R的候選碼為AD，而且AD是R唯一的候選碼。分析如下: (1)檢查 F發(fā)現(xiàn)，A，D只出現(xiàn)在函數(shù)依賴的左部，所以為L類屬性，而F包含了全屬性，即不存在NLR類的屬性。 (2)根據(jù)

16、求屬性閉包的算法，F(xiàn)中AC，ADB可以求得 =ABCD=U，而在 AD中不存在一個真子集能決定全屬性，故AD為R的候選碼。,舉例,【例2.19】設關系模式R(U，F(xiàn))，其中U=H，I，J，K，L，M，F(xiàn)=HI，KI，LMK，IK，KHM。求R的候選碼。,舉例,解:根據(jù)結論(1) 、(2) 、(3)和(4) 可以求得R的候選碼為HLJ，而且HLJ是R唯一的候選碼。分析如下: (1)檢查 F發(fā)現(xiàn)， H，L只出現(xiàn)在函數(shù)依賴的左部，所以為L類屬性， J為NLR類的屬性。 (2)根據(jù)求屬性閉包的算法，F(xiàn)中HI，IK， KHM可以求得 =HIJKLM=U，而在HLJ中不存在一個真子集能決定全屬性，故HLJ

17、為R的候選碼。,2）結果為3NF的依賴保持分解,算法6-4：結果為3NF的依賴保持分解算法 輸入：關系模式R和函數(shù)依賴集F 輸出：結果為3NF的一個依賴保持分解 步驟： (1)如果R中有某些屬性與F的最小覆蓋F 中的每個依賴的左邊和右邊都無關，原則上可由這些屬性構成一個關系模式，并從R中將它們消除； (2)如果F中有一個依賴涉及到R的所有屬性，則輸出R; (3)否則，輸出一個分解,它由模式XA組成，其中XAF。但當XAl，XA2，XAn均屬于F時，則用模式XAlA2An代替XAi(i=1,2，,n)。 例6-15：對于上例， F=CT,CSG,HTR,HRC,CHR,HSR,KEYHS 所以

18、= CT,CSG,HRT,CHR,HSR,定理6-11：設是由結果為3NF的依賴保持分解算法得到的3NF分解，X為R的一個候選關鍵字，則X是R的一個分解，且中的所有關系模式均滿足3NF,同時，既具有連接不失真性，又具有依賴保持性。,3）結果為3NF且具有依賴保持和連接不失真的分解,例：已知R(C,T,H,R,S,G), F=CT,HRC,CSG,HSR,HTR，KEY=HS， 則 = CT,CSG,HRT,CHR,HSR,HS 但HS HSR，故 =CT，CSG，HRT，CHR，HSR,6.4 關系模式的分解 及其問題,6.4.1 什么叫模式分解 6.4.2 分解的無損連接性 6.4.3 保持

19、函數(shù)依賴性,6.4.1 什么叫模式分解,例6.6：設在模式R(U,F)中 USNO，SNAME，DNAME，DADDR FSNOSNAME，SNODNAME，DNAMEDADDR 如果對R作如下分解（方法1）： =R1（SNO,SNAME,SNOSNAME）， R2（ DNAME，DADDR, DNAMEDADDR）,定義6.11（模式分解）：關系模式R(U，F(xiàn))的一個分解是若干個關系模式的一個集合：=R1(U1,F1),R2(U2,F2),Rn(Un,Fn) 式中：(1) 。 (2) 對每個i，j（1i,jn）有 。 (3) Fi(i=1，2，,n)是F在Ui上的投影，即,（1）連接不失真問

20、題,方法2：假設按下列方法對R進行分解 =R1 (SNO,SNAME,DNAME,SNOSNAME,SNODNAME ), R2（DNAME,DADDR），DNAMEDADDR）,（2）依賴保持問題,上例方法1： FSNOSNAME，SNODNAME，DNAMEDADDR F1F2SNOSNAME，DNAMEDADDR F+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR (F1F2)+SNOSNAME，DNAMEDADDR,一個關系模式經分解后，其函數(shù)依賴集F也隨之被分解，則分解后的依賴集Fi并集是否能保持原有的函數(shù)依賴關系？即 ? 若出現(xiàn) ，說明分解后有些函數(shù)依賴

21、被丟失了。,上例方法2： FSNOSNAME，SNODNAME，DNAMEDADDR F1F2SNOSNAME,SNODNAME,DNAMEDADDR F+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR (F1F2)+ SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR,6.4.2 分解的無損連接性,1）無損連接分解的定義,定義6.12（無損連接分解，即連接不失真分解）：設關系模式R（U，F(xiàn)）上的一個分解為=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)，F(xiàn)是R（U，F(xiàn)）上的一個函數(shù)依賴集。如果對R中滿足F的任一關系r都有 則稱這

22、個分解相對于F的是連接不失真分解或稱無損連接分解。,對于關系模式R關于F的無損連接條件是： 任何滿足F的關系r有r = m(r)。,r 和m(r)之間的聯(lián)系,定理6.4：設R是一關系模式，=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)是關系模式R的一個分解，r是R的任一關系，（1ik）,那么有： ； 如果s= m(r)，則 ，或 mm(r)= m(r),定理6.4證明, 由定理6-5可知 ，可得到 ，即 （因為s= m(r)）（也就是兩邊同時在Ui上投影，得 ）。 為了證明 。假設 ，則s中必存在滿足tRi=ti的元組t。由于ts,對每個j,在rj中必存在元組uj滿足tRj=uj

23、 (1jk),即 。 于是對那個特定的i，亦有tRi=ui，即tRiri。但tRi=ti，所以tiri，從而得到 （即 ）。 由 和 可得 （即 ）。, 由定理6-5可知 (i=1,2,k)，于是有 。 此式左式m(s)= mm(r)（由得），右式 m(r)， 因此得：mm(r) =m(r) 該定理說明，關系模式只有在第一次分解的連接恢復后有可能丟失信息，此后的多次分解恢復均能使分解不失真,證明： 設任意一個元組tr,ti=tUi(i=1,2,k);則tiRi。根據(jù)自然連接定義，可知t在 中，即tm(r)，所以 。 該定理說明，一個關系模式經分解再連接恢復所得的新關系m(r)的元組一般比原關系

24、的元組要多，而且m(r)一定包括原關系的元組。 只有當r= m(r)時，分解才是連接不失真分解。,2）無損連接的檢驗,方法1：采用檢驗表格構造法 算法6.2：連接不失真檢驗,方法1： (1)構造一個n列k行表，每一行對應于一個模式Ri（1ik），每一列對應于一個屬性Aj（1jn），如下表所示。,(2) 初始表（填表）：若AjRi，則第i行第j列上填入aj，否則填入bij。 (3) 修改表：反復檢查F中的每一個函數(shù)依賴XY，按下方法修改表格中的元素：取F中的函數(shù)依賴XY，檢查Y中的屬性所對應的列，找出X相等的那些行，將這些X的符號相同的行中的Y的屬性所對應的符號改成一致。即如果其中有aj，則將b

25、ij改為aj；若無aj，則將它們全改為bij。一般取i是為其中的最小行號值。 (4) 如發(fā)現(xiàn)某一行變成a1，a2，,ak，則此分解具有連接不失真性。,事例說明,例：設有R(U,F)，其中：U =(A,B,C,D,E), F=(AC,BC,CD,DEC,CEA)，R的一個分解為： R1(AD)，R2 (AB)，R3(BE) ，R4(CDE) ，R5(AE)是否無損分解？,根據(jù)算法6.2中(1)和(2)構造初始表，如表(a)所示。 根據(jù)AC，對表(a)進行處理，將b13、b23、b53改成同一符號b13，即b13b23b53。再根據(jù)BC，將b33、b13（R2中）改成同一符號b13。修改后如表(b

26、)所示。 考慮CD，根據(jù)上述修改原則，將D所在的第4列的b24、b34、b54均修改成a4，其結果如表（c）所示。(因為AC,BC) 再考慮DEC，根據(jù)修改原則，將C所在的第3列第3、4、5行的b13、a3、b13均修改成a3，其結果如表（d）所示。(因為BC, AC, CD) 再考慮CEA，根據(jù)修改原則，將A所在的第1列第3、4、5行的b31（由BC推出）、b41（由AC推出）、a1均修改成a1，其結果如表（e）所示。,簡單的檢驗方法,方法2： 定理6.5：設= R1,R2是關系模式R的一個分解，F(xiàn)是R的一個函數(shù)依賴集，則對于F, 具有連接不失真性的充分必要條件是R1R2R1R2 F+，或R

27、1R2R2R1F+。,例6.8：設有關系模式R(S,SN,C,G，SSN,(S,C)G)的一個分解為： =R1(S,SN,SSN)，R2(S,C,G,(S,C)G) 因為R1R2=S#，R1R2=SN，故R1R2R1R2，且S#SN屬于F，所以該分解具有連接不失真性。,定理6-8和例6-9告訴我們一個事實：如果兩個關系模式間的公共屬性集至少包含其中一個關系模式的關鍵字，則此分解必定具有連接不失真性。,6.4.3 函數(shù)依賴保持性,定義6.13：設有關系模式R,F是R上的函數(shù)依賴集，Z是R上的一個屬性集合，則稱Z所涉及到的F+中的所有函數(shù)依賴為F在Z上的投影，記為z(F)。,該定義實質上是，當XY

28、F+時，若XYZ，則有z(F)， 可以定義為：,定義6-17：設關系模式R的一個分解為=R1,F1，R2,F2，Rk,Fk,F是R上的依賴集，如果對于所有的i=1,2, ,k，z(F)中的全部函數(shù)依賴的并集邏輯地蘊涵F中的全部依賴，則稱分解具有依賴保持性。,判斷兩個函數(shù)依賴集是否等價的方法也可以用來判斷一個分解是否保持依賴。 下面以一個例子來說明一下。 ：設R(A,B,C,D)，F(xiàn)AB,CD，=R1(A,B，AB)，R2（C,D，CD）。 因為FAB,CD，F(xiàn)1F2AB,CD 所以 F+ = (F1F2)+,該例還說明，一個具有依賴保持性的分解不一定具有連接不失真性。反之，一個連接不失真分解也

29、不一定具有依賴保持性。,例：設R(A,B,C)，F(xiàn)AB，CB，=R1(A,B，AB)，R2（A,C，AC）。 R1R2=A, R1R2=B，R2R1=C R1R2R1R2= ABF 但FAB,CB，F(xiàn)1F2AB,AC,即F+ (F1F2)+ 可見具有連接不失真性，但不具有依賴保持性。,范式的概念是由E. F. Codd在1970年首先提出來的。 滿足特定要求的模式稱之為范式。 所謂模式規(guī)范化，就是對關系模式應當滿足的條件的某種處理，其目的是： (1)消除異常現(xiàn)象。 (2)方便用戶使用，簡化檢索操作。 (3)加強數(shù)據(jù)獨立性。 (4)使關系模式更靈活，更容易使用非過程化的高級查詢語言。 (5)更容

30、易進行各種查詢統(tǒng)計工作。 關系規(guī)范化的條件可以分成幾級，每一級稱為一個范式，記為XNF，其中X表示級別,NF是范式(Normal Form)，即關系模式滿足的條件。 范式的級別越高，條件越嚴格，因此有：,6.5 關系模式的規(guī)范化6.5.1 范式,1）第一范式（1NF）,定義6.14（1NF）：如果一個關系模式R的每個屬性的域都只包含單純值，而不是一些值的集合或元組，則稱R是第一范式，記為R1NF, 把一個非規(guī)范化關系模式變?yōu)?NF有兩種方法，一是把不含單純值的屬性分解為多個屬性，并使它們僅含單純值。,例如，設模式： P (PNO，PNAME，QOH,PJ(PJNO,PJNAME，PJMNO，P

31、QC） 將模式P變?yōu)椋?P(PNO,PNAME,QOH,PJNO,PJNAME,PJMNO,PQC） 第二種方法是把關系模式分解，并使每個關系都符合1NF。則： Pl (PNO,PNAME,QOH) PJl (PNO,PJNO,PJNAME,PJMNO,PQC),關系PJl存在異?，F(xiàn)象，例如，當一個新工程剛提出，僅有工程名，沒有工程號，也沒有使用零部件，此時工程數(shù)據(jù)就不能寫入數(shù)據(jù)庫。原因是存在部分函數(shù)依賴：,2）第二范式（2NF）,定義6.15（2NF）：如果關系模式R1NF，且它的任一非主屬性都完全函數(shù)依賴于任一候選關鍵字，則稱R滿足第二范式，記為R2NF。 把一個1NF的關系模式變?yōu)?NF

32、的方法是，通過模式分解，使任一非主屬性都完全函數(shù)依賴于它的任一候選關鍵字。,例如對上例，若把PJ1進一步分解成： PJ2 (PNO,PJNO,PQC) J(PJNO,PJNAME,PJMNO),3）第三范式（3NF）,定義6.16（3NF）：如果關系模式R2NF,且每一個非主屬性不傳遞依賴于任一候選關鍵字，則稱R3NF。,例如把關系模式S分解成： ST (SNO，NAME，DNAME） DEPT(DNAME，DADDR),考察關系模式S (SNO，SNAME，DNAME，DADDR),SNO為候選關鍵字。但若假定一個系的學生的所在系地址相同，即一個系的學生的DADDR值一樣。顯然，SNODNA

33、ME,DNAMEDADDR，故SNODADDR,該關系模式在DADDR列存在高度數(shù)據(jù)冗余。 這是由于原關系模式中存在傳遞函數(shù)依賴。因此，要消除數(shù)據(jù)冗余這種異?，F(xiàn)象，必須使關系模式中不出現(xiàn)傳遞函數(shù)依賴。,3NF定義告訴我們，一個關系模式滿足3NF的充分必要條件是，它的每個非主屬性既不部分依賴也不傳遞依賴于候選關鍵字。,4）Boyce-Codd范式（BCNF),例如，模式S (NAME,SEX,BIRTH,ADDR,DNAME)的主屬性為：NAME,SEX,BIRTH和ADDR，候選關鍵字為：(NAME,SEX)、(NAME,BIRTH)以及(NAME，ADDR)。定義中的A為(ADDR,DNAM

34、E)。顯然有：,定義6.17（BCNF）：設有關系模式R及其函數(shù)依賴集F,X和A是R的屬性集合，且AX。如果只要R滿足XA，X就必包含R的一個候選關鍵字，則稱R滿足BCNF，記為RBCNF。 該定義主要有三點： (1)所有非主屬性A對鍵都是完全函數(shù)依賴的(R2NF)。 (2)沒有屬性完全函數(shù)依賴于非鍵的任何屬性組(R3NF)。 (3)所有主屬性對不包含它的鍵是完全函數(shù)依賴的（新增加條件）。,事例,解由語義可得到如下的函數(shù)依賴： （SNO，CNO）TNO，（SNO，TNO）CNO，TNOCNO 這里（SNO，CNO），（SNO，TNO）都是侯選關鍵字。 因為沒有任何非主屬性對侯選關鍵字部分依賴，

35、所以STC2NF。 沒有任何非主屬性對侯選關鍵字傳遞依賴，所以STC3NF。 但在F中有TNOCNO，而TNO不包含侯選關鍵字，所以STC不是BCNF關系,例6.13：關系模式STC（SNO，TNO，CNO），SNO表示學號，TNO表示教師編號，CNO表示課程號。每一個教師只教一門課，每門課有若干教師，某一個學生選定某門課，就對應一個固定教師。試判斷ST的最高范式。,這里我們可以將STC（SNO，TNO，CNO）分解成ST（SNO，TNO）和TC（TNO，CNO），它們都是BCNF。,范式之間的關系,1NF,3NF,BCNF,2NF,6.5.2 模式分解的算法,按照上面討論的模式分解理論，一個

36、模式分解必須滿足： 連接不失真性； 依賴保持性 某一級范式。 但事實上不能順利地同時滿足上述三個條件。一般而言： (1)若要求連接不失真，分解可達到BCNF； (2)若要求依賴保持，則分解可達到3NF，但不一定能達到BCNF。 (3)若同時要求連接不失真和依賴保持，則分解可達到3NF，但不一定能達到BCNF。,1）結果為BCNF的連接不失真分解,定理6.6：分解定理 (1) 設F是關系模式R的函數(shù)依賴集，=R1，R2，,Rk是R的一個分解，且對于F有連接不失真性。設Fi為F在Ri上的投影，即： 如果X和Y均為Ri的子集，則XYF+。又設1=S1,S2,Sm為Ri的一個分解，且對于Fi具有連接不

37、失真性。如果將R分解為 R1，R2，,Ri1,S1,S2,Sm，Ri+1，Rk 則這一分解相對于F的一個連接不失真性分解。 (2) 設2=R1，R2，,Rk,Rk+1，Rn為R的一個分解，其中包含了的那些關系模式,則2相對于F的一個連接不失真性分解。,結果為BCNF的連接不失真分解算法,輸入：R(U，F(xiàn)) 輸出：分解=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)，且，滿足BCNF。 方法：反復應用定理610（分解定理），逐步分解關系模式R，使每次分解具有連接不失真性，并且分解出來的模式是BCNF。 置初值=R； 如果中所有關系模式都是BCNF，則轉； 如果中有一個關系模式S不是B

38、CNF，則S中必能找到一個函數(shù)依賴XA有X不是S的鍵，且AX，設S1XA，S2SA，用分解S1，S2代替S，則轉； 分解結束，輸出。,事例,例6.14：設有關系模式CTHRSG(C,T,H,R,S,G)及其函數(shù)依賴集F= CSG, CT,HRC , HSR, THR。 (1) 求所有候選關鍵字 如果直接根據(jù)候選關鍵字的定義來求一個關系模式的所有關鍵字： 若屬性A僅出現(xiàn)在所有函數(shù)依賴的右部，則它一定不包含在任何候選關鍵字中； 若屬性A僅出現(xiàn)在所有函數(shù)依賴的左部，則它一定包含在某個候選關鍵字中； 若屬性A既出現(xiàn)在函數(shù)依賴的右部，又出現(xiàn)在左部，則它可能包含在候選關鍵字中； 在上述基礎上求屬性集閉包。

39、 對本例,G僅出現(xiàn)在函數(shù)依賴的右部，則它不包含在候選關鍵字中；又屬性H和S僅出現(xiàn)在函數(shù)依賴的左部，則H和S必包含在候選關鍵字中。計算(HS)+為： (HS)(0) =HS (HS)(1) =HSR (HS)(2) =HSRC (HS)(3) = CTHRSG (HS)(4) = CTHRSG 即(HS)+=CTHRSG，故HS是模式CTHRSG的唯一關鍵字。,(2) 分解,首先在F中找出這樣一個函數(shù)依賴XA，其中X不包含R的任何候選關鍵字，也不包含A。把R分解成R1(X,A)和R2(S-A)。 對本例首先考慮CSG，則CTHRSGCSG,CTHRS。 為進一步分解，需求F+在CSG和CTHRS

40、上的投影： CSG(F)=CSG；CTHRS(F)=CT,THR,HRC,HSRF1 很顯然，模式CSG是BCNF。模式CTHRS不是BCNF，還要繼續(xù)分解。 (2-1)求得CTHRS的候選關鍵字為HS。 (2-2)再分解CTHRS，選CT，將CTHRS分解為 CTHRSCT,CHRS。 函數(shù)依賴集CT上投影的最小覆蓋是CT，在CHRS上的投影的最小覆蓋是CHR，HSR，HRC。記作： CT(F1)=CT；CHRS(F1)=CHR，HSR，HRCF2 顯然,模式CT為BCNF，但模式CHRS不是BCNF，還要繼續(xù)分解。 (2-3) 求得CHRS的唯一關鍵字為HS。 (2-4) 再分解CHRS，

41、選CHR，將CHRS分解為 CHRSCHR，CHS。 F2在CHR、CHS上投影的最小覆蓋為： CHR(F2)=CHR，HRC；CHS(F2)=HSC 在模式CHR中，HC、HR為鍵，其所有決定因素都是鍵，在模式CHS中，HS為鍵，顯然CHR、CHS都為BCNF。,分解樹,2）結果為3NF的依賴保持分解,算法6-4：結果為3NF的依賴保持分解算法 輸入：關系模式R和函數(shù)依賴集F 輸出：結果為3NF的一個依賴保持分解 步驟： (1)如果R中有某些屬性與F的最小覆蓋F 中的每個依賴的左邊和右邊都無關，原則上可由這些屬性構成一個關系模式，并從R中將它們消除； (2)如果F中有一個依賴涉及到R的所有屬

42、性，則輸出R; (3)否則，輸出一個分解,它由模式XA組成，其中XAF。但當XAl，XA2，XAn均屬于F時，則用模式XAlA2An代替XAi(i=1,2，,n)。 例6-15：對于上例， F=CT,CSG,HTR,HRC,CHR,HSR,KEYHS 所以 = CT,CSG,HRT,CHR,HSR,定理6-11：設是由結果為3NF的依賴保持分解算法得到的3NF分解，X為R的一個候選關鍵字，則X是R的一個分解，且中的所有關系模式均滿足3NF,同時，既具有連接不失真性，又具有依賴保持性。,3）結果為3NF且具有依賴保持和連接不失真的分解,例：已知R(C,T,H,R,S,G), F=CT,HRC,CSG,HSR,HTR，KEY=HS， 則 = CT,CSG,HRT,CHR,HSR,HS 但HS HSR，故 =CT，CSG，HRT，CHR，HSR,6.6 多值函數(shù)依賴與4NF,6.6.1 BCNF關系模式存在的問題(CTB是關鍵字),6.6.2 多值函數(shù)依賴,為了形式地定義多值依賴，根據(jù)上例，構造一個抽象關系R(U)（如下表），并設X,Y是U的子集，其余屬性為Z=UXY。又設s、t、u、v是該關系中的任意元組。,定義6-23：設有R(U),X,Y是U的子集，Z=UXY。多值依賴XY成立，當且僅當對