【正文】 利用關(guān)系來描述現(xiàn)實(shí)世界。數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 第六章 關(guān)系數(shù)據(jù)理論 問題的提出 規(guī)范化 數(shù)據(jù)依賴的公理系統(tǒng) * 模式的分解 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 問題的提出 關(guān)系數(shù)據(jù)庫(kù)邏輯設(shè)計(jì) ? 針對(duì)具體問題 ， 如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式 ? 數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具 ──關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論 ? 關(guān)系 ：描述實(shí)體、屬性、實(shí)體間的聯(lián)系。 從形式上看，它由一組關(guān)系組成。 3. 數(shù)據(jù)依賴的類型 ? 函數(shù)依賴（ Functional Dependency，簡(jiǎn)記為 FD） ? 多值依賴（ Multivalued Dependency，簡(jiǎn)記為 MVD） ? 其他 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 四、關(guān)系模式的簡(jiǎn)化表示 關(guān)系模式 R（ U, D, DOM, F） 簡(jiǎn)化為一個(gè)三元組： R（ U, F） 當(dāng)且僅當(dāng) U上的一個(gè)關(guān)系 r 滿足 F時(shí)， r稱為關(guān)系 模式 R（ U, F）的一個(gè) 關(guān)系 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 五、數(shù)據(jù)依賴對(duì)關(guān)系模式的影響 例：描述學(xué)校的數(shù)據(jù)庫(kù)： 學(xué)生的學(xué)號(hào)（ Sno）、所在系（ Sdept） 系主任姓名（ Mname）、課程名（ Cname） 成績(jī)（ Grade） 單一 的關(guān)系模式 ： Student U、 F U ＝｛ Sno, Sdept, Mname, Cname, Grade ｝ 學(xué)校數(shù)據(jù)庫(kù)的語(yǔ)義： ⒈ 一個(gè)系有若干學(xué)生， 一個(gè)學(xué)生只屬于一個(gè)系； ⒉ 一個(gè)系只有一名主任； ⒊ 一個(gè)學(xué)生可以選修多門課程， 每門課程有若干學(xué)生選修； ⒋ 每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績(jī)。 ⒋ 刪除異常（ Deletion Anomalies） 不該刪除的數(shù)據(jù)不得不刪 例，如果某個(gè)系的學(xué)生全部畢業(yè)了， 我們?cè)趧h除該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。 原因： 由存在于模式中的 某些數(shù)據(jù)依賴 引起的 . 解決方法： 通過 分解 關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 規(guī)范化 規(guī)范化理論 正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。 Y=f(x) 說明： 1. 函數(shù)依賴不是指關(guān)系模式 R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的 所有關(guān)系實(shí)例 均要滿足的約束條件。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名 →年齡”成立。 但 Ssex →Sage 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 二、平凡函數(shù)依賴與非平凡函數(shù)依賴 在關(guān)系模式 R(U)中，對(duì)于 U的 子集 X和 Y， 如果 X→Y，但 Y ? X，則稱 X→Y是 平凡的函數(shù)依賴 例：在關(guān)系 SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) → Grade 平凡函數(shù)依賴： (Sno, Cno) → Sno (Sno, Cno) → Cno 對(duì)于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語(yǔ)義，因此若不特別聲明， 我們總是討論非平凡函數(shù)依賴。 定義 在關(guān)系模式 R(U)中，如果 X→Y， Y→Z，且 Y ?X，Y→X，則稱 Z傳遞函數(shù)依賴 于 X。 ? 主屬性與非主屬性 ? 全碼 (ALL KEY) 定義 關(guān)系模式 R 中屬性或?qū)傩越M X 并非 R的碼，但 X 是另一個(gè)關(guān)系模式的碼，則稱 X 是 R 的 外部碼（ Foreign key） 也稱外碼 ? 主碼又和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。 ? 范式的種類： 第一范式 (1NF) 第二范式 (2NF) 第三范式 (3NF) BC范式 (BCNF) 第四范式 (4NF) 第五范式 (5NF) ? 各種范式之間存在聯(lián)系： NF5NF4BC N FNF3NF2NF1 ?????? 某一關(guān)系模式 R為第 n范式，可簡(jiǎn)記為 :R∈ nNF。 ? 但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。 (2) 刪除異常 假定某個(gè)學(xué)生本來只選修了 3號(hào)課程這一門課。 (4) 修改復(fù)雜 例如學(xué)生轉(zhuǎn)系，在修改此學(xué)生元組的 Sdept值的同時(shí)，還可能需要修改住處（ Sloc）。 ? 采用投影分解法將一個(gè) 1NF的關(guān)系分解為多個(gè) 2NF的關(guān)系，可以在一定程度上減輕原 1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 Sno Sdept SD Sdept Sloc DL 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例， SL(Sno, Sdept, Sloc) ∈ 2NF SL(Sno, Sdept, Sloc) ? 3NF SD（ Sno， Sdept） ∈ 3NF DL（ Sdept， Sloc） ∈ 3NF 3NF的定義 定義 關(guān)系模式 RU， F 中若不存在這樣的碼 X、屬性組 Y及 非主屬性 Z（ Z ? Y） , 使得 X→Y， Y → X， Y→Z，成立，則稱 RU， F ∈ 3NF。 ? 將一個(gè) 2NF關(guān)系分解為多個(gè) 3NF的關(guān)系后，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。則必然存在如下條件的函數(shù)依賴，X→Y （ Y?X）， Y→Z ，其中 X是含有碼的屬性， Y是任意屬性組， Z是非主屬性， Z?Y，這樣 Y→Z 函數(shù)依賴的決定因素 Y不包含候選碼，這與BCNF范式的定義相矛盾，所以如果R?BCNF，則 R也是 3NF 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 1 對(duì)關(guān)系模式 C、 SC、 S進(jìn)行分析。其他屬性不存在對(duì)碼的傳遞依賴與部分依賴，所以 S∈ 3NF。由語(yǔ)義可得到下面的函數(shù)依賴 : (S， J)→P ； (J， P)→S 候選碼為 :(S， J)與 (J， P) 這兩個(gè)碼各由兩個(gè)屬性組成，而且它們是相交的。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。 ? 一個(gè)模式中的關(guān)系模式如果都屬于 BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了徹底的分離，已消除了插入和刪除的異常。 ⒊ 沒有任何屬性完全函數(shù)依賴于 非碼 的任何一組屬性 . 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴 例 1: 學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。 (4) 修改操作復(fù)雜： 某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組。 這里， X， Y是 U的子集， Z=UXY。 倉(cāng)庫(kù)管理關(guān)系 按照語(yǔ)義對(duì)于 W的每一個(gè)值 Wi， S有一個(gè)完整的集合與之對(duì)應(yīng)而不論 C取何值。 若 X→Y，則 X→→Y。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴與函數(shù)依賴的區(qū)別 (1) 有效性 ? 多值依賴的有效性與屬性集的范圍有關(guān) 若 X→→Y在 U上成立，則在 W（ X Y ? W ? U）上一定成立；反之則不然，即 X→→Y在 W（ W ? U）上成立，在 U上并不一定成立 ? 多值依賴的定義中不僅涉及屬性組 X和 Y，而且涉及 U中其余屬性 Z。 成立 ? 多值依賴 X→→Y若在 R(U)上成立，不能斷言對(duì)于任何 Y? ? Y有 X→→Y? 成立。 ? 如果只考慮 函數(shù)依賴 ，則屬于 BCNF的關(guān)系模式規(guī)范化程度已最高了。 ? 規(guī)范化程度可以有多個(gè)不同的級(jí)別 ? 規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界，可能會(huì)存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題 ? 一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合（這個(gè)分解不是唯一的），這個(gè)過程就叫 關(guān)系模式的規(guī)范化 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 關(guān)系模式規(guī)范化的基本步驟 1NF ↓ 消除非主屬性對(duì)碼的部分函數(shù)依賴 消除決定屬性 2NF 集非碼的非平 ↓ 消除非主屬性對(duì)碼的傳遞函數(shù)依賴 凡函數(shù)依賴 3NF ↓ 消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴 BCNF ↓ 消除非平凡且非函數(shù)依賴的多值依賴 4NF 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 規(guī)范化的基本思想 ? 消除不合適的數(shù)據(jù)依賴 ? 模式中的各關(guān)系模式達(dá)到某種程度的“分離” ? 采用“一事一地”的模式設(shè)計(jì)原則 讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 數(shù)據(jù)依賴的公理系統(tǒng) 邏輯蘊(yùn)含 定義 對(duì)于滿足一組 函數(shù)依賴 F 的關(guān)系模式 R U， F，其任何一個(gè)關(guān)系 r，若函數(shù)依賴 X→Y都成立 , 則稱： F邏輯蘊(yùn)含 X →Y Armstrong公理系統(tǒng) 一套推理規(guī)則，是模式分解算法的理論基礎(chǔ) 用途 :1) 求給定關(guān)系模式的碼 2)從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 1. Armstrong公理系統(tǒng) 關(guān)系模式 R U， F 來說有以下的推理規(guī)則： （ Reflexivity）： 若 Y ? X ? U，則 X →Y為 F所蘊(yùn)含。 證： 設(shè) X→Y為 F所蘊(yùn)含，且 Z ? U。 對(duì) RU， F 的任一關(guān)系 r中的任意兩個(gè)元組 t， s。 分解規(guī)則 ：由 X→Y及 Z?Y，有 X→Z。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 F的閉包 F={A→B,B→C}, F+計(jì)算是 NP完全問題， X→A1A2...An F+={ A→φ, B→φ, C→φ, AB→φ, AC→φ, BC→φ, ABC→φ, A→A, B→B, C→C, AB→A, AC→A, BC→B, ABC→A, A→B, B→C , AB →B, AC→B, BC→C, ABC→B, A →C, B→BC, AB →C, AC→C, BC→BC, ABC →C, A→AB, AB→AB, AC→AB, ABC→AB, A→AC, AB→BC, AC→AC, ABC→BC, A→BC, AB→AC, AC→AB, ABC→AC, A→ABC, AB→ ABC,AC→ABC, ABC→ABC } 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 關(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+的子集的問題。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 求閉包的算法 [例 1] 已知關(guān)系模式 RU， F，其中 U={A， B， C， D， E}； F={AB→C， B→D， C→E， EC→B，