第09章關(guān)系數(shù)據(jù)理論-文庫吧
2025-04-07 20:46 本頁面
【正文】 [X]，由于 Y ? X， 所以 t[Y]=s[Y]， 由定義 X→ Y成立 ， 自反律得證 。 26 證明增廣律 ： 設(shè) X→ Y， 且 Z?U， r、 t、 s的含義同上 如果 t[XZ]=s[XZ]， 則一定有 t[X]=s[X]和 t[Z]=s[Z] 又根據(jù) X→ Y可有 t[Y]=s[Y] 由 t[Y]=s[Y]和 t[Z]=s[Z]可得 t[YZ]=s[YZ] 即由 t[XZ]=s[XZ]推導(dǎo)出了 t[YZ]=s[YZ] 由定義 XZ→ YZ成立 ， 增廣律得證 。 27 證明傳遞律 ： 設(shè) X→ Y、 Y→ Z， r、 t、 s的含義同上 如果 t[X]=s[X]， 由于 X→ Y， 根據(jù)定義 t[Y]=s[Y] 同理由于 Y→ Z， 可得 t[Z]=s[Z] 即由 t[X]=s[X]推導(dǎo)出了 t[Z]=s[Z] 根據(jù)定義 X→ Z成立 ， 傳遞律得證 。 28 Amstrong公理的推論： 推論 ① 合并規(guī)則：如果 X→ Y、 X→ Z， 則X→ YZ； 推論 ② 分解規(guī)則：如果 X→ YZ， 則 X→ Y、X→ Z； 推論 ③ 偽傳遞規(guī)則：如果 X→ Y、 YW→ Z， 則XW→ Z。 29 定理 ： Amstrong公理的三個(gè)推論是正確的。 30 證明合并規(guī)則： 設(shè) X→ Y、 X→ Z 根據(jù)增廣律分別有 X→ XY、 XY→ YZ 又根據(jù)傳遞律有 X→ YZ， 合并規(guī)則得證 。 31 證明分解規(guī)則 ： 設(shè) X→ YZ 根據(jù)自反律有 YZ→ Y和 YZ→ Z 又根據(jù)傳遞律分別有 X→ Y和 X→ Z，分解規(guī)則得證 。 32 證明偽傳遞規(guī)則： 設(shè) X→ Y、 YW→ Z 根據(jù)增廣律有 XW→ YW 又根據(jù)傳遞律有 XW→ Z， 偽傳遞規(guī)則得證 。 33 引理 引理 ： X→ A1A2… An的充分必要條件是 X→ Ak成立 (k=1,2,… ,n)。 根據(jù)合并規(guī)則和分解規(guī)則可以得出如下重要結(jié)論： 34 邏輯蘊(yùn)涵和閉包 有時(shí)需要根據(jù)給定的一組函數(shù)依賴來判斷另外一些函數(shù)依賴是否成立，這就是函數(shù)依賴邏輯蘊(yùn)涵所要研究的內(nèi)容。 比如有關(guān)系模式 R(U,F)， U={A,B,C}，F(xiàn)={A→B,B → C} ， 問 A → C 是否也成立？ 35 邏輯蘊(yùn)涵 定義 ：設(shè)有關(guān)系模式 R(U,F)，X?U、 Y ? U， 如果從 F中的函數(shù)依賴能夠推導(dǎo)出 X→ Y， 則稱 F邏輯蘊(yùn)涵 X→ Y，或稱 X→ Y是 F的邏輯蘊(yùn)涵。 36 閉包 定義 在關(guān)系模式 R(U,F)中，被 F 所邏輯蘊(yùn)涵的函數(shù)依賴的全體稱作 F 的閉包，記為 F + 。 37 閉包計(jì)算舉例 ??????????????????????????,, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,X Y ZX Y ZX Y ZXZX Y ZXYX Y ZXYZX Y ZYZXZYZXYYZXXZX Y ZXZXZXZXYXZXXYX Y ZXYXZXYXYXYXYZYZYZYZX Y ZZXZZXYZXZYZZYYX Y ZYXZYXYYXZZYYZYYXX Y ZXXZXXYXXZYZYX Y ZXZXYX→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→Φ→Φ→Φ→Φ→Φ→Φ→Φ→ 假設(shè)有關(guān)系模式 R(U,F)， U={X,Y,Z}，F(xiàn)={X→ Y,Y→ Z}， 則 F+ 為： 38 屬性集閉包 39 計(jì)算屬性集閉包舉例 ?FX?FX?FX如果 X={A}， 則： ＝｛ A,B,C｝ 如果 X={B}， 則 ＝｛ B,C｝ 如果 X={C}， 則 ＝｛ C｝ 設(shè)有關(guān)系模式 R(U,F)， U={A,B,C}， F={A→ B,B→ C} 40 公理的完備性 建立一套公理系統(tǒng)必須明確兩個(gè)問題： 一是能否保證按公理推導(dǎo)出的函數(shù)依賴都是正確的 ， 即這些函數(shù)依賴是否都屬于 F+； 也就是說對(duì)于關(guān)系模式R(U,F)， 只要 F中的函數(shù)依賴為真 ， 則用公理根據(jù) F推導(dǎo)出的函數(shù)依賴也一定為真 ， 這就是公理的正確性； 另外一個(gè)問題是：用公理能否推導(dǎo)出所有的函數(shù)依賴 ？也就是說 F+中所有的函數(shù)依賴是否都能用公理推導(dǎo)出來 ？這是一個(gè)很重要的問題 ， 因?yàn)槿绻?F+中有函數(shù)依賴不能用公理推導(dǎo)出來 ， 那么就說明這些公理不夠用 、 不完全 ，就必須補(bǔ)充新的公理 ， 這就是公理的完備性問題 。 41 引理 42 引理 ： YXXY F ??? ?43 引理 ： ????FXYYX44 公理的完備性還可以理解為： 所有不能用公理推導(dǎo)出的函數(shù)依賴都不為真，即如果 X→ Y不能根據(jù) F用公理導(dǎo)出，則 X→ Y? F+ 。 或者說存在一個(gè)具體的關(guān)系 r， F+ 中的所有函數(shù)依賴都滿足r， 而不能用公理推導(dǎo)出的 X→ Y不滿足 r。也就是說，不能根據(jù) F用公理導(dǎo)出的函數(shù)依賴不屬于 F+ 。 如果我們能夠找到這樣的 r， 則公理的完備性證明問題就解決了。 45 定理 ： Amstrong公理是完備的。 為了證明公理的完備性，找到了如下具體的關(guān)系 r： 如果能夠證明以下兩點(diǎn)，則公理的完備性問題就證明了： ⑴
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1