第 7 章關聯式資料庫的正規化 1 7-1 正規化的基礎 7-2 功能相依 7-3 第一階到第三階正規化型式 7-4 多重值相依與第四階正規化型式 7-5 合併相依與第五階正規化型式
7-1 正規化的基礎 2 7-1-1 關聯表為什麼需要正規化 7-1-2 正規化的型式
7-1 正規化的基礎 - 說明 3 正規化 (Normalization) 是一種標準處理程序來決定關聯表應該擁有哪些屬性, 其目的是建立 良好結構關聯表 (Well-structured Relation) 良好結構關聯表是一種沒有重複資料的關聯表, 而且在新增 刪除或更新資料時, 不會造成錯誤或資料不一致的異常情況
7-1 正規化的基礎 - 目的 4 去除重複性 (Eliminating Redundancy): 就是建立沒有重複資料的關聯表, 因為重複資料不只浪費資料庫的儲存空間, 而且會產生資料維護上的問題 去除不一致的相依性 (Eliminating Inconsistent Dependency): 資料相依是指關聯表中的屬性之間擁有關係, 如果關聯表擁有不一致的資料相依, 這些屬性就會在新增 刪除或更新資料時, 造成異常現象
7-1-1 關聯表為什麼需要正規化 5 關聯式資料庫正規化的目的以一句話來說, 就是避免資料重複 WHY? 因為將不應該放在同一個關聯表的屬性誤放或硬置於同一個關聯表, 形成非自然結合 關聯表擁有非自然結合的屬性, 就會造成資料重複的問題, 稱為 非正規化型式 (Unnormalized Form) 關聯表
非正規化型式 關聯表 6 存在非自然結合的屬性, e.g., {name, birthday}, {title, credit}
非正規化型式 關聯表 - 更新異常 (Update Anomaly) 7 在 Student_Course_Classes 關聯表更新指定的屬性資料 因為資料重複儲存在多筆值組 ( 記錄 ), 需要同時更新多筆值組的資料
非正規化型式 關聯表 - 刪除異常 (Deletion Anomaly) 8 在 Student_Course_Classes 關聯表刪除值組, 可能一併刪除了合法資料 例如 :CS101 和 CS121 課程都有一筆值組 ( 第 1, 2 筆值組 ), 故若刪除掉這 2 筆值組, 則將會遺失了 CS101 和 CS121 課程的資訊 ( 只因沒有人選修!) 如下頁
非正規化型式 關聯表 - 刪除異常 ( 續 ) 9 刪除值組, 可能一併刪除了合法資料
非正規化型式 關聯表 - 新增異常 (Insertion Anomaly) 10 在 Student_Course_Classes 關聯表新增值組和刪除相反, 可能只新增部分值組的資料 例如 : 新增一筆值組, 課程編號是 CS240, 課程名稱為 資料結構, 學分是 3, 但是 sid 出現 Null, 如下 :
7-1-2 正規化的型式 - 階段 11 正規化的處理過程一共分為五個階段, 每一階正規化型式是在處理不同的屬性間資料相依 (Dependency) 的問題, 如下圖所示 :
7-1-2 正規化的型式 - 前三階 12 第一階正規化型式 (First Normal Form, 1NF): 在關聯表刪除多重值屬性, 讓關聯表只擁有單元值屬性 第二階正規化型式 (Second Normal Form, 2NF): 滿足 1NF 且關聯表沒有 部分相依 (Partial Dependency) 第三階正規化型式 (Third Normal Form, 3NF): 滿足 2NF 且關聯表沒有 遞移相依 (Transitive Dependency)
7-1-2 正規化的型式 -BCNF 4 5 階 13 Boyce-Codd 正規化型式 (Boyce-Codd Normal Form, BCNF): 屬於一種廣意的第三階正規化型式, 如果關聯表擁有多個複合候選鍵, 刪除候選鍵間的功能相依 第四階正規化型式 (Fourth Normal Form, 4NF): 滿足 BCNF 且沒有多重值相依 第五階正規化型式 (Fifth Normal Form, 5NF): 滿足 4NF 且沒有合併相依
7-2 功能相依 14 7-2-1 功能相依的定義 7-2-2 功能相依的種類 7-2-3 找出所有的功能相依 7-2-4 阿姆斯壯推論規則 7-2-5 功能相依的推論範例
7-2 功能相依 - 說明 15 功能相依 (Functional Dependency, 簡稱 FD) 是描述關聯表中屬性間的相依關係, 這是關聯式資料庫正規化的基礎 簡單的說, 關聯表正規化的第一步, 就是在關聯表找出所有屬性間的功能相依
7-2 功能相依 - 目的 16 當在關聯表找出所有屬性間的功能相依後, 就可以幫助我們在關聯表找出 : 重複資料 : 不該屬於此關聯表的屬性 候選鍵和主鍵 : 如果關聯表的所有屬性都功能相依於一個或一組屬性, 這個屬性就是候選鍵 (Candidate Key) 或主鍵 (Primary Key)
7-2-1 功能相依的定義 - 定義 17 定義 7.1: 功能相依 (Functional Dependency) 以關聯表 R 為例, 若關聯表 R 擁有屬性 A 與 B(A 與 B 可以是複合屬性 ), 則若屬性 B 功能相依 (Functional dependent) 於 A, 或 A 功能決定 (Functional determines)b, 可表示為 : R.A R.B 或簡寫為 : A B 若關聯表 R 擁有 A B 的功能相依, 則在關聯表 R 的每一對 t1 和 t2 值組且 t1(a) = t2(a), 可以得到 :t1(b) = t2(b)
7-2-1 功能相依的定義 - 說明 18 關聯表中如果有 2 個值組的屬性 A 值是相同, 我們就可以知道屬性 B 的值也一定相同 換句話說, 如果知道屬性 A 的值, 就可以知道屬性 B 的值, 如 : A1 B1 A1 { B1, B2, Bn } { A1, A2,, An } B1 { A1, A2,, An } { B1, B2, Bn } 功能相依屬於一種單方向的關聯,A B 不表示 B A 功能相依是一種屬性間的關係
7-2-1 功能相依的定義 - 範例 19 在 Students 關聯表的一些功能相依範例, 如下 : sid birthday sid GPA sid tel sid { name, birthday } sid { name, birthday, GPA } sid { name, birthday, GPA, tel } { sid, name } { name, birthday, GPA, tel }
20 如果一個屬性或一組屬性可以決定關聯表的所有屬性, 這個屬性就是候選鍵 PS. 應該是超鍵 (Superkeys) 例如 : sid { name, birthday, GPA, tel }
7-2-1 功能相依的定義 - 範例 例子 : R(A, B) (X) A B (O) B A A B 1 4 1 5 3 7 21
7-2-2 功能相依的種類 22 功能相依的種類主要可以分為三種 : 1. 完全相依 (Full Dependency) 2. 部分相依 (Partial Dependency) 3. 遞移相依 (Transitive Dependency)
7-2-2 功能相依的種類 - 範例 23 關聯表範例是 Student_Course_Instructors 關聯表, 如下圖所示 :
7-2-2 功能相依的種類 - 完全相依 24 完全相依是指如果屬性 A( 可能是複合屬性 ) 和 B 是關聯表屬性,B 功能相依於 A, 且 B 沒有功能相依於任何 A 的子集, 則稱 B 完全功能相依於 A 例如 :Student_Course_Instructors 關聯表的完全相依, 如下所示 : sid name c_no title eid instructor eid office { sid,c_no,eid } { name,title,instructor,office }
7-2-2 功能相依的種類 - 部分相依 25 部分相依是指如果 A( 可能是複合屬性 ) 和 B 是關聯表的屬性,B 是功能相依於 A, 如果刪除 A 子集的部分屬性, 仍然不會影響功能相依, 則稱 B 部分功能相依於 A 例如 :Student_Course_Instructors 關聯表的部分相依, 如下所示 : { sid, c_no } name { sid, c_no} title { eid, instructor} office
7-2-2 功能相依的種類 - 遞移相依 26 如果 A B 和 C 是關聯表的屬性,A B 且 B C, 則稱 C 是遞移相依於 A,A C 例如 :Student_Course_Instructors 關聯表的遞移相依, 如下所示 : { sid, c_no, eid } office 上述 office 屬性是遞移相依於 { sid, c_no, eid }, 因為 : { sid, c_no, eid } instructor instructor office
27 7-2-2 功能相依的種類 - 遞移相依
7-2-3 找出所有的功能相依 28 暴力演算法 (Brute Force Algorithm): 這是一種破解密碼常用的演算法, 以作苦工方式嘗試所有可能的密碼組合 ; 也就是說, 在關聯表找出各屬性間的所有可能組合, 然後一一檢查是否符合功能相依, 如果關聯表的屬性很多, 相對就需要花費更多的時間 推論基礎演算法 (Inference-based Algorithm): 因為功能相依可以由其他功能相依來推論出, 換句話說, 推論基礎演算法是從關聯表已知的功能相依, 使用推論規則推論出所有可能的功能相依
7-2-4 阿姆斯壯推論規則 - 說明 29 阿姆斯壯推論規則 (Armstrong s Inference Rule) 可以從某些已知的功能相依推論出其他隱含的功能相依, 這是一種建全且完整的規則, 其意義如下 : 建全 (Sound): 阿姆斯壯推論規則不會導出多餘的功能相依 完整 (Complete): 阿姆斯壯推論規則可以導出所有的功能相依
7-2-4 阿姆斯壯推論規則 - 反身規則 (Reflexitivity Rule) 30 如果屬性 B 是屬性 A 的子集合, 則 A B, 定義如下 : 若 :{ B1, B2,, Bn } { A1, A2,., An } 則 :{ A1, A2,., An } { B1, B2,, Bn } 例如 : { sid, name } { name } 所有屬性都是本身的子集合, 所以 : sid sid name name 和 { sid, name } { sid, name }
7-2-4 阿姆斯壯推論規則 - 擴充規則 (Augmentation Rule) 31 如果 A B 且屬性 C 是屬性 D 的子集合, 則 AD BC, 其定義如下 : 若 :{A1,A2,.,An} {B1,B2,,Bn} 且 {C1,,Cn} {D1,...,Dn} 則 :{A1,A2,.,An,D1,,Dn} {B1,B2,,Bn,C1,...,Cn} 例如 :sid name 且 { GPA } 是 { birthday, GPA } 子集合, 則可以得到 :{ sid, birthday, GPA } { name, GPA }
7-2-4 阿姆斯壯推論規則 - 遞移規則 (Transitivity Rule) 32 如果 A B 且 B C, 則 A C, 其定義如下 : 若 :{A1,,An} {B1,,Bn} 且 {B1,,Bn} {C1,...,Cn} 則 :{ A1,..., An } { C1,..., Cn } 例如 :sid instructor 且 instructor office, 則可以得到 : sid office
7-2-4 阿姆斯壯推論規則 - 分解規則 (Decomposition Rule) 33 如果 A BC, 則 A B 且 A C, 其定義如下 : 若 :{ A1,, An } { B1,, Bn, C1,..., Cn } 則 :{A1,...,An} {B1,...,Bn} 且 {A1,...,An} {C1,...,Cn} 例如 :sid { name, birthday }, 則可以得到 : sid name 且 sid birthday
7-2-4 阿姆斯壯推論規則 - 聯集規則 (Union Rule) 34 如果 A B 且 A C, 則 A BC, 其定義如下 : 若 :{A1,,An} {B1,,Bn} 且 {A1,,An} {C1,...,Cn} 則 :{ A1,..., An } { B1,..., Bn, C1,..., Cn } 例如 :sid name 且 sid birthday, 則可得 : sid { name, birthday }
7-2-5 功能相依的推論範例 - 範例 35 現在只需使用推論規則, 就可以從關聯表現有的功能相依推論出其他的功能相依 例如 : 關聯表已經擁有 3 條功能相依 (FD), 如下所示 : 1: AB D 2: BD E 3: E C 請使用上述 3 條功能相依推論出 AB C
7-2-5 功能相依的推論範例 - 過程 步驟使用規則結果 1 FD 1 : AB D FD 4 : AB D 2 AB AB 使用反身規則 FD 5 : AB AB 3 以 FD 5 :AB AB 使用分解規則 FD 6 : AB B 4 以 FD 4 :AB D 和 FD 6 :AB B 使用聯集規則 FD 7 : AB BD 5 以 FD 7 :AB BD 和 FD 2 : BD E 使用遞移規則 FD 8 : AB E 6 以 FD 8 :AB E 和 FD 3 : E C 使用遞移規則 AB C 36
7-2-5 功能相依的推論範例 - 改寫 步驟使用規則結果 1 因為 B AB 使用反身規則 FD 4 : AB B 2 以 FD 1 :AB D 和 FD 4 :AB B 使用聯集規則 FD 5 : AB BD 3 以 FD 5 :AB BD 和 FD 2 : BD E 使用遞移規則 FD 6 : AB E 4 以 FD 6 :AB E 和 FD 3 : E C 使用遞移規則 Goal: AB C 37
7-2-5 功能相依的推論範例 - 另解 FD 1 : AB D FD 2 : BD E FD 3 : E C Goal: AB C 步驟使用規則結果 1 2 FD 1 : AB D 兩邊加上 B ( 擴充規則 ) FD 4 : AB BD, FD 2 : BD E ( 遞移規則 ) FD 4 : AB BD FD 5 : AB E 3 以 FD 5 :AB E 和 FD 3 : E C ( 遞移規則 ) Goal: AB C 38
7-3 第一階到第三階正規化型式 39 7-3-1 第一階正規化型式 1NF 7-3-2 第二階正規化型式 2NF 7-3-3 第三階正規化型式 3NF 7-3-4 Boyce-Codd 正規化型式 BCNF 7-3-5 符合 Boyce-Codd 正規化型式的範例
7-3-1 第一階正規化型式 (1NF)- 定義 40 定義 7.2: 關聯表 R 符合第一階正規化型式 (First Normal Form;1NF) 是指關聯表的每一個定義域 (Domain) 都是單元值 (Atomic Value) 且只能是單元值, 也就是刪除多重值屬性型態 (Multivalue Attribute Type) 與複合屬性型態 (Composite Attribute Type) 的屬性 簡單的說, 上述定義是指關聯表沒有多重值和複合屬性
7-3-1 第一階正規化型式 範例 41 例如 : 在 Students 關聯表儲存學生的選課資料, 主鍵是學號 sid, 如下圖所示 :
7-3-1 第一階正規化型式 正規化方法一 42 方法一 : 分割成不同的關聯表 關聯表違反 1NF, 一階正規化可以將這些多重值屬性連同主鍵分割成新關聯表, 如下圖所示 :
7-3-1 第一階正規化型式 正規化方法二 43 方法二 : 分割成值組 1NF 關聯表的每一個屬性只能儲存單元值, 所以一階正規化可以將多重值屬性改成重複值組, 屬性的每一個多重值新增一筆值組, 如下圖所示 :
7-3-1 第一階正規化型式 正規化方法三 44 方法三 : 分割成不同屬性 一階正規化還可以將多重值屬性配合虛值 (Null) 新增為關聯表的多個屬性, 不過其先決條件是多重值的個數是有限的 例如 : 一位學生規定只能修兩門課程,Students 關聯表可以使用 2 組屬性儲存選課資料的課程編號與名稱, 雖然符合 1NF, 但是若學生選課數不只兩門, 就會產生資料無法新增的異常情況
1NF 正規化方法三 -- 多重值屬性配合 null 值新增為關聯表的多個屬性 學號姓名手機 1 手機 2 手機 3 S001 Tom 0921-000000 0922-000000 NULL S002 John 0923-000000 NULL NULL S003 Mary 0924-000000 0925-000000 0926-000000 45
7-3-2 第二階正規化型式 (2NF)- 定義 46 定義 7.3: 關聯表 R 符合第二階正規化型式 (Second Normal Form;2NF) 是指關聯表符合 1NF, 而且所有非主鍵 (Primary Key) 的屬性都完全相依 (Fully Dependency) 於主鍵, 也就是刪除所有部份相依的屬性 簡單的說, 上述定義是指關聯表中, 不是主鍵的屬性需要完全相依於主鍵 ; 反過來說, 就是刪除關聯表所有部分相依 (Partial Dependency) 的屬性
7-3-2 第二階正規化型式 - 範例 47 Students 關聯表執行一階正規化後, 已經分割成 Students 和 Classes 關聯表, Classes 關聯表繼續第二階正規化, 如下圖 :
7-3-2 第二階正規化型式 功能相依 48 Classes 關聯表的主鍵是 (sid, c_no, eid), 關聯表已知的功能相依, 如下所示 : FD1:{ sid, c_no, eid } room FD2:c_no title FD3:eid { instructor, office }
7-3-2 第二階正規化型式 功能相依 ( 續 ) 49 所以 title 是部分相依於主鍵 { sid, c_no, eid }, 因為 FD2: c_no title 同理, instructor, office 也是部分相依於主鍵, 因為 FD3:eid { instructor, office }
7-3-2 第二階正規化型式 50 正規化方式 部分相依表示有其他資料的子集合, 應獨立成新關聯表 1. 將功能相依的兩邊的屬性獨立成新關聯表 2. 功能相依的左邊 ( 決定屬性 ) 是新關聯表的主鍵 3. 原關聯表必須有連外鍵 (FK) 指向新關聯表的主鍵
7-3-2 第二階正規化型式 正規化結果 51
7-3-3 第三階正規化型式 (3NF)- 定義 52 定義 7.4: 關聯表 R 符合第三階正規化型式 (Third Normal Form;3NF) 是指關聯表符合 2NF, 而且所有非主鍵 (Primary Key) 的屬性都只能功能相依 (Functional Dependency) 於主鍵 ; 沒有功能相依於其他非主鍵的屬性, 即刪除遞移相依的屬性 簡單的說, 上述定義是指關聯表中不屬於主鍵的屬性都只能功能相依於主鍵, 而不能同時功能相依於其他非主鍵的屬性, 也就是刪除關聯表所有遞移相依 (Transitive Dependency) 的屬性
7-3-3 第三階正規化型式 範例 53 例如 : 執行 Instructors 關聯表的第三階正規化, 如下圖所示 :
7-3-3 第三階正規化型式 正規化結果 54 eid office 是遞移相依, 故須排除 o_no office
7-3-4 Boyce-Codd 正規化型式 (BCNF) - 條件 55 Boyce-Codd 正規化 (BCNF) 是在處理關聯表擁有多個候選鍵的特殊情況 Boyce-Codd 正規化處理的關聯表至少擁有二個或更多個候選鍵, 而且這兩個候選鍵是 : 1. 複合候選鍵 2. 在複合候選鍵之間擁有重疊屬性, 也就是說至少擁有一個相同屬性 如果關聯表沒有上述情況,3NF 就等於 BCNF
7-3-4 Boyce-Codd 正規化型式 定義 56 定義 7.5: 關聯表 R 符合 BCNF 正規化型式 (Boyce- Codd Normal Form;BCNF) 是指關聯表所有主要的功能相依 A B,A 一定且只可以是候選鍵 (Candidate Keys), 也就是刪除只功能相依候選鍵部分屬性的功能相依 簡單的說,BCNF 是指關聯表中, 主要功能相依 A B 的左邊屬性 A ( 稱為 決定屬性, Determinant) 一定是候選鍵或主鍵 如下所示 : 候選鍵或主鍵 其他屬性
7-3-4 Boyce-Codd 正規化型式 範例 57 例如 : 學生身份證字號 (SSN) 與成績 (grade) 的 Students 關聯表, 如下圖所示 : Students 關聯表擁有兩個候選鍵, 如下所示 : ( sid, c_no ) ( SSN, c_no )
7-3-4 Boyce-Codd 正規化型式 範例 ( 續 ) 58 兩個候選鍵擁有重疊屬性 c_no, 在候選鍵之間擁有功能相依 SSN sid, 因為身份證字號可以決定學生編號, 如下所示 : { sid, c_no } SSN SSN sid 上述 SSN 屬性可以決定 sid 屬性, 不過 SSN 只是候選鍵的一部分, 且不是超鍵 (Superkey), 所以違反 BCNF
59 7-3-4 Boyce-Codd 正規化型式 範例 ( 續 ) Students 符合 2NF 及 3NF, 但是 主鍵的一部分功能相依於非主鍵屬性 R (sid, cno, SSN, grade)
7-3-4 Boyce-Codd 正規化型式 正規化結果 60 例如 : 執行前述的關聯表 Students 關聯表的 BCNF 正規化, 如下圖所示 :
7-3-4 Boyce-Codd 正規化型式 正規化結果 ( 續 ) 61 因為 Students 關聯表的 sid 和 SSN 兩個屬性間相互擁有功能相依, 如下所示 : sid SSN SSN sid 所以執行 BCNF 正規化分割 Students 關聯表時, 也可以使用 SSN 屬性進行分割, 如下圖所示 :
7-3-5 符合 Boyce-Codd 正規化型式的 範例 62 Boyce-Codd 正規化型式的條件是關聯表至少擁有二個或多個複合候選鍵 不過關聯表擁有兩個複合候選鍵, 並不表示一定需要進行 BCNF 正規化, 兩個複合候選鍵的關聯表仍可以符合 BNCF
7-3-5 符合 Boyce-Codd 正規化型式的 範例 ( 範例 1) 63 例如 : 學生期末考座位的 Exams 關聯表, 因為期末考分成多天進行考試, 所以各科的考試座位可能不同, 如下圖所示 :
7-3-5 符合 Boyce-Codd 正規化型式的 範例 ( 範例 2) 64 在 Exams 關聯表一共有兩個候選鍵, 如下所示 : ( sid, c_no ) ( seat_no, c_no ) 兩個候選鍵擁有重疊屬性 c_no, 不過在候選鍵之間並沒有功能相依 seat_no sid 在 Exams 關聯表擁有的功能相依清單, 如下所示 : { sid, c_no } seat_no { seat_no, c_no } sid 上述 2 個功能相依的決定屬性都是候選鍵, 符合 BCNF 定義 所以,Exams 關聯表雖然擁有 2 組候選鍵, 但是它不但符合 3NF, 而且符合 BCNF
複習 -2NF 65 去除部分相依於 PK R(A,B,C,D,E) 所有非鍵值屬性 ( 例 :C, D, E) 必須功能相依於主鍵的全部 ({A, B}), 但不限制非鍵值屬性 (E) 相依於其他非鍵值屬性 (D) R (A, B, C, D, E)
複習 -3NF 66 去除遞移相依 滿足 2NF 且所有非鍵值屬性 ( 例 :C, D, E) 必須只功能相依於主鍵 ({A,B}), 但不限制非鍵值屬性 (C) 也能功能決定一些在候選鍵中的屬性 (B) R (A, B, C, D, E) 不討論 trivial ( 瑣碎的, 普通的 )FD: S 1 S 2 若 S 2 S 1, 例 :C C
複習 -BCNF(1) 67 滿足 3NF, 且 FD 中所有決定屬性皆為候選鍵 ( 超鍵 ), 但 trivial FD 不在討論範圍內! R (A, B, C, D, E)
複習 -BCNF(2) 68 證明 : 若 R 有複合主鍵, 且主鍵的一部分功能相依於非主鍵欄位 (R 違反 BCNF), 則 R: 1. 擁有二個或更多個候選鍵 ; 2. 複合候選鍵之間擁有重疊屬性 例 : 違反 BCNF: R(A, B, C, D, E) 且 C B 1. AC AB ( 擴充性 ), 2. AC 為另一個候選鍵!( 遞移性 ). 3. A 為重疊屬性 練習
7-4 多重值相依與第四階正規化型 式 69 7-4-1 多重值相依 (Multi-valued Dependency) 7-4-2 第四階正規化型式 4NF
7-4 多重值相依與第四階正規化型 式 70 第四階正規化型式的基礎是 多重值相依 (Multi-valued Dependency, MVD), 這是 1977 年 R. Fagin 所提出, 屬於功能相依的廣義定義, 即 : 功能相依是多重值相依的一種特例 多重值相依的先決條件是關聯表擁有 3 個 * 以上的屬性 * 不盡然
7-4-1 多重值相依 ( 範例 ) 71 例如 : 一門課可能由多位講師授課, 每一門課可以使用多本教課書, 儲存這些資料的 Course_Instructor_Textbook 關聯表, 簡稱為 CIT, 如下圖所示 :
7-4-1 多重值相依 ( 說明 ) 72 CIT 關聯表的屬性仍然有類似功能相依的相依情況 例如 : 對於每一門課, 存在課程相關教課書的子集合 ; 同樣的, 對於每一門課, 存在此課程相關講師的子集合, 如下所示 : 教課書 textbook 相依於課程 course( 在此的相依不是指功能相依 ) 講師 instructor 相依於課程 course( 在此的相依不是指功能相依 ) 上述相依關係就是 多重值相依 (Multi-valued Dependency), 以雙箭頭表示寫成 : course textbook course instructor
7-4-1 多重值相依 ( 定義 ) 73 定義 7.6: 多重值相依 (Multi-valued Dependency) 以關聯表 R 為例, 若關聯表 R 是由屬性 A B 與 C 組成 R(A, B, C),A B 與 C 可以是複合屬性, 我們可以說屬性 B 多重值相依 (Multi-valued Dependent) 於 A, 或 A 多重決定 (Multidetermines) 於 B, 寫成 : R.A R.B 或簡寫成 : A B 若關聯表 R 擁有 A B 多重值相依, 則表示存在 t1 和 t2 值組且 t1(a) = t2(a), 且另外存在二個值組 t3 和 t4 滿足下列條件 : t1(a) = t2(a) = t3(a) = t4(a) t3(b) = t1(b) t3(c) = t2(c) t4(b) = t2(b) t4(c) = t1(c)
MVD: A B 74 t1 t2 A B C 必存在t3 t4
7-4-1 多重值相依 ( 定義說明 ) 75 以 CIT 關聯表為例, 因為關聯表 CIT 擁有 course textbook(a B) 多重值相依, 所以在關聯表可以找到交換 instructor 屬性的 2 對值組 t1 t2 和 t3 t4, 如下圖所示 :
7-4-1 多重值相依 ( 異常狀況 ) 76 在 CIT 關聯表擁有很多重複資料, 這些重複資料會導致新增或更新異常 例如 : 新增講師陳慶新教授程式語言這門課, 雖然只有一門課, 但是需要同時新增 3 筆值組, 每一個值組是一本教課書, 否則就會產生資料不一致的問題
7-4-1 多重值相依 ( 推論規則 1)* 77 多重值相依的推論規則是 1977 年 C. Beeri R. Fagin 和 J. H. Howard 擴充自阿姆斯壯推論規則, 其中前 3 個推論規是源自功能相依, 如下所示 : FD 反身規則 (FD Reflexitivity): 如果屬性 B 是屬性 A 的子集合, 則 A B FD 擴充規則 (FD Augmentation): 如果 A B 且屬性 C 是屬性 D 的子集合, 則 AD BC FD 遞移規則 (FD Transitivity): 如果 A B 且 B C, 則 A C MVD 擴充規則 (MVD Augmentation): 如果 A B 且屬性 C 是屬性 D 的子集合, 則 AD BC MVD 遞移規則 (MVD Transitivity): 如果 A B 且 B C, 則 A C B
7-4-1 多重值相依 ( 推論規則 2)* 78 MVD 互補規則 (MVD Complementation): 如果 A B, 則 A (R A B) MVD 聯集規則 (MVD Union): 如果 A B 且 A C, 則 A BC MVD 分解規則 (MVD Decomposition): 如果 A BC, 則 A B C,A B - C 且 A C - B 複製規則 (Replication 或稱為升級 Promotion): 如果 A B, 則 A B 合併規則 (Coalescence): 如果 A B 且 C D,D 是 B 的子集合,C 與 B 的交集是空集合, 則 A D 偽裝遞移規則 (Pseudotransitivity): 如果 A B 且 CB D, 則 CA D - CB 混合偽裝遞移規則 (Mixed Pseudotransitivity): 如果 A B 且 AB C, 則 A C - B
7-4-2 第四階正規化型式 4NF( 定義 ) 79 定義 7.7: 關聯表 R 符合第四階正規化型式 (Fourth Normal Form;4NF) 是指關聯表符合 BCNF, 而且所有多重值相依 (Multi-valued Dependency) 都是功能相依, 也就是刪除多重值相依 簡單的說, 上述定義是指關聯表沒有存在的多重值相依, 只有功能相依
7-4-2 第四階正規化型式 (4NF) - 正規化 80 CIT 關聯表擁有 2 個多重值相依, 如下所示 : course textbook course instructor 執行第四階正規化, 只需將多重值相依 A B 兩邊的屬性獨立成關聯表即可, 如下圖所示 :
4NF 補充範例 -1 81 R( 貸款編號, 客戶, 居住地區, 居住城市 ) 客戶 居住地區, 居住城市 貸款編號 客戶 居住地區 居住城市 L-23 Bob 西屯區 台中 L-23 Bob 信義區 台北 L-93 Alice 北屯區 台中
4NF 補充範例 -2 82 客戶 居住地區, 居住城市 客戶 居住地區 居住城市 貸款編號 Bob 西屯區 台中 L-23 Bob 信義區 台北 L-23 Bob 西屯區 台中 L-25 Bob 信義區 台北 L-25
4NF 補充範例 -3 83 客戶 貸款編號 客戶 貸款編號 居住地區 居住城市 Bob L-23 西屯區 台中 Bob L-23 信義區 台北 Bob L-25 西屯區 台中 Bob L-25 信義區 台北
4NF 補充範例 -4 84 R( 貸款編號, 客戶, 居住地區, 居住城市 ) 客戶 居住地區, 居住城市 或 : 客戶 貸款編號 分割成 : R1( 客戶, 居住地區, 居住城市 ) R2( 客戶, 貸款編號 )
*7-5 合併相依與第五階正規化型式 85 7-5-1 合併相依 (Join Dependency) 7-5-2 第五階正規化型式 5NF
7-5 合併相依與第五階正規化型式 86 關聯式資料庫正規化分析的第一階到第三階正規化型式是使用功能相依找出關聯表的重複資料 在第四階正規化型式的基礎是多重值相依, 這是功能相依的擴充 第五階正規化型式的基礎則是擴充多重值相依的 合併相依 (Join Dependency) 簡單的說, 合併相依是指當關聯表分割成 3 個或更多關聯表後, 一定能夠透過多次合併運算恢復成原來的關聯表
7-5-1 合併相依 ( 範例 ) 87 例如 : 每個科系 (department) 開多門課, 課程 (course) 可以給多位學生修, 學生 (student) 可以修不同科系的課, 這 3 個屬性循環關聯儲存在同一個關聯表 DCS, 如下圖所示 :
7-5-1 合併相依 ( 說明 ) 88 將 DCS 分割成 2 個關聯表, 看看是否可以解決資料重複的問題, 分割方式有多種組合, 如下所示 : DC (department, course) CS (course, student) 或 : DC (department, course) DS (department, student) 以第一種分割方式為例, 在分割成 2 個關聯表 DC 和 CS 後, 可以看到減少一些資料重複, 不過如果將這 2 個關聯表以自然合併進行結合, 可以發現多出幾筆值組, 和原始關聯表不同
7-5-1 合併相依 ( 自然合併 ) 89 CH5-3-2 合併運算
( 參考 ) 5-3-2 合併運算 - 說明 90 合併運算是在兩個關聯表中, 使用具有相同定義域 (Domain) 的屬性為條件合併兩個關聯表, 相當於先執行基本運算的卡笛生乘積運算, 再配合選擇運算取出所需值組的關聯表 合併運算滿足交換律和結合律, 合併運算可以分為數種 : θ 合併 Equijoin 合併 自然合併 外部合併
( 參考 )5-3-2 合併運算 - 自然合併 ( 語法 ) 91 自然合併是一種使用主鍵和外來鍵為條件的合併方式, 其隱含的條件是主鍵等於外來鍵條件的 Equijoin 合併, 所以自然合併屬於一種特殊格式的 Equijoin 合併, 其基本語法和定義如下所示 : R S = π r s (R r = s S) 上述語法並沒有指明條件, 這是因為預設使用主鍵和外來鍵對應的條件, 即所有共通屬性值 (All Common Attributes) 都需要相等 自然合併的執行結果關聯表綱要的共通屬性部分在運算結果中只會顯示一次
( 參考 ) 5-3-2 合併運算 - 自然合併 ( 範例 ) 92 例如 :Students 和 Departments 關聯表的自然合併運算式, 如下所示 : Result = Students Departments SELECT * FROM Students INNER JOIN Departments ON Students.d_no = Departments.d_no
7-5-1 合併相依 ( 投影分割 ) 93 將關聯表使用投影運算分割成 3 個關聯表 :DC (department, course) CS (course, student) SD (student, department), 如下圖所示 :
7-5-1 合併相依 ( 自然合併 ) 94 關聯表可以分割成 3 個或更多個關聯表, 然後透過多次合併運算恢復成原始關聯表, 就稱為 合併相依 (Join Dependency)
7-5-1 合併相依 ( 定義 ) 95 定義 7.8: 合併相依 (Join Dependency) 以關聯表 R 為例, 若關聯表 R 等於自然合併運算 R 1 R 2, R n,r i 是關聯表 R 屬性的子集合, 我們可以說, 關聯表 R 滿足合併相依 (R 1, R 2,, R n ) 關聯表 DCS 可以使用投影運算分割成 DC CS 和 SD 三個關聯表, 執行 DC CS SD 自然合併運算就可以還原成原始 DCS 關聯表, 所以關聯表 DCS 擁有合併相依
7-5-1 合併相依 ( 異常狀況 1) 96 如果關聯表擁有合併相依, 在新增和刪除時就會產生異常情況, 例如 :DCS 關聯表擁有合併相依, 如下圖所示 : 在 DCS 關聯表新增一筆值組 { 資管系, 101, 江小魚 }, 如右圖所示 :
7-5-1 合併相依 ( 異常狀況 2) 97 將上述關聯表以投影運算分割成 DC CS 和 SD 三個關聯表, 再將它使用合併運算結合起來, 可以發現多了一筆值組, 如下圖所示 : 如果新增一筆值組 { 資訊系, 101, 江小魚 }, 在分割和合併後, 就不會多出一筆值組
7-5-2 第五階正規化型式 5NF( 定義 ) 98 定義 7.9: 關聯表 R 符合第五階正規化型式 (Fifth Normal Form;5NF), 也稱為投影 - 合併正規化型式 (Project-Join Normal Form;PJNF), 這是指關聯表符合 4NF, 且所有合併相依 (R1, R2,, Rn) 的關聯表屬性子集 Ri, 都是關聯表 R 的超鍵 (Superkey), 也就是刪除合併相依 上述定義是指關聯表沒有存在合併相依 以上一節的 DCS 關聯表為例,DCS 關聯表擁有合併相依, 所以不符合 5NF
7-5-2 第五階正規化型式 5NF( 正規化 ) 99 DCS 關聯表擁有合併相依, 可以使用投影運算進行再次的分割, 並不符合 5NF, 所以需要執行第五階正規化, 使用投影運算分割成 3 個關聯表, 如下圖所示 :
練習 100 給定關聯表 R 和已知的功能相依分別如下 : a) R(A, B, C, D, E),FD: B C, D E b) R(A, B, C, D, E, F),FD: EF B, D C c) R(A, B, C, D),FD: A B, BC D, A C 請分別分割 (a)(b)(c) 中的關聯表 R, 得到一組皆符合 BCNF 的關聯表綱要 ( 需標明主鍵 )