第09章關(guān)系數(shù)據(jù)理論-文庫吧資料
2025-05-12 20:46本頁面
【正文】 果為： {A → B,B → C,C→ A} 65 注意：算法 3兩步是不可以顛倒的。 ?? GXA必要性證明 充分性證明 63 計(jì)算最小覆蓋的算法 算法 給定函數(shù)依賴集 F， 求其最小覆蓋的過程如下： ? 逐一檢查 F 中各函數(shù)依賴 X→ Y， 若 Y=A1… Ak， k=2，則用 {X→ Aj | j=1,… ,k}來取代它（分解規(guī)則）； ? 逐一取出 F中各函數(shù)依賴 X→ A， 若 X=B1B2… Bm， m=2，則逐一考查 Bj（ j=1,…, m）， 如果 ，則 F與 F{X→ A} ∪ {(XBj)→ A}等價(jià)（引理 ），故以 XBj取代 X； ? 逐一檢查 F中各函數(shù)依賴 X→ A， 令 G=F{X→ A}， 根據(jù)引理 ，如果 ，則 F與 G等價(jià)，故從 F中去掉X→ A。 58 例： 假設(shè)有屬性集 U={A,B,C,D,E}， 函數(shù)依賴集 F={A→ B,B→ C,AD→ E}和函數(shù)依賴集G={A→ B,A→ C,B→ C,AD→ E}， 問 F和 G是否是最小函數(shù)依賴集 ？ 答案： F是最小依賴集， G不是最小依賴集。 56 研究函數(shù)依賴集等價(jià)的目的 研究函數(shù)依賴集等價(jià)的目的是為了對(duì)指定函數(shù)依賴集找出它的最小函數(shù)依賴等價(jià)集，即找出包含函數(shù)依賴盡可能少、甚至最少的函數(shù)依賴等價(jià)集，從而使模式分解簡(jiǎn)化，分解出最簡(jiǎn)單的關(guān)系模式。 54 引理 F +=G +的充分必要條件是 F ?G +并且 G ? F +。 為了證明公理的完備性，找到了如下具體的關(guān)系 r： 如果能夠證明以下兩點(diǎn)，則公理的完備性問題就證明了： ⑴在關(guān)系 r中， F + 中的所有函數(shù)依賴都成立； ⑵在關(guān)系 r中，不能根據(jù) F用 Amstrong公理推導(dǎo)出的函數(shù)依賴 X→ Y不成立。 如果我們能夠找到這樣的 r， 則公理的完備性證明問題就解決了。 或者說存在一個(gè)具體的關(guān)系 r， F+ 中的所有函數(shù)依賴都滿足r， 而不能用公理推導(dǎo)出的 X→ Y不滿足 r。 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ǔ)充新的公理 ， 這就是公理的完備性問題 。 比如有關(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)涵。 33 引理 引理 ： X→ A1A2… An的充分必要條件是 X→ Ak成立 (k=1,2,… ,n)。 31 證明分解規(guī)則 ： 設(shè) X→ YZ 根據(jù)自反律有 YZ→ Y和 YZ→ Z 又根據(jù)傳遞律分別有 X→ Y和 X→ Z，分解規(guī)則得證 。 29 定理 ： Amstrong公理的三個(gè)推論是正確的。 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成立 ， 傳遞律得證 。 25 證明自反律 ： 設(shè) Y?X ? U 對(duì)關(guān)系模式 R的任一關(guān)系 r 中的任意兩個(gè)元組 t和 s， 如果 t[X]=s[X]，由于 Y ? X， 所以 t[Y]=s[Y]， 由定義 X→ Y成立 ， 自反
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1