PowerPoint Presentation

Transcription

1 第八章關聯式資料庫的正規化 資料庫系統設計理論李紹綸著

2 本章內容 功能相依 (Functional Dependencies) 完全功能相依與部份功能相依 功能相依的推理法則 鍵 關聯式資料庫非正式設計準則 能清楚的表達每個關聯表綱目和其屬性的語意 盡量減少資料的重複, 避免更新異常現象產生 盡量減少虛值的產生, 避免懸掛列錄現象產生 關聯表分解的過程必須滿足無遺失聯結分解, 避免偽造列錄現象產生 關聯表分解的過程必須保留所有的功能相依, 避免遺失資訊現象產生 正規化型式 (Normal Form) 第一正規化型式 (First Normal Form,1NF) 第二正規化型式 (Second Normal Form,2NF) 第三正規化型式 (Third Normal Form,3NF) 波亦師 - 高德正規化型式 (Boyce/Codd Normal Form,BCNF) 合成法 (Synthesis) 第四正規化型式 (Fourth Normal Form,4NF) 第五正規化型式 (Fifth Normal Form,5NF) 正規化處理的步驟 2

3 功能相依 (Functional Dependencies) [F.D. 定義 ]: 功能相依 F.D. 可以表示成 X Y 此限制表示對於所有在關聯表 R 中的任意兩個列錄 tuple 1 和 tuple 2 而言, 當 tuple 1 [X] = tuple 2 [X] 時, 則 tuple 1 [Y] = tuple 2 [Y] 必定為真 在關聯表 R 中的每一個屬性 X 的值都恰好有一個屬性 Y 的值與其相對映 屬性 Y 的值是功能相依於屬性 X 的值 屬性 Y 的值可以由屬性 X 的值所決定 (Determined) 屬性 X 的值可決定 (Determine) 屬性 Y 的值 具有下列兩點特性 : 當關聯表 R 中存在一個功能相依 X Y 時, 並不保證功能相依 Y X 也存在於關聯表 R 中 當屬性 X 是關聯表 R 中的候選鍵時, 屬性 X 一定可以直接或間接推導出關聯表 R 中的任何屬性集合 也因為 X 是候選鍵, 所以具 有唯一性 3

4 範例 8.1 員工 關聯表 員工 身分證號碼 姓名 生日 地址 薪水 A 李鴻章 61/09/01 板橋市忠孝路 100 號 E 李紹綸 58/11/01 台北市信義路 200 號 F 簡嘉祐 61/07/11 台北市仁愛路 168 號 F 賴怡君 63/07/03 板橋市四川路 120 號 Null F 莊雅玫 62/12/04 台北市信義路 100 號 身分證號碼 姓名 身分證號碼 生日 身分證號碼 地址 和 身分證號碼 薪水 等功能相依性都成立? 姓名 身分證號碼 姓名 生日 姓名 地址 和 姓名 薪水 等功能相依性也都成立? 4

5 完全功能相依與部份功能相依 關聯表綱目 R(X, Y, Z) 中包含一組功能相依 X Y 如果我們從屬性集合 X 中移除任一屬性 Z 時, 則使得這個功能相依 (X-Z) Y 不存在, 此時我們稱 Y 完全功能相依 (Full Functional Dependency) 於 X 反之, 若 (X-Z) Y 存在, 我們稱 Y 部份功能相依 (Partial Functional Dependency) 於 X 5

6 範例 8.2 關聯表綱目 R(A, B, C, D, E, F), 功能相依 F = { AC B, C B, AC D, A EF } AC B 是完全功能相依或部份功能相依? C B 是完全功能相依或部份功能相依? AC D 是完全功能相依或部份功能相依? A EF 是完全功能相依或部份功能相依? 6

7 功能相依的推理法則 由已知的功能相依推導出某些隱含的功能相依, 我們稱之為 阿姆斯壯公理 (Armstrong Axioms) 每一個功能相依 F 皆存在一個封閉性 F + (Closure of F) 而 F + 則表示所有可經由 F 推論出來的功能相依, 即 F + = { X Y F X Y} 一般稱之為 阿姆斯壯推理法則 (Armstrong s Inference Rules) 反射法則 (Reflexivity): 對 X 和 Y 兩組屬性而言, 若屬性 Y 是屬性 X 的子集合時, 我們可以推論出 X Y 這個功能相依 換言之, 若 Y X 則 X Y 擴充法則 (Augmentation): 當 F 包含 X Y 和 Z 是一組屬性時, 則可推論出 XZ YZ 這個功能相依 換言之,{ X Y } XZ YZ 遞移法則 (Transitivity): 當 F 包含 X Y 和 Y Z 兩組功能相依 時, 則我們可以推論出 X Z 即 { X Y, Y Z } X Z 7

8 功能相依的推理法則 阿姆斯壯推理法則已經被證明是 安全及完整的 (Sound and Complete) 為簡化推理步驟, 所以有下列三條推理法則 分割法則 (Decomposition): 當 F 包含 X YZ 時, 則可以推論出 X Y 及 X Z 也在 F 中 即 { X YZ } X Y 及 X Z 聯集法則 (Union): 當 F 包含 X Y 和 X Z 時, 則 X YZ 也在 F 中 換言之,{ X Y, X Z} X YZ 偽遞移法則 (Psuedotransitivity): 當 F 包含 X Y 和 WY Z 時, 則 F 也包含 WX Z 即 { X Y, WY Z } WX Z 8

9 範例 8.3 關聯表綱目 R(A, B, C, D, E, F), 功能相依 F = { A B, B C }, 請找出 F + F + = { A A, A B, A C, B B, B C, C C, AB A, AB B, AB C, AB AB, AB AC, } 9

10 從功能相依 F 中的屬性 X 計算出 X F + 演算法 8.1 Input:X,F Output:X + F Let X F+ := X; Repeat Original_X F+ := X F+ ; For each functional dependency Y Z in F do If Y X F+ Then X F+ := X F+ Z; Until (Original_X F+ = X F+ ); 10

11 範例 8.4 關聯表綱目 R(A, B, C, D, E, F), 功能相依 F = { AC B, C B, AC D, A EF }, 請找出 A F + A F+ = { A, E, F } A F + 含有 { A A, A E, A F, A AE, A EF, A AF, A AEF } 等七個功能相依 11

12 範例 8.5 關聯表綱目 R(A, B, C, D, E, F), 功能相依 F = { A B, B C }, 請找出 A F + A F+ = { A, B, C } A F + 含有 { A A, A B, A C, A AB, A BC, A AC, A ABC } 等七個功能相依 12

13 鍵 當關聯表綱目 R 中所有屬性皆功能相依於屬性 X 時, 則屬性 X 即為關聯表綱目 R 中的超級鍵 假設此刻屬性 X 又為關聯表綱目 R 的最小超級鍵時, 則屬性 X 即是關聯表綱目 R 的鍵 有時候一個關聯表綱目 R 可能會存在一個以上的鍵, 這些鍵我們通常稱之為關聯表綱目 R 的候選鍵 然而一個關聯表中只能有一個主鍵, 因此在這些候選鍵中, 我們通常會選擇其中一個長度最短 語意最清楚候選鍵當作關聯表綱目 R 中的主鍵 而其它未被選中的候選鍵則稱之為次選鍵 在一個關聯表綱目 R 中, 若屬性 Y 是屬於關聯表綱目 R 的候選鍵之一部份, 則屬性 Y 被稱為關聯表綱目 R 的主要屬性 (Prime Attribute) 反之, 屬性 Y 則被稱為關聯表綱目 R 中的非主要屬性 (Non-Prime Attribute) 13

14 可依照下列的規則與步驟, 找到關聯表 所有 的鍵 只出現在功能相依的左手邊的屬性, 一定是 鍵的一部分 從來沒有出現在功能相依的左右兩邊的屬性, 一定是 鍵的一部分 同時出現在功能相依的左右兩邊的屬性, 可能是 鍵的一部分 鍵 14

15 範例 8.6 關聯表綱目 R(A, B, C, D, E, F), 功能相依 F = { AC B, C B, AC D, A EF }, 請找出 R 中所有的鍵 A F+ = { A, E, F } C F+ = { B, C } (AC) F+ = { A, B, C, D, E, F } AC 是 R 的主鍵 15

16 範例 8.7 關聯表綱目 R(A, B, C, D, E, F), 功能相依 F = { A B, B C }, 請找出 R 中所有的鍵 A F+ = { A, B, C } (AD) F+ = { A, B, C, D } (ADE) F+ = { A, B, C, D, E } (ADEF) F+ = { A, B, C, D, E, F } ADEF 是 R 的主鍵 16

17 關聯式資料庫非正式設計準則 能清楚的表達每個關聯表綱目和其屬性的語意 (Semantics) 盡量減少資料的重複, 避免更新異常 (Update Anomalies) 現象產生 盡量減少虛值的產生, 避免懸掛列錄 (Dangling Tuples) 現象產生 關聯表分解的過程必須滿足無遺失聯結分解 (Lossless Join Decomposition), 避免偽造列錄 (Spurios Tuples) 現象產生 關聯表分解的過程必須保留所有的功能相依 (Functional Dependency), 避免遺失資訊現象產生 17

18 能清楚的表達每個關聯表綱目和其屬性的語意 員工參加計劃實體關係圖 姓名 計劃代號 委託單位 身分證號碼 生日 員工 M 參加 N 工作時數 計劃名稱 計劃 執行地點 18

19 能清楚的表達每個關聯表綱目和其屬性的語意 員工 參加 和 計劃 三個關聯表 員工身分證號碼姓名生日參加身分證號碼計劃代號工作時數 A 李鴻章 61/09/01 E 李紹綸 58/11/01 F 簡嘉祐 61/07/11 F 賴怡君 63/07/03 F 莊雅玫 62/12/04 E E E F F F F F F 計劃 計劃代號 計劃名稱 執行地點 委託單位 1 P 1 台北 政府機關 2 P 2 台中 私人企業 3 P 3 台中 私人企業 4 P 4 台南 私人企業 5 P 5 高雄私人企業 19

20 能清楚的表達每個關聯表綱目和其屬性的語意 員工計劃 關聯表 員工計劃 身分證號碼 姓名 生日 工作時數 計劃代號 計劃名稱 執行地點 委託單位 E 李紹綸 58/11/ P 1 台北 政府機關 E 李紹綸 58/11/ P 2 台中 私人企業 E 李紹綸 58/11/ P 3 台中 私人企業 F 簡嘉祐 61/07/ P 2 台中 私人企業 F 賴怡君 63/07/ P 1 台北 政府機關 F 賴怡君 63/07/ P 4 台南 私人企業 F 莊雅玫 62/12/ P 2 台中 私人企業 F 莊雅玫 62/12/ P 3 台中 私人企業 F 莊雅玫 62/12/ P 5 高雄 私人企業 20

21 能清楚的表達每個關聯表綱目和其屬性的語意 第一條設計準則 (Guideline 1) 為 : 關聯表綱目的語意要能夠很容易地被解釋清楚 關聯表綱目通常只用來描述單一個實體類型或關係類型 每個屬性名稱都只能代表一種涵義 21

22 盡量減少資料的重複, 避免更新異常現象產生 在 員工計劃 關聯表中, 有許多資料都重複出現 多餘重複的資料會浪費記憶體空間 更嚴重的問題是會產生更新異常 (Update Anomalies) 的問題 將 員工計劃 關聯表切割成 員工 參加 和 計劃 等三個關聯表的優點就是避免資料的重複, 避免更新異常現象產生 22

23 更新異常 (Update Anomalies) 新增異常 資料不一致的問題 試考慮簡嘉祐這位員工新參加 計劃代號 = 1 的計劃 無法儲存相關的資訊 試考慮一個沒有任何員工參與的計劃, 或一位沒有參與任何計劃之員工 刪除異常 會遺失相關的資訊 試考慮賴怡君這位員工要離職 修改異常 資料不一致的問題 試考慮將賴怡君的生日由 63/07/03 改為 63/07/13 23

24 盡量減少資料的重複, 避免更新異常現象產生 第二條設計準則 (Guideline 2) 為 : 關聯表綱目中應避免更新異常現象發生 如為了改進系統執行效率, 而允許在所設計出的資料庫中, 有更新異常現象產生時, 則我們要確定所有更新動作皆能正確地執行, 不會有資料不一致性現象產生 24

25 盡量減少虛值的產生, 避免懸掛列錄現象產生 虛值可以代表一個不存在的值 一個存在但目前是未知的值, 在未來該虛值可以被其他的值所取代, 或是完全不知道屬性值是否存在等三種 當某些屬性不能在每一筆列錄均能解釋其語意時, 就會產生虛值 (Null Values) 將兩個關聯性不高的關聯表合併儲存在同一個關聯表之中, 就會產生很多含有虛值的屬性 25

26 盡量減少虛值的產生, 避免懸掛列錄現象產生 虛值會造成記憶體的浪費 含虛值的 員工 關聯表 員工 身分證號碼 姓名 生日 重大疾病 薪水 A 李鴻章 61/09/01 心臟病 E 李紹綸 58/11/01 Null F 簡嘉祐 61/07/11 Null F 賴怡君 63/07/03 Null Null F 莊雅玫 62/12/04 Null

27 盡量減少虛值的產生, 避免懸掛列錄現象產生 虛值會造成在正規化分解過程中產生懸掛列錄問題 含懸掛列錄的 員工 1 和 員工病歷 兩個關聯表 員工 1 身分證號碼姓名生日薪水 員工病歷身分證號碼重大疾病 A 李鴻章 61/09/ E 李紹綸 58/11/ F 簡嘉祐 61/07/ F 賴怡君 63/07/03 Null F 莊雅玫 62/12/ A 心臟病 27

28 盡量減少虛值的產生, 避免懸掛列錄現象產生 虛值會增加查詢處理的困難度 虛值可以代表許多不同的涵義和任意的值, 所以對一個含有虛值的資料庫而言, 要找出所有滿足查詢條件的列錄將是一件很困難的事 更嚴重的問題是當我們在查詢時, 該如何去計算含有虛值的聚合函數結果 試考慮計算 員工 關聯表中所有員工的平均薪水 28

29 盡量減少虛值的產生, 避免懸掛列錄現象產生 第三條設計準則 (Guideline 3) 為 : 每一個關聯表綱目應盡量避免虛值的產生 29

30 關聯表分解的過程必須滿足無遺失聯結分解, 避免偽造列錄現象產生 正規化處理是將一個複雜的關聯表綱目分解至數個較簡單且能滿足需求的關聯表綱目, 所以此分解的結果必須是無遺失聯結分解 如果分解的過程不滿足無遺失聯結分解的特性, 那麼所設計出的關聯表綱目一定是不正確的 30

31 無遺失聯結分解 當關聯表綱目 R 被分解成數個關聯表綱目 R 1, R 2,, R n 時, 則下列公式必定成立 : (t) π R2 (t) π Rn (t) = t π R1 無遺失 (Lossless) 並不是指列錄的遺失, 而是指資訊的遺失 遺失聯結分解是指在執行完自然聯結運算和投射運算後, 可能會新增許多原本不存在的列錄, 這些原本不存在的列錄我們稱之為 偽造的列錄 (Spurios Tuples) 31

32 無遺失聯結分解 試考慮將 員工計劃 關聯表分解成 員工地點 和 計劃 1 兩個關聯表 員工地點 和 計劃 1 兩個關聯表 員工地點姓名執行地點 計劃 1 身分證號碼生日工作時數計劃代號計劃名稱執行地點委託單位 李紹綸李紹綸簡嘉祐賴怡君賴怡君莊雅玫莊雅玫 台北台中台中台北台南台中高雄 E /11/ P 1 台北 政府機關 E /11/ P 2 台中 私人企業 E /11/ P 3 台中 私人企業 F /07/ P 2 台中 私人企業 F /07/ P 1 台北 政府機關 F /07/ P 4 台南 私人企業 F /12/ P 2 台中 私人企業 F /12/ P 3 台中 私人企業 F /12/ P 5 高雄 私人企業 32

33 偽造的列錄 員工計劃 1 關聯表存放 員工地點 計劃 1 員工計劃 1 身分證號碼 姓名 生日 工作時數 計劃代號 計劃名稱 執行地點 委託單位 E 李紹綸 58/11/ P 1 台北 政府機關 E 李紹綸 58/11/ P 2 台中 私人企業 E 李紹綸 58/11/ P 3 台中 私人企業 F 簡嘉祐 61/07/ P 2 台中 私人企業 F 賴怡君 63/07/ P 1 台北 政府機關 F 賴怡君 63/07/ P 4 台南 私人企業 F 莊雅玫 62/12/ P 2 台中 私人企業 F 莊雅玫 62/12/ P 3 台中 私人企業 F 莊雅玫 62/12/ P 5 高雄 私人企業 # F 李紹綸 63/07/ P 1 台北 政府機關 # F 李紹綸 61/07/ P 2 台中 私人企業 # F 李紹綸 62/12/ P 2 台中 私人企業 # F 李紹綸 62/12/ P 3 台中 私人企業 # E 簡嘉祐 58/11/ P 2 台中 私人企業 # E 簡嘉祐 58/11/ P 3 台中 私人企業 # F 簡嘉祐 62/12/ P 2 台中 私人企業 # F 簡嘉祐 62/12/ P 3 台中 私人企業 # E 賴怡君 58/11/ P 1 台北 政府機關 # E 莊雅玫 58/11/ P 2 台中私人企業 # E 莊雅玫 58/11/ P 3 台中私人企業 33 # F 莊雅玫 61/07/ P 2 台中私人企業

34 如何判斷一個關聯表的分解是否為無遺失聯結分解 當關聯表綱目 R 依據功能相依 F 而被分解成 R 1 和 R 2 時, 若此分解滿足下列兩點特性, 則此分解必定是無遺失聯結分解 : (R 1 R 2 ) R 1 (R 1 R 2 ) R 2 試考慮將 員工計劃 分解成 員工地點 和 計劃 1 兩個關聯表的過程是否為無遺失分解 34

35 如何確保一個關聯表的分解是無遺失聯結分解 關聯表綱目 R(W, X, Y, Z), 依據功能相依 X Y 將 R(W, X, Y, Z) 作無遺失聯結分解 R 1 關聯表是由功能相依 X Y 左手邊的 X 屬性和右手邊的 Y 屬性所組成, 即 R 1 (X, Y) R 2 關聯表是由關聯表綱目 R 中的所有屬性 W X Y 和 Z, 減去功能相依 X Y 右手邊的 Y 屬性, 即 R 2 (W, X, Z) 35

36 範例 8.11 試考慮關聯表綱目 R(A, B, C, D, E, F), 依據功能相依 F = {AC B, C D, A EF} 作無遺失聯結分解 R(A, B, C, D, E, F) AC B R 1 (A, B, C) R 2 (A, C, D, E, F) C D R 3 (C, D) R 4 (A, C, E, F) A EF R 5 (A, E, F) R 6 (A, C) 36

37 關聯表分解的過程必須滿足無遺失聯結分解, 避免偽造列錄現象產生 第四條設計準則 (Guideline 4) 為 : 在關聯表分解的過程必須滿足無遺失聯結分解, 避免偽造列錄現象產生 37

38 關聯表分解的過程必須保留所有的功能相依, 避免遺失資訊現象產生 假設關聯表綱目 R 被分解成 R 1, R 2,, R n 個關聯表綱目,F 為 R 中的功能相依,F i 則為關聯表綱目 R i 的功能相依 若此分解的過程滿足 (F 1 F 2 F n ) + = F + 條件時, 則此分解必定能保留 F 中所有的功能相依 在關聯式資料庫中, 每一條功能相依即代表一種限制, 因此在執行資料庫更新動作時, 必須要確保在更新資料庫之後, 所有的資料依然能滿足每一條功能相依, 否則便違反了資料的一致性 否則當一個功能相依遺失時, 資料庫設計人員則必須花費更大的力氣, 利用程式來描述此一個遺失的功能相依 38

39 範例 8.12 試考慮 計劃 關聯表, 功能相依 F 包含 計劃代號 計劃名稱, 執行地點, 委託單位 和 執行地點 委託單位 計劃 關聯表 計劃 計劃代號 計劃名稱 執行地點 委託單位 1 P 1 台北 政府機關 2 P 2 台中 私人企業 3 P 3 台中 私人企業 4 P 4 台南 私人企業 5 P 5 高雄 私人企業 39

40 無遺失聯結分解 計劃單位 和 計劃地點 關聯表 遺失功能相依 計劃 ( 計劃代號, 計劃名稱, 執行地點, 委託單位 ) 計劃代號 委託單位計劃單位 ( 計劃代號, 委託單位 ) 計劃地點 ( 計劃代號, 計劃名稱, 執行地點 ) 計劃單位 計劃代號 委託單位 計劃地點 計劃代號 計劃名稱 執行地點 1 政府機關 1 P 1 台北 2 私人企業 2 P 2 台中 3 私人企業 3 P 3 台中 4 私人企業 4 P 4 台南 5 私人企業 5 P 5 高雄 遺失 執行地點 委託單位 這條功能相依 40

41 遺失功能相依的後果 將 計劃地點 的 <5, P 5, 高雄 > 改為 <5, P 5, 台北 > 計劃單位 * 計劃地點 計劃單位計劃代號委託單位 1 政府機關 2 私人企業 3 私人企業 4 私人企業 5 私人企業 計劃單位 * 計劃地點計劃代號計劃名稱執行地點委託單位 1 P 1 台北政府機關 2 P 2 台中私人企業 3 P 3 台中私人企業 4 P 4 台南私人企業 5 P 5 台北私人企業 計劃地點計劃代號計劃名稱執行地點 1 P 1 台北 2 P 2 台中 3 P 3 台中 4 P 4 台南 5 P 5 台北 <1, P 1, 台北, 政府機關 > 和 <5, P 5, 台北, 私人企業 > 違反了 執行地點 委託單位 這條功能相依 41

42 如何確保一個關聯表的分解會保留所有的功能相依性 關聯表綱目 R(X, Y, Z) 包含一組功能相依 {X Y, Y Z, X Z} 先依據遞移法則排出 X Y Z 的順序 從後面的功能相依 Y Z, 依據無遺失聯結分解將其分解成 R 1 (Y, Z) 和 R 2 (R-Z) = R 2 (X, Y) 兩個關聯表綱目, 即可做到無遺失任何功能相依的分解 42

43 無遺失聯結分解 無遺失任何功能相依 計劃 ( 計劃代號, 計劃名稱, 執行地點, 委託單位 ) 執行地點 委託單位地點單位 ( 執行地點, 委託單位 ) 計劃地點 1 ( 計劃代號, 計劃名稱, 執行地點 ) 地點單位 和 計劃地點 1 關聯表 地點單位 執行地點 委託單位 計劃地點 1 計劃代號 計劃名稱 執行地點 台北 政府機關 1 P 1 台北 台中 私人企業 2 P 2 台中 台南 私人企業 3 P 3 台中 高雄 私人企業 4 P 4 台南 5 P 5 高雄 此分解不但是無遺失聯結分解且也能保留 F 中所有的功能相依 43

44 關聯表分解的過程必須保留所有的功能相依, 避免遺失資訊現象產生 第五條設計準則 (Guideline 5) 為 : 在關聯表分解的過程必須保留所有的功能相依, 避免遺失資訊現象產生 44

45 正規化型式 (Normal Form) 第一正規化型式 (First Normal Form, 簡稱 1NF) 第二正規化型式 (Second Normal Form, 簡稱 2NF) 第三正規化型式 (Third Normal Form, 簡稱 3NF) 波亦師 - 高德正規化型式 (Boyce/Codd Normal Form, 簡稱 BCNF) 第四正規化型式 (Fourth Normal Form, 簡稱 4NF) 第五正規化型式 (Fifth Normal Form, 簡稱 5NF) 或投射 - 聯結正規化型式 (Projection-Join Normal Form, 簡稱 PJNF) 45

46 1NF 2NF 3NF BCNF 4NF PJNF 正規化型式 之間的關係 正規化型式 1NF 2NF 3NF BCNF 4NF PJNF 46

47 1NF 定義 當一個關聯表綱目 R 屬於 1NF 時, 則在 R 中, 每一個屬性定義域 (Domain) 的屬性值皆必須是單元值 (Atomic Value) 47

48 未經正規化的 員工 關聯表 員工 身分證號碼 姓名 電話 生日 薪水 A 李鴻章 { , } 61/09/ E 李紹綸 Null 58/11/ F 簡嘉祐 Null 61/07/ F 賴怡君 /07/03 Null F 莊雅玫 /12/ 轉換成 1NF 的 員工 關聯表 員工 身分證號碼 姓名 電話 生日 薪水 A 李鴻章 /09/ A 李鴻章 /09/ E 李紹綸 Null 58/11/ F 簡嘉祐 Null 61/07/ F 賴怡君 /07/03 Null F 莊雅玫 /12/ 範例

49 造成 1NF 更新異常問題的原因 員工計劃 關聯表 員工計劃身分證號碼姓名生日工作時數計劃代號計劃名稱執行地點委託單位 E 李紹綸 58/11/ P 1 台北政府機關 E 李紹綸 58/11/ P 2 台中私人企業 E 李紹綸 58/11/ P 3 台中私人企業 F 簡嘉祐 61/07/ P 2 台中私人企業 F 賴怡君 63/07/ P 1 台北政府機關 F 賴怡君 63/07/ P 4 台南私人企業 F 莊雅玫 62/12/ P 2 台中私人企業 F 莊雅玫 62/12/ P 3 台中私人企業 F 莊雅玫 62/12/ P 5 高雄私人企業 該關聯表綱目的某些非主要屬性與鍵之間具有 部分功能相依 關係存在 49

50 2NF 定義 當一個關聯表綱目 R 屬於 2NF 時, 則 R 必定屬於 1NF, 且在 R 中, 所有的非主要屬性皆 完全功能相依 於 R 的鍵 50

51 範例 8.14 試考慮員工計劃 ( 身分證號碼, 姓名, 生日, 工作時數, 計劃代號, 計劃名稱, 執行地點, 委託單位 ), 功能相依 F 如下 : FD1: 身分證號碼, 計劃代號 工作時數 FD2: 身分證號碼, 計劃名稱 工作時數 FD3: 身分證號碼 姓名, 生日 FD4: 計劃代號 計劃名稱, 執行地點, 委託單位 FD5: 計劃名稱 計劃代號, 執行地點, 委託單位 FD6: 執行地點 委託單位 51

52 尋找鍵 身分證號碼 F + = { 身分證號碼, 姓名, 生日 } 計劃代號 F + = { 計劃代號, 計劃名稱, 執行地點, 委託單位 } 計劃名稱 F + = { 計劃代號, 計劃名稱, 執行地點, 委託單位 } ( 身分證號碼, 計劃代號 ) F+ = { 身分證號碼, 姓名, 生日, 工作時數, 計劃代號, 計劃名稱, 執行地點, 委託單位 } ( 身分證號碼, 計劃名稱 ) F+ = { 身分證號碼, 姓名, 生日, 工作時數, 計劃代號, 計劃名稱, 執行地點, 委託單位 } 鍵 = { 身分證號碼, 計劃代號 } 或 { 身分證號碼, 計劃名稱 } 主要屬性 = 身分證號碼, 計劃代號, 計劃名稱 非主要屬性 = 姓名, 生日, 執行地點, 委託單位, 工作時數 52

53 當主鍵為 { 身分證號碼, 計劃代號 } 時 無遺失聯結分解 員工計劃 ( 身分證號碼, 姓名, 生日, 工作時數, 計劃代號, 計劃名稱, 執行地點, 委託單位 ) FD3: 身分證號碼 姓名, 生日 員工 ( 身分證號碼, 姓名, 生日 ) 員工計劃 1( 身分證號碼, 計劃代號, 工作時數, 計劃名稱, 執行地點, 委託單位 ) FD4: 計劃代號 計劃名稱, 執行地點, 委託單位 計劃 ( 計劃代號, 計劃名稱, 執行地點, 委託單位 ) 參加 ( 身分證號碼, 計劃代號, 工作時數 ) 53

54 分解成三個 2NF 關聯表 轉換成 2NF 的 員工 參加 和 計劃 三個關聯表 員工 身分證號碼 姓名 生日 A 李鴻章 61/09/01 E 李紹綸 58/11/01 F 簡嘉祐 61/07/11 F 賴怡君 63/07/03 F 莊雅玫 62/12/04 參加 身分證號碼 計劃代號 工作時數 E E E F F F F F F 計劃 計劃代號 計劃名稱 執行地點 委託單位 1 P 1 台北 政府機關 2 P 2 台中 私人企業 3 P 3 台中 私人企業 4 P 4 台南私人企業 5 P 5 高雄私人企業 54

55 當主鍵為 { 身分證號碼, 計劃名稱 } 時 無遺失聯結分解 員工計劃 ( 身分證號碼, 姓名, 生日, 工作時數, 計劃代號, 計劃名稱, 執行地點, 委託單位 ) FD3: 身分證號碼 姓名, 生日 員工 ( 身分證號碼, 姓名, 生日 ) 員工計劃 1( 身分證號碼, 計劃代號, 工作時數, 計劃名稱, 執行地點, 委託單位 ) FD5: 計劃名稱 計劃代號, 執行地點, 委託單位 計劃 ( 計劃名稱, 計劃代號, 執行地點, 委託單位 ) 參加 ( 身分證號碼, 計劃名稱, 工作時數 ) 55

56 分解成三個 2NF 關聯表 轉換成 2NF 的 員工 參加 和 計劃 三個關聯表 員工 身分證號碼 姓名 生日 A 李鴻章 61/09/01 E 李紹綸 58/11/01 F 簡嘉祐 61/07/11 F 賴怡君 63/07/03 F 莊雅玫 62/12/04 參加 身分證號碼 計劃名稱 工作時數 E P 1 10 E P 2 8 E P 3 12 F P 2 8 F P 1 12 F P 4 7 F P 2 5 F P 3 11 F P 5 6 計劃 計劃名稱 計劃代號 執行地點 委託單位 P 1 1 台北 政府機關 P 2 2 台中 私人企業 P 3 3 台中 私人企業 P 4 4 台南私人企業 P 5 5 高雄私人企業 56

57 解決 1NF 中更新異常問題 解決 1NF 新增異常問題 資料不一致的問題 試考慮簡嘉祐這位員工新參加 計劃代號 = 1 的計劃 無法儲存相關的資訊 試考慮一個沒有任何員工參與的計劃, 或一位沒有參與任何計劃之員工 解決 1NF 刪除異常問題 會遺失相關的資訊 試考慮賴怡君這位員工要離職 解決 1NF 修改異常問題 資料不一致的問題 試考慮將賴怡君的生日由 63/07/03 改為 63/07/13 57

58 計劃 關聯表更新異常的問題 新增異常 資料不一致的問題 試考慮將列錄 <6, P6, 高雄, 私人企業 > 新增至 計劃 關聯表 無法儲存相關的資訊 試考慮 執行地點 在 板橋 的計劃, 受理的 委託單位 均是為 政府機關 刪除異常 會遺失相關的資訊 試考慮刪除 計劃代號 = 1 的計劃資料 修改異常 資料不一致的問題 試考慮將 計劃代號 = 5 的計劃 執行地點 由 高雄 遷移到 台北 58

59 造成 2NF 更新異常問題的原因 關聯表綱目的某些非主要屬性與鍵之間具有 遞移功能相依 關係存在 59

60 3NF 定義 當一個關聯表綱目 R 屬於 3NF 時, 則 R 必定屬於 2NF, 且在 R 中, 所有的非主要屬性皆 不遞移功能相依 於 R 的鍵 當一個關聯表綱目 R 屬於 3NF 時, 則 R 必定屬於 2NF, 且在 R 中, 每一條功能相依 X A 一定滿足下列其中一個條件 : 功能相依左手邊的屬性 X 是一個超級鍵 (Super Key), 或 功能相依右手邊的屬性 A 是一個主要屬性 (Prime Attribute) 60

61 計劃 關聯表功能相依圖 遞移功能相依 計劃 ( 計劃代號, 委託單位, 計劃名稱, 執行地點 ) p.k. FD4 FD6 61

62 當主鍵為 { 身分證號碼, 計劃代號 } 時 無遺失聯結分解 員工計劃 ( 身分證號碼, 姓名, 生日, 工作時數, 計劃代號, 計劃名稱, 執行地點, 委託單位 ) FD3: 身分證號碼 姓名, 生日 員工 ( 身分證號碼, 姓名, 生日 ) 員工計劃 1( 身分證號碼, 計劃代號, 工作時數, 計劃名稱, 執行地點, 委託單位 ) FD4: 計劃代號 計劃名稱, 執行地點, 委託單位 計劃 ( 計劃代號, 計劃名稱, 執行地點, 委託單位 ) 參加 ( 身分證號碼, 計劃代號, 工作時數 ) FD4: 計劃代號 委託單位 計劃單位 ( 計劃代號, 委託單位 ) 計劃地點 ( 計劃代號, 計劃名稱, 執行地點 ) 62

63 跨越關聯表的功能相依性 計劃單位 和 計劃地點 關聯表外鍵參考與功能相依圖 計劃單位 ( 計劃代號, 委託單位 ) 計劃地點 ( 計劃代號, 計劃名稱, 執行地點 ) p.k. p.k. f.k. 計劃單位 和 計劃地點 關聯表 計劃單位 計劃代號 委託單位 1 政府機關 2 私人企業 3 私人企業 4 私人企業 5 私人企業 計劃地點 計劃代號 計劃名稱 執行地點 1 P 1 台北 2 P 2 台中 3 P 3 台中 4 P 4 台南 5 P 5 高雄 63

64 遺失功能相依造成更新異常的問題 新增異常 資料不一致的問題 刪除異常 試考慮將列錄 <6, P6, 高雄, 私人企業 > 新增至 計劃單位 和 計劃地點 兩個關聯表 會遺失相關的資訊 修改異常 試考慮刪除 計劃代號 = 1 的計劃資料 資料不一致的問題 試考慮將 計劃代號 = 5 的計劃 執行地點 由 高雄 遷移到 台北 64

65 當主鍵為 { 身分證號碼, 計劃代號 } 時 無遺失聯結分解 員工計劃 ( 身分證號碼, 姓名, 生日, 工作時數, 計劃代號, 計劃名稱, 執行地點, 委託單位 ) FD3: 身分證號碼 姓名, 生日 員工 ( 身分證號碼, 姓名, 生日 ) 員工計劃 1( 身分證號碼, 計劃代號, 工作時數, 計劃名稱, 執行地點, 委託單位 ) FD4: 計劃代號 計劃名稱, 執行地點, 委託單位 計劃 ( 計劃代號, 計劃名稱, 執行地點, 委託單位 ) 參加 ( 身分證號碼, 計劃代號, 工作時數 ) FD6: 執行地點 委託單位 地點單位 ( 執行地點, 委託單位 ) 計劃地點 1( 計劃代號, 計劃名稱, 執行地點 ) 65

66 保留所有功能相依 地點單位 和 計劃地點 1 關聯表外鍵參考與功能相依圖 地點單位 ( 執行地點, 委託單位 ) 計劃地點 1( 計劃代號, 計劃名稱, 執行地點 ) p.k. p.k. f.k. 地點單位 和 計劃地點 1 關聯表 地點單位 執行地點 委託單位 台北 政府機關 台中 私人企業 台南 私人企業 高雄 私人企業 計劃地點 1 計劃代號 計劃名稱 執行地點 1 P 1 台北 2 P 2 台中 3 P 3 台中 4 P 4 台南 5 P 5 高雄 66

67 解決 2NF 中更新異常問題 解決 2NF 新增異常問題 資料不一致的問題 試考慮將列錄 <6, P 6, 高雄, 私人企業 > 新增至 計劃 關聯表 無法儲存相關的資訊 試考慮 執行地點 在 板橋 的計劃, 受理的 委託單位 均是為 政府機關 解決 2NF 刪除異常問題 會遺失相關的資訊 試考慮刪除 計劃代號 = 1 的計劃資料 解決 2NF 修改異常問題 資料不一致的問題 試考慮將 計劃代號 = 5 的計劃 執行地點 由 高雄 遷 移到 台北 67

68 範例 8.15 試考慮部門經理 ( 部門代號, 部門名稱, 地點, 經理身分證號碼 ), 功能相依 F 如下 : FD1: 部門代號 部門名稱 FD2: 部門名稱 部門代號 FD3: 部門代號, 地點 經理身分證號碼, 到職日 FD4: 部門名稱, 地點 經理身分證號碼, 到職日 部門經理 關聯表 部門經理 部門代號 部門名稱 地點 經理身分證號碼 到職日 1 資訊 台北 E /08/01 1 資訊 台中 B /08/01 1 資訊 高雄 C /08/01 2 研發 台北 F /02/01 68

69 尋找鍵 部門代號 F + = { 部門代號, 部門名稱 } 部門名稱 F + = { 部門代號, 部門名稱 } ( 部門代號, 地點 ) F+ = { 部門代號, 部門名稱, 地點, 經理身分證號碼, 到職日 } ( 部門名稱, 地點 ) F+ = { 部門代號, 部門名稱, 地點, 經理身分證號碼, 到職日 } 鍵 = { 部門代號, 地點 } 或 { 部門名稱, 地點 } 主要屬性 = 部門代號, 部門名稱, 地點 非主要屬性 = 經理身分證號碼, 到職日 69

70 部門經理 關聯表更新異常的問題 新增異常 無法儲存相關的資訊 刪除異常 試考慮成立第三個部門, 部門名稱 為 會計 部門, 但是我們並不知道該部門的設置 地點 為何 會遺失相關的資訊 修改異常 試考慮 F 這位經理要離職 資料不一致的問題 試考慮將將 資訊 部門改為 電資 部門 70

71 造成 3NF 更新異常問題的原因 關聯表綱目含有許多個候選鍵, 而且這些候選鍵皆至少包含兩個以上屬性所組成, 如果這些候選鍵之間至少具有一個共同屬性時, 則此關聯表中亦可能會有資料重複的情形 因為 3NF 並不考慮主要屬性間的功能相依, 所以對功能相依 X A 而言, 只要 A 是主要屬性, 便滿足 3NF 的定義 在 3NF 的定義中並沒有規範 : 所有的主要屬性之間, 不可以有任何功能相依性存在 71

72 BCNF 定義 當一個關聯表綱目 R 屬於 BCNF 時, 則 R 必定屬於 3NF, 且在 R 中, 所有的主要屬性皆 完全功能相依 於 R 的鍵 當一個關聯表綱目 R 屬於 BCNF 時, 則 R 必定屬於 3NF, 且在 R 中, 每一條功能相依 X A 一定滿足 功能相依左手邊的屬性 X 是一個超級鍵 (Super Key) 這個條件 72

73 當主鍵為 { 部門代號, 地點 } 時 無遺失聯結分解 部門經理 ( 部門代號, 部門名稱, 地點, 經理身分證號碼 ) FD1: 部門代號 部門名稱部門 ( 部門代號, 部門名稱 ) 分公司經理 ( 部門代號, 地點, 經理身分證號碼 ) 部門 和 分公司經理 兩個關聯表 部門部門代號部門名稱 1 資訊 2 研發 分公司經理 部門代號 地點 經理身分證號碼 到職日 1 台北 E /08/01 1 台中 B /08/01 1 高雄 C /08/01 2 台北 F /02/01 73

74 當主鍵為 { 部門名稱, 地點 } 時 無遺失聯結分解 部門經理 ( 部門代號, 部門名稱, 地點, 經理身分證號碼 ) FD2: 部門名稱 部門代號部門 ( 部門名稱, 部門代號 ) 分公司經理 ( 部門名稱, 地點, 經理身分證號碼 ) 部門 和 分公司經理 兩個關聯表 部門部門名稱部門代號 資訊 1 研發 2 分公司經理部門名稱地點經理身分證號碼到職日 資訊台北 E /08/01 資訊台中 B /08/01 資訊高雄 C /08/01 研發台北 F /02/01 74

75 解決 3NF 新增異常問題 無法儲存相關的資訊 解決 3NF 中更新異常問題 試考慮成立第三個部門, 部門名稱 為 會計 部門, 但是我們並不知道該部門的設置 地點 為何 解決 3NF 刪除異常問題 會遺失相關的資訊 試考慮 F 這位經理要離職 解決 3NF 修改異常問題 資料不一致的問題 試考慮將將 資訊 部門改為 電資 部門 75

76 範例 8.16 試考慮郵遞號碼 ( 縣市, 鄉鎮市, 郵遞區號 ), 功能相依 F 如下 : FD1: 縣市, 鄉鎮市 郵遞區號 FD2: 郵遞區號 縣市 郵遞號碼 關聯表 郵遞號碼 縣市 鄉鎮市 郵遞區號 台北市 中正區 100 台北市 中山區 104 基隆市 中正區 202 基隆市 中山區 203 台中市 中區 400 台南市 中區

77 不適合正規化成 BCNF 的功能相依 郵遞號碼 關聯表功能相依圖 郵遞號碼 ( 縣市, 鄉鎮市, 郵遞區號 ) FD1 FD2 77

78 ( 縣市, 鄉鎮市 ) F+ = { 縣市, 鄉鎮市, 郵遞區號 } ( 鄉鎮市, 郵遞區號 ) F+ = { 縣市, 鄉鎮市, 郵遞區號 } 鍵 = { 縣市, 鄉鎮市 } 或 { 鄉鎮市, 郵遞區號 } 主要屬性 = 縣市, 鄉鎮市, 郵遞區號 非主要屬性 = { } 尋找鍵 78

79 郵遞號碼 關聯表更新異常的問題 刪除異常 會遺失相關的資訊 試考慮刪除 台北市中正區 79

80 當主鍵為 { 縣市, 鄉鎮市 } 時 無遺失聯結分解 郵遞號碼 ( 縣市, 鄉鎮市, 郵遞區號 ) FD2: 郵遞區號 縣市縣市號碼 ( 郵遞區號, 縣市 ) 鄉鎮市號碼 ( 鄉鎮市, 郵遞區號 ) 縣市號碼 和 鄉鎮市號碼 兩個關聯表 縣市號碼 郵遞區號 縣市 100 台北市 104 台北市 202 基隆市 203 基隆市 400 台中市 700 台南市 鄉鎮市號碼 鄉鎮市 郵遞區號 中正區 100 中山區 104 中正區 202 中山區 203 中區 400 中區

81 證明 只要一個關聯表 R 只包含兩個屬性 A 和 B 的話, 那麼 R(A, B) 一定是 BCNF 如果 {A, B} 是候選鍵? 如果 A 是候選鍵但 B 不是候選鍵? 如果 A 和 B 兩個都是候選鍵? 81

82 跨越關聯表的功能相依性 縣市號碼 和 鄉鎮市號碼 關聯表外鍵參考與功能相依圖 f.k. 縣市號碼 ( 郵遞區號, 縣市 ) 鄉鎮市號碼 ( 鄉鎮市, 郵遞區號 ) p.k. p.k. p.k. FD2 遺失 FD1: 縣市, 鄉鎮市 郵遞區號 這條功能相依 82

83 不適合正規化成 BCNF 的功能相依格式 當一個 3NF 關聯表 R(A, B, C) 含有下列功能相依格式時 FD1 FD2 R(A, B, C) 分解後的 R 1 和 R 2 關聯表皆符合 BCNF 規範 R 1 (A, B) 和 R 2 (A, C) R 1 (C, B) 和 R 2 (A, B) R 1 (C, B) 和 R 2 (A, C) 但都會遺失 FD1:A, B C 這條功能相依, 甚至第一種和第二種分解方式更可能因為不符合無遺失聯結分解, 而產生許多的偽造列錄 83

84 分解法 V.S. 合成法 分解法 反覆進行將關聯表綱目逐歩針對某一條 功能相依 作無遺失聯結分解, 一直分解到每一個子關聯表至少都能達到 3NF 或 BCNF 的規範 合成法 利用 功能相依集合相等 (Equivalence of Sets of Functional Dependence) 和 最小覆蓋 (Minimal Cover) 的觀念, 事先依據每一條 功能相依 左手邊 (LHS) 的屬性先進行分類, 將 功能相依 左手邊具有共同屬性的 功能相依 先 合併 在一起, 然後再將 合併 之後的每一條 功能相依, 依據每一條 功能相依 所包含的全部屬性, 各自合組成一個新的子關聯表, 如此便可對原關聯表綱目進行分解到 3NF 或 BCNF, 而達到分解之效果 84

85 覆蓋 (Cover) 假設 F 和 G 分別代表兩組不同的功能相依 何謂 F 覆蓋 G? 在 G 中的每一條功能相依皆可以從 F 的功能相依中所推導出來 G 中所有的功能相依皆存在於 F + 中 可以針對 G 中的每一條功能相依 X Y, 去判斷 Y 是否存在於 X F + 中 85

86 功能相依集合相等 何謂 F 和 G 是 功能相依集合相等? 在 G 中的每一條功能相依皆可以從 F 的功能相依中所推導出來, 而且在 F 中的每一條功能相依皆可以從 G 的功能相依中所推導出來 F + = G + F 覆蓋 G 和 G 覆蓋 F 皆成立 86

87 範例 8.17 試考慮一個關聯表綱目 R(A, B, C, D, E), 和其兩組功能相依 F = { A BD, B DE, AB C } 和 G = { A BC, B DE }, 請問 F 和 G 是否相等? F 覆蓋 G 對 F 而言,A F+ = { A, B, C, D, E } 及 B F+ = { B, D, E } 對 G 而言, 屬性 B 和 C 皆在 A F + 中,F 可以推論出 A BC, 同理, 屬性 D 和 E 也都在 B F + 中, F 可以推論出 B DE G 覆蓋 F 對 G 而言,A G+ = { A, B, C, D, E } 及 B G+ = { B, D, E } 對 F 而言, 屬性 B 和 D 皆在 A G + 中,G 可以推論出 A BD, 同理, 屬性 D 和 E 也都在 B F + 中, G 可以推論出 B DE, 屬性 C 也在 (AB) F + 中, G 可以推論出 AB C 87

88 功能相依最小集合 對一組功能相依 F 來說, 假設 F min 為 F 的功能相依最小集合, 功能相依最小集合 F min 又可稱為 最小覆蓋, F min 一定要滿足下列三個條件 : 確保在 F min 中的每一條功能相依右手邊都只能有一個屬性, 皆為標準格式 (Canonical Form) 對於每一條功能相依 X Y 而言,Y 只能是一個屬性而非一組屬性 確保在 F min 中每一條功能相依左手邊不包含無關的屬性或多餘的屬性 (Extraneous Attribute) 不會存在一個功能相依 X Y 及一組屬性 Z, 使得 F - {X Y} {Z Y} = F, 其中,Z X 確保在 F min 中不含有多餘的功能相依 不會存在一個功能相依 X Y, 使得 F - {X Y} = F 88

89 範例 8.18 試考慮範例 8.17 關聯表綱目 R(A, B, C, D, E) 中的功能相依 F = { A BD, B DE, AB C }, 試找出 F 的最小覆蓋 F min F = { A B, A D, B D, B E, AB C } 對於 AB C 而言, 因為 A + = { A, B, C, D, E }, 所以 C A +, 因此 B 是一個無關的屬性, 移除多餘的屬性後可得到 F = { A B, A D, B D, B E, A C } 依據 遞移法則, 我們可以將 A B B D 和 A D 化簡成 A B 和 B D, 因此 A D 是一條多餘的功能相依, 移除多餘的功能相依後可得到 F 的最小覆蓋 F min = { A B, B D, B E, A C } 89

90 從功能相依 F 中消除多餘的屬性 演算法 8.2 Input:F For each functional dependence X A in F do Begin Let A' := X; For each attribute D A' do If A is in (A' - D) + Then A' := A' - D; Replace X A by A' A; End. 90

91 從功能相依 F 中消除多餘的功能相依 演算法 8.3 Input:F For each functional dependence X A in F do Begin Let F' := F - {X A}; If A X F'+ Then F := F'; End. 91

92 最小覆蓋 對一組功能相依 F 而言, 有可能會存在 多個 不同的最小覆蓋 F min 因此資料庫設計師可能會選擇不同的最小覆蓋, 來正規化分解該關聯表, 所以對同一個資料庫而言, 有可能會有許多不同的設計結果 92

93 範例 8.19 試考慮關聯表綱目 R(A, B, C, D), 和其功能相依 F = { AB C, A D, A B, B A, C D }, 試找出 F 的所有最小覆蓋 F min 對於 AB C 而言, 因為 A + = { A, B, C, D}, 且 B + = { A, B, C, D}, 所以 C A +, 且 C B +, 因此屬性 A 或 B 皆可為無關的屬性, 移除多餘的屬性後可得到 F 1 = { A C, A D, A B, B A, C D } 和 F 2 = { B C, A D, A B, B A, C D } 依據 遞移法則, 我們可以將 A C C D 和 A D 化簡成 A C 和 C D, 因此在 F 1 和 F 2 中, A D 均是一條多餘的功能相依, 移除多餘的功能相依後可得到兩組最小覆蓋 F min1 = {A C, A B, B A, 93 C D } 和 F min2 = { B C, A B, B A, C D }

94 演算法 8.4 在無遺失聯結分解和不會遺失任何的功能相依情形下, 將關聯表綱目 R 分解至 3NF Input:R,F Find a minimal cover F min for F; I := 1; For each left-hand-side X of F.D. that appear in F min do Begin create a relational schema R I (X,A 1,...,A n ),X is the key of relational schema R I,where X A 1,..., X A n are F.D. in F min with X as left-hand side; I := I + 1; End; Place all remaining attributes in a single relation schema; If none of the relational schema contains a key of R,Then create one more relation schema that contains R's primary key; 94

95 演算法 8.5 在無遺失聯結分解情形下, 將關聯表綱目 R 分解至 BCNF Input:R,F I := 1; While R is not in BCNF do Begin Find a F.D. X A in R that violates BCNF; create a relational schema R I (X, A); R := R - A; I := I + 1; End; 95

96 範例 8.20 試考慮範例 8.17 關聯表綱目 R(A, B, C, D, E) 中的功能相依 F = { A BD, B DE, AB C }, 試利用合成法將關聯表綱目 R 分解至 3NF 或 BCNF F 的最小覆蓋 F min = { A B, B D, B E, A C } 依據演算法 8.4, 可以將功能相依左手邊具有共同屬性的功能相依先 合併 在一起, 因此可以得到 F min = { A BC, B DE } 利用最小覆蓋 F min 各自合組成一個新的子關聯表, 因此可以得到 R 1 (A, B, C) 和 R 2 (B, D, E) 可直接將含有 遞移功能相依 屬於 2NF 的關聯表綱目 R(A, B, C, D, E), 分解成屬於 BCNF 的 R 1 (A, B, C) 和 R 2 (B, D, E) 兩個子關聯表 96

97 造成 BCNF 更新異常問題的原因 關聯表同時具有兩組以上的多重值屬性時, 在此關聯表的列錄被展開後, 可能還是會有更新異常的問題產生 關聯表綱目包含三組以上屬性時, 假設在這三組屬性當中, 有兩組的屬性是相互獨立而且互不相關的多重值屬性時, 便會有 多重值相依 (Multi-Valued Dependencies,MVD) 的關係, 所以就算是此關聯表已經屬於 BCNF, 但是仍然會有更新異常的問題 97

98 範例 8.21 試考慮未經正規化的 員工 關聯表, 假設每一位員工可能擁有許多支電話, 且每一位員工都可以參與許多不同的計劃, 同時員工的 電話 與 計劃名稱 之間並沒有任何功能相依性存在 未經正規化的 員工 關聯表 員工姓名電話計劃名稱 李鴻章 { , } P 1 賴怡君 { , } { P 1, P 4 } 轉換成正規化的 員工 關聯表 員工 關聯表綱目是屬於 BCNF 員工姓名電話計劃名稱 李鴻章 P 1 李鴻章 P 1 賴怡君 P 1 賴怡君 P 4 賴怡君 P 1 賴怡君 P 4 98

99 新增異常 員工 關聯表更新異常的問題 資料不一致的問題 試考慮 賴怡君 這位員工又參加 P 3 計劃 試考慮 賴怡君 家中又增加一支電話 99

100 直接解決 多重值相依 問題方法 轉換成 4NF 的 員工電話 和 員工計劃 兩個關聯表 員工電話 姓名 電話 李鴻章 李鴻章 賴怡君 員工計劃 姓名 計劃名稱 李鴻章 P 1 賴怡君 P 1 賴怡君 P 4 賴怡君

101 解決 BCNF 中更新異常問題 解決 BCNF 新增異常問題 資料不一致的問題 試考慮 賴怡君 這位員工又參加 P 3 計劃 試考慮 賴怡君 家中又增加一支電話 101

102 MVD 定義 關聯表 R(X, Y, Z), 如果屬性 Y 是多重值相依於屬性 X, 亦即 X Y 成立時, 則對於關聯表 R 中的任意四筆列錄 tuple 1 tuple 2 tuple 3 和 tuple 4 而言, 下列的條件必須成立 : tuple 1 [X] = tuple 2 [X] = tuple 3 [X] = tuple 4 [X] tuple 1 [Y] = tuple 3 [Y] 且 tuple 2 [Y] = tuple 4 [Y] tuple 1 [R-XY] = tuple 2 [R-XY] 且 tuple 3 [R-XY] = tuple 4 [R-XY] 102

103 多重值相依 對於一個擁有三個屬性的關聯表 R(X, Y, Z) 而言, 如果 X Y 成立時,X Z 也一定成立, 其中 Z = R-XY 當關聯表 R(X, Y, Z) 擁有 X Y 這組 多重值相依 時, 如果有兩筆列錄 <x, y 1, z 1 > 和 <x, y 2, z 2 > 同時出現在關聯表 R 中的話, 那麼一定會有另外兩筆列錄 <x, y 1, z 2 > 和 <x, y 2, z 1 > 也會同時出現在關聯表 R 中, 否則便會有資料不一致的問題 對於 X Y 而言, 如果屬性 Y 是屬性 X 的子集合, 或是 X Y = R 時, 那麼我們稱 X Y 是一個 無用的多重值相依 (Trivial MVD) 反之, 我們則稱為一個 有用的多重值相依 103

104 範例 8.22 試考慮 員工 關聯表, 請依據 MVD 定義 找出 員工 關聯表是否存在 多重值相依 X 對應到 姓名 屬性 Y 對應到 計劃名稱 屬性 Z 對應到 電話 屬性 tuple 1 對應到 員工 關聯表的第三列 < 賴怡君, , P 1 > tuple 2 對應到 員工 關聯表的第四列 < 賴怡君, , P 4 > tuple 3 對應到 員工 關聯表的第五列 < 賴怡君, , P 1 > tuple 4 對應到 員工 關聯表的第六列 < 賴怡君, , P 4 > 104

105 依據 MVD 定義 尋找多重值相依 tuple 3 [ 姓名 ] = tuple 4 [ 姓名 ] = tuple 5 [ 姓名 ] = tuple 6 [ 姓名 ] tuple 3 [ 計劃名稱 ] = tuple 5 [ 計劃名稱 ] 且 tuple 4 [ 計劃名稱 ] = tuple 6 [ 計劃名稱 ] tuple 3 [ 電話 ] = tuple 4 [ 電話 ] 且 tuple 5 [ 電話 ] = tuple 6 [ 電話 ] 因此我們可以找到第一條 多重值相依 : 姓名 計劃名稱 105

106 尋找多重值相依 X 對應到 姓名 屬性 Y 對應到 電話 屬性 Z 對應到 計劃名稱 屬性 tuple 1 對應到 員工 關聯表的第三列 < 賴怡君, , P 1 > tuple 2 對應到 員工 關聯表的第五列 < 賴怡君, , P 1 > tuple 3 對應到 員工 關聯表的第四列 < 賴怡君, , P 4 > tuple 4 對應到 員工 關聯表的第六列 < 賴怡君, , P 4 > 106

107 依據 MVD 定義 尋找多重值相依 tuple 3 [ 姓名 ] = tuple 5 [ 姓名 ] = tuple 4 [ 姓名 ] = tuple 6 [ 姓名 ] tuple 3 [ 電話 ] = tuple 4 [ 電話 ] 且 tuple 5 [ 電話 ] = tuple 6 [ 電話 ] tuple 3 [ 計劃名稱 ] = tuple 5 [ 計劃名稱 ] 且 tuple 4 [ 計劃名稱 ] = tuple 6 [ 計劃名稱 ] 因此我們可以找到另一條 多重值相依 : 姓名 電話 所以可證明當 姓名 計劃名稱 成立時, 姓名 電話 也一定成立 107

108 功能相依 V.S. 多重值相依 多重值相依 不一定是定義在擁有三個屬性以上的關聯表上 只含有兩個屬性的關聯表 R(X, Y), 如果屬性 X 和屬性 Y 完全沒有任何功能相依時, 我們也可以視為是一個 退化的多重值相依 (Degenerate MVD): φ X 且 φ Y 多重值相依 也不一定是定義在擁有四筆列錄以上的關聯表上 只含有兩筆列錄的關聯表 R(X, Y, Z), 定義中所指的任意四筆列錄 tuple 1 tuple 2 tuple 3 和 tuple 4 也不一定是要完全不同的列錄 功能相依 只是 多重值相依 一個特例而已 108

109 4NF 定義 當一個關聯表綱目 R 屬於 4NF 時, 則 R 必定屬於 BCNF, 且在 R 中, 對於每一條 有用的多重值相依 X Y 一定滿足 功能相依左手邊的屬性 X 是一個超級鍵 (Super Key) 這個條件 109

110 4NF 的無遺失聯結分解 當關聯表 R 被分解成 R 1 和 R 2 兩個子關聯表時, 若此分解滿足 (R 1 R 2 ) R 1 或 (R 1 R 2 ) R 2 的條件時, 則此分解必定是無遺失聯結分解 110

111 演算法 8.6 在無遺失聯結分解情形下, 將關聯表綱目 R 分解至 4NF Input:R,F I := 1; While R is not in 4NF do Begin Find a nontrivial MVD X Y in R that violates 4NF; create a relational schema R I (X, Y); R := R - Y; I := I + 1; End; 111

112 範例 8.23 試考慮 員工 關聯表, 請依據 多重值相依 和無遺失聯結分解方式, 將 員工 關聯表分解至 4NF 姓名 計劃名稱 和 姓名 電話 兩條 多重值相依, 都是 有用的 多重相依性 依據 4NF 定義來看, 姓名 屬性並不是 員工 關聯表中的超值鍵, 所以 員工 關聯表雖然是屬於 BCNF, 但並不是 4NF 員工姓名電話計劃名稱 李鴻章 P 1 李鴻章 P 1 賴怡君 P 1 賴怡君 P 4 賴怡君 P 1 賴怡君 P 4 112

113 無遺失聯結分解 依據 姓名 電話 這條 多重值相依 利用演算法 8.6 做無遺失聯結分解 員工 ( 姓名, 電話, 計劃名稱 ) 姓名 電話 員工電話 ( 姓名, 電話 ) 員工計劃 ( 姓名, 計劃名稱 ) 員工電話 和 員工計劃 兩個關聯表 員工電話 姓名 電話 李鴻章 李鴻章 賴怡君 員工計劃 姓名 計劃名稱 李鴻章 P 1 賴怡君 P 1 賴怡君 P 4 賴怡君

114 第五正規化型式 從 1NF 到 4NF 的分解方式皆是依據無遺失聯結分解的特性將一個關聯表分解成為兩個關聯表 如果在關聯表 R 中並沒有 功能相依 和 多重值相依 時, 我們便無法利用無遺失聯結分解的特性, 將一個關聯表分解成為兩個關聯表 但還是可能可以依據 聯結相依 將關聯表 R 由 4NF 分解成兩個以上屬於 5NF 的關聯表 在分解成數個子關聯表之後, 依然可以將這些子關聯表經過自然聯結還原得到原來的關聯表, 不會產生 遺失聯結分解 的情形 114

115 範例 8.24 試考慮 學籍 關聯表, 我們假設不同的 學年度, 各 科系 的 班級 數都有可能有所不同 4NF 的 學籍 關聯表 學籍 學年度 科系 班級 94 資管 1A 94 資管 1B 94 電子 1A 95 資管 1A 115

116 遺失聯結分解 學籍 關聯表中, 因為並沒有所屬的 功能相依 和 多重值相依 即使勉強分解成 年度科系 和 科系班級 兩關聯表, 或是 科系班級 和 年度班級 兩關聯表, 還是 年度科系 和 年度班級 兩關聯表, 都會產生 遺失聯結分解 的情形 116

117 遺失聯結分解 年度科系 科系班級 和 年度班級 三個關聯表 年度科系學年度科系 94 資管 94 電子 95 資管 科系班級科系班級 年度科系 * 科系班級 關聯表 資管 資管 電子 有標示著 # 的第 5 筆列錄, 是屬於 偽造的列錄 資訊 1A 1B 1A 年度科系 * 科系班級學年度科系班級 94 資管 1A 94 資管 1B 94 電子 1A 95 資管 1A # 95 資管 1B 年度班級學年度班級 94 1A 94 1B 95 1A 117

118 一分為 N 的分解 1977 年 A. V. Aho, C. Beeri 和 J. D. Ullman 等三位學者發現此一現象 : 我們在分解一個關聯表的過程中, 不一定 都是要將此關聯表一分為二 只要能夠達到 無遺失聯結分解 的目的, 我們便可以將一個關聯表一分為 N J. M. Nicolas 在 1978 年更提出 投射聯結 學籍 = 年度科系 * 科系班級 * 年度班級 是一分為三的分解 如果 <94, 資管 > 出現在 年度科系 關聯表中, < 資管, 1A> 出現在 科系班級 關聯表中, 而且 <94, 1A > 出現在 年度班級 關聯表中, 則 <94, 資管, 1A> 一定會出現在 學籍 關聯表中 118

119 JD 定義 對於一個關聯表 R 而言, 如果此關聯表可以被分解成任意 N 個子關聯表 R 1, R 2,, R n, 而且滿足 R = R 1 * R 2 * * R n 的限制條件時, 此時我們稱此關聯表 R 存在 聯結相依 性 119

120 5NF 定義 當一個關聯表綱目 R 屬於 5NF 時, 則 R 必定屬於 4NF, 且在 R 中的所有滿足聯結相依限制條件 R = R 1 * R 2 * * R n 的各個子關聯表 R i, 1 i n, 一定滿足下列其中一個條件 : 此聯結相依是一個無用的聯結相依 (Trivial Join Dependencies), 亦即其中某一子關聯表 R i 會等於原關聯表 R, 或 對於任意兩個子關聯表 R i 和 R j 而言,1 i,j n,r i 和 R j 兩個子關聯表所具有的共同屬性一定是 R 的候選鍵, 亦即 (R i R j ) R 120

121 結論 此定義說明 5NF 中是不可以存在 聯結相依 性 學籍 關聯表, 因為含有 學籍 = 年度科系 * 科系班級 * 年度班級 這條 聯結相依, 因此 學籍 關聯表並不屬於 5NF 分解之後的三個子關聯表都不含 聯結相依 性了, 因此 年度科系 科系班級 和 年度班級 等三個子關聯表都是屬於 5NF 要找出一個關聯表的所有 聯結相依 並不是一件容易的事, 至目前為止, 仍然沒有一個具體的演算法可以幫助我們辨別某一關聯表是屬於 4NF 而不屬於 5NF 因此我們通常都不會特別去考慮所謂 聯結相依 性的問題 121

122 正規化處理的步驟 Unnormalized Form (UNF) 移除 非簡單型屬性 ( 合成法 ) First Normal Form (1NF) ( 分解法 ) 移除非主要屬性的 部份功能相依 Second Normal Form (2NF) 移除非主要屬性的 遞移功能相依 Third Normal Form (3NF) 移除主要屬性的 部份功能相依 Boyce-Codd Normal Form (BCNF) 移除 多重值相依 Fourth Normal Form (4NF) 移除 聯結相依 Fifth Normal Form (5NF) 122