【正文】 止 所以（ AB） F+ =ABCDE。 于是 X（ 1） =AB∪ CD=ABCD。 解 設(shè) X（ 0） =AB； (1)計(jì)算 X（ 1） : 逐一的掃描 F集合中各個(gè)函數(shù)依賴， 找左部為 A， B或 AB的函數(shù)依賴。 數(shù)據(jù)庫系統(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， AC→B}。 （ 6）若否，則 i=i+l，返回第（ 2）步。 數(shù)據(jù)庫系統(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ù)庫系統(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ù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 3. 函數(shù)依賴閉包 定義 在關(guān)系模式 RU， F中為 F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包 ，記為 F+。 分解規(guī)則 ：由 X→Y及 Z?Y，有 X→Z。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 2. 導(dǎo)出規(guī)則 A1， A2， A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則 ：由 X→Y， X→Z，有 X→YZ。 對(duì) RU， F 的任一關(guān)系 r中的任意兩個(gè)元組 t， s。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 (3) 傳遞律：若 X→Y及 Y→Z為 F所蘊(yùn)含，則 X→Z為 F所蘊(yùn)含。 證： 設(shè) X→Y為 F所蘊(yùn)含，且 Z ? U。 （ Transitivity）：若 X→Y及 Y→Z為 F所蘊(yùn)含，則 X→Z為 F所蘊(yùn)含。 數(shù)據(jù)庫系統(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ù)庫系統(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è)計(jì)數(shù)據(jù)庫模式結(jié)構(gòu)時(shí)，必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式。 ? 規(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ù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 關(guān)系模式規(guī)范化的基本步驟 1NF ↓ 消除非主屬性對(duì)碼的部分函數(shù)依賴 消除決定屬性 2NF 集非碼的非平 ↓ 消除非主屬性對(duì)碼的傳遞函數(shù)依賴 凡函數(shù)依賴 3NF ↓ 消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴 BCNF ↓ 消除非平凡且非函數(shù)依賴的多值依賴 4NF 數(shù)據(jù)庫系統(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ù)庫系統(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ù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 規(guī)范化小結(jié) ? 關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具。 ? 如果只考慮 函數(shù)依賴 ，則屬于 BCNF的關(guān)系模式規(guī)范化程度已最高了。 定義 關(guān)系模式 RU， F∈ 1NF，如果對(duì)于 R的每個(gè)非平凡多值依賴 X→→Y（ Y ? X）， X都含有候選碼，則 R∈ 4NF。 成立 ? 多值依賴 X→→Y若在 R(U)上成立，不能斷言對(duì)于任何 Y? ? Y有 X→→Y? 成立。 (2) ? 若函數(shù)依賴 X→Y在 R（ U）上成立，則對(duì)于任何 Y39。 數(shù)據(jù)庫系統(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。 （ 5）若 X→→Y， X→→Z，則 X→→Y∩Z。 若 X→Y，則 X→→Y。 Si1 ， Si2 ， … … Sin Ci1 ， Ci2 ， … … C in Wi S C Wi Wi 于是 {S}Wi與 {C}Wi之間正好形式一個(gè)完全二分圖，如圖 : 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴的性質(zhì) （ 1）多值依賴具有對(duì)稱性 若 X→→Y，則 X→→Z，其中 Z＝ U－ X－ Y 多值依賴的對(duì)稱性可以用完全二分圖直觀地表示出來。 倉庫管理關(guān)系 按照語義對(duì)于 W的每一個(gè)值 Wi， S有一個(gè)完整的集合與之對(duì)應(yīng)而不論 C取何值。假設(shè)每個(gè)倉庫有若干個(gè)保管員，有若干種商品。 這里， X， Y是 U的子集， Z=UXY。 例 Teaching（ C, T, B） 對(duì)于 C的每一個(gè)值， T有一組值與之對(duì)應(yīng)，而不論 B取何值。 (4) 修改操作復(fù)雜： 某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組。 (2) 插入操作復(fù)雜： 當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組。 ⒊ 沒有任何屬性完全函數(shù)依賴于 非碼 的任何一組屬性 . 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴 例 1: 學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。 BCNF的關(guān)系模式所具有的性質(zhì) ⒈ 所有 非主屬性 都完全函數(shù)依賴于每個(gè)候選碼 。 ? 一個(gè)模式中的關(guān)系模式如果都屬于 BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了徹底的分離，已消除了插入和刪除的異常。 由語義可得到下面的函數(shù)依賴 : (S， J)→T， (S， T)→J， T→J ? 候選碼為： (S， J)和 (S， T) ? S、 T、 J都是主屬性 ， 所以 STJ∈ 3NF ? T→J， T是決定屬性集， T不是候選碼 STJ∈ BCNF S J T S T J 解決方法： 將 STJ分解為二個(gè)關(guān)系模式： SJ(S， J) ∈ BCNF， TJ(T， J)∈ BCNF T J TJ S J ST 沒有 任何屬性 對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 練習(xí)題 指明下列關(guān)系模式屬于第幾范式 . 1. R(X,Y,Z) F={XY→Z} 2. R(X,Y,Z) F={Y→Z,XZ→Y} 3. R(X,Y,Z) F={Y→Z,Y→X,X→YZ} 4. R(X,Y,Z) F={X→Y,X→Z} 5. R(W,X,Y,Z) F={X→Z,WX→Y} 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 3NF與 BCNF的關(guān)系與區(qū)別 ? 如果關(guān)系模式 R∈ BCNF，必定有 R∈ 3NF ? 如果 R∈ 3NF，且 R只有一個(gè)候選碼，則 R必屬于 BCNF。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。所以 SJP∈ 3NF，而且除 (S,J)與 (J,P)以外沒有其它決定因素，所以 SJP∈ BCNF 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 3：在關(guān)系模式 STJ（ S， T， J）中， S表示學(xué)生， T表示教師，J表示課程。由語義可得到下面的函數(shù)依賴 : (S， J)→P ； (J， P)→S 候選碼為 :(S， J)與 (J， P) 這兩個(gè)碼各由兩個(gè)屬性組成，而且它們是相交的。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 2：關(guān)系模式 SJP(S,J,P)中， S是學(xué)生， J表示課程， P表示名次。其他屬性不存在對(duì)碼的傳遞依賴與部分依賴，所以 S∈ 3NF。同時(shí) C中 Cno是唯一的決定因素，所以 C∈ BCNF。則必然存在如下條件的函數(shù)依賴，X→Y （ Y?X）， Y→Z ，其中 X是含有碼的屬性， Y是任意屬性組， Z是非主屬性， Z?Y，這樣 Y→Z 函數(shù)依賴的決定因素 Y不包含候選碼，這與BCNF范式的定義相矛盾，所以如果R?BCNF，則 R也是 3NF 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 1 對(duì)關(guān)系模式 C、 SC、 S進(jìn)行分析。 若 R∈ BCNF ? 每一個(gè)決定屬性集（因素）都包含（候選）碼 ? R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼 ? R∈ 3NF（證明） ? 若 R∈ 3NF 則 R不一定 ∈ BCNF 證明：采用反證法。 ? 將一個(gè) 2NF關(guān)系分解為多個(gè) 3NF的關(guān)系后，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。 ? 如果 R∈ 3NF，則 R也是 2NF。 Sno Sdept SD Sdept Sloc DL 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論