【正文】 o→Mname ， Sdept→Mname ， (Sno， Cno)→Grade ， (Sno， Sdept)→Sdept} F是最小覆蓋，而 F’不是。 因為： F ’ {Sno→Mname} 與 F ’等價 F ’ {(Sno， Sdept)→Sdept} 也與 F ’等價 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 6. 極小化過程 定理 每一個函數(shù)依賴集 F均等價于一個極小函數(shù)依賴集 Fm。 此 Fm稱為 F的最小依賴集 。 證明 : 構造性證明 ， 找出 F的一個最小依賴集 。 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 極小化過程（續(xù)） (1) 逐一檢查 F 中各函數(shù)依賴 FDi ： X→ Y ， 若Y=A1A2 … Ak， k 2,則用 { X→ Aj |j=1， 2， … ， k} 來取代 X→ Y。 (2)逐一檢查 F中各函數(shù)依賴 FDi： X→ A，令 G=F{X→ A}，若 A?XG+， 則從 F中去掉此函數(shù)依賴。 (3) 逐一取出 F 中各函數(shù)依賴 FDi ： X→ A ， 設X=B1B2… Bm， 逐一考查 Bi （ i=l， 2， … ， m） ， 若 A ?（ XBi ） F+ ， 則以 XBi 取代 X。 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 極小化過程（續(xù)） [例 3] F = {A→ B， B→ A， B→ C， A→ C， C→ A} Fm Fm2都是 F的最小依賴集： Fm1= {A→ B， B→ C， C→ A} Fm2= {A→ B， B→ A， A→ C， C→ A} ? F的最小依賴集 Fm不唯一 ? 極小化過程 ( 定理 )也是檢驗 F是否為極小依賴集的一個算法 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 第六章 關系數(shù)據(jù)理論 問題的提出 規(guī)范化 數(shù)據(jù)依賴的公理系統(tǒng) * 模式的分解 小結 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 模式的分解 ? 把低一級的關系模式分解為若干個高一級的關系模式的方法不是唯一的 ? 只有能夠保證分解后的關系模式與原關系模式等價，分解方法才有意義 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 關系模式分解的標準 三種模式分解等價的定義： ⒈ 分解具有無損連接性 ⒉ 分解要保持函數(shù)依賴 ⒊ 分解既要保持函數(shù)依賴，又要具有無損連接性 這三個定義是實行分解的三條不同準則。按照不同的分解準則，模式分解能達到的分離程度各不相同，各種范式就是對分離程度的測度。 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 模式的分解（續(xù)） 例： SL（ Sno， Sdept， Sloc） F={ Sno→Sdept, Sdept→Sloc, Sno→Sloc} SL∈ 2NF 分解方法可以有多種： 1. SL分解為三個關系模式： SN(Sno) SD(Sdept) SL(Sloc) 2. 將 SL分解為下面二個關系模式： ND(Sno, Sdept) NL(Sno, Sloc) 3. 將 SL分解為 ND(Sno, Sdept) DL(Sdept, Sloc) 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 分析 1. Sno Sdept Sloc S1 D1 A S2 D1 A S3 D2 B S4 D3 C ?假設分解為 SN(SNO), SD(SDEPT), SL(SLOC) 則 r1={S1,S2,S3,S4} r2={D1,D2,D3} r3={A,B,C} 分解后的數(shù)據(jù)庫，要回答 “ S1在哪個系學習 ” 已不可能了，丟失了原來的信息不能恢復。 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 分析 2. Sno Sdept S1 D1 S2 D1 S3 D2 S4 D3 Sno Sloc S1 A S2 A S3 B S4 C SL=ND NL, 所以對 SL的分解能恢復原來的信息 ， 具有無損連接性 。 但原 R中的函數(shù)依賴 SDEPT→ SLOC， 現(xiàn)在在 ND和 NL中都不存在了 。 因此不保持函數(shù)依賴 。 NL ND 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 分析 3. Sno Sdept S1 D1 S2 D1 S3 D2 S4 D3 Sdept Sloc D1 A D2 B D3 C ND 該分解既具有無損連接性，又保持函數(shù)依賴。它解決了更新異常，又沒有丟失原數(shù)據(jù)庫的信息，這是所希望的分解。 SL=ND DL 函數(shù)依賴集： F1={SNO→ SDEPT}, F2={SDEPT→ SLOC} DL 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 模式的分解（續(xù)） ? 如果一個分解具有無損連接性，則它能夠保證不丟失信息 ? 如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況 ? 分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨立的標準。具有無損連接性的分解不一定能夠保持函數(shù)依賴；同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 模式的分解（續(xù)） 第 1種分解方法既不具有無損連接性，也未保持函數(shù)依賴，它不是原關系模式的一個等價分解 第 2種分解方法具有無損連接性，但未保持函數(shù)依賴 第 3種分解方法既具有無損連接性，又保持了函數(shù)依賴 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 分解算法 ? 算法 判別一個分解的無損連接性 ? 算法 （ 合成法 ） 轉換為 3NF的保持函數(shù)依賴的分解 。 ? 算法 轉換為 3NF既有無損連接性又保持函數(shù)依賴的分解 ? 算法 （ 分解法 ） 轉換為 BCNF的無損連接分解 ? 算法 達到 4NF的具有無損連接性的分解 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 模式的分解（續(xù)） ? 如何判斷分解后的關系模式是否具有無損連接性和 保持函數(shù)依賴？ 定義 1 若 F+ =(F1 F2 … FK) + ， 則 R(U,F) 的分解 ρ ={R1(U1,F1), … , RK(UK,FK)}保持函數(shù)依賴。 定理 1（ 只適合分解為兩個關系模式的情況 ） 關系模式 R(U,F)的一個分解 ρ ={R1(U1,F1), R2(U2,F2)}具有無損連接性的充分必要條件是： U1 U2→U1 U2 ∈ F+ 或 U1 U2→U2 U1 ∈ F+ 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 判別無損連接性的算法 例 8 關系模式 R(U,F),其中 U={A,B,C,D,E}, F={AC→ E, E→ D, A→ B, B→ D}。判斷如下分解是否無損連接。 （ 1） ρ1={R1(AC), R2(ED), R3(AB)} （ 2） ρ2={R1(ABC), R2(ED), R3(ACE)} 解（ 1） A B C D E R1(AC) a1 b12 a3 b14 b15 R2(ED) b21 b22 b23 a4 a5 R3(AB) a1 a2 b33 b34 b35 屬性 模式 結論：分解 ρ1是有損的。 屬性模式河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 ? 解（ 2） ρ2={R1(ABC), R2(ED), R3(ACE)} F={AC→E, E→D, A→B, B→D} A B C D E R1(ABC) R2(ED) R3(ACE) 屬性 模式 屬性模式河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 習題：設關系模式 R(ABCD)上成立的函數(shù)依賴集 F={A→B, C→D} ，試把 R分解成 3NF模式集，且具有無損連接和保持函數(shù)依賴兩個特性。 練習 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 答案 解：確定 R的碼為（ AC）。 判斷 R只屬于 1NF，根據(jù)函數(shù)依賴集將 R分解為 R1(AB)和 R2(CD)。 驗證是否具有無損連接性和保持函數(shù)依賴兩個特性。 A B C D R1(AB) a1 a2 b13 b14 R2(CD) b21 b22 a3 a4 屬性 模式 結論：不具有無損連接性 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 ? 增加關系模式 R3(AC)，即將 R分解為 R1(AB) ， R2(CD)， R3(AC)。 經(jīng)驗證既保持無損連接性又保持函數(shù)依賴且都屬于 3NF。 A B C D R1(AB) a1 a2 b13 b14 R2(CD) b21 b22 a3 a4 R3(AC) a1 b32 a3 b34 屬性 模式 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 第六章 關系數(shù)據(jù)理論 問題的提出 規(guī)范化 數(shù)據(jù)依賴的公理系統(tǒng) * 模式的分解 小結 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 小結 函數(shù)依賴 （ 平凡的函數(shù)依賴 、 非平凡的函數(shù)依賴 部分函數(shù)依賴 、 完全函數(shù)依賴 、 傳遞函數(shù)依賴 ） 碼 （ 候選碼 、 主碼 、 全碼 、 外碼 、 主屬性 、 非主屬性 ） 規(guī)范化 （ 1NF、 2NF、 3NF、 BCNF、 4NF的條件 ） 候選碼的求解方法 最小依賴集 判斷分解保持函數(shù)依賴 判斷分解保持無損連接性 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 小結 (續(xù) ) ? 規(guī)范化理論為數(shù)據(jù)庫設計提供了理論的指南和工具 ? 也僅僅是指南和工具 ? 并不是規(guī)范化程度越高 ， 模式就越好 ? 必須結合應用環(huán)境和現(xiàn)實世界的具體情況合理地選擇數(shù)據(jù)庫模式 河北經(jīng)貿(mào)大學信息技術學院 2021/11/10 下課了。 休息一會兒。