【文章內(nèi)容簡(jiǎn)介】 y2 z2 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 平凡多值依賴(lài)和非平凡的多值依賴(lài) ? 若 X→→Y，而 Z＝ φ，則稱(chēng) X→→Y為 平凡的多值依賴(lài) ? 否則稱(chēng) X→→Y為 非平凡的多值依賴(lài) 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 2：關(guān)系模式 WSC(W,S,C)中， W表示倉(cāng)庫(kù)，S表示保管員， C表示商品。假設(shè)每個(gè)倉(cāng)庫(kù)有若干個(gè)保管員，有若干種商品。每個(gè)保管員保管所在倉(cāng)庫(kù)的所有商品，每種商品被所有保管員保管。 倉(cāng)庫(kù)管理關(guān)系 按照語(yǔ)義對(duì)于 W的每一個(gè)值 Wi， S有一個(gè)完整的集合與之對(duì)應(yīng)而不論 C取何值。所以 W→→S。 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ù)理論 多值依賴(lài)的性質(zhì) （ 1）多值依賴(lài)具有對(duì)稱(chēng)性 若 X→→Y，則 X→→Z，其中 Z＝ U－ X－ Y 多值依賴(lài)的對(duì)稱(chēng)性可以用完全二分圖直觀(guān)地表示出來(lái)。 （ 2）多值依賴(lài)具有傳遞性 若 X→→Y， Y→→Z， 則 X→→Z Y Xi Zi1 Zi2 … Zim Yi1 Yi2 … Yin （ 3）函數(shù)依賴(lài)是多值依賴(lài)的特殊情況。 若 X→Y，則 X→→Y。 （ 4）若 X→→Y， X→→Z，則 X→→Y? Z。 （ 5）若 X→→Y， X→→Z，則 X→→Y∩Z。 （ 6）若 X→→Y， X→→Z，則 X→→YZ， X→→Z Y。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴(lài)與函數(shù)依賴(lài)的區(qū)別 (1) 有效性 ? 多值依賴(lài)的有效性與屬性集的范圍有關(guān) 若 X→→Y在 U上成立，則在 W（ X Y ? W ? U）上一定成立；反之則不然，即 X→→Y在 W（ W ? U）上成立，在 U上并不一定成立 ? 多值依賴(lài)的定義中不僅涉及屬性組 X和 Y，而且涉及 U中其余屬性 Z。 ? 一般地，在 R（ U）上若有 X→→Y在 W（ W ? U）上成立，則稱(chēng) X→→Y為 R（ U）的嵌入型多值依賴(lài) ? 只要在 R（ U）的任何一個(gè)關(guān)系 r中，元組在 X和 Y上的值滿(mǎn)足定義 （函數(shù)依賴(lài)），則函數(shù)依賴(lài) X→Y在任何屬性集 W（ X Y ? W ?U）上成立。 (2) ? 若函數(shù)依賴(lài) X→Y在 R（ U）上成立，則對(duì)于任何 Y39。 ? Y均有 X→Y39。 成立 ? 多值依賴(lài) X→→Y若在 R(U)上成立，不能斷言對(duì)于任何 Y? ? Y有 X→→Y? 成立。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 第四范式（ 4NF） ? 如果 R ∈ 4NF， 則 R ∈ BCNF 不允許 有非平凡且非函數(shù)依賴(lài)的 多值依賴(lài)，允許 的是 函數(shù)依賴(lài)（是平凡多值依賴(lài)）。 定義 關(guān)系模式 RU， F∈ 1NF，如果對(duì)于 R的每個(gè)非平凡多值依賴(lài) X→→Y（ Y ? X）， X都含有候選碼，則 R∈ 4NF。 （ X→Y） ? 函數(shù)依賴(lài)和多值依賴(lài)是兩種最重要的數(shù)據(jù)依賴(lài)。 ? 如果只考慮 函數(shù)依賴(lài) ，則屬于 BCNF的關(guān)系模式規(guī)范化程度已最高了。 ? 如果考慮 多值依賴(lài) ，則屬于 4NF的關(guān)系模式規(guī)范化程度是最高的了。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 存在非平凡的多值依賴(lài) C→→T，且 C不是候選碼 ? 用投影分解法把 Teach分解為如下兩個(gè)關(guān)系模式： CT(C, T) ∈ 4NF CB(C, B) ∈ 4NF C→→T， C→→B是平凡多值依賴(lài) ? 同樣的方法可以把 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ì)的工具。 ? 一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng)，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。 ? 規(guī)范化程度可以有多個(gè)不同的級(jí)別 ? 規(guī)范化程度過(guò)低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界，可能會(huì)存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問(wèn)題 ? 一個(gè)低一級(jí)范式的關(guān)系模式，通過(guò)模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合（這個(gè)分解不是唯一的），這個(gè)過(guò)程就叫 關(guān)系模式的規(guī)范化 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 關(guān)系模式規(guī)范化的基本步驟 1NF ↓ 消除非主屬性對(duì)碼的部分函數(shù)依賴(lài) 消除決定屬性 2NF 集非碼的非平 ↓ 消除非主屬性對(duì)碼的傳遞函數(shù)依賴(lài) 凡函數(shù)依賴(lài) 3NF ↓ 消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴(lài) BCNF ↓ 消除非平凡且非函數(shù)依賴(lài)的多值依賴(lài) 4NF 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 規(guī)范化的基本思想 ? 消除不合適的數(shù)據(jù)依賴(lài) ? 模式中的各關(guān)系模式達(dá)到某種程度的“分離” ? 采用“一事一地”的模式設(shè)計(jì)原則 讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去 ? 所謂規(guī)范化實(shí)質(zhì)上是概念的 單一 化 ? 不能說(shuō)規(guī)范化程度越高的關(guān)系模式就越好。 ? 在設(shè)計(jì)數(shù)據(jù)庫(kù)模式結(jié)構(gòu)時(shí)，必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況和用戶(hù)應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式。 ? 上面的規(guī)范化步驟可以在其中任何一步終止。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 數(shù)據(jù)依賴(lài)的公理系統(tǒng) 邏輯蘊(yùn)含 定義 對(duì)于滿(mǎn)足一組 函數(shù)依賴(lài) F 的關(guān)系模式 R U， F，其任何一個(gè)關(guān)系 r，若函數(shù)依賴(lài) X→Y都成立 , 則稱(chēng)： F邏輯蘊(yùn)含 X →Y Armstrong公理系統(tǒng) 一套推理規(guī)則，是模式分解算法的理論基礎(chǔ) 用途 :1) 求給定關(guān)系模式的碼 2)從一組函數(shù)依賴(lài)求得蘊(yùn)含的函數(shù)依賴(lài) 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 1. Armstrong公理系統(tǒng) 關(guān)系模式 R U， F 來(lái)說(shuō)有以下的推理規(guī)則： （ Reflexivity）： 若 Y ? X ? U，則 X →Y為 F所蘊(yùn)含。 （ Augmentation）：若 X→Y為 F所蘊(yùn)含，且 Z ? U，則XZ→YZ為 F所蘊(yùn)含。 （ Transitivity）：若 X→Y及 Y→Z為 F所蘊(yùn)含，則 X→Z為 F所蘊(yùn)含。 注意：由自反律所得到的函數(shù)依賴(lài)均是平凡的函數(shù)依賴(lài)，自反律的使用并不依賴(lài)于 F 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 定理 Armstrong推理規(guī)則是正確的 (l)自反律 :若 Y ? X ? U，則 X →Y為 F所蘊(yùn)含 證 : 設(shè) Y ? X ? U 對(duì) R U， F 的任一關(guān)系 r中的任意兩個(gè)元組 t， s： 若 t[X]=s[X]，由于 Y ? X，有 t[y]=s[y]， 所以 X→Y成立 . 自反律得證 (2)增廣律 : 若 X→Y為 F所蘊(yùn)含，且 Z ? U，則 XZ→YZ 為 F所蘊(yùn)含。 證： 設(shè) X→Y為 F所蘊(yùn)含，且 Z ? U。 設(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)含 . 增廣律得證。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 (3) 傳遞律：若 X→Y及 Y→Z為 F所蘊(yùn)含，則 X→Z為 F所蘊(yùn)含。 證： 設(shè) X→Y及 Y→Z為 F所蘊(yùn)含。 對(duì) RU， F 的任一關(guān)系 r中的任意兩個(gè)元組 t， s。 若 t[X]=s[X]，由于 X→Y，有 t[Y]=s[Y]； 再由 Y→Z，有 t[Z]=s[Z]，所以 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。 偽傳遞規(guī)則 ：由 X→Y， WY→Z，有 XW→Z。 分解規(guī)則 ：由 X→Y及 Z?Y，有 X→Z。 ，可得引理 引理 X→A1 A2…A k成立的充分必要條件是 X→Ai成立（ i=l， 2， … ，k）。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 3. 函數(shù)依賴(lài)閉包 定義 在關(guān)系模式 RU， F中為 F所邏輯蘊(yùn)含的函數(shù)依賴(lài)的全體叫作 F的閉包 ，記為 F+。 定義 設(shè) F為屬性集 U上的一組函數(shù)依賴(lài)， X ?U， XF+ ={ A|X→A能由 F 根據(jù) Armstrong公理導(dǎo)出 }， XF+稱(chēng)為屬性集 X關(guān)于函數(shù)依賴(lài)集 F 的閉包 例 :設(shè) RU， F， U={A， B， C)， F＝ {A→B， B→C}， 則： ① 當(dāng) X＝ A時(shí) ， XF+＝ ABC； ② 當(dāng) X＝ B時(shí) ， XF+＝ BC； ③ 當(dāng) X＝ C時(shí) ， XF+＝ C。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 F的閉包 F={A→B,B→C}, F+計(jì)算是 NP完全問(wèn)題， 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ù)依賴(lài)， X， Y ? U， X→Y能由F 根據(jù) Armstrong公理導(dǎo)出的充分必要條件是 :Y ?XF+ 用途 將判定 X→Y是否能由 F根據(jù) Armstrong公理導(dǎo)出的問(wèn)題，就轉(zhuǎn)化為求出 XF+ ，判定 Y是否為 XF+的子集的問(wèn)題。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 求閉包的算法 算法 求屬性集 X（ X ? U）關(guān)于 U上的函數(shù)依賴(lài)集 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）