第09章關(guān)系數(shù)據(jù)理論-wenkub
2023-05-09 20:46:07 本頁(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成立 ， 增廣律得證 。 保持函數(shù)依賴(lài)是指分解后的關(guān)系不能破壞原來(lái)的函數(shù)依賴(lài)（不能破壞原來(lái)的語(yǔ)義）。如何改造這個(gè)關(guān)系模式？克服以上種種問(wèn)題，就是我們這一章要解決的根本問(wèn)題，也是我們要討論函數(shù)依賴(lài)的根本原因。 14 術(shù)語(yǔ)和符號(hào) (7) 如果 X→ Y， 并且對(duì)于 X的一個(gè)任意真子集 X/ 都有 X/ Y， 則稱(chēng) Y完全函數(shù)依賴(lài)于 X， 并記作 ；如果 X/ → Y成立，則稱(chēng) Y部分函數(shù)依賴(lài)于 X， 并記作 。 如 學(xué)號(hào) → 所在系 ，則 學(xué)號(hào) 稱(chēng)作決定因素 11 用 U表示關(guān)系模式 R的屬性全集，即 U={A1,A2,…, An}， 用 F表示關(guān)系模式 R上的函數(shù)依賴(lài)集，則關(guān)系模式 R可表示為 R(U,F)。如不特別說(shuō)明，我們總是討論非平凡函數(shù)依賴(lài)。1 第 9章 關(guān)系數(shù)據(jù)理論 基本概念 函數(shù)依賴(lài)的公理系統(tǒng) 規(guī)范化 模式分解 2 基本概念 函數(shù)依賴(lài) 術(shù)語(yǔ)和符號(hào) 為什么要討論函數(shù)依賴(lài)？ 模式分解 3 函數(shù)依賴(lài) Y=f(X) 函數(shù) Y=sin(X) Y=X+1 Y=X2+2X+1 省 =f(城市 ) 姓名 =f(學(xué)號(hào) ) 4 函數(shù)依賴(lài)的直觀定義： 如果有一個(gè)關(guān)系模式 R(A1,A2,…,A n)， X和 Y為 {A1,A2,…,A n}的子集，那么對(duì)于關(guān)系 R中的任意一個(gè) X值，都只有一個(gè) Y值與之對(duì)應(yīng)，則稱(chēng) X函數(shù)決定 Y， 或 Y函數(shù)依賴(lài)于 X， 并用 X→Y 表示。 如： (學(xué)號(hào) ,課程號(hào) )→ 成績(jī) 如： (學(xué)號(hào) ,所在系 )→ 所在系 非平凡依賴(lài) 平凡依賴(lài) 9 術(shù)語(yǔ)和符號(hào) (2) 如果 Y不函數(shù)依賴(lài)于 X， 則記作 X Y。 術(shù)語(yǔ)和符號(hào) (4) 如 U={倉(cāng)庫(kù)號(hào) ,城市 ,面積 } F={倉(cāng)庫(kù)號(hào) → 城市 ,倉(cāng)庫(kù)號(hào) → 面積 } 則 R(U,F)表示倉(cāng)庫(kù)關(guān)系 12 術(shù)語(yǔ)和符號(hào) (5) 如果 K是關(guān)系模式 R(U,F)的任一候選關(guān)鍵字， X是任一屬性或?qū)傩约?，如?X?K， 則 X稱(chēng)為主屬性；否則稱(chēng)為非主屬性。 YX f? ??YX p? ??如： (學(xué)號(hào) ,課程號(hào) )→ 成績(jī) 是完全函數(shù)依賴(lài) 而： (學(xué)號(hào) ,所在系 )→ 系主任 是部分函數(shù)依賴(lài) 15 術(shù)語(yǔ)和符號(hào) (8) 如果 X→ Y（ 非平凡函數(shù)依賴(lài)，并且 Y X）、 Y→ Z， 則稱(chēng) Z傳遞函數(shù)依賴(lài)于 X。 19 模式分解 解決各種操作異?，F(xiàn)象的方法就是進(jìn)行模式分解，即把一個(gè)關(guān)系模式分解成兩個(gè)或多個(gè)關(guān)系模式，在分解的過(guò)程中消除那些 “ 不良 ” 的函數(shù)依賴(lài)，從而獲得好的關(guān)系模式。 22 函數(shù)依賴(lài)的公理系統(tǒng) Amstrong公理的內(nèi)容及正確性 Amstrong公理的推論 邏輯蘊(yùn)涵和閉包 公理的完備性 閉包的計(jì)算 函數(shù)依賴(lài)集的等價(jià)和最小化 23 Amstrong公理： 設(shè)有關(guān)系模式 R(U,F)， X、 Y、 Z均為 U的子集 ， 推理規(guī)則如下： ① 自反律 ： 如果 Y?X， 則 X→ Y； ② 增廣律 ： 如果 X→ Y， 則 XZ→ YZ； ③ 傳遞律 ： 如果 X→ Y、 Y→ Z， 則 X→ Z 。 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成立 ， 傳遞律得證 。 31 證明分解規(guī)則 ： 設(shè) X→ YZ 根據(jù)自反律有 YZ→ Y和 YZ→ Z 又根據(jù)傳遞律分別有 X→ Y和 X→ Z，分解規(guī)則得證 。 比如有關(guān)系模式 R(U,F)， U={A,B,C}，F(xiàn)={A→B,B → C} ， 問(wèn) A → C 是否也成立？ 35 邏輯蘊(yùn)涵 定義 ：設(shè)有關(guān)系模式 R(U,F)，X?U、 Y ? U， 如果從 F中的函數(shù)依賴(lài)能夠推導(dǎo)出 X→ Y， 則稱(chēng) F邏輯蘊(yùn)涵 X→ Y，或稱(chēng) X→ Y是 F的邏輯蘊(yùn)涵。 或者說(shuō)存在一個(gè)具體的關(guān)系 r， F+ 中的所有函數(shù)依賴(lài)都滿(mǎn)足r， 而不能用公理推導(dǎo)出的 X→ Y不滿(mǎn)足 r。 為了證明公理的完備性，找到了如下具體的關(guān)系 r： 如果能夠證明以下兩點(diǎn)，則公理的完備性問(wèn)題就證明了： ⑴在關(guān)系 r中， F + 中的所有函數(shù)依賴(lài)都成立； ⑵在關(guān)系 r中，不能根據(jù) F用 Amstrong公理推導(dǎo)出的函數(shù)依賴(lài) X→ Y不成立。 56 研究函數(shù)依賴(lài)集等價(jià)的目的 研究函數(shù)依賴(lài)集等價(jià)的目的是為了對(duì)指定函數(shù)依賴(lài)集找出它的最小函數(shù)依賴(lài)等價(jià)集，即找出包含函數(shù)依賴(lài)盡可能少、甚至最少的函數(shù)依賴(lài)等價(jià)集，從而使模式分解簡(jiǎn)化，分解出最簡(jiǎn)單的關(guān)系模式。 ?? GXA必要性證明 充分性證明 63 計(jì)算最小覆蓋的算法 算法 給定函數(shù)依賴(lài)集 F， 求其最小覆蓋的過(guò)程如下： ? 逐一檢查 F 中各函數(shù)依賴(lài) X→ Y， 若 Y=A1… Ak， k=2，則用 {X→ Aj | j=1,… ,k}來(lái)取代它（分解規(guī)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1