【正文】 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 分解算法 算法 判別一個分解的無損連接性 算法 （ 合成法 ） 轉(zhuǎn)換為 3NF的保持函數(shù)依賴的分解 。 ? 如果一個分解 既具有無損連接性又保持了函數(shù)依賴 ，則既能夠保證不丟失信息，還可以減輕或解決各種異常情況，是比較好的分解。具有無損連接性的分解不一定能夠保持函數(shù)依賴。那么這個模式分解一定能夠達到 3NF，但不一定能夠達到BCNF。那么這個模式分解一定能夠達到 4NF。 定義 519 設 ρ={R1U1,F1, R2U2,F2,...RnUn,Fn}是 RU,F的一個分解， 若F+ =( F1∪ F2∪ … ∪ Fn ) +,則稱關系模式 R的這個分解 ρ是保持函數(shù)依賴的 。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 具有無損連接性和保持函數(shù)依賴的模式分解定義 定義 平共 設 ρ={R1U1,F1, R2U2,F2,...RkUk,Fk}是 RU,F的一個分解，若對 RU,F的任何一個關系 r均有 r = mρ(r)成立，則稱分解 ρ具有無損聯(lián)接性。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 模式分解的定義 定義 關系模式 RU,F的一個分解： ρ={ R1U1,F1， R2U2,F2， … ， RnUn,Fn} U=U1∪ U2∪ … ∪ Un，且 不存在 Ui ? Uj， Fi 為 F在 Ui 上的投影。 沒有保持函數(shù)依賴，沒有丟失信息，是無損連接，但有數(shù)據(jù)冗余。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 第四種分解 Sno 95001 95002 95003 95004 95005 Sdept CS IS MA IS PH SD Sloc A B C B Sdept CS IS MA PH DL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B SD DL 這種分解方法 沒有丟失信息 和 數(shù)據(jù)冗余 ， 并保持了函數(shù)依賴 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 例 : SL（ Sno， Sdept， Sloc） F={ Sno→Sdept,Sdept→Sloc,Sno→Sloc} SL∈ 2NF 存在插入異常、刪除異常、冗余度大和修改復雜等問題 分解方法可以有多種 : SD(Sno， Sdept) DL (Sdept， Sloc) 4. SD(Sno， Sdept) SL (Sno， Sloc) 3. SL(Sno， Sloc) DL (Sdept， Sloc) 2. S (Sno) D (Sdept) L(Sloc) 1. Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B SL 既沒有保持函數(shù)依賴，又無法連接。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 第三種分解 Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B SD SL Sno 95001 95002 95003 95004 95005 Sdept CS IS MA IS PH SD Sloc A B C B B Sno 95001 95002 95003 95004 95005 SL 沒有丟失信息 ， 但原關系 SL中的函數(shù)依賴 Sdept→Sloc 在關系模式 SD和 SL上不見了。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 第二種分解 Sno 95001 95002 95003 95004 95005 Sloc A B C B B SL Sloc A B C B Sdept CS IS MA PH DL SL DL Sno Sdept Sloc 95001 CS A 95002 IS B 95002 PH B 95003 MA C 95004 IS B 95004 PH B 95005 IS B 95005 PH B ? ? ? 連接后比原來的 SL關系多了 3個元組，無法知道 9500 9500 95005究竟是哪個系的學生。 例如無法查詢 95001學生所在系或所在宿舍 。 以上也是模式分解的原則。 ⒉ 分解要保持函數(shù)依賴。 ? 只有能夠保證分解后的關系模式與原關系模式等價，分解方法才有意義。 Key的求法： X(i) =XF+ X(i) =U，則選出其中的 X， X中選出最簡的主屬性組 Xi , 4. Xi 就是所求的碼。 ?判斷關系模式能達到哪一級范式 由關系模式中的 U、 F和 Key根據(jù)各范式定義來判斷。 ?設計數(shù)據(jù)庫的標準 不存在插入異常、刪除異常、修改異常和冗余度大等問題。反過來， R2的關系也一定是 R1的關系。 所以， Fm=﹛ A→C， A→D， D→E， D→B ， AF→G， AF→H， AF→I， I→J ﹜ 。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 ② .AF→G： ∴ (A)F+= ﹛ ACDEB﹜ ， ∴ (F)F+= ﹛ ACDEB﹜ ， ∵ G ? (A)F+ ； G ? (F)F+ ， ∴ 不能用 A→G或 F→G代替 AF→G ， 記 F=﹛ A→C， A→D， D→E， D→B ， AF→G， AF→H， AF→I， I→J ﹜ 。 故記 F為： F=﹛ A→C， A→D， D→E， DE→B， AF→G， AF→H， AF→I， I→J ﹜ 。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 ③ A→E：記 G=F﹛ A→E﹜ ， ∴ (A)G+= ﹛ ACDEB﹜ ， ∴ E∈ (A)G+ ， ∴ 去掉 A→E ， F=F﹛ A→E﹜ =﹛ A→C， A→D， D→E， DE→B， AF→G， AF→H， AF→I， I→J ﹜ 。 2. ① A→B：記 G=F﹛ A→B﹜ ， ∴ (A)G+= ﹛ ACDEB﹜ ， ∴ B∈ (A)G+ ， ∴ 去掉 A→B ， F=F﹛ A→B﹜ =﹛ A→C， A→D， A→E， D→E， DE→B，AF→G， AF→H， AF→I， I→J ﹜ 。 故極小函數(shù)依賴集 Fm1=﹛ A→B， B→C， C→A﹜ Fm1= {A→B， B→C， C→A} Fm2= {A→B， B→A， A→C， C→A} Fm Fm2都是 F的最小依賴集： ? F的最小依賴集 Fm不一定是唯一的它與對各函數(shù)依賴 FDi 及 X→A中 X各屬性的處置順序有關 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 例 4：已知關系 R U， F， U=﹛ A， B， C， D， E， F， G， H， I， J﹜ ，F(xiàn)=﹛ A→B， A→C， A→DE， D→E， DE→B， AF→GHI， I→J﹜ 。 ④在 F中去掉 A→C， (A)F+={ABC}， ∵ C∈ (A)F+ ， ∴ 應去掉 ⑤在 F中去掉 C→A， (C)F+={C}， ∵ A ? (C)F+ ， ∴ 不去掉。 ②在 F中去掉 B→A ， (B)F+={ABC}， ∵ A∈ (B)F+ ， ∴ 應去掉。 由定義，最后剩下的 F就一定是極小依賴集。 定理 也是求 F極小依賴集的過程 (3)逐一取出 F中各函數(shù)依賴 FDi： X→A， 設 X=B1B2… Bm， 逐一考查 Bi （ i=l， 2， … ， m） ， 若 A ?（ XBi ） F+ ， 則以 XBi 取代 X。 由于 F與 G =F{X→A}等價的充要條件是 A?XG+ 因此 F變換前后是等價的。 引理 F變換前后的等價性 。 此 Fm稱為 F的最小依賴集 證 :構造性證明 ， 依據(jù)定義分三步對 F進行 “ 極小化處理 ” ， 找出 F的一個最小依賴集 。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 [例 2] 對于 SU， F， 其中： U={ SNO， SDEPT， MN， CNAME， G }， F={ SNO→SDEPT， SDEPT→MN， （ SNO， CNAME） →G } 設 F’={SNO→SDEPT， SNO→MN， SDEPT→MN， (SNO， CNAME)→G， (SNO， SDEPT)→SDEPT} F是最小覆蓋，而 F ’不是。 (2) F中不存在這樣的函數(shù)依賴 X→A， 使得 F與 F{X→A}等價 。 亦稱為 最小依賴集 或 最小覆蓋 。 因此引理 給出了判斷兩個函數(shù)依賴集等價的可行算法 。 （ 3）同理可證 G+ ? F+ ，所以 F+ = G+。 所以 X→Y ? (G+） += G+。 （ 1）若 F?G+ ，則 XF+ ? XG++ 。 Armstrong公理的完備性及有效性說明 : “蘊含” == “導出” 等價的概念 F+ ==由 F出發(fā)借助 Armstrong公理導出的函數(shù)依賴的集合 數(shù)據(jù)庫系統(tǒng)概論 第六章 關系數(shù)據(jù)理論 5. 函數(shù)依賴集等價 定義 如果 G+=F+，就說函數(shù)依賴集 F覆蓋 G（ F是 G的覆蓋，或 G是F的覆蓋），或 F與 G等價 。 ? 若 X→Y 不能由 F從 Armstrong公理導出，則 Y 不是 XF+ 的子集。 所以 r必是 RU， F的一個關系 。 若 r不是 RU， F 的關系 ， 則必由于 F中有函數(shù)依賴 V→W在 r上不成立所致 。 /* 而不能用 Armstrong公理推導出來的 f , 在 r上不成立。 /* Armstrong正確 完備性 ： F+中的每一個函數(shù)依賴，必定可以由 F出發(fā)根據(jù) Armstrong公理推導出來 。 求 R 的碼？ 解法： X(i) =XF+ ， X(i) =U，則選出其中的 X， X中選出最簡的主屬性組 Xi , 4. Xi 就是所求的碼。 (3)因為 X（ 2） =U，算法終