【正文】 同樣，保持函數(shù)依賴的分解也不一定具有無(wú)損連接性。 其中： mρ(r) 是 r在 ρ中各關(guān)系模式上的投影的連接。 有數(shù)據(jù)冗余。 ⒊ 分解既要保持函數(shù)依賴，又要具有無(wú)損連接性。 ?設(shè)計(jì)數(shù)據(jù)庫(kù)方法 概念模型 →關(guān)系數(shù)據(jù)模型 → 關(guān)系數(shù)據(jù)規(guī)范化 （將數(shù)據(jù)庫(kù)中的各關(guān)系盡量達(dá)到高一級(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ù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 因?yàn)閷?duì) F的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)，因此剩下的 F與原來(lái)的 F等價(jià)。 (3) F中不存在這樣的函數(shù)依賴 X→A， X有真子集 Z 使得 F{X→A}∪ {Z→A}與 F等價(jià) 。即 F+ ? G+。 XF+ UXF+ 11......1 00......0 11......1 11......1 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 (3) /* 若 f 不能用 Armstrong公理推導(dǎo)出來(lái)， f∈ F+ /* 而不能用 Armstrong公理推導(dǎo)出來(lái)的 f , 在 r上不成立。 具體解為： (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+ 挑選出 最簡(jiǎn) 的是： (AB)F+ ， (AC)F+ 所以 R 的 碼 為： AB 和 AC 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 證明： 1. 有效性： 可由定理 2. 完備性： 只需證明 逆否命題 : 若函數(shù)依賴 X→Y不能由 F從 Armstrong公理導(dǎo)出，那么它必然不為 F所蘊(yùn)含 分三步證明： 4. Armstrong公理系統(tǒng)的有效性與完備性 有效性： 由 F出發(fā)根據(jù) Armstrong公理推導(dǎo)出來(lái)的每一個(gè)函數(shù)依賴一定在 F+中。 求（ AB） F+ 。 ，可得引理 引理 X→A1 A2…A k成立的充分必要條件是 X→Ai成立（ i=l， 2， … ，k）。 設(shè) RU， F 的任一關(guān)系 r中任意的兩個(gè)元組 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所蘊(yùn)含 . 增廣律得證。若多于一個(gè)概念就把它“分離”出去 ? 所謂規(guī)范化實(shí)質(zhì)上是概念的 單一 化 ? 不能說(shuō)規(guī)范化程度越高的關(guān)系模式就越好。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 第四范式（ 4NF） ? 如果 R ∈ 4NF， 則 R ∈ BCNF 不允許 有非平凡且非函數(shù)依賴的 多值依賴，允許 的是 函數(shù)依賴（是平凡多值依賴）。 （ 4）若 X→→Y， X→→Z，則 X→→Y? Z。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 平凡多值依賴和非平凡的多值依賴 ? 若 X→→Y，而 Z＝ φ，則稱 X→→Y為 平凡的多值依賴 ? 否則稱 X→→Y為 非平凡的多值依賴 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 2：關(guān)系模式 WSC(W,S,C)中， W表示倉(cāng)庫(kù)，S表示保管員， C表示商品。 關(guān)系模式 : Teaching(C, T, B) 課程 C、教師 T 和 參考書 B 課 程 C 教 員 T 參 考 書 B 物理 數(shù)學(xué) 計(jì)算數(shù)學(xué) … 李 勇 王 軍 李 勇 張 平 張 平 周 峰 … 普通物理學(xué) 光學(xué)原理 物理習(xí)題集 數(shù)學(xué)分析 微分方程 高等代數(shù) 數(shù)學(xué)分析 … 表 數(shù)據(jù)庫(kù)系統(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ù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 用二分圖表示 Teaching 物 理 普通物理學(xué) 光學(xué)原理 物理習(xí)題集 李勇 王軍 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? Teaching∈ BCNF: ? Teaching具有唯一候選碼 (C， T， B)， 即全碼 ? Teaching關(guān)系模式中存在的問(wèn)題 (1) 數(shù)據(jù)冗余度大： 有多少名任課教師，參考書就要存儲(chǔ)多少次。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱 。同時(shí) S中除 Sno， Sname外沒(méi)有其他決定因素，所以S∈ BCNF。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 BC范式（ BCNF） 定義 設(shè)關(guān)系模式 RU， F∈ 1NF，如果對(duì)于 R的 每個(gè)函數(shù)依賴X→Y，若 Y不屬于 X，則 X必含有候選碼，那么 R∈ BCNF。 ? 將一個(gè) 1NF關(guān)系分解為多個(gè) 2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。現(xiàn)在因身體不適，他連 3號(hào)課程也不選修了。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 2NF ? 1NF的定義 如果一個(gè)關(guān)系模式 R的所有屬性都是 不可分的基本數(shù)據(jù)項(xiàng) ，則 R∈ 1NF。 例 : 在關(guān)系 Std(Sno, Sdept, Mname)中，有： Sno → Sdept， Sdept → Mname Mname傳遞函數(shù)依賴于 Sno 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 碼 定義 設(shè) K為關(guān)系模式 RU,F中的屬性或?qū)傩越M合。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在， 則拒絕裝入該元組。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 函數(shù)依賴 一、函數(shù)依賴 定義 設(shè) R(U)是一個(gè)屬性集 U上的關(guān)系模式， X和 Y是 U的子集。 Student(Sno, Sdept, Mname, Cname, Grade ) ⒉ 更新異常（ Update Anomalies） 數(shù)據(jù)冗余 ， 更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。 ? 關(guān)系數(shù)據(jù)庫(kù)的模式 ：定義這組關(guān)系的關(guān)系模式的全體。 ? 關(guān)系模式 ：用來(lái)定義關(guān)系。 例，如果一個(gè)系剛成立，尚無(wú)學(xué)生，我們就無(wú)法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫(kù)。 SG (SNO, CNAME, G, (SNO, CNAME) → G)。只能根據(jù)數(shù)據(jù)的語(yǔ)義來(lái)確定函數(shù)依賴。 若 X→Y，但 Y不完全函數(shù)依賴于 X，則稱 Y部分函數(shù)依賴 于 X，記作X P Y。 ? 關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿足一定的要求。 函數(shù)依賴包括： (Sno, Cno) F Grade Sno → Sdept (Sno, Cno) P Sdept Sno → Sloc (Sno, Cno) P Sloc Sdept → Sloc Sno Cno Grade Sdept Sloc SLC SLC的碼為 (Sno, Cno) SLC滿足第一范式。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 函數(shù)依賴圖： Sdept Sloc Sno SL Sno Cno Grade SC ? 原因 Sdept、 Sloc部分函數(shù)依賴于碼。 ? 如果 R∈ 3NF，則 R也是 2NF。同時(shí) C中 Cno是唯一的決定因素，所以 C∈ BCNF。所以 SJP∈ 3NF，而且除 (S,J)與 (J,P)以外沒(méi)有其它決定因素，所以 SJP∈ BCNF 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 3：在關(guān)系模式 STJ（ S， T， J）中， S表示學(xué)生， T表示教師，J表示課程。 BCNF的關(guān)系模式所具有的性質(zhì) ⒈ 所有 非主屬性 都完全函數(shù)依賴于每個(gè)候選碼 。 例 Teaching（ C, T, B） 對(duì)于 C的每一個(gè)值， T有一組值與之對(duì)應(yīng)，而不論 B取何值。 Si1 ， Si2 ， … … Sin Ci1 ， Ci2 ， … … C in Wi S C Wi Wi 于是 {S}Wi與 {C}Wi之間正好形式一個(gè)完全二分圖，如圖 : 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴的性質(zhì) （ 1）多值依賴具有對(duì)稱性 若 X→→Y，則 X→→Z，其中 Z＝ U－ X－ Y 多值依賴的對(duì)稱性可以用完全二分圖直觀地表示出來(lái)。 (2) ? 若函數(shù)依賴 X→Y在 R（ U）上成立，則對(duì)于任何 Y39。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 存在非平凡的多值依賴 C→→T，且 C不是候選碼 ? 用投影分解法把 Teach分解為如下兩個(gè)關(guān)系模式： CT(C, T) ∈ 4NF CB(C, B) ∈ 4NF C→→T， C→→B是平凡多值依賴 ? 同樣的方法可以把 WSC（ W， S， C） 分解為： WS（ W， S） ∈ 4NF WC（ W， C） ∈ 4NF 例： Teach(C,T,B) ∈ 4NF 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 規(guī)范化小結(jié) ? 關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具。 （ Transitivity）：若 X→Y及 Y→Z為 F所蘊(yùn)含，則 X→Z為 F所蘊(yùn)含。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 2. 導(dǎo)出規(guī)則 A1， A2， A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則 ：由 X→Y， X→Z，有 X→YZ。 （ 6）若否，則 i=i+l，返回第（ 2）步。 (3)因?yàn)?X（ 2） =U，算法終止 所以（ AB） F+ =ABCDE。 若 r不是 RU， F 的關(guān)系 ， 則必由于 F中有函數(shù)依賴 V→W在 r上不成立所致 。 （ 1）若 F?G+ ，則 XF+ ? XG++ 。 亦稱為 最小依賴