1、1第第4章章 關系數據庫的規范化設計關系數據庫的規范化設計n關系數據庫的規范化設計是指面對一個現實問題，如何選擇一個比較好的關系模式集合。n規范化設計理論涉及的內容包括：函數依賴、范式、模式的分解特性。n函數依賴研究不同屬性之間的依賴聯系；范式是一個好的關系模式應該遵循的標準；模式的分解特性是指對關系模式進行分解以符合某種范式時，在分解過程中應保持的特性。（不是定義）n規范化設計理論對關系數據庫結構的設計起到重要的作用。2第第4章章 關系數據庫的規范化設計關系數據庫的規范化設計 4.1 關系模式的問題 4.2 函數依賴 4.3 關系模式的分解特性 4.4 關系模式的范式 小結34.1 關系模式

2、的問題關系模式的問題n關系模式：對關系（表）的描述，由關系名關系名+屬性集屬性集（表名表名+表頭表頭）組成。n關系模式的問題：數據冗余 數據冗余數據冗余是指一個數據在多個元組中重復出現（重復存儲）。 數據冗余導致的問題是操作異常操作異常，即修改異常、插入異常、刪除異常。【例】設一個關系模式R(S#, C#, Grade, TName, TAddr)，其中的屬性分別表示學生學號，選修課程的課程號，成績，任課教師姓名，教師辦公地址。 并規定： 每個學生每學一門課只有一個成績， 每門課程只有一個任課教師， 每個教師只有一個辦公地址。 則該關系模式的主鍵為(S#, C#)。44.1 關系模式的問題（續

3、關系模式的問題（續1）【例】關系模式R(S#, C#, Grade, TName, TAddr)的實例：存在的問題：n數據冗余(data redundancy)：每個教師的地址重復存儲。由于數據冗余帶來的操作異常問題：n修改異常(update anomalies)：更改某教師地址時，必須修改與該教師有關的每一個元組；否則，將造成該教師地址的異常。C-178陳 剛85C2S3D-346呂 宋70C3S2C-529金 謙90C1S2D-346呂 宋82C3S1C-178陳 剛70C2S1C-529金 謙80C1S1TAddrTNameGradeC#S#54.1 關系模式的問題（續關系模式的問題（續

4、2）由于數據冗余帶來的操作異常問題：n插入異常(insertion anomalies)：若一個教師剛調來，尚未分配教學任務，則無法將該教師姓名與辦公地址存入該關系模式中（因為主鍵為S#和C#，不能為空），導致該插的數據插不進去。n刪除異常(deletion anomalies)：若一個學生已畢業，則在刪除該學生選課信息的同時，將把任課教師的地址也刪掉，導致不該刪除的數據被刪掉。n關系模式數據冗余問題的根源n表面原因：把太多的信息放在同一個關系模式中。n實質根源（以前例進行分析）64.1 關系模式的問題（續關系模式的問題（續3）n關系模式數據冗余問題的根源n實質根源分析實質根源分析 【例】設一

5、個關系模式R(S#, C#, Grade, TName, TAddr)；并規定： 每個學生每學一門課只有一個成績； 每門課程只有一個任課教師； 每個教師只有一個辦公地址；則該關系模式的主鍵為(S#, C#)。 實質根源與這三個規定有關；但不是說這三個規定不對；而是在這三個規定之下，該關系模式R(S#, C#, Grade, TName, TAddr)是一個不好的關系模式（表現為數據異常、操作異常）。 用形式化方法（不用該模式的一個具體表）分析為什么“在這三個規定之下，該關系模式是一個不好的關系模式”？ 給出這3個規定的數學表示（函數依賴）：74.1 關系模式的問題（續關系模式的問題（續4）n關

6、系模式數據冗余問題的根源n實質根源分析實質根源分析 每個學生每學一門課只有一個成績：(S#, C#) Grade 每門課程只有一個任課教師：C# TName 每個教師只有一個辦公地址：TName TAddr 主鍵與其他屬性（稱為非主屬性）之間的函數依賴形式：(S#, C#) (Grade, TName, TAddr) 該函數依賴即說明為什么關系模式R(S#, C#, Grade, TName, TAddr)的主鍵為(S#, C#)。 實質根源與這四個函數依賴有關，采用圖示方法表示主鍵與非主屬性之間的函數依賴。84.1 關系模式的問題（續關系模式的問題（續5）n關系模式數據冗余問題的根源(S#,

7、 C#) (Grade, TName, TAddr)S#C#GradeTNameTAddrS#C#GradeTNameTAddr (S#, C#) Grade C# TName TName TAddrS#C#GradeTNameTAddr94.1 關系模式的問題（續關系模式的問題（續6）n關系模式數據冗余問題的根源n實質根源實質根源 (1) 在一個關系模式中，當存在非主屬性對主鍵的部分依賴時，就會產生數據冗余和操作異常。 (2) 在一個關系模式中，當存在非主屬性對主鍵的傳遞依賴時，就會產生數據冗余和操作異常。n關系模式數據冗余問題的解決途徑 分解是解決數據冗余的主要途徑。如前例的關系模式可分解

8、為三個關系模式R1(S#, C#, Grade)，R2(C#, TName)，R3(TName, TAddr)。 (S#, C#) Grade C# TName TName TAddrS#C#GradeTNameTAddr104.1 關系模式的問題（續關系模式的問題（續7）n關系模式數據冗余問題的解決途徑 規范化設計理論規范化設計理論就是通過分解不好的關系模式來消除某些函數依賴的影響，從而得到好的關系模式，以解決數據冗余和修改異常、插入異常、刪除異常問題。 衡量關系模式好壞的標準就是范式。n本章的符號規定n用英文字母表首部的大寫字母A, B, C, 表示單個屬性。n用英文字母表尾部的大寫字母

9、, U, V, W, X, Y, Z表示屬性集。n大寫字母 R 表示關系模式，小寫字母 r 表示其關系。n另外，關系模式R(A, B, C)簡記為R(ABC)；屬性集X和Y的并集XY簡記為XY。114.2 函數依賴函數依賴 4.2.1 函數依賴的定義 4.2.2 FD的邏輯蘊涵 4.2.3 FD的推理規則 4.2.4 FD和關鍵碼的聯系 4.2.5 屬性集的閉包 4.2.6 FD集的最小依賴集（教材4.2.7）124.2.1 函數依賴的定義函數依賴的定義n定義4.1 設有關系模式R(U)，X和Y是屬性集U的子集，函數函數依賴依賴（Functional Dependency，簡記為FD）是形為X

10、Y的一個命題，只要 r 是 R 的關系，對 r 中任意兩個元組 t 和s，都有tX=sX蘊涵tY=sY，那么稱FD XY在關系模式R(U)中成立。（“蘊涵”可理解為“必定有”）n定義的理解：定義的理解：若在關系模式R(U)上FD XY成立，則表明在關系模式R的任意一個關系 r 中，任意找兩個元組，若在屬性集X上的值相同，則在屬性集Y的值必相同。 或者說：若在關系模式R(U)上FD XY成立，則表明在關系模式R的任意一個關系 r 中，不可能存在兩個元組在屬性集X上的值相同，而在屬性集Y上的值不相同。nFD XY可讀作“X函數決定Y”或“Y函數依賴于X”。4.2 函數依賴134.2.1 函數依賴的

11、定義（續函數依賴的定義（續1）【例4.2】設有關系模式R(A, B, C, D)，并有如下所示的兩個關系： 則在關系模式R上，FD AB不成立。【例4.4】設關系模式R(ABCD)，屬性之間有這樣的聯系：A與B是一對多聯系（即每個A值有多個B值與之聯系，而每個B值只有一個A值與之聯系），C與D是一對一聯系（即每個C值只有一個D值與之聯系，每個D值也只有一個C值與之聯系）。試根據這些規則寫出相應的函數依賴。4.2 函數依賴r1d4c4b1a3d3c3b2a2d2c2b1a1d1c1b1a1DCBAr2d4c4b1a3d3c3b2a2d2c2b2a1d1c1b1a1DCBA144.2.1 函數依賴

12、的定義（續函數依賴的定義（續2）解：解：A與B是一對多聯系（如宿舍與學生），其函數依賴為BA。 C與D是一對一聯系（如座位與乘客），其函數依賴為CD和DC。4.2 函數依賴154.2.2 FD的邏輯蘊涵的邏輯蘊涵n定義4.2 設F是在關系模式R上成立的函數依賴的集合（即R的每個關系 r 均滿足F中的函數依賴），XY是一個函數依賴。若R的每個關系 r 也滿足XY，那么稱F邏輯蘊涵XY，記為F XY。 表示：表示：由關系模式R的函數依賴集F可以邏輯推導出函數依賴XY。【例】前例的關系模式R(S#, C#, Grade, TName, TAddr)，設其滿足三個函數依賴：(S#, C#)Grade，

13、C#TName，TNameTAddr，則R的函數依賴集F為 (S#, C#)Grade，C#TName，TNameTAddr 。 由F可以邏輯推導出C#TAddr，則稱F邏輯蘊涵C#TAddr，記為F C#TAddr或 (S#, C#)Grade，C#TName，TNameTAddr C#TAddr。4.2 函數依賴164.2.2 FD的邏輯蘊涵（續的邏輯蘊涵（續1）n定義4.3 設F是函數依賴集，被F邏輯蘊涵的函數依賴全體構成的集合，稱為函數依賴集F的閉包（Closure），記為F+。即 F+= XY | F XY 。 表示：表示：F+集合中包括所有由函數依賴集F邏輯推導出來的函數依賴。【例

14、】關系模式R(S#, C#, Grade, TName, TAddr)的函數依賴集F為 (S#, C#)Grade，C#TName，TNameTAddr ，由F可以推導出來的全部函數依賴組成的集合為F+。 F+= C#TAddr，(S#, C#)Grade，C#TName，TNameTAddr， 4.2 函數依賴174.2.3 FD的推理規則的推理規則nFD的基本推理規則有以下三條：nA1(自反性，Reflexivity)：若YXU，則XY在R上成立。即屬性集X必函數決定其子集Y。 【例】(S#, C#)S#，(S#, C#)C#nA2(增廣性，Augmentation)：若XY在R上成立，且

15、ZU，則XZYZ在R上成立。 【例】若C#TName成立，則(C#, Grade)(TName, Grade)成立。nA3(傳遞性，Transitivity)：若XY和YZ在R上成立，則XZ在R上成立。 【例】若C#TName，TNameTAddr成立，則C#TAddr成立。4.2 函數依賴184.2.3 FD的推理規則（續的推理規則（續1）nFD的其他五條推理規則：nA4(合并性，Union)： XY, XZ XYZnA5(分解性，Decomposition)： XY, ZY XZnA6(偽傳遞性)： XY, WYZ WXZnA7(復合性，Composition)： XY, WZ XWYZn

16、A8(通用一致性定理，General Unification Theorem)： XY, WZ X(W-Y)YZn這五條推理規則可以由A1、A2、A3三條基本規則推導出來。4.2 函數依賴194.2.3 FD的推理規則（續的推理規則（續2）nA4(合并性，Union)： XY, XZ XYZ證：證：已知XY，根據A2增廣性，兩邊分別添加X，得到XXY； 已知XZ，根據A2增廣性，兩邊分別添加Y，得到XYYZ； 根據A3傳遞性，由XXY和XYYZ可得到XYZ。nA5(分解性，Decomposition)： XY, ZY XZ證：證：已知ZY可得到YZ；由XY和YZ可得到XZ。nA6(偽傳遞性)：

17、 XY, WYZ WXZ證：證：已知XY可得到WXWY；由WXWY和WYZ可得到WXZ。4.2 函數依賴204.2.3 FD的推理規則（續的推理規則（續3）nA7(復合性，Composition)： XY, WZ XWYZ證：證：已知XY可得到XWYW；已知WZ可得到YWYZ；由XWYW和YWYZ可得到XWYZ。 nA8(通用一致性定理，General Unification Theorem)： XY, WZ X(W-Y)YZ證：證：已知XY，根據A2增廣性，兩邊分別添加W-Y，得到X(W-Y)Y(W-Y)； 而Y(W-Y)=YW，因此有X(W-Y)YW； 已知WZ可得到YWYZ； 由X(W-

18、Y)YW和YWYZ可得到X(W-Y)YZ。 4.2 函數依賴214.2.3 FD的推理規則（續的推理規則（續4）nA8(通用一致性定理，General Unification Theorem)： XY, WZ X(W-Y)YZ4.2 函數依賴IDAgeSNameS#S#C#GradeXYWZ注：注：ID表示身份證號碼。IDC#AgeSNameS#GradeX(W-Y)YZ224.2.3 FD的推理規則（續的推理規則（續5）4.2 函數依賴n定理4.1 如果一個函數依賴XY可以從一個關系模式的函數依賴集 F 用推理規則導出，那么XY必在該函數依賴集的閉包F+中。【例4.5】已知關系模式R(ABC

19、)，F= AB, BC ，求F+。 據規則A1自反性可推出A(表示空屬性集)，B，C，AA，BB，CC，。據已知的AB及規則A2增廣性可推出AAB，ABB，ACBC，。另外，根據傳遞性還可推出AC等等。 F+中共有43個FD。234.2.3 FD的推理規則（續的推理規則（續6）4.2 函數依賴【例4.5】已知關系模式R(ABC)，F= AB, BC ，求F+。 F+中共有43個FD：A AB AC ABC B C AA ABA ACA ABCA BB CCAB ABB ACB ABCB BC AC ABC ACC ABCC BBCAAB ABAB ACAB ABCAB BCAAC ABAC A

20、CAC ABCAC BCBABC ABBC ACBC ABCBC BCCAABC ABABC ACABC ABCABC BCBCn定義4.4 對于一個FD XY，如果YX，那么稱XY是一個“平凡的FD”，否則稱為“非平凡的FD”。 我們主要關注非平凡的FD。 24【習題4.4】設關系模式R有n個屬性，在模式R上可能成立的函數依賴有多少個？其中平凡的FD有多少個？非平凡的FD有多少個？ 設函數依賴形式為XY：4.2.3 FD的推理規則（續的推理規則（續7）4.2 函數依賴 從n個屬性中選擇屬性組成X共有種方法；同理組成Y也有2n種方法；則組成XY應該有2n2n=4n種方法。即可能成立的FD有4n

21、個。nnnnnnCCCC2210 平凡的FD要求YX，則有： 即平凡的FD有3n個，非平凡的FD有4n-3n個。nnnnnnnnnnCCCCCCCCCCCCC3)()()(10221202211011000254.2.4 FD和關鍵碼的聯系和關鍵碼的聯系n關鍵碼包括4種：超鍵、候選鍵、主鍵、外鍵。n超鍵、候選鍵的概念可用FD進行數學定義。n定義4.5 設關系模式R的屬性集是U，X是U的一個子集。如果XU在R上成立，那么稱X是R的一個超鍵。如果XU在R上成立，但對于X的任一真子集X1都有X1U不成立，那么稱X是R上的一個候選鍵。【例】設一個關系模式R(S#, C#, Grade, TName,

22、TAddr)，并規定： 每個學生每學一門課只有一個成績， 每門課程只有一個任課教師， 每個教師只有一個辦公地址；則該關系模式的候選鍵是什么？ 已知(S#, C#)Grade，C#TName，TNameTAddr，求滿足X(S#, C#, Grade, TName, TAddr)的最小X。4.2 函數依賴264.2.4 FD和關鍵碼的聯系（續和關鍵碼的聯系（續1） (S#, C#)C#，C#TName (S#, C#)TName C#TName，TNameTAddr C#TAddr (S#, C#)C#，C#TAddr (S#, C#)TAddr (S#, C#)Grade，(S#, C#)TN

23、ame， (S#, C#)TAddr (S#, C#)(Grade, TName, TAddr) (S#, C#)(S#, C#)， (S#, C#)(Grade, TName, TAddr) (S#, C#)(S#, C#, Grade, TName, TAddr) 故該關系模式的候選鍵為(S#, C#)；則其他屬性集，如(S#, C#, TName)，雖然也能函數決定該關系模式的全部屬性，但是超鍵，不是候選鍵。4.2 函數依賴274.2.4 FD和關鍵碼的聯系（續和關鍵碼的聯系（續2）【習題4.6】設R(ABCD)，F是R上成立的FD集，F= AB, CB ，則相對于F，試寫出該關系模式的

24、候選鍵。 找候選鍵時，進行邏輯推理的基本方向：推理出來的函數依賴右邊的屬性要不斷增加，以達到FD的右邊包括該關系模式的全部屬性（XU）。 AB, AA AAB CB, CC CBC AAB, CBC ACABC ACABC, DD ACDABCD 另外，還需要判斷能否由AC或AD或CD邏輯推理出ABCD。 故該關系模式的候選鍵為ACD。4.2 函數依賴284.2.4 FD和關鍵碼的聯系（續和關鍵碼的聯系（續3）【習題4.7】設關系模式R(ABCD)上FD集為F，F= ABC, CD, DA ，試求R的所有候選鍵。 (1) ABC, ABAB ABABC ABC, CD ABD ABABC, A

25、BD ABABCD AB是一個候選鍵。(2) CD, CC CCD CD, DA CA CCD, CA CACD CACD, BB BCABCD BC是一個候選鍵。4.2 函數依賴294.2.4 FD和關鍵碼的聯系（續和關鍵碼的聯系（續4）【習題4.7】設關系模式R(ABCD)上FD集為F，F= ABC, CD, DA ，試求R的所有候選鍵。 (3) DA, DD DAD DAD, BB BDABD BDABD, ABC BDCD BDABD, BDCD BDABCD BD是一個候選鍵。因此R的候選鍵有3個：AB、BC、BD。4.2 函數依賴304.2.5 屬性集的閉包屬性集的閉包n在實際使用

26、中，經常需要判斷能否從一個關系模式R已知的函數依賴集 F 推導出一個函數依賴XY，那么可先求出 F 的閉包F+，然后再看函數依賴XY是否在F+中。如果在F+中，則表明可以從函數依賴集 F 推導出。n但是，求一個函數依賴集的閉包F+屬于NP問題（Non-Polynomial，即一個問題不能在多項式時間內得到解）。n因此，引入屬性集閉包的概念，將“從一個關系模式R已知的函數依賴集 F 推導出一個函數依賴XY”的問題，轉變為求該關系模式屬性集閉包的問題。4.2 函數依賴314.2.5 屬性集的閉包（續屬性集的閉包（續1）n定義4.6 設F是屬性集U上的FD集，X是U的子集，那么（相對于F）屬性集X的

27、閉包用X+表示，它是一個從F集使用FD推理規則推出的所有滿足XA的屬性A的集合：X+= 屬性A | XA可從F集使用推理規則推出 【例4.7】屬性集U為ABCD，FD集為 AB, BC, DB ，試求A+，(AD)+，(BD)+。 解：解：A+= A, B, C =ABC，(AD)+= A, B, C, D =ABCD，(BD)+= B, C, D =BCD。 n定理4.4 一個函數依賴XY能從函數依賴集 F 用推理規則推出的充分必要條件是YX+。【練習練習】教材p162習題4.9。 (BD)+=BCD 左邊是B的FD有4個：B、BB、BC、BBC324.2.6 FD集的最小依賴集集的最小依賴

28、集n一個函數依賴集F的最小依賴集是指與該函數依賴集等價的，且不含有多余的FD的集合。多余的FD包括平凡的FD，利用其他FD能夠推導出來的FD等。n定義4.7 如果關系模式R(U)上的兩個函數依賴集F和G，有F+=G+，則稱F和G是等價的函數依賴集。n定義4.8 設F是屬性集U上的FD集。如果Fmin是F的一個最小依賴集，那么Fmin應滿足下列四個條件：(1) F+min =F+；(2) 每個FD的右邊都是單屬性；(3) Fmin中沒有冗余的FD（即Fmin中不存在這樣的函數依賴XY，使得Fmin與Fmin XY 等價）；(4) 每個FD的左邊沒有冗余的屬性。n一個函數依賴集 F 的最小依賴集

29、Fmin 不一定是唯一的。4.2 函數依賴334.2.6 FD集的最小依賴集（續集的最小依賴集（續1）【例4.8】設F是關系模式R(ABC)的FD集，F= ABC, BC, AB, ABC ，試求Fmin。 先把F中的FD寫成右邊是單屬性形式： F= AB, AC, BC, AB, ABC 顯然多了一個AB，可刪去，得F= AB, AC, BC, ABC 。 F中AC可以從AB和BC推出，因此AC是冗余的，可刪去，得F= AB, BC, ABC 。 F中ABC可以從AB和BC推出，因此ABC也可刪去，最后得F= AB, BC ，即所求的Fmin。 n算法4.2 計算函數依賴集 F 的最小依賴集

30、 Fmin 算法。（教材p141）4.2 函數依賴344.3 關系模式的分解特性關系模式的分解特性 4.3.1 模式分解定義 4.3.2 無損分解 4.3.3 無損分解的測試方法 4.3.4 保持函數依賴的分解 4.3.5 模式分解與模式等價問題354.3.1 模式分解定義模式分解定義n定義4.9 設有關系模式R(U)，屬性集為U，R1、R2 、 、Rk都是U的子集，并且有R1R2RkU。關系模式R1、 R2、Rk的集合用表示，= R1, R2, , Rk 。用代替R的過程稱為關系模式的分解。稱為R的一個分解，也稱為數據庫模式。n一般把上述的R稱為泛關系模式，R對應的表稱為泛關系 r。數據庫模

31、式對應的表稱為數據庫實例，用=表示。4.3 關系模式的分解特性圖圖4.5 模式分解示意圖模式分解示意圖 364.3.1 模式分解定義（續模式分解定義（續1）n因此，在計算機中數據并不是存儲在泛關系 r 中，而是存儲在數據庫實例中。那么，存在兩個問題： (1)和 r 是否等價，即是否表示同樣的數據。這個問題用“無損分解”特性表示。 (2) 在泛關系模式R上有一個FD集F，在數據庫模式中的每一個模式R i上有一個FD集F i，則 F1, F2, , Fk 與F是否等價。這個問題用“保持函數依賴”特性表示。4.3 關系模式的分解特性圖圖4.5 模式分解示意圖模式分解示意圖 374.3.2 無損分解無

32、損分解【例4.9】設泛關系模式R(ABC)，分解為數據庫模式= AB, AC 。 (1) 設泛關系模式R對應的泛關系 r 如下所示： 則相應的數據庫實例 r1 和 r2 可由泛關系 r 分別在屬性集AB和AC上投影得到。4.3 關系模式的分解特性 顯然有 ，即由 r 分解得到的 r1 和 r2 仍然能夠恢復成 r，并未丟失或增加信息。這種分解稱為無損分解。r1r2= r121111CBA泛關系泛關系r2111BA數據庫實例數據庫實例r111CA數據庫實例數據庫實例r2121111CBAr1r2384.3.2 無損分解（續無損分解（續1）【例4.9】設泛關系模式R(ABC)，分解為數據庫模式=

33、AB, AC 。 (2) 設泛關系模式R對應的泛關系 r 如下所示： 同樣，相應的數據庫實例 r1 和 r2 可由泛關系 r 投影得到。4.3 關系模式的分解特性 顯然有 ，即由 r 分解得到的 r1 和 r2 不能夠恢復成 r，元組比以前多（增加了噪聲）。這種分解稱為有損分解或損失分解。r1r2 r321411CBA泛關系泛關系r2111BA數據庫實例數據庫實例r14131CA數據庫實例數據庫實例r2311411321421CBAr1r2394.3.2 無損分解（續無損分解（續2）n定義4.10 設R是一個關系模式，F是R上的一個FD集。R分解成數據庫模式= R1, R2, , Rk 。如果

34、對R中滿足F的每一個關系 r，都有 那么稱分解相對于F是“無損連接分解”（Lossless Join Decomposition），簡稱為“無損分解”；否則稱為“損失分解”（Lossy Decomposition）。其中符號R i(r)表示關系 r 在模式R i屬性集上的投影。n設 r i=R i(r)，其中 1ik，并用m(r)表示上面公式等號右邊的部分，則上式可改寫為：4.3 關系模式的分解特性r=R1(r) R2(r) Rk(r)r =R1(r) R2(r) Rk(r)=r1 r2 r k= r i= m(r)i=1k404.3.2 無損分解（續無損分解（續3）n無損分解和損失分解有如下

35、的定理： 定理4.6 設= R1, R2, , Rk 是關系模式R的一個分解， r 是R的任一關系， r i=R i(r)（1ik），那么有下列性質： (1) r m(r)； (2) 若s=m(r)，則R i(s)=r i； (3) m(m(r)=m(r)，稱為冪等性（Idempotent）。n該定理成立的先決條件： 在明確知道數據庫實例 r i 是由泛關系 r 投影得到（即 r i=R i(r)成立）的前提下，該定理才成立，稱為泛關系假設（Universal Relation Assumption）。 若不存在該前提，稱為無泛關系假設。4.3 關系模式的分解特性414.3.2 無損分解（續無

36、損分解（續4）【例4.10】（無泛關系假設的例子）設關系模式R(ABC)分解的數據庫模式= AB, BC ，AB和BC對應的數據庫實例 r1 和 r2 如下所示： 則 s2=BC(s)r2。我們把r2中使s2r2的元組(b2, c2)稱為懸掛元組（Dangling Tuple）。4.3 關系模式的分解特性b1a1BAr1C1b1C2b2CBr2b1Bc1a1CAs=r1 r2424.3.2 無損分解（續無損分解（續5）n模式分解（包括無損分解和損失分解）都能消除數據冗余和操作異常現象（無損分解是目標）。n但是分解之后，檢索操作需要做笛卡爾積或連接操作，這將付出時間代價。n一般認為，為了消除冗余

37、和異常現象，對模式進行分解是值得的。4.3 關系模式的分解特性434.3.3 無損分解的測試方法無損分解的測試方法n在把泛關系模式R分解成數據庫模式以后，如何測試分解是否是無損分解？可采用如下的測試算法： 算法4.3 無損分解的測試（以教材p145例4.11為例說明） 已知：已知：關系模式R(A1A2An)，F是R上成立的函數依賴集， = R1, , Rk是R的一個分解。 目的：目的：判斷相對于F是否具有無損分解特性。 方法：方法： 構造一張k行n列的表格，每列對應一個屬性A j（1jn），每行對應一個模式R i（1ik）。如果A j在R i中出現，那么在表格的第i行第j列處填上符號a j；否

38、則填上b ij。 把表格看成模式R的一個關系，反復檢查F中每個FD在表格中是否成立，若不成立，則修改表格中的值。修改方法如下：4.3 關系模式的分解特性444.3.3 無損分解的測試方法（續無損分解的測試方法（續1） 把表格看成模式R的一個關系，反復檢查F中每個FD在表格中是否成立，若不成立，則修改表格中的值。修改方法如下： 對于F中一個FD XY，如果表格中有兩行在X值上相等，在Y值上不相等，那么把這兩行在Y值上也改成相等的值。如果Y值中有一個是a j，那么另一個也改成a j；如果沒有a j，那么用其中一個b ij替換另一個值（盡量把下標ij改成較小的數）。一直到表格不能修改為止。（這個過程

39、稱為chase過程） 若修改的最后一張表格中有一行是全a，即a1a2an，那么相對于F是無損分解，否則是損失分解。 4.3 關系模式的分解特性454.3.3 無損分解的測試方法（續無損分解的測試方法（續2）【習題4.17】設關系模式R(ABCDEG)上FD集為F，并且F= DG, CA, CDE, AB ，分解2= DG, AC, CDE, AB ，問該分解是無損分解嗎？ 解：解： 故2= DG, AC, CDE, AB 相對于 F 是無損分解。4.3 關系模式的分解特性b46b45b44b43a2a1ABb36a5a4a3b32b31CDEb26b25b24a3b22a1ACa6b15a4b

40、13b12b11DGGEDCBAa6a1a2a2464.3.3 無損分解的測試方法（續無損分解的測試方法（續3）【習題4.18】設關系模式R(ABCD)，F是R上成立的FD集，F= AB, BC, AD, DC ，= AB, AC, BD 是R的一個分解，問相對于F，是無損分解嗎？ 解：解： 故= AB, AC, BD 相對于 F 是損失分解。【練習練習】教材p163習題4.19。4.3 關系模式的分解特性a4b33a2b31BDb24a3b22a1ACb14b13a2a1ABDCBAb14a2a3a3474.3.4 保持函數依賴的分解保持函數依賴的分解n保持函數依賴的分解 設泛關系模式R(U

41、)的FD集為F，在將R分解為數據庫模式 = R1, R2, , Rk （其中每個R i均是U的子集）時，R的FD集 F 中的函數依賴也將被分配到每個R i上，構成R i自己的FD集F i；保持函數依賴的分解是指分解后的 F i 集合 F1, F2, , Fk 與 F 等價。n由泛關系模式R(U)的FD集 F 如何得到分解后的每個子集 R i 上的FD集 F i ？有如下定義： 定義4.11 設F是屬性集U上的FD集，Z是U的子集，F在Z上的FD集 Fz 用Z(F)表示，定義為Fz=Z(F)= XY | XYF+，且XYZ 4.3 關系模式的分解特性484.3.4 保持函數依賴的分解（續保持函數

42、依賴的分解（續1）n定義4.12 設R的FD集為F，= R1, R2, , Rk 是R的一個分解，R i 上的FD集為 F i =Ri(F) （1ik），若有 F1, F2, , Fk F，那么稱分解保持函數依賴集 F 的特性。 表明：表明：判斷一個分解是否保持FD特性，方法是判斷能否由分解后的FD集的集合 F1, F2, , Fk 邏輯推出分解前的FD集 F 中的每個函數依賴。若能推出，表明該分解保持了分解前FD集 F 的特性；否則，則不能保持。【例4.12】教材p147。4.3 關系模式的分解特性494.3.4 保持函數依賴的分解（續保持函數依賴的分解（續2）【習題4.17】設關系模式R(

43、ABCDEG)上FD集為F，并且F= DG, CA, CDE, AB ，分解2= DG, AC, CDE, AB ，問該無損分解是否保持FD特性？ 解：解：FDG=DG(F)= DG FAC=AC(F)= CA FCDE=CDE(F)= CDE FAB=AB(F)= AB 則 FDG, FAC, FCDE, FAB = DG, CA, CDE, AB = DG, CA, CDE, AB F 故該無損分解2= DG, AC, CDE, AB 保持了FD特性（保持了分解前FD集 F 的特性）。4.3 關系模式的分解特性504.3.4 保持函數依賴的分解（續保持函數依賴的分解（續3）【習題4.18】

44、設關系模式R(ABCD)，F是R上成立的FD集，F= AB, BC, AD, DC ，= AB, AC, BD 是R的一個分解，問損失分解是否保持FD特性？ 解：解：FAB=AB(F) = AB FAC=AC(F) = AC FBD=BD(F) = 則由 FAB, FAC, FBD = AB, AC, = AB, AC 不能邏輯推出 F。 故該損失分解= AB, AC, BD 不能保持FD特性。 說明：說明：這兩個例子不能說明“無損分解一定保持FD特性”，“損失分解一定不保持FD特性”。無損分解特性和保持FD特性兩者之間沒有必然的聯系。4.3 關系模式的分解特性514.3.5 模式分解與模式等

45、價問題模式分解與模式等價問題n模式分解是指將泛關系模式R分解為數據庫模式，從而消除數據冗余和操作異常現象。n模式分解的兩個特性實際上涉及到泛關系模式R和數據庫模式這兩個模式等價的問題，模式等價包括數數據等價據等價和函數依賴等價函數依賴等價兩個方面。n數據等價數據等價是指泛關系模式R對應的泛關系r與數據庫模式對應的數據庫實例應表示同樣的信息內容，用“無損分解”特性衡量。n函數依賴等價函數依賴等價是指泛關系模式R和數據庫模式應具有相同的函數依賴集，用“保持函數依賴”特性衡量。4.3 關系模式的分解特性524.3.5 模式分解與模式等價問題模式分解與模式等價問題 （續續1）n“無損分解”特性和“保持

46、FD”特性兩者之間沒有必然的聯系；故將泛關系模式R分解為數據庫模式時，在兩個特性方面存在以下4種可能性： (1) 分解既是無損分解，又保持FD； (2) 分解是無損分解，但不保持FD； (3) 分解是損失分解，但保持FD； (4) 分解既是損失分解，也不保持FD。 相應的實例請參見教材p148例4.13。n由于上述4種可能性的存在，在評價一個關系模式的優劣時，存在著不同級別的標準（范式）：有的范式僅要求滿足其中一個特性，有的范式要求同時滿足這兩個特性。4.3 關系模式的分解特性534.4 關系模式的范式關系模式的范式n衡量關系模式好壞的標準就是范式（Normal Forms，簡記為NF）。n范

47、式的種類： 1NF、2NF、3NF、BCNF、4NF、5NFn左左右：右：表示范式的級別越高、規定越嚴，高一級的范式總是在低一級范式的基礎上做進一步的規定；n左左右：右：表示范式的級別越低，符合高一級范式的關系模式肯定也符合低一級的范式。n在數據庫設計中最常用的是3NF和BCNF。544.4 關系模式的范式關系模式的范式 4.4.1 第一范式(1NF) 4.4.2 第二范式(2NF) 4.4.3 第三范式(3NF) 4.4.4 BC范式(BCNF) 4.4.5 模式分解方法的原則554.4.1 第一范式第一范式(1NF)n定義4.13 在關系模式 R 的每個關系 r 中，如果每個屬性值都是不可

48、再分的原子值，那么稱R是第一范式（First Normal Form，簡記為1NF）的關系模式。n滿足1NF的關系稱為規范化的關系；否則，稱為非規范化的關系。關系數據庫研究的關系都是規范化的關系。n1NF是關系模式應具備的最起碼的條件。 4.4 關系模式的范式564.4.2 第二范式第二范式(2NF)n如果關系模式中存在局部依賴，就需要將關系模式分解，以排除局部依賴，使模式達到2NF的標準，相關定義如下： 定義4.14 對于FD WA，如果對于W的真子集X有XA成立，那么稱WA是局部依賴（A局部依賴于W）；否則，稱WA是完全依賴。 定義4.15 如果一個屬性是關系模式R候選鍵中的屬性，那么稱該

49、屬性是R的主屬性；否則，稱該屬性是R的非主屬性。 定義4.16 如果關系模式R是1NF，且每個非主屬性完全函數依賴于候選鍵，那么稱R是第二范式（2NF）的關系模式。 如果數據庫模式 = R1, R2, , Rk 中的每個關系模式都是2NF，則稱數據庫模式 為2NF的數據庫模式。4.4 關系模式的范式574.4.2 第二范式第二范式(2NF)（續（續1）n2NF就是要消除非主屬性對候選鍵的的局部依賴。n算法4.4 將關系模式R分解成2NF模式集。 設關系模式R(U)，候選鍵為W，對于W的真子集X存在FD XA（其中A為非主屬性集），則WA就是一個局部依賴。此時應把R分解成兩個模式： R1(XA)

50、，候選鍵是X； R2(U-A)，候選鍵仍是W，外鍵是X。 如果R1和R2還不是2NF，則重復上述過程，直到數據庫模式 中每一個關系模式都是2NF為止。 4.4 關系模式的范式候選鍵候選鍵W 屬性集屬性集X屬性集屬性集A584.4.2 第二范式第二范式(2NF)（續（續2）【例】設關系模式R(S#, C#, Grade, TName, TAddr)，其函數依賴集F為 (S#, C#)Grade，C#TName， TNameTAddr ，候選鍵為(S#, C#) 。 問：問：R是否為2NF？如不是，將其分解為2NF。 答：答：由 C#TName，TNameTAddr C#(TName, TAddr

51、)知該關系模式 R 存在非主屬性對候選鍵的局部依賴。 分解為R1(C#, TName, TAddr)、R2(S#, C#, Grade)。 則R1是2NF，R2是2NF。【練習練習】教材p163習題4.22。 R的候選鍵為AB，由AD可知R不是2NF。 分解為 =AD, ABC。4.4 關系模式的范式594.4.3 第三范式第三范式(3NF)n定義4.17 如果XY，YA，且A不是Y的子集（即 YA不是平凡的FD），那么稱XA是傳遞依賴（A傳遞依賴于X）。n定義4.18 如果關系模式R的每個非主屬性都不傳遞依賴于R的候選鍵，那么稱R是第三范式（3NF）的關系模式。 如果數據庫模式 = R1,

52、R2, , Rk 中的每個關系模式都是3NF，則稱其為3NF的數據庫模式 。n3NF就是要消除非主屬性對候選鍵的的傳遞依賴。4.4 關系模式的范式候選鍵候選鍵W屬性集屬性集X屬性集屬性集A候選鍵候選鍵W屬性集屬性集A屬性集屬性集X604.4.3 第三范式第三范式(3NF)（續（續1）【例】接前例，學生選課關系模式 R 已分解為兩個2NF模式 R1(C#, TName, TAddr)、R2(S#, C#, Grade)。 則R1的FD集F= C#TName， TNameTAddr ，候選鍵為C#；R2的FD集F= (S#, C#)Grade ，候選鍵為(S#, C#)。 問：問：R1、R2是否為

53、3NF？如不是，如何分解？ 答：答：R2是3NF。 對于R1，由 C#TName， TNameTAddr C# TAddr，知C#TAddr是一個傳遞依賴，故R1不是3NF。 有如下的分解算法：n算法4.7 將關系模式R無損分解且保持函數依賴地分解成3NF模式集。（教材p154）4.4 關系模式的范式614.4.3 第三范式第三范式(3NF)（續（續2）4.4 關系模式的范式 對于關系模式R和R上成立的FD集F，先求出F的最小依賴集，然后再把最小依賴集中那些左部相同的FD用合并性合并起來。 對最小依賴集中每個FD XY去構成一個關系模式XY。 在構成的模式集中，如果每個模式都不包含R的候選鍵，

54、那么把候選鍵單獨作為一個模式放入模式集中。 這樣得到的模式集是關系模式R的一個符合3NF的分解，并且這個分解既是無損分解，又能保持FD。 【前例】 對于其中的R1(C#, TName, TAddr)， FD集F= C#TName，TNameTAddr 。 則R1可分解為R11(C#, TName)和R12(TName, TAddr)。624.4.3 第三范式第三范式(3NF)（續（續3）4.4 關系模式的范式 故關系模式R(S#, C#, Grade, TName, TAddr)若分解為3NF，應分解為R1(C#, TName)、R2(TName, TAddr)、 R3(S#, C#, Gra

55、de)。【例4.17】設關系模式R(ABCDE)，R的最小依賴集為 AB，C D ，試將其分解為3NF。 根據最小FD集，可得到兩個關系模式AB，CD； R的候選鍵為ACE，這兩個模式中都不包含候選鍵，則將候選鍵作為一個單獨的關系模式； 故，分解結果為 = AB, CD, ACE ，且該分解是無損分解且保持函數依賴。63【練習練習】教材p163習題4.23。 R的候選鍵為C，由 CB，BA CA，知CA是一個傳遞依賴，故R不是3NF。 應分解為 = CB, BA 。n定理4.9 如果R是3NF模式，那么R也是2NF模式。4.4.3 第三范式第三范式(3NF)（續（續4）4.4 關系模式的范式6

56、44.4.4 BC范式范式(BCNF)4.4 關系模式的范式n2NF是要消除非主屬性對候選鍵的的局部依賴；3NF是要消除非主屬性對候選鍵的的傳遞依賴。nBCNF是要消除主屬性對候選鍵的傳遞依賴。n定義4.19 如果關系模式R是3NF，且每個主屬性都不傳遞依賴于R的候選鍵，那么稱R是BCNF的關系模式。如果數據庫模式 = R1, R2, , Rk 中的每個關系模式都是BCNF，則稱其為BCNF的數據庫模式 。候選鍵候選鍵W屬性集屬性集X屬性集屬性集A候選鍵候選鍵W屬性集屬性集X屬性集屬性集A654.4.4 BC范式范式(BCNF)（續（續1）4.4 關系模式的范式【例】設關系模式R(B#, BN

57、ame, Author)，候選鍵為(Author, BName)，FD集F= (Author, BName)B#，B#BName。 問：問：R是否為BCNF？如不是，將其分解為BCNF。 答：答：由 (Author, BName)B#，B#BName (Author, BName)BName，知關系模式R中存在主屬性BName對候選鍵的傳遞依賴，故不是BCNF。 有如下的分解算法：n算法4.6 將關系模式R無損分解成BCNF模式集。 設關系模式R(U)的候選鍵為W，且存在FD XA（其中X為非主屬性，A為主屬性），則必然存在主屬性A對候選鍵W的傳遞依賴。此時應把R分解成XA和U-A兩個關系模式

58、。 重復上述過程，直到數據庫模式 中每一個關系模式都是BCNF為止。 664.4.4 BC范式范式(BCNF)（續（續2）4.4 關系模式的范式 故關系模式R(B#, BName, Author)可分解為兩個BCNF模式：R1(B#, BName)，R2(B#, Author)。n注意：上述分解為BCNF模式的算法是無損分解，但不一定能保持函數依賴。【前例】關系模式R(B#, BName, Author)FD集F= (Author, BName)B#，B#BName ；將R分解為兩個BCNF模式：R1(B#, BName)，R2(B#, Author)，是否能保持FD特性？ FR1=B#, B

59、Name(F)= B#BName ； FR2=B#, Author(F)= ； 由 FR1, FR2 = B#BName, 不能邏輯推出 F，則該分解不能保持FD特性。674.4.4 BC范式范式(BCNF)（續（續3）4.4 關系模式的范式【習題4.20】設關系模式R(ABCD)上FD集為F，并且F= AB, BC, DB 。 (1) R分解成 =ACD, BD，試求F在ACD和BD上的投影。 (2) ACD和BD是BCNF嗎？如不是，試分解成BCNF。解：解：(1) ACD= AC, DC ，候選鍵為AD； BD= DB ，候選鍵為D。 (2) 對于模式ACD，候選鍵為AD，由AC或DC知ACD不是2NF，則肯定不是BCNF。可有兩種分解方式： 若采用AC進行分解，ACD可分解為AC和AD，均是BCNF； 若采用DC進行分解，ACD可分解為CD和AD，均是BCNF； 對于模式BD，則是BCNF。684.4.5 模式分解方法的原則模式分解方法的原則n設泛關系模式R的FD集為F，將R分解為數據庫模式 = R1, R2, , Rk ，一般應做到以