數據庫課件第6章關系數據理論.ppt

1、4.關系模式的規(guī)范化,2.范式的定義和分類,3.關系模式所屬范式類型的判別,本次課內容,1.關系模式中的函數依賴,例：學校數據庫的語義： 一個系有若干學生， 一個學生只屬于一個系，學號唯一，姓名可能重名； 一個系只有一名系主任，系名不重復，系主任可能重名； 一個學生可以選修多門課程， 每門課程有若干學生選修； 每個學生所學的每門課程都有一個成績，課程號唯一，課程名不排除相同情況。,根據語義，有如下函數依賴：,學生(學號, 姓名, 系名, 系主任, 課程號,課程名, 分數),假設某個人根據上述語義設計了如下關系模式:,學號姓名,學號系名,系名系主任, (學號,課程號) 分數,課程號課程名,學生(

2、學號, 姓名, 系名, 系主任, 課程號,課程名, 分數),關系模式R(U)， U 是R的屬性集合，X、Y、Z是U的子集，X是X的任意真子集。 1.完全函數依賴：X Y， X Y，則 X Y。,關系模式R(U)， U 是R的屬性集合，X、Y、Z是U的子集，X是X的任意真子集。 2.部分函數依賴： X Y，存在一個 X Y， X P Y 。,關系模式R(U)， U 是R的屬性集合，X、Y、Z是U的子集，X是X的任意真子集。 3.傳遞函數依賴： XY，YZ，且Y X，Y X，則XZ ,稱Z傳遞函數依賴于X。,1.范式,范式(Normal Form, NF)：關系模式的規(guī)范形式。是符合某一種級別的關

3、系模式的集合。,規(guī)范化目的：逐漸消除異常,減少冗余。,規(guī)范化方法：一般采用分解的辦法，將低級別范式向高級別范式轉化，使關系的語義單純化。,規(guī)范化：將一個給定的關系模式轉化為某種級別范式的過程稱為關系模式的規(guī)范化過程，簡稱規(guī)范化。,2.規(guī)范化,定義：如果一個關系模式R的所有屬性都是不可分的基本數據項，則稱該關系模式為第一范式關系模式，記作R1NF。,(1)第一范式（1NF）,以函數依賴為基礎的范式種類：第一范式、第二范式、第三范式和BCNF范式。,3.以函數依賴為基礎的范式,非第一范式的關系轉換為1NF關系：將復合屬性變?yōu)楹唵螌傩约纯伞?學 生,學生(學號, 姓名, 系名, 系主任, 課程號,課

4、程名, 分數),a.插入情況:若要插入一個沒選課的學生,能插入嗎?,X,結論:存在插入異常,b.刪除情況:,如某學生只選了一門課，如果要刪除學生的該門選課，則會出現什么后果?,結論:存在刪除異常,c.冗余情況:,結論:冗余度大,d.更新情況：如果某學生要轉系,要修改那些數據?,可見：滿足1NF是不夠的，它可能出現插入、刪除和更新異常,冗余度也大。 原因:因為可能存在“部分函數依賴”與“傳遞函數依賴”。,2NF實質：不存在非主屬性“部分函數依賴”于碼的情況。,定義 若關系模式R1NF，并且每一個非主屬性都完全函數依賴于R的碼，則稱該關系模式為第二范式關系模式則記作R2NF,(2)第二范式（2NF

5、）,示例：,學生(學號, 姓名, 系, 系主任, 課程號,課程名, 分數),1NF關系向2NF的轉換：消除其中的部分函數依賴，一般是將一個關系模式分解成多個2NF的關系模式。即：將部分函數依賴于碼的非主屬性及其決定屬性移出，另成一關系，使其滿足2NF。,(1) 學生信息(學號, 姓名, 系名, 系主任),(2) 修課 (學號,課程號,分數),(3) 課程 (課程號,課程名),上述“學生”關系模式分解成如下三個關系模式:,異常情況分析：,學生,修課,課程,b.刪除情況：如某學生只選了一門課，如果要刪除學生的該門選課，則會出現什么后果?,a.插入情況:若要插入一個沒選課的學生,能插入嗎?,c.冗余

6、情況:,d.更新情況：如果某學生要轉系,要修改那些數據?,能,學生、系的信息仍可保留,減少了，但仍存在,只需修改一次 但如果要更換系主任，則要修改多條記錄,2NF判斷: 語義:一個國家可參加多項比賽,一個比賽項目有多個國家參加,關系模式如下: 比賽(國家名稱,參賽項目名稱,項目得分, 總分),2NF關系可能的異常：仍可能存在插入異常、刪除異常、更新異常和冗余。因為，還可能存在非主屬性對碼的“傳遞函數依賴”。,3NF的得來： 3NF是從1NF消除非主屬性對碼的部分函數依賴和從2NF消除非主屬性對碼的傳遞函數依賴而得到的關系模式。,定義：若關系模式R是2NF，而且它的任何一個“非主屬性”都不傳遞函

7、數依賴于R的碼，則稱該關系模式為第三范式關系模式，記作3NF。,(3)第三范式（3NF）,學生(學號, 姓名, 系名, 系主任),示例：,(1) 學生信息(學號, 姓名, 系名, 系主任),(2) 修課 (學號,課程號,分數),(3) 課程 (課程號,課程名),上述三個關系模式中，存在非主屬性對碼的傳遞函數依賴的關系模式是：,2NF關系向3NF的轉換：消除傳遞函數依賴，將2NF關系分解成多個3NF關系模式。,(1) 學號 (學號, 姓名, 系名),(2) 系 (系名, 系主任),例題分析: 1、工人(工號,姓名,工種,定額,車間,車間主任) 若有如下函數依賴:,工號姓名,工號工種,工種定額,工

8、號車間,車間車間主任,2.比賽(球隊,比賽場次,得分) 函數依賴情況: 3.假設一個帳號一天只能取一次款,那么關系模式: 取款(日期,帳號,取款金額,取款身份證號),其中的函數依賴有：,3NF異常示例： 每一教師只教一門課,每門課有若干教師,某一學生選定了某門課，就對應一個固定的教師。,(學號,課程號)教師號, (學號,教師號)課程號, 教師號課程號,STC (學號, 教師號, 課程號),STC,(學號,課程號)教師號, (學號,教師號)課程號, 教師號課程號,STC,(學號,課程號)教師號, (學號,教師號)課程號, 教師號課程號,a.插入異常分析：插入尚未選課的學生時，能否插入?或 插入沒

9、有學生選課的課程時，能否插入? 都不能,STC,(學號,課程號)教師號, (學號,教師號)課程號, 教師號課程號,b.刪除異常分析：如選修某課程的學生全畢業(yè)，刪除學生則會刪除課程的信息。,STC,(學號,課程號)教師號, (學號,教師號)課程號, 教師號課程號,c.冗余：每個選修某課程的學生均帶有教師的信息，故冗余。,STC,(學號,課程號)教師號, (學號,教師號)課程號, 教師號課程號,d.更新異常：如教師所教的課程變更了,則修改某門課程對應的教師信息，則要修改多行。,可見：3NF關系可能的異常仍可能存在插入異常、刪除異常、更新異常和冗余。因為，還可能存在“主屬性”“部分函數依賴”于碼。,

10、定義：若關系模式R是1NF，如果對于R的每個函數依賴XY，X必為候選碼，則R為BCNF范式（Boyce-Codd Normal Form, BCNF）。,每個BCNF范式具有的三個性質： a. 所有非主屬性都完全函數依賴于每個候選碼； b. 所有主屬性都完全函數依賴于每個不包含它的候選 碼； c. 沒有任何屬性完全函數依賴于非碼的任何一組屬性。,提出：由Boyce和Codd提出，故稱BCNF范式。亦被認為是增強的第三范式，有時也歸入第三范式。,(4)BCNF范式,說明：,由于BCNF的每一個非平凡函數依賴的決定因素必為候選碼，故不會出現3NF中決定因素可能不是候選碼的情況。 3NF不一定是BC

11、NF，而BCNF一定是3NF。 不過，屬于3NF而非BCNF的關系模式不多，即使有，對數據庫設計者來說，所引起的更新異常也不太重要。,3NF和BCNF常常都是數據庫設計者所追求的關系范式。有些文獻有時統(tǒng)稱它們?yōu)榈谌妒?，只要不引起誤解。 如果一個關系數據庫的所有關系模式都屬于BCNF，那么，在函數依賴范疇內，它已達到了最高的規(guī)范化程度(但不是最完美的范式)，在一定程度上已消除了插入和刪除的異常。,3NF關系向BCNF的轉換：消除那些決定因素不是候選碼的函數依賴，即可將3NF關系分解成多個BCNF關系模式。,ST (學號,教師號),示例：,TC (教師號,課程號),關系模式STC (學號, 教師

12、號, 課程號) 可分解為下列兩個關系模式：,范式級別與異常問題之關系：一般，級別越低，出現異 地常的程度越高, 范式不一定越高就越好,設計中一般達到3NF或BCNF即可。,范式之間存在的關系：,關系模式中的范式：1NF、2NF、3NF、BCNF、4NF和5NF。,6.2.7 多值依賴與第四范式（4NF）,例: 學校中某一門課程由多個教師講授，他們使用相同的一套參考書。每個教師可講授多門課,每種參考書可以供多門課使用。 關系模式Teaching(課程,教師,參考書),表6.3,用二維表表示Teaching,TeachingBCNF: Teaching具有唯一候選碼(課程,教師,參考書)， 即全碼

13、 Teaching模式中存在的問題 (1)數據冗余度大：有多少名任課教師，參考書就要存儲多少次,Teaching,(2)插入操作復雜：當某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組 例如物理課增加一名教師劉關，需要插入三個元組： （物理，劉關，普通物理學） （物理，劉關，光學原理） （物理，劉關，物理習題集）,Teaching,t,s,v,w,(3) 刪除操作復雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組 (4) 修改操作復雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組 產生原因 存在多值依賴,一、多值依賴,定義5.1

14、0 設R(U)是一個屬性集U上的一個關系模式， X、 Y和Z是U的子集，并且ZUXY，多值依賴 XY成立當且僅當對R的任一關系r，r在（X，Z）上的每個值對應一組Y的值，這組值僅僅決定于X值而與Z值無關 例 Teaching（課程,教師,參考書） 對于課程(X)和參考書(Z)的每一個值，教師(Y)有一組值與之對應，這組值與參考書(Z)無關，只與課程(X)有關,在R（U）的任一關系r中，如果存在元組t，s 使得tX=sX，那么就必然存在元組 w，v r，（w，v可以與s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交換s，t元組的Y值所得的兩個新元組必在r

15、中），則Y多值依賴于X，記為XY。 這里，X，Y是U的子集，Z=U-X-Y。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2,平凡多值依賴和非平凡的多值依賴 若XY，而Z，則稱 XY為平凡的多值依賴 否則稱XY為非平凡的多值依賴,多值依賴的性質,（1）多值依賴具有對稱性 若XY，則XZ，其中ZUXY 多值依賴的對稱性可以用完全二分圖直觀地表示出來。 （2）多值依賴具有傳遞性 若XY，YZ， 則XZ -Y,多值依賴的對稱性,多值依賴的對稱性,（3）函數依賴是多值依賴的特殊情況。 若XY，則XY。 （4）若XY，XZ，則XY Z(或表示為YZ)。 （5）若XY，XZ

16、，則XYZ。 （6）若XY，XZ，則XY-Z，XZ -Y。,多值依賴與函數依賴的區(qū)別,(1) 有效性 多值依賴的有效性與屬性集的范圍有關 若XY在U上成立，則在W（X Y W U）上一定成立；反之則不然，即XY在W（W U）上成立，在U上并不一定成立 多值依賴的定義中不僅涉及屬性組 X和 Y，而且涉及U中其余屬性Z。 一般地，在R（U）上若有XY在W（W U）上成立，則稱XY為R（U）的嵌入型多值依賴,只要在R（U）的任何一個關系r中，元組在X和Y上的值滿足函數依賴定義， 則函數依賴XY在任何屬性集W（X Y W U）上成立。,(2) 若函數依賴XY在R（U）上成立，則對于任何Y Y均有XY

17、成立 多值依賴XY若在R(U)上成立，不能斷言對于任何Y Y有XY 成立,二、第四范式（4NF）,定義5.10 關系模式R1NF，如果對于R的每個非平凡多值依賴XY（Y X），X都含有候選碼，則R4NF。 （XY） 如果R 4NF， 則R BCNF 不允許有非平凡且非函數依賴的多值依賴 允許的是函數依賴（是非平凡多值依賴）,例：關系模式:Teaching(課程,教師,參考書) 4NF 存在非平凡的多值依賴課程教師，且課程不是候選碼 用投影分解法把Teaching分解為如下兩個關系模式： CT(課程,教師) 4NF CB(課程,參考書) 4NF 課程教師，課程參考書 是平凡多值依賴,三、關系模式

18、的規(guī)范化 1.規(guī)范化步驟,規(guī)范化的實質：概念的單一化。即：一個關系只描述一個概念、一個實體或實體間的一種聯系，若多于一個概念就應將其它概念分離出去。,規(guī)范化基本步驟：,問題提出：在關系模式的規(guī)范化處理過程中，不僅要知道一個給定的函數依賴集合，還要知道由給定的函數依賴集合所蘊涵（或推導出）的所有函數依賴的集合。為此，需要一個有效而完備的公理系統(tǒng)，Armstrong公理系統(tǒng)即是這樣的一個系統(tǒng)。,2.Armstrong公理系統(tǒng),蘊含定義：設F是R上的函數依賴集合， XY是R的一個函數依賴 。如果R的任何一個關系實例r, XY都成立，則稱F邏輯蘊含(Imply) XY。,Armstrong公理：為從已

19、知的函數依賴推導出其他的函數依賴，Armstrong提出了一套推理規(guī)則，稱為Armstrong公理(Armstrongs Axioms)。,(2) 增廣律(Augmentation) ：若XY，ZU，則XZYZ。,(1) 自反律(Reflexivity) ：若YXU，則XY。,(3) 傳遞律(Transitivity) ：若XY和YZ，則XZ。,定理.6.1：Armstrong公理是正確的，即：如F成立，則由F根據Armstrong公理所推導的函數依賴總是成立的。,公理包含如下三條推理規(guī)則：,根據上述三條推理規(guī)則可以得到下面有用的三條推理規(guī)則：,(2) 偽傳遞規(guī)則(Pseudo Transit

20、ivity)：如果XY，YWZ，則XWZ。,(1) 合并規(guī)則(Union)：如果XY，XZ，則XYZ。,(3) 分解規(guī)則(Decomposition)：如果XY，ZY，則XZ。 或：如XYZ，則XY，XZ。,根據合并規(guī)則和分解規(guī)則，可得如下： 引理6.1: XA1 A2Ak成立的充分必要條件是XAi成立(i=l,2,k)。 定義6.12:函數依賴集F的閉包：在關系模式R中為F所邏輯蘊含的函數依賴的全體叫作F的閉包，記為F+。 定義6.13: 屬性集X關于函數依賴集F的閉包：設F為屬性集U上的一組函數依賴，X U，XF+ = A|XA能由F根據Armstrong公理導出，XF+稱為屬性集X關于函

21、數依賴集F 的閉包。 引理6.2：設F為屬性集U上的一組函數依賴，X，Y U，XY能由F 根據Armstrong公理導出的充分必要條件是Y XF+。,閉包的用途：將判定XY是否能由F根據Armstrong公理導出的問題，就轉化為求出XF+ ，判定Y是否為XF+的子集的問題。 Armstrong公理系統(tǒng)的有效性與完備性 有效性(正確性)：由F出發(fā)根據Armstrong公理推導出的每個函數依賴一定在F+中。 完備性：F+中的每一個函數依賴，必定可以由F出發(fā)根據Armstrong公理推導出來。,求屬性集X(XU)關于U上函數依賴集F 的閉包XF+的算法： 輸入：X，F 輸出：XF+ 令X (0) =

22、X，i=0。 求B，B = A |(V)(W)(VWFV X (i) AW)。 X (i+1) =BX (i) 。 判斷X (i+1) = X (i)嗎? 若相等或X (i) =U , 則X (i)就是XF+ , 算法終止；否則i=i+1，返回第2步。,例1已知關系模式R，其中U=A,B,C,D,E，F=ABC,BD,CE,ECB,ACB，求(AB)F+。 設X (0) =AB ； 計算X (1) : 逐一的掃描F集合中各個函數依賴，找左部為A、B或AB的函數依賴，有ABC，BD， 于是X (1) =ABCD=ABCD。 因為X (0) X (1) ，所以再找出左部為ABCD子集的那些函數依賴

23、，又得到CE，ACB， 于是X (2) =X (1) BE=ABCDE。 因為X (2) =U，算法終止。 所以(AB)F+ =ABCDE。,根據閉包可以求關系模式的候選碼：如已知關系模式R(ABCDEG)上FD集F=DG,CA,CDE,AB， S(ABCD)上FD集F=BC, ACB，利用閉包概念可以分別求它們的候選碼。 (D)F+, (C)F+, (CD)F+, (A)F+ (B)F+, (AC)F+,函數依賴集的等價 定義：若G+=F+，則函數依賴集F覆蓋G(F是G的覆蓋或G是F的覆蓋)，或F與G等價。 充要條件：F+ =G+ 的充分必要條件是F G+ 和G F+。 證: 必要性顯然，只

24、證充分性。 若FG+ ，則XF+ XG+ 。 任取XYF+ ， 則有YXF+ XG+ ， 所以XY(G+)+= G+。即F+ G+。 同理可證G+ F+ ，所以F+ =G+。 判斷方法：要判定F G+，只須逐一對F中的函數依賴XY，考察Y是否屬于XG+就行了。,最小依賴集：如果函數依賴集F滿足下列條件，則稱F為一個極小函數依賴集，亦稱為最小依賴集或最小覆蓋。 F中任一函數依賴的右部僅含有一個屬性。 F中不存在這樣的函數依賴XA，使得F與FXA等價。 F中不存在這樣的函數依賴XA，X有真子集Z使得FXAZA與F等價。,例:設關系模式S中，U= Sno,Sdept,Mname,Cno,Grade

25、， 設F=SnoSdept,SdeptMname，(Sno,Cno)Grade ， F=SnoSdept,SnoMname,SdeptMname, (Sno,Cno)Grade ，(Sno,Sdept)Sdept，則F是最小覆蓋，而F 不是。 因為： FSnoMname與F等價； F(Sno, Sdept)Sdept也與F等價； F(Sno, Sdept)SdeptSnoSdept也與F等價 。,求F最小依賴集Fm的過程 使每一函數依賴右邊單屬性化：逐一檢查F中各函數依賴FDi：XY，若Y=A1A2Ak，則以 XAj |j=1,2,k 取代XY。 去掉多余的函數依賴：逐一檢查F中各函數依賴FD

26、i：XA，令G=FXA，若AXG+，則從F中去掉此函數依賴。因F與G =FXA等價的充要條件是AXG+，故F變換前后等價。 去掉每一函數依賴左邊多余的屬性：逐一取出F中各函數依賴FDi：XA，設X=B1B2Bm，逐一考查Bi (i=l,2,m)，若A (X-Bi )F+ ，則以X-Bi 取代X。 由于F與FXAZA等價的充要條件是AZF+，其中Z=X Bi ，故F變換前后等價。 最后剩下的F就是最小依賴集Fm 。,例:F=AB,BA,BC,AC,CA，則Fm1、Fm2都是F的最小依賴集： Fm1=AB,BC,CA Fm2=AB,BA,AC,CA F的最小依賴集Fm不一定是唯一的，它與對各函數依

27、賴FDi及XA中X各屬性的處理順序有關。,例：學生(學號, 姓名, 系名, 系主任, 課程號,課程名, 分數),F=學號姓名,課程號課程名,系名系主任, 學號系主任，學號系名, (學號,課程號) 分數,1、使每一函數依賴右邊單屬性化： 逐一檢查F中各函數依賴FDi：XY，若Y=A1A2Ak，則以 XAj |j=1,2,k 取代XY。 2、去掉多余的函數依賴： 去掉：學號姓名 G1=課程號課程名,系名系主任,學號系主任 學號系名, (學號,課程號) 分數， 求（學號）G1+ ，檢查“姓名”是否屬于該閉包。如果是則去掉該函數依賴。同理檢查其他四個函數依賴。,去掉：課程號課程名 G2=學號姓名，系名

28、系主任,學號系主任 學號系名, (學號,課程號) 分數 去掉：系名系主任 G3=學號姓名，課程號課程名， 學號系名, 學號系主任,(學號,課程號) 分數 去掉：學號系主任 G4=學號姓名，課程號課程名，學號系名， 系名系主任, (學號,課程號) 分數 因學號在G4上的閉包包含系主任， 所以函數依賴學號系主任可以去掉。 去掉：學號系名 G5=學號姓名，課程號課程名，系名系主任, (學號,課程號) 分數,去掉： (學號,課程號) 分數 G6=學號姓名，課程號課程名，系名系主任, 學號系名。 G7=學號姓名，課程號課程名，系名系主任, 學號系名， (學號,課程號) 分數 3、去掉每一函數依賴左邊多余

29、的屬性 (學號,課程號) 分數，分別檢查“學號”、“課程號”在G7上的閉包是否包含“分數”，由于不包含，所以 G7為最小函數依賴集,6.4 模式的分解 把低一級的關系模式分解為若干個高一級的關系模式的方法并不是唯一的 只有能夠保證分解后的關系模式與原關系模式等價，分解方法才有意義 1.分解具有無損連接性 2.分解要保持函數依賴 3.分解既要保持函數依賴，又要具有無損連接性,定義: 關系模式R的一個分解： = R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi 為 F在 Ui 上的投影 定義: 函數依賴集合XY | XY F+XY Ui 的一個覆蓋 Fi 叫作 F 在屬性 Ui 上的

30、投影,示例：關系模式SDL(Sno,Sdept,Mname) F=Sno Sdept, Sdept Mname 對關系模式SDL(Sno,Sdept,Mname)分解 第一種分解：R1(Sno), R2(Sdept), R3(Mname) 第二種分解：R1(Sno,Sdept), R2(Sno，Mname) 第三種分解：R1(Sno,Sdept), R2(Sdept, Mname),關系模式R的一個分解 = R1，R2， ，Rn 若R與R1、R2、Rn自然連接的結果相等，則稱關系 模式R的這個分解具有無損連接性（Lossless join） 具有無損連接性的分解保證不丟失信息 無損連接性不一定

31、能解決插入異常、刪除異常、修改復雜、數據冗余等問題 算法 6.2 判別一個分解的無損連接性 P189,例設有關系模式Student(U,F)，其中U=Sno,Sdept,Sloc,Cno,Grade，F=SnoSdept, SdeptSloc,(Sno,Cno)Grade，顯然Student1NF，它存在冗余度大、插入異常、刪除異常、更新異常問題。 根據給定的函數依賴集F，求出其最小集為F=F。 采用投影方法，將關系模式Student分解為三個關系模式： SCG(U1,F1)、SD(U2,F2)、DL(U3,F3)，其中： U1=Sno,Cno,Grade, F1=(Sno,Cno)Grade

32、, U2=Sno,Sdept , F2=SnoSdept, U3=Sdept,Sloc, F3=SdeptSloc 考察該分解是否具有無損連接性：具有。,定義6.19 保持函數依賴 P190 示例1：對關系模式SDL(Sno,Sdept,Sloc)保持函數依賴的分解 示例2：對關系模式R(A,B,C,D)，F=ABC,CA,CD，=ACD,BC，判斷分解是否保持函數依賴。(否?) 示例3：對關系模式R(ABCD)，F=ABC,CAD，=ABC,AD，判斷分解是否保持函數依賴。(是?),模式分解的算法 關于模式分解的幾個重要事實 若要求分解保持函數依賴，則模式分離總可以達到3NF，但不一定能達到

33、BCNF。 若要求分解既保持函數依賴，又具有無損連接性，則模式分離總可以達到3NF，但不一定能達到BCNF。 若要求分解具有無損連接性，則模式一定可達到4NF。 如果一個分解具有無損連接性，則它能夠保證不丟失信息。 如果一個分解保持函數依賴，則分解前后兩個模式的函數依賴集的閉包是等價的。 分解具有無損連接性和分解保持函數依賴是兩個互相獨立的標準。具有無損連接性的分解不一定能夠保持函數依賴。同樣，保持函數依賴的分解也不一定具有無損連接性。,算法6.3(合成法): R轉換為3NF的保持函數依賴的分解。P191 求F的最小集F。 若F中有一函數依賴XA，且XA=U，則輸出=R。 若R中某些屬性與F中

34、所有函數依賴的左右部均無關，則將它們構成關系模式，并從R中將它們分離出去。 對于F中的每一個XiAi,都構成一個關系模式Ri=XiAi。 分解結束，輸出。 例設有關系模式Student，其中： U=Sno,Sdept,Sloc,Cno,Grade， F= SnoSdept, SdeptSloc,(Sno,Cno)Grade， 則Student保持函數依賴的一個分解為： =SCG(Sno,Cno,Grade) ,SD(Sno,Sdept), DL(Sdept,Sloc),算法6.4 : R轉換為3NF既有無損連接又保持函數依賴的分解。 例設有關系模式Student，其中： U=Sno,Sdept,Sloc,Cno,Grade， F=SnoSdept, SdeptSloc,(Sno,Cno)Grade， 則Student保持函數依賴的一個分解為： =SCG(Sno,Cno,Grade) ,SD(Sno,Sdept), DL(Sdept,Sloc) 它具有無損連接性。,算法6.5 :R轉換為BCNF的無損連接分解。 1.令=R。 2.若中所有模式都是BCNF，分解結束，輸出 。 3.若