[工學(xué)]數(shù)據(jù)庫(kù)原理與技術(shù)第六章new(編輯修改稿)
2025-01-30 23:31 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 X??Z，其中 Z=U–X–Y。 ? 函數(shù)依賴是多值依賴的特例，即 若 X?Y，則 X??Y。 ? 若 X??Y， X??Z，則 X??YZ ? 若 X??Y， X??Z，則 X??Y∩Z ? 若 X??Y， X??Z，則 X??Y－ Z， X?? Z－ Y ? 若 X??Y， Y??Z，則 X?? Z － Y 多值依賴 Vs 函數(shù)依賴 (Ⅰ ) ?函數(shù)依賴有效性范圍 ? X?Y的有效性僅決定于 X、 Y屬性集上的值，它在任何屬性集 W（ XY ? W ? U）上都成立。 若 X?Y在 R(U)上成立，則對(duì)于任何 Y′? Y，均有X?Y ′成立。 多值依賴 Vs 函數(shù)依賴 (Ⅱ ) ?多值依賴有效性范圍 ? X??Y的有效性與屬性集范圍有關(guān)。 X??Y在 U上成立 ? X??Y在屬性集 W（ XY ? W ? U）上成立。反之則不然。 若在 R(U)上， X??Y在屬性集 W(XY ? W ? U)上成立，則稱 X??Y為 R(U) 的嵌入式多值依賴。 若 X??Y在 R(U)上成立，則不能斷言對(duì)于 Y′? Y，是否有 X??Y ′成立。 4NF ?定義 ? 關(guān)系模式 R U , F ? 1NF，如果對(duì)于 R到每個(gè)非平凡的多值依賴 X??Y（ Y?X）是， X都含有碼，則稱 R?4NF。 ?4NF就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴。因?yàn)楦鶕?jù)定義，對(duì)于每一個(gè)非平凡的多值依賴 X??Y， X都含有候選碼，于是就有 X?Y，所以 4NF所允許的非平凡的多值依賴實(shí)際上是函數(shù)依賴。 4NF ? 如關(guān)系模式 CPB， C??P， C??B， 碼為 (C, P, B)，所以 CPB?4NF。 如果一門課 Ci有 m個(gè)教師， n本參考書，則關(guān)系中分量為 Ci的元組共有 m n個(gè)，數(shù)據(jù)冗余非常大。 ?改造 將 CPB分解為 CP（ C， P）， CB（ C，B） 。 數(shù)據(jù)依賴的公理系統(tǒng) ?定義 ? 對(duì)于滿足一組函數(shù)依賴 F的關(guān)系模式 R U, F ，其任何一個(gè)關(guān)系 r，若函數(shù)依賴 X?Y都成立，則稱 F邏輯蘊(yùn)涵 X?Y。 ?Armstrong公理 X， Y， Z是屬性集， ? 自反律。若 Y?X?U， 則 X?Y為 F所蘊(yùn)含。 ? 增廣律。若 X?Y為 F所蘊(yùn)含，且 Z?U，則 XZ ? YZ為 F所蘊(yùn)含。 ? 傳遞律。若 X?Y及 Y?Z為 F所蘊(yùn)含，則 X?Z為 F所蘊(yùn)含。 數(shù)據(jù)依賴的公理系統(tǒng) ?在關(guān)系模式 R U, F 中，為 F所邏輯蘊(yùn)涵的函數(shù)依賴的全體稱作 F的閉包，記作 F+。 例： F={X?Y， Y?Z}，則 {X?Z} ? F+。 ?Armstrong公理的有效性及完備性 ? 有效性：由 F出發(fā)根據(jù) Armstrong公理推導(dǎo)出來的函數(shù)依賴一定在 F+中。 ? 完備性： F+中的每一個(gè)函數(shù)依賴都可以由 F出發(fā)根據(jù) Armstrong公理從 F中導(dǎo)出。 數(shù)據(jù)依賴的公理系統(tǒng) ?關(guān)于 Armstrong公理有效性的證明 ? 設(shè) Y?X?U， RU, F上的任一關(guān)系 r的兩個(gè)元組 t， s 若 t[X]=s[X]，由 Y?X，有 t[Y]=s[Y]，所以 X?Y成立，自反律得證。 ? 設(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ù)依賴的公理系統(tǒng) ? 設(shè) X?Y及 Y?Z為 F所蘊(yùn)含。 設(shè) 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)含，傳遞律得證。 ?由 Armstrong公理導(dǎo)出的推理規(guī)則 ? 合并律。若 X ? Y， X ? Z，則 X ? YZ。 ? 分解律。若 X ? YZ ，則 X ? Y， X ? Z 。 ? 偽傳遞律。若 X ? Y， WY ? Z，則 XW ? Z 數(shù)據(jù)依賴的公理系統(tǒng) ?示例 R U, F , U = (A, B, C, G, H, I), F = {A?B, A?C, CG?H, CG?I, B?H}, ? A? H？ ? CG ? HI？ ? AG ? I？ 數(shù)據(jù)依賴的公理系統(tǒng) 問題：有沒有一般性的算法判定 X?Y是否能由 F根據(jù) Armstrong公理導(dǎo)出？ ?屬性集的閉包 ? 設(shè) F為屬性集 U上的一組函數(shù)依賴， X ? U， = {A | X?A能由 F根據(jù) Armstrong公理導(dǎo)出 } 稱 為屬性集 X關(guān)于函數(shù)依賴集 F的閉包。 ?FX?FX數(shù)據(jù)依賴的公理系統(tǒng) ? 引理一： X?A1 A2 ? Ak成立 ? X?Ai成立 (i=1, 2, ? ,k) ? 引理二： 設(shè) F為屬性集 U上的一組函數(shù)依賴， X， Y ?U， X?Y能由 F根據(jù) Armstrong公理導(dǎo)出的充分必要條件是 Y ? ?FX數(shù)據(jù)依賴的公理系統(tǒng) ?算法（求屬性集的閉包） Input： X， F Output： 步驟： (1)令 X(0)＝ X， i=0 (2)求 B， B={A|(?V)(?W)(V?W∧ V ? X(i) ∧ A∈ W)} (3) X(i+1)＝ B∪ X (i) (4)判斷 X(i+1)＝ X (i) ？ (5)若相等，或 X(i+1)＝ U，則 X(i+1)就是 ，算法終止。 (6)若否，則 i=i+1，返回第二步。 ?FX?FX數(shù)據(jù)依賴的公理系統(tǒng) ?示例 R U, F , U = (A, B, C, D, E), F = {AB?C, B?D, C?E, CE?B, AC?B},計(jì)算 。 所用依賴 AB?C ABC B?D ABCD C?E ABCDE = ABCDE ?FAB )(?FAB )(?FAB )(數(shù)據(jù)依賴的公理系統(tǒng) ?Armstrong公理完備性的證明 證明：用反證法， 假定存在函數(shù)依賴 X?Y被 F邏輯蘊(yùn)涵，但 X?Y不能用 Armstrong公理從 F中導(dǎo)出。 (1) 若 V?W?F，且 V? ，則 W ? 證：因?yàn)?V ? ，所以有 X?V；于是 X ?W成立，所以 W ? 。 ?FX ?FX?FX?FX數(shù)據(jù)依賴的公理系統(tǒng) （ 2） 構(gòu)造一張二維表 r，它由下列兩個(gè)元組構(gòu)成，可以證明 r必是 R(U, F)的一個(gè)關(guān)系，即 F中的全部函數(shù)依賴在 r上成立。 r（ U ? ） t 11…1 00 …0 s 11…1 11…1 若 r不是 R(U, F)的關(guān)系，則必由于 F中有函數(shù)依賴V?W在 r上不成立所致。由 r的構(gòu)成可知， V必定是 的子集，而 W不是 的子集，可是由第（ 1）步可知， W? 矛盾，所以 r必是 R(U, F)的一個(gè)關(guān)系。 ?FX ?FX?FX?FX?FX數(shù)據(jù)依賴的公理系統(tǒng) （ 3）若 X?Y不能由 F從 Armstrong公理導(dǎo)出，則Y不是 的子集，因此必有 Y的子集 Y‘滿足Y’?U– ，則 X?Y在 r中不成立，即 X?Y必不為 R(U, F)所蘊(yùn)含。 ?FX?FX數(shù)據(jù)依賴的公理系統(tǒng) ?定義 ? 函數(shù)依賴集的等價(jià)性 ? 函數(shù)依賴集 F， G，若 F+= G+，則稱 F與 G等價(jià)。 ? F+ = G+ ? F ? G+， G ? F+ ? 最小依賴集（最小覆蓋） 滿足下列條件的函數(shù)依賴集 F稱為最小覆蓋，記作 Fm： ? F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性 。 ? F中不存在這樣的函數(shù)依賴 X ? A，使得 F
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1