【正文】 各種異常情況和數(shù)據(jù)冗余。 ? 若 R∈ 3NF，則 R的每一個 非主屬性 既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 BC范式（ BCNF） 定義 設(shè)關(guān)系模式 RU， F∈ 1NF，如果對于 R的 每個函數(shù)依賴X→Y，若 Y不屬于 X，則 X必含有候選碼，那么 R∈ BCNF。 C(Cno,Cname,Po) SC(Sno,Cno,Grade) S(Sno,Sname,Sdept,Sage) 它只有一個碼 Cno，這里沒有任何屬性對Cno部分依賴或傳遞依賴，所以 C∈ 3NF。同時 S中除 Sno， Sname外沒有其他決定因素，所以S∈ BCNF。這個關(guān)系模式中顯然沒有屬性對碼傳遞依賴或部分依賴。某個學(xué)生選修某個教師的課就確定了所選課的名稱 。 ? 3NF的“不徹底”性表現(xiàn)在可能存在主屬性對碼的部分依賴和傳遞依賴。 關(guān)系模式 : Teaching(C, T, B) 課程 C、教師 T 和 參考書 B 課 程 C 教 員 T 參 考 書 B 物理 數(shù)學(xué) 計算數(shù)學(xué) … 李 勇 王 軍 李 勇 張 平 張 平 周 峰 … 普通物理學(xué) 光學(xué)原理 物理習(xí)題集 數(shù)學(xué)分析 微分方程 高等代數(shù) 數(shù)學(xué)分析 … 表 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 普通物理學(xué) 光學(xué)原理 物理習(xí)題集 普通物理學(xué) 光學(xué)原理 物理習(xí)題集 數(shù)學(xué)分析 微分方程 高等代數(shù) 數(shù)學(xué)分析 微分方程 高等代數(shù) … 李 勇 李 勇 李 勇 王 軍 王 軍 王 軍 李 勇 李 勇 李 勇 張 平 張 平 張 平 … 物 理 物 理 物 理 物 理 物 理 物 理 數(shù) 學(xué) 數(shù) 學(xué) 數(shù) 學(xué) 數(shù) 學(xué) 數(shù) 學(xué) 數(shù) 學(xué) … 參考書 B 教員 T 課程 C 用二維表表示 Teaching 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 用二分圖表示 Teaching 物 理 普通物理學(xué) 光學(xué)原理 物理習(xí)題集 李勇 王軍 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? Teaching∈ BCNF: ? Teaching具有唯一候選碼 (C， T， B)， 即全碼 ? Teaching關(guān)系模式中存在的問題 (1) 數(shù)據(jù)冗余度大： 有多少名任課教師，參考書就要存儲多少次。 ? 產(chǎn)生原因： 存在多值依賴 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴的定義 定義 設(shè) R(U)是一個屬性集 U上的一個關(guān)系模式， X、 Y和 Z是 U的子集，并且 Z＝ U－ X－ Y， 多值依賴 X→→Y成立當(dāng)且僅當(dāng)對 R的 任一關(guān)系 r，r在（ X， Z）上的每個值對應(yīng)一組 Y的值，這組值僅僅決定于 X值而與Z值無關(guān)。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 平凡多值依賴和非平凡的多值依賴 ? 若 X→→Y，而 Z＝ φ，則稱 X→→Y為 平凡的多值依賴 ? 否則稱 X→→Y為 非平凡的多值依賴 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 2：關(guān)系模式 WSC(W,S,C)中， W表示倉庫，S表示保管員， C表示商品。所以 W→→S。 （ 4）若 X→→Y， X→→Z，則 X→→Y? Z。 ? 一般地，在 R（ U）上若有 X→→Y在 W（ W ? U）上成立，則稱 X→→Y為 R（ U）的嵌入型多值依賴 ? 只要在 R（ U）的任何一個關(guān)系 r中，元組在 X和 Y上的值滿足定義 （函數(shù)依賴），則函數(shù)依賴 X→Y在任何屬性集 W（ X Y ? W ?U）上成立。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 第四范式（ 4NF） ? 如果 R ∈ 4NF， 則 R ∈ BCNF 不允許 有非平凡且非函數(shù)依賴的 多值依賴，允許 的是 函數(shù)依賴（是平凡多值依賴）。 ? 如果考慮 多值依賴 ，則屬于 4NF的關(guān)系模式規(guī)范化程度是最高的了。若多于一個概念就把它“分離”出去 ? 所謂規(guī)范化實質(zhì)上是概念的 單一 化 ? 不能說規(guī)范化程度越高的關(guān)系模式就越好。 （ Augmentation）：若 X→Y為 F所蘊含，且 Z ? U，則XZ→YZ為 F所蘊含。 設(shè) RU， F 的任一關(guān)系 r中任意的兩個元組 t， s； 若 t[XZ]=s[XZ]，則有 t[X]=s[X]和 t[Z]=s[Z]； 由 X→Y，于是有 t[Y]=s[Y]，所以 t[YZ]=s[YZ]，所以 XZ→YZ為 F所蘊含 . 增廣律得證。 若 t[X]=s[X]，由于 X→Y，有 t[Y]=s[Y]； 再由 Y→Z，有 t[Z]=s[Z]，所以 X→Z為 F所蘊含 . 傳遞律得證。 ，可得引理 引理 X→A1 A2…A k成立的充分必要條件是 X→Ai成立（ i=l， 2， … ，k）。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 求閉包的算法 算法 求屬性集 X（ X ? U）關(guān)于 U上的函數(shù)依賴集 F 的閉包 XF+ 輸入： X， F 輸出： XF+ 步驟： （ 1）令 X（ 0） =X， i=0 （ 2）求 B，這里 B = { A |(? V)( ? W)(V→W?F∧ V ? X（ i） ∧ A? W)}； （ 3） X（ i+1） =B∪ X（ i） （ 4）判斷 X（ i+1） = X （ i） 嗎 ? （ 5）若相等或 X（ i） =U , 則 X（ i） 就是 XF+ , 算法終止。 求（ AB） F+ 。 (2)因為 X（ 0） ≠ X（ 1） ，所以再找出左部為 ABCD子集的那些函數(shù)依賴，又得到 AB→C， B→D， C→E， AC→B， 于是 X（ 2） =X（ 1） ∪ BCDE=ABCDE。 具體解為： (AB)F+=﹛ ABCDE﹜ (B)F+=﹛ BD﹜ (C)F+=﹛ CBDE﹜ (EC)F+=﹛ CBDE﹜ (AC)F+=﹛ ABCDE﹜ (ABC)F+=﹛ ABCDE﹜ (ABCE)F+=﹛ ABCDE﹜ (BC)F+=﹛ BCDE﹜ (BEC)F+=﹛ BCDE﹜ (AEC)F+=﹛ ABCDE﹜ 包含 全部屬性 的有 (AB)F+ ， (AC)F+ ， (ABC)F+ ， (ABCE)F+ ， (AEC)F+ 挑選出 最簡 的是： (AB)F+ ， (AC)F+ 所以 R 的 碼 為： AB 和 AC 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 證明： 1. 有效性： 可由定理 2. 完備性： 只需證明 逆否命題 : 若函數(shù)依賴 X→Y不能由 F從 Armstrong公理導(dǎo)出，那么它必然不為 F所蘊含 分三步證明： 4. Armstrong公理系統(tǒng)的有效性與完備性 有效性： 由 F出發(fā)根據(jù) Armstrong公理推導(dǎo)出來的每一個函數(shù)依賴一定在 F+中。 構(gòu)造一張二維表 r，它由下列兩個元組構(gòu)成，可以證明 r必是 R（ U， F）的一個關(guān)系 ，即 F+中的全部函數(shù)依賴在 r上成立。 XF+ UXF+ 11......1 00......0 11......1 11......1 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 (3) /* 若 f 不能用 Armstrong公理推導(dǎo)出來， f∈ F+ /* 而不能用 Armstrong公理推導(dǎo)出來的 f , 在 r上不成立。 引理 F+ = G+ 的充分必要條件是： F ? G+ ， 和 G ? F+ 證 : 必要性顯然，只證充分性。即 F+ ? G+。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 6. 最小依賴集 定義 如果函數(shù)依賴集 F滿足下列條件 ， 則稱 F為一個 極小函數(shù)依賴集 。 (3) F中不存在這樣的函數(shù)依賴 X→A， X有真子集 Z 使得 F{X→A}∪ {Z→A}與 F等價 。 (1)逐一檢查 F中各函數(shù)依賴 FDi： X→Y， 若 Y=A1A2 … Ak， k 2， 則用 { X→Aj |j=1， 2， … ， k} 來取代 X→Y。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 因為對 F的每一次“改造”都保證了改造前后的兩個函數(shù)依賴集等價，因此剩下的 F與原來的 F等價。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 [例 3]已知： F = {A→B， B→A， B→C， A→C， C→A}， 求 F 的極小函數(shù)依賴集 Fm 解： ： F=﹛ A→B， B→A， B→C， A→C， C→A﹜ 2. ① 在 F中去掉 A→B， (A)F+={AC}， ∵ B ? (A)F+ ， ∴ 不去掉。 ，故不用再取其子集去考察。 ② A→C：記 G=F﹛ A→C ﹜ ， ∴ (A)G+= ﹛ ADEB﹜ ， ∴ C ? (A)G+ ， ∴ 不去掉 A→C ， F=﹛ A→C， A→D， A→E， D→E， DE→B， AF→G， AF→H， AF→I， I→J ﹜ 。 3. 函數(shù)依賴左部的分解 ① .DE→B： ∴ (D)F+= ﹛ DEB﹜ ， ∴ B∈ (D)F+ ， ∴ 用 D→B代替 DE→B ， 記 F=﹛ A→C， A→D， D→E， D→B ， AF→G， AF→H， AF→I， I→J ﹜ 。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 極小化過程 ( 定理 )也是檢驗 F是否為極小依賴集的一個算法 若改造后的 F與原來的 F相同，說明 F本身就是一個最小依賴集 ? 在 RU， F中可以用與 F等價的依賴集 G來取代 F 原因：兩個關(guān)系模式 R1 U， F， R2U， G，如果 F與 G等價，那么 R1的關(guān)系一定是 R2的關(guān)系。 ?設(shè)計數(shù)據(jù)庫方法 概念模型 →關(guān)系數(shù)據(jù)模型 → 關(guān)系數(shù)據(jù)規(guī)范化 （將數(shù)據(jù)庫中的各關(guān)系盡量達到高一級的范式）。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 模式的分解 ? 把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的。 ⒊ 分解既要保持函數(shù)依賴，又要具有無損連接性。 如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系 ， 那么這種分解就沒有 丟失信息 。 有數(shù)據(jù)冗余。 既保持函數(shù)依賴，又能無損連接。 其中： mρ(r) 是 r在 ρ中各關(guān)系模式上的投影的連接。 ? 如果一個模式分解 保持了函數(shù)依賴 ，則它可以減輕或解決各種異常情況。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。 算法 轉(zhuǎn)換為 3NF既有無損連接性又保持函數(shù)依賴的分解 算法 轉(zhuǎn)換為 BCNF的無損連接分解 （ 分解法 ） 算法 達到 4NF的具有無損連接性的分解