【正文】 X →Y為 F所蘊含 證 : 設(shè) Y ? X ? U 對 R U， F 的任一關(guān)系 r中的任意兩個元組 t， s： 若 t[X]=s[X]，由于 Y ? X，有 t[y]=s[y]， 所以 X→Y成立，自反律得證 An Introduction to Database System 定理 Armstrong推理規(guī)則是正確的（續(xù)） (2)增廣律 : 若 X→Y為 F所蘊含，且 Z ? U，則 XZ→YZ 為 F所蘊含。 證： 設(shè) X→Y及 Y→Z為 F所蘊含。 （ A2， A3） ? 分解規(guī)則 ：由 X→Y及 Z?Y，有 X→Z。 An Introduction to Database System 算法 對于算法 ， 令 ai =|X（ i） |， {ai }形成一個步長大于 1的嚴(yán)格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| |X| 次循環(huán)就 會終止。 (2) X（ 0） ≠ X（ 1） X（ 2） =X（ 1） ∪ BE=ABCDE。 An Introduction to Database System 5. 函數(shù)依賴集等價 定義 如果 G+=F+，就說函數(shù)依賴集 F覆蓋 G（ F是 G的覆蓋，或 G是 F的覆蓋），或 F與 G等價 。 所以 X→Y ? (G+） += G+。 亦稱為 最小依賴集 或 最小覆蓋 。 An Introduction to Database System 最小依賴集 [例 2] 關(guān)系模式 SU， F， 其中： U={ Sno， Sdept， Mname， Cno， Grade }， F={ Sno→Sdept， Sdept→Mname， (Sno， Cno)→Grade } 設(shè) F’={Sno→Sdept， Sno→Mname， Sdept→Mname， (Sno， Cno)→Grade， (Sno， Sdept)→Sdept} F是最小覆蓋，而 F’不是。 An Introduction to Database System 極小化過程（續(xù)） (1)逐一檢查 F中各函數(shù)依賴 FDi： X→Y， 若 Y=A1A2 … Ak， k 2， 則用 { X→Aj |j=1， 2， … ， k} 來取代 X→Y。具有無損連接性的分解不一定能夠保持函數(shù)依賴；同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。 。 ?算法 轉(zhuǎn)換為 3NF既有無損連接性又保持函數(shù)依賴的分解 ?算法 （ 分解法 ） 轉(zhuǎn)換為 BCNF的無損連接分解 ?算法 達到 4NF的具有無損連接性的分解 An Introduction to Database System 第六章 關(guān)系數(shù)據(jù)理論 問題的提出 規(guī)范化 數(shù)據(jù)依賴的公理系統(tǒng) * 模式的分解 小結(jié) An Introduction to Database System 小結(jié) 關(guān)系模式的規(guī)范化，其基本思想： An Introduction to Database System 小結(jié) (續(xù) ) ?若要求分解具有無損連接性，那么模式分解一定能夠達到 4NF ?若要求分解保持函數(shù)依賴，那么模式分解一定能夠達到 3NF，但不一定能夠達到 BCNF ?若要求分解既具有無損連接性，又保持函數(shù)依賴，則模式分解一定能夠達到 3NF，但不一定能夠達到 BCNF An Introduction to Database System 小結(jié) (續(xù) ) ?規(guī)范化理論為數(shù)據(jù)庫設(shè)計提供了理論的指南和工具 ? 也僅僅是指南和工具 ?并不是規(guī)范化程度越高 ， 模式就越好 ? 必須結(jié)合應(yīng)用環(huán)境和現(xiàn)實世界的具體情況合理地選擇數(shù)據(jù)庫模式 An Introduction to Database System 下課了。 (3)逐一取出 F中各函數(shù)依賴 FDi： X→A， 設(shè) X=B1B2… Bm， 逐一考查 Bi （ i=l， 2， … ， m） ， 若 A ?（ XBi ） F+ ， 則以 XBi 取代 X。 此 Fm稱為 F的最小依賴集 。 (2) F中不存在這樣的函數(shù)依賴 X→A， 使得 F與 F{X→A}等價 。 （ 3）同理可證 G+ ? F+ ，所以 F+ = G+。 （ 1）若 F?G+ ，則 XF+ ? XG++ 。 An Introduction to Database System 4. Armstrong公理系統(tǒng)的有效性與完備性 ?定理 Armstrong公理系統(tǒng)是有效的、完備的 ?證明： 1. 有效性 可由定理 2. 完備性 只需證明 逆否命題 : 若函數(shù)依賴 X→Y不能由 F從 Armstrong公理導(dǎo)出，那么它必然不為 F所蘊含 An Introduction to Database System Armstrong公理系統(tǒng)完備性證明 (1) 引理 : 若 V→W成立 ， 且 V ? XF+， 則 W ? XF+ (2) 構(gòu)造一張二維表 r，它由下列兩個元組構(gòu)成，可以證明 r必是 R（ U， F）的一個關(guān)系 ，即 F+中的全部函數(shù)依賴在 r上成立。 求（ AB） F+ 。 定義 設(shè) F為屬性集 U上的一組函數(shù)依賴， X ?U， XF+ ={ A|X→A能由 F 根據(jù) Armstrong公理導(dǎo)出 }，XF+稱為屬性集 X關(guān)于函數(shù)依賴集 F 的閉包 An Introduction to Database System F的閉包 F={X?Y, Y?Z} F+={ X?φ, Y?φ, Z?φ, XY?φ, XZ?φ, YZ?φ, XYZ?φ, X?X, Y?Y, Z?Z, XY?X, XZ?X, YZ?Y, XYZ?X, X?Y, Y ?Z, XY?Y, XZ?Y, YZ?Z, XYZ?Y, X?Z, Y?YZ, XY?Z, XZ?Z, YZ?YZ,XYZ?Z, X?XY, XY?XY,XZ?XY, XYZ?XY, X?XZ, XY?YZ,XZ?XZ, XYZ?YZ, X?YZ, XY?XZ,XZ?XY, XYZ?XZ, X?ZYZ, XY?XYZ,XZ?XYZ, XYZ?XYZ } F={X?A1, …… , X ?An}的閉包 F+計算是一個 NP完全問題 An Introduction to Database System 關(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+的子集的問題 An Introduction to Database System 求閉包的算法 算法 求屬性集 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+ , 算法終止。 An Introduction to Database System 2. 導(dǎo)出規(guī)則 A1， A2， A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： ? 合并規(guī)則 ：由 X→Y， X→Z，有 X→YZ。 設(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所蘊含，增廣律得證。 ? （ Augmentation）：若 X→Y為 F所蘊含，且 Z ? U，則 XZ→YZ為 F所蘊含。 成立 ? 多值依賴 X→→Y若在 R(U)上成立，不能斷言對于任何 Y39。 （ 5）若 X→→Y， X→→Z，則 X→→Y∩Z。 這里， X， Y是 U的子集，Z=UXY。 ? 函數(shù)依賴： (S， J)→T， (S， T)→J， T→J ? (S， J)和 (S， T)都是候選碼 An Introduction to Database System BCNF（續(xù)） J S J T S T STJ中的函數(shù)依賴 An Introduction to Database System BCNF（續(xù)） ?STJ∈ 3NF ? 沒有任何非主屬性對碼傳遞依賴或部分依賴 ?STJ∈ BCNF ? T是決定因素， T不包含碼 An Introduction to Database System BCNF（續(xù)） ?解決方法：將 STJ分解為二個關(guān)系模式： ST(S， T) ∈ BCNF， TJ(T， J)∈ BCNF 沒有 任何屬性 對碼的部分函數(shù)依賴和傳遞函數(shù)依賴 S J ST T J TJ An Introduction to Database System 3NF與 BCNF的關(guān)系 ?R ∈ BCNF R ∈ 3NF ?如果 R∈ 3NF，且 R只有一個候選碼 R ∈ BCNF R ∈ 3NF 充分 不必要 充分 必要 An Introduction to Database System 規(guī)范化 函數(shù)依賴 碼 范式 2NF 3NF BCNF 多值依賴 4NF 規(guī)范化小結(jié)