【正文】 y4 x1 y1 x3 y2 x2 y4 x4 y4 T3 A B B A A B B A A B B A School of software Yunnan University 74 Functional Dependencies ?Definition 給定表 T和兩個屬性集，分別為X=A1A2… AK和 Y=B1B2… Bm。 我們說 X→ Y（讀做 “ X函數(shù)決定 Y”或者 “ Y函數(shù)依賴于 X”），當(dāng)且僅當(dāng)設(shè)計者的意圖是對于表中可能存在的任何行的集合， T中的兩行不能在 X上取相同值而在 Y上取不同值。 ?More formally: X=A1 A2… AK and Y=B1 B2… Bm given two rows r1 and r2 in T, if r1(Ai)= r2(Ai) for every Ai in X, then r1(Bj)= r2(Bj) for every Bj in Y. School of software Yunnan University 75 Functional Dependencies ? Example ?We list all the functional dependencies (FDs) for the emp_info table of Figure . (1) emp_id (2) dept_name (3) skill_id (4) emp_id skill_id emp_name emp_phone dept_name dept_phone dept_mgrname skill_name skill_date skill_lvl School of software Yunnan University 76 Functional Dependencies ? Logical Implications（ 邏輯蘊涵 ） among Functional Dependencies Theorem Inclusion Rule（ 包含規(guī)則 ） ? Given a table T with a specified heading ( set of attributes, ), Head(T). If X and Y are sets of attributes contained in Head(T), and Y ? X, then X Y Definition Trivial Dependency（ 平凡依賴 ） ? A trivial dependency is an FD of the form X Y, in a table T where X ∪ Y ? Head(T), that will hold for any possible content of the table T. Theorem Given a trivial dependency X Y in T, it must be the case that Y ? X ?School of software Yunnan University 77 Functional Dependencies ?Armstrong’s Axioms（ 公理 ） 給定表 T， 其中 X、 Y、 Z是 T的屬性集并為 U的子集 ， 則有以下推理規(guī)則： A1：自反律 （ Reflexivity rule ） 如果 Y? X?U， 則 X→ Y為 F所蘊涵 。 A2：增廣律 （ Augmentation rule） 如果 X→ Y為 F所蘊涵 ， 且 Z?U， 則 XZ→ YZ為 F所蘊涵 。 A3：傳遞律 （ Transitivity rule ） 如果 X→ Y和 Y→ Z為 F所蘊涵 ， 則 X→ Z為 F所蘊涵 。 ?School of software Yunnan University 78 Functional Dependencies ? Armstrong公理是正確的 ， 即由 F出發(fā)根據(jù) Armstrong公理推導(dǎo)出來的每一個函數(shù)依賴必定為 F所邏輯蘊涵 。 ? 根據(jù) Armstrong公理可以得到下面幾條推論 ， 它們也是很有用的推理規(guī)則 。 （ 1） Union Rule If X→Y ， X→Z ， then X→YZ 。 （ 2） Pseudotransitivity Rule If X→Y 、 WY→Z ， then XW→Z 。 （ 3） Deposition Rule If X→YZ ， then X→Y and X→Z 。 （ 4） Set accumulation Rule If X→YZ ， and Z→W ， then X→YZW 。 School of software Yunnan University 79 Functional Dependencies 證明： （ 1） 合并規(guī)則可用公理 A2和 A3證明 。 因為 X→Y ， 所以根據(jù)A2可得 XX→XY ， 即 X→XY ；同理由 X→Z 可得 XY→YZ 。 根據(jù) A3，由 X→XY 和 XY→YZ 可得 X→YZ 。 （ 2） 偽傳遞規(guī)則也可用公理 A2和 A3證明 。 首先根據(jù) A2， 由X→Y 得 XW→WY ；再根據(jù) A3， 由 XW→WY 和 WY→Z 得 XW→Z 。 （ 3） 分解規(guī)則可用公理 A1和 A3證明 。 根據(jù) A1， 如果 Z?Y， 則得 Y→Z ；又根據(jù) A3， 由 X→Y 和 Y→Z ， 得 X→Z 。 ? 分解規(guī)則說明若 Y函數(shù)依賴于 X， 則把 Y分解后的各部分屬性也函數(shù)依賴于 X。 因此 ， 可以用更為直觀的形式表述分解規(guī)則 ， 即若 X→YZ ， 則 X→Y 、 X→Z 。 ? 根據(jù)合并規(guī)則和分解規(guī)則可以得出一個重要的結(jié)論：X→A 1A2? An成立的充分必要條件是 X→A i（ i＝ 1， 2， ? ， n）成立 。 School of software Yunnan University 80 ? Closure(閉包 ),Cover(覆蓋 ) and Minimal Cover (最小覆蓋 ) Definition Closure of a Set of FDs Given a set F of FDs on attributes of a table T, we define the Closure of F, symbolized by F+, to be the set of all FDs implied by F. 給定表 T和函數(shù)依賴集 F， 被 F所邏輯蘊涵的函數(shù)依賴的全體稱為 F的閉包 ， 記為 F+。 Functional Dependencies School of software Yunnan University 81 Definition FD Set Cover 設(shè) F和 G是兩個函數(shù)依賴集 ， 如果 F+＝ G+， 則稱 F和 G等價 ， 也稱 F覆蓋 G， 或 G覆蓋 F。 F+＝ G+ 的充分必要條件是 F?G+和 G?F+。 Example F= {B→ CD, AD→ E ,B→ A } and G= {B→ CDE, B→ ABC, AD→ E} We will demonstrate that F covers G(G?F+). Functional Dependencies School of software Yunnan University 82 Definition Closure of a Set of Attributes 設(shè) F是屬性集 U上的函數(shù)依賴集 ， X是 U的子集 ， 則由Armstrong公理可從 F推導(dǎo)出的所有 X→A i所形成的屬性集{Ai｜ i＝ 1,2,? }稱為 X對于 F的閉包 ， 記為 X+。 引理 : 當(dāng)且僅當(dāng) Y ? X+時 ， X→Y 能根據(jù) Armstrong公理由 F導(dǎo)出 。 例：設(shè) R＝ ABC， F＝ ｛ A→B ， B→C ｝ ， 則 ① 當(dāng) X＝ A時 ， X+＝ ABC； ② 當(dāng) X＝ B時 ， X+＝ BC； ③ 當(dāng) X＝ C時 ， X+＝ C。 Functional Dependencies School of software Yunnan University 83 ? Algorithm Set Closure 算法 求屬性集 X關(guān)于函數(shù)依賴集 F的閉包 X+。 輸入：關(guān)系模式 R的屬性全集 U， 在 U上的函數(shù)依賴集 F， 以及 U的子集 X。 輸出：屬性集 X關(guān)于 F的閉包 X+。 Functional Dependencies School of software Yunnan University 84 ? Algorithm Set Closure 方法： （ 1） 令 X(0)＝ X， i=0； （ 2） 計算 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)， 則令 i＝ i+1， 返回 （ 2） ； （ 5）輸出 X (i)，它就是 X+。 Functional Dependencies School of software Yunnan University 85 Functional Dependencies ? 函數(shù)依賴集 F計算 F+是一件相當(dāng)費時的事 。 即使 F很小 ， F+卻可能很大 。 ? 但幸運的是計算 F+的目的往往是為了判斷函數(shù)依賴 X→ Y 是否為 F所蘊涵 ， 而根據(jù)引理 ， 只要知道 Y ? X+， 就可以斷定 X→ Y 為 F所蘊涵 。 因此 ， 可以用計算 X+代替計算 F+， 通過判斷是否滿足 Y ? X+來判定 X→ Y 是否為 F所蘊涵 。 School of software Yunnan University 86 ? 例 已知關(guān)系模式 R中 U＝ {A， B， C， D， E， G}，F(xiàn)＝ {AB→ C， C→ A， BC→ D， ACD→ B， D→ EG， BE→ C，CG→ BD， CE→ AG｝ ， 求 (BD)+。 解：設(shè) X＝ BD （ 1） 令 X(0)＝ BD。 （ 2） 計算 X(1)：在 F中找左邊為 X(0)子集即 B、 D或 BD的函數(shù)依賴 ， 結(jié)果有 D→ EG， 所以 X(1)＝ X(0)∪ EG＝ BDEG。 （ 3） 計算 X(2)：在 F中找尚未使用過的 、 左邊為 X(1)子集的函數(shù)依賴 ， 得 BE→ C， 所以 X(2)＝ X(1)∪ C＝ BCDEG。 （ 4） 計算 X(3)：在 F中找尚未用過且左邊為 X(2)子集的函數(shù)依賴 ， 得 C→ A、 BC→ D、 CG→ BD、 CE→ AG， 所以 X(3)＝X(2)∪ ABDG＝ ABCDEG。 由于 X(3)已包含全部屬性，顯然 X(4)＝ X(3)，算法終止，得 (BD)+＝ ABCDEG。 Functional Dependencies School of software Yunnan University 87 定義 如果函數(shù)依賴集 F 滿足： （ 1） F中每一個函數(shù)依賴的右部僅含單個屬性； （ 2） 對于 F中的任一函數(shù)依賴 X→ A， 函數(shù)依賴集 F－{ X→ A }不等價于 F； （ 3）對于 F中的任一函數(shù)依賴 X→ A和 X的任何真子集Z，函數(shù)依賴集 (F－ { X→ A })∪{ Z→ A}不等價于 F，則稱 F為 最小函數(shù)依賴集 或稱 最小覆蓋 。 Functional Dependencies School of software Yunnan University 88 ? 最小函數(shù)依賴集的計算方法 。 （ 1） 為了滿足條件 （ 1） ， 只要根據(jù)分解規(guī)則把右側(cè)是屬性組的函數(shù)依賴分解為單屬性的多個函數(shù)依賴即可 。 例如A→BC 可分解為 A→B 和 A→C ， 從而滿足條件 （ 1） 。 （ 2） 逐一考察 F中的函數(shù)依賴 X→ Y， 令 G＝ F－ { X→ Y }， 且對 G求 X+， 因為 F與 G等價的充要條件是 Y ?X+， 所以如果 Y ?X+， 則 X→ Y 冗余 ， 可以刪去 。 （ 3） 逐一考察 F中留下的函數(shù)依賴 ， 消去左側(cè)冗余的屬性 。為了判斷函數(shù)依賴 XY→ A中 Y是否冗余 ， 可在 F 中求 X+， 若A?X+， 則 Y是冗余屬性 。 經(jīng)過上述三步處理之后剩下的 F一定是最小函數(shù)依賴集，并且與原來的 F等價。 F的最小函數(shù)依賴集不一定是唯一的。 Functional Dependencies School of software