【正文】 1(A, D) a1 b12 b13 a4 b15 R2(A, B) a1 a2 b13 a4 b25 R3(B, E) b31 a2 b13 a4 a5 R4(C, D, E) b41 b42 a3 a4 a5 R5(A, E) a1 b52 b13 a4 a5 關系模式的分解算法 ?DE?C A B C D E R1(A, D) a1 b12 a3 a4 b15 R2(A, B) a1 a2 a3 a4 b25 R3(B, E) b31 a2 a3 a4 a5 R4(C, D, E) b41 b42 a3 a4 a5 R5(A, E) a1 b52 a3 a4 a5 關系模式的分解算法 ?CE?A A B C D E R1(A, D) a1 b12 a3 a4 b15 R2(A, B) a1 a2 a3 a4 b25 R3(B, E) a1 a2 a3 a4 a5 R4(C, D, E) a1 b42 a3 a4 a5 R5(A, E) a1 b52 a3 a4 a5 關系模式的分解算法 ? 定理 若 U1?U2 ? U1(或 U2)，則 r =∏U1(r) ? ∏U2(r) 。 關系模式的分解算法 ?保持函數(shù)依賴的分解 ? 定義 若 F+ = ( Fi)+， 則稱 R U , F 的分解 ? = {R1U1 , F1 , … , R nUn , Fn}保持函數(shù)依賴。 如表（職工，級別，工資）的分解， 分解一：（職工，工資），（工資，級別） 丟失函數(shù)依賴，職工 ?級別 分解二：（職工，級別），（工資，級別） 保持函數(shù)依賴。 ?ni 1?關系模式的分解算法 ?算法：（達到 3NF且保持函數(shù)依賴的分解） ⒈ 對 RU， F 中的函數(shù)依賴集 F進行“極小化處理”（處理后得到的依賴集仍記為 F）。 ⒉找出不在 F中出現(xiàn)的屬性，將它們構成一個關系模式，并從 U中去掉它們 (剩余屬性仍記為 U)。 ⒊若有 X?A? F ，且 XA=U， 則 ? ={R}，算法終止。 關系模式的分解算法 ⒋ 否則，對 F按具有相同左部的原則進行分組（設為 k組），每一組函數(shù)依賴 Fi‘所涉及的全部屬性為 Ui。若 Ui ? Uj （ i≠j） ，就去掉 Ui 。由于經(jīng)過了步驟 2，故 U = Ui ，于是 ? = {R1U1 , F1 , … , R kUk , Fk}是 RU , F的一個保持函數(shù)依賴的分解，并且每個 RiUi , Fi ?3NF。 ?ni 1?關系模式的分解算法 ? 示例 U={SNO， DEPT， HEAD， CNO， G} F={SNO?DEPT， SNO?HEAD， DEPT?HEAD，(SNO,CNO)?G} ⒈ FC={SNO?DEPT， DEPT?HEAD ，(SNO,CNO)?G} ⒉ 分組 {(SNO， DEPT)， SNO?DEPT} {(DEPT， HEAD)， DEPT?HEAD} {(SNO， CNO， G)， (SNO,CNO)?G} 關系模式的分解算法 ? 示例： R（ ABC； A?C， B?C） ⒈按保持無損連接分解 碼為 AB，分解為 {AC； A?C}， {AB}。 丟失了函數(shù)依賴 B?C。 ⒉按保持函數(shù)依賴分解 進行分組， {AC； A?C}， {BC； B?C}。 分解是有損的。 A B C 1 1 1 2 1 1 2 2 1 A C 1 1 2 1 B C 1 1 2 1 A B C 1 1 1 1 2 1 2 1 1 2 2 1 關系模式的分解算法 ? 算法：（達到 3NF且同時保持無損連接與函數(shù)依賴的分解） 設 X為 RU , F的碼，設 ? = {R1U1 , F1 , … , RkUk , Fk}是 RU , F的一個保持函數(shù)依賴的 3NF分解。令 τ = ?∪ {R? X， FX} 若有某個 Ui， X ? Ui，則 將 R? X， FX從 τ去掉。 τ = ?∪ R? X， FX即為所求的解。 關系模式的分解算法 ? 示例： 求 R（ ABC； A?C， B?C）的保持無損連接和函數(shù)依賴的 3NF分解。 ⒈按保持函數(shù)依賴分解 進行分組， ?={{AC； A?C}， {BC； B?C}}。 ⒉鍵為 AB τ = ?∪ {AB} 最后的分解為： {{AC； A?C}， {BC； B?C}， {AB}} 關系模式的分解算法 ?算法：（達到 BCNF無損連接分解算法） 給定關系模式 RU , F ， ⒈令 ? = {RU , F} ⒉ 檢查 ?中各關系模式是否屬于 BCNF，若是，則 算法終止。 ⒊設 ? 中 RiUi , Fi不屬于 BCNF， 則存在函數(shù)依賴 X?A? ，且 X不是 Ri的碼， 則 XA是 Ri的真子集，將 Ri分解為 ?={S1， S2}， 其中 US1 = XA， US2 = Ui ? {A} 以 ?代替 Ri ，返回到 ⒉ ?iF關系模式的分解算法 ? 示例： U={SNO， DEPT， HEAD， CNO， G} Fc={SNO?DEPT， DEPT?HEAD， (SNO,CNO)?G} ⒈ U1={DEPT， HEAD} , F1={DEPT?HEAD} U2={SNO, DEPT, CNO, G}, F2={SNO?DEPT, (SNO,CNO)?G} ⒉ U1 = {DEPT， HEAD}, F1={DEPT?HEAD} U2 = {SNO, DEPT}, F2={SNO?DEPT} U3 = {SNO, CNO, G}, F3 = {(SNO,CNO)?G} 例子 ?設有關系 R（ U, F） ? U={A, B, C, D, E, F, G} ? F={E→D, C→B, CE→AF, B→A, C→AB } ?求： ? R的候選碼 ? 判斷 R所屬的范式 ? 如果 R不屬于第三范式，將 R規(guī)范化到第三范式，并保持函數(shù)依賴和無損連接的分解 例子－求 R的候選碼 ?L: E, C ?R: A, D, F ?LR: B ?N: G ?首先查看 ?因此， CEG是 R唯一的候選碼 }{)()( A B CE F GFCE GFNL ?????例子－判斷 R屬于第幾范式 ?R的主屬性： C, E, G ?R的非主屬性： A, B, D, F ?非主屬性與候選碼的關系： ? E→D, 故 CEG→D 為部分函數(shù)依賴 ?故 R屬于第一范式 例子－分解為第三范式 ?求最小函數(shù)依賴集 ?第一步：將函數(shù)依賴的右部分解為單屬性 ?Fm＝ {E→ D, C→ B, CE→ A, CE→ F, B→ A, C→ A, C→ B} ?第二步：去掉多余的函數(shù)依賴 ?Fm＝ {E→ D, C→ B, CE→ F, B→ A} ?第三步：檢查是否存在部分函數(shù)依賴 例子－分解為第三范式 ?按相同左部分組，得到以下 4個屬性組： ? R1(E, D)， F={E→D} ? R2(C, B) ， F={C→B} ? R3(C, E, F) ， F={CE→F} ? R4(B, A) ， F={B→A} ?這些屬性組之間沒有相互包含的情況，因此，我們得到了保持函數(shù)依賴且達到第三范式的分解結(jié)果 例子－分解為第三范式 ?判斷上述結(jié)果是否是無損連接分解 ?因為上述分解后的關系模式中沒有哪一個包含了原關系模式 R的候選碼 CEG，所以上述分解結(jié)果是有損的。 ?為此，在上述分解結(jié)果中加入一個全由候選碼中屬性構成的關系模式 ? R5(C, E, G) ， F=φ 例子－分解為第三范式 ?最后的分解結(jié)果為： ? R1(E, D)， F={E→D} ? R2(C, B) ， F={C→B} ? R3(C, E, F) ， F={CE→F} ? R4(B, A) ， F={B→A} ? R5(C, E, G) ， F=φ