【正文】 (Sdept) SL(Sloc) 2. 將 SL分解為下面二個關(guān)系模式： ND(Sno, Sdept) NL(Sno, Sloc) 3. 將 SL分解為 ND(Sno, Sdept) DL(Sdept, Sloc) 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 分析 1. Sno Sdept Sloc S1 D1 A S2 D1 A S3 D2 B S4 D3 C ?假設(shè)分解為 SN(SNO), SD(SDEPT), SL(SLOC) 則 r1={S1,S2,S3,S4} r2={D1,D2,D3} r3={A,B,C} 分解后的數(shù)據(jù)庫，要回答 “ S1在哪個系學(xué)習(xí) ” 已不可能了，丟失了原來的信息不能恢復(fù)。 NL ND 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 分析 3. Sno Sdept S1 D1 S2 D1 S3 D2 S4 D3 Sdept Sloc D1 A D2 B D3 C ND 該分解既具有無損連接性，又保持函數(shù)依賴。 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 模式的分解（續(xù)） 第 1種分解方法既不具有無損連接性，也未保持函數(shù)依賴，它不是原關(guān)系模式的一個等價分解 第 2種分解方法具有無損連接性，但未保持函數(shù)依賴 第 3種分解方法既具有無損連接性，又保持了函數(shù)依賴 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 分解算法 ? 算法 判別一個分解的無損連接性 ? 算法 （ 合成法 ） 轉(zhuǎn)換為 3NF的保持函數(shù)依賴的分解 。 （ 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 屬性 模式 結(jié)論：分解 ρ1是有損的。 驗證是否具有無損連接性和保持函數(shù)依賴兩個特性。 休息一會兒。 經(jīng)驗證既保持無損連接性又保持函數(shù)依賴且都屬于 3NF。 練習(xí) 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 答案 解：確定 R的碼為（ AC）。 定理 1（ 只適合分解為兩個關(guān)系模式的情況 ） 關(guān)系模式 R(U,F)的一個分解 ρ ={R1(U1,F1), R2(U2,F2)}具有無損連接性的充分必要條件是： U1 U2→U1 U2 ∈ F+ 或 U1 U2→U2 U1 ∈ F+ 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 判別無損連接性的算法 例 8 關(guān)系模式 R(U,F),其中 U={A,B,C,D,E}, F={AC→ E, E→ D, A→ B, B→ D}。 SL=ND DL 函數(shù)依賴集： F1={SNO→ SDEPT}, F2={SDEPT→ SLOC} DL 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 模式的分解（續(xù)） ? 如果一個分解具有無損連接性，則它能夠保證不丟失信息 ? 如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況 ? 分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨立的標(biāo)準(zhǔn)。 但原 R中的函數(shù)依賴 SDEPT→ SLOC， 現(xiàn)在在 ND和 NL中都不存在了 。 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 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)大學(xué)信息技術(shù)學(xué)院 2021/11/10 第六章 關(guān)系數(shù)據(jù)理論 問題的提出 規(guī)范化 數(shù)據(jù)依賴的公理系統(tǒng) * 模式的分解 小結(jié) 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 模式的分解 ? 把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法不是唯一的 ? 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 關(guān)系模式分解的標(biāo)準(zhǔn) 三種模式分解等價的定義： ⒈ 分解具有無損連接性 ⒉ 分解要保持函數(shù)依賴 ⒊ 分解既要保持函數(shù)依賴，又要具有無損連接性 這三個定義是實行分解的三條不同準(zhǔn)則。 證明 : 構(gòu)造性證明 ， 找出 F的一個最小依賴集 。 (3) F中不存在這樣的函數(shù)依賴 X→A ， X有真子集Z使得 F{X→A} ∪ {Z→A} 與 F等價 。 AB ABD 練習(xí) 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 5. 最小依賴集 定義 如果函數(shù)依賴集 F滿足下列條件 ，則稱 F為一個 極小函數(shù)依賴集 。 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 例 2 設(shè)關(guān)系模式 R(U,F)， U={A,B,C,D}, F={A→C, C→B, AD→B} ，求 R的候選碼。 ? 若 X是 L類屬性， X+F =U，則 X必為 R的唯一候選碼。 （ 2） R：僅出現(xiàn)在函數(shù)依賴集 F右部 的屬性。 解： 設(shè) X（ 0） =AB； (1) X（ 1） =AB∪ CD=ABCD。 (AE)＋ F = ABE。 定義 設(shè) F為屬性集 U上的一組函數(shù)依賴，X ?U， XF+ ={ A|X→A 能由 F 根據(jù) Armstrong公理導(dǎo)出 }， XF+稱為屬性集 X關(guān)于函數(shù)依賴集 F 的閉包 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 F的閉包 F={X?Y, Y?Z} F+={ X?φ, Y?φ, Z?φ, XY?φ, XZ?φ, YZ?φ, XYZ?φ, X?X, Y?Y, Z?Z, XY?X, XZ?X, YZ?Y, XYZ?X, X?Y, Y ?Z, XY?Y, XZ?Y, YZ?Z, XYZ?Y, X?Z, Y?YZ, XY?Z, XZ?Z, YZ?YZ,XYZ?Z, X?XY, XY?XY,XZ?XY, XYZ?XY, X?XZ, XY?YZ,XZ?XZ, XYZ?YZ, X?YZ, XY?XZ,XZ?XY, XYZ?XZ, X?ZYZ, XY?XYZ,XZ?XYZ, XYZ?XYZ } F={X?A1, …… , X ?An}的閉包 F+計算是一個 NP完全問題 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 關(guān)于閉包的引理 ? 引理 設(shè) F為屬性集 U上的一組函數(shù)依賴， X， Y ? U，X→ Y能 由 F 根據(jù) Armstrong公理導(dǎo)出的充分必要條件是 Y ?XF+ ? 用途 將判定 X→Y 是否能由 F根據(jù) Armstrong公理導(dǎo)出的問題，轉(zhuǎn)化為求出 XF+ 、判定 Y是否為 XF+的子集的問題 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 例 1 已知關(guān)系模式 R(U,F)， U={A,B,C,D,E}, F={A→B, D→C, BC→E, AC→B} 。 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 2. 導(dǎo)出規(guī)則 A1， A2， A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： ? 合并規(guī)則 ：由 X→ Y， X→ Z，有 X→ YZ。 ? 如果考慮多值依賴，則屬于 4NF的關(guān)系模式規(guī)范化程度是最高的。 ? 如果 R ∈ 4NF， 則 R ∈ BCNF ? 不允許 有非平凡且非函數(shù)依賴的 多值依賴 ? 允許 的非平凡多值依賴是 函數(shù)依賴 即消除非平凡且非函數(shù)依賴的多值依賴。這是因為多值依賴的定義中不僅涉及屬性組 X和 Y，而且涉及 U中其余屬性 Z。 （ 4）若 X→→Y， X→→Z，則 X→→Y? Z。每個教員可以講授多門課程，每種參考書可以供多門課程使用。 即（ 3NF基礎(chǔ)上）消除主屬性對碼 的部分和傳遞依賴。 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 學(xué)號 姓名 年齡 性別 系號 系名 1001 王靜 18 女 1 通信工程 2021 張路 19 女 2 電子工程 2021 李遠(yuǎn) 20 男 2 電子工程 3001 王燁 21 男 3 計算機 3004 張路 20 女 3 計算機 3005 孫小明 19 男 3 計算機 習(xí)題 1： 如下表學(xué)生關(guān)系 S，試問 S是否屬于 3NF? 為什么？ 若不是，它屬于第幾范式？并將其規(guī)范化為 3NF。 即 (2NF基礎(chǔ)上 )消除非主屬性對碼的傳遞依賴。 例： SLC(Sno, Sdept, Sloc, Cno, Grade) ∈ 1NF SLC(Sno, Sdept, Sloc, Cno, Grade) ∈ 2NF SC（ Sno， Cno， Grade） ∈ 2NF SL（ Sno， Sdept， Sloc） ∈ 2NF 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 2NF（續(xù)） ? 采用投影分解法將一個 1NF的關(guān)系分解為多個 2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。如果這個學(xué)生選修了 K門課，則必須無遺漏地修改K個元組中全部 Sdept、 Sloc信息?，F(xiàn)在因身體不適，他連 3號課程也不選修了。 ? 一個低一級范式的關(guān)系模式，通過 模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式的集合，這種過程就叫 規(guī)范化 NF5NF4BC N FNF3NF2NF1 ?????河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 5NF 4NF BCNF 3NF 2NF 1NF 各種范式之間的聯(lián)系 河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 2021/11/10 規(guī)范化 函數(shù)依賴 碼