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