第09章關(guān)系數(shù)據(jù)理論(編輯修改稿)
2025-06-16 20:46 本頁面
【文章內(nèi)容簡介】 在關(guān)系 r中， F + 中的所有函數(shù)依賴都成立； ⑵在關(guān)系 r中，不能根據(jù) F用 Amstrong公理推導(dǎo)出的函數(shù)依賴 X→ Y不成立。 46 證：在關(guān)系 r中， F+ 中的所有函數(shù)依賴都成立 47 證： 在關(guān)系 r中，不能根據(jù) F用 Amstrong公理推導(dǎo)出的函數(shù)依賴 X→ Y不成立 48 由公理的完備性和引理 ： ?? ???? FXYFYX49 屬性集閉包的計算 50 算法 ： 51 例：設(shè)有 R（ U,F）， U={A,B,C,D,E}， F={AB→ C,B → D,C → E,EC → B,AC → B} 求 ?FAB )(?FAB )( {A,B,C,D,E} = 52 函數(shù)依賴集的等價和最小化 53 覆蓋和等價的定義 定義 設(shè) F和 G是兩個函數(shù)依賴集： ① 如果 F +?G +， 則稱 G是 F的一個覆蓋 ，或稱 G覆蓋 F； ② 如果 F +?G +和 G +?F +同時成立 ，即 F +=G +， 則稱 F和 G等價 。 54 引理 F +=G +的充分必要條件是 F ?G +并且 G ? F +。 必要性證明： 充分性證明： 55 F+=G+ ? F?G+并且 G ? F+ 為判定兩個函數(shù)依賴集是否等價提供了簡便方法： 可以首先檢查 F中的每個函數(shù)依賴 X→ Y是否屬于 G+（ 即計算 Y是否屬于 XG+） ？ 如果對 F中的每個函數(shù)依賴都有 X→ Y?G+， 則有 F?G+ ；然后用同樣的方法再檢查 G?F+是否成立 ？ 如果它們都成立則 F和 G等價 。 56 研究函數(shù)依賴集等價的目的 研究函數(shù)依賴集等價的目的是為了對指定函數(shù)依賴集找出它的最小函數(shù)依賴等價集，即找出包含函數(shù)依賴盡可能少、甚至最少的函數(shù)依賴等價集，從而使模式分解簡化，分解出最簡單的關(guān)系模式。 57 最小函數(shù)依賴集的定義 定義 如果函數(shù)依賴集 F 滿足如下條件 ， 則稱F 為一個最小函數(shù)依賴集 ， 也稱為極小函數(shù)依賴集或最小覆蓋： ① F 中任一函數(shù)依賴的右部都僅含有一個屬性； ② F中不存在這樣的函數(shù)依賴 X→ A， X有真子集 Z， 使得 F與 F{X→ A} ∪ {Z→ A}等價； ③ F中不存在這樣的函數(shù)依賴 X→ A， 使得 F與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不是最小依賴集。 59 引理 60 引理 61 引理 性證明 62 引理 設(shè) X→ A是 F 中任意函數(shù)依賴， G=F {X→ A}，F(xiàn) 與 G 等 價的充分必要條件是 。 ?? GXA必要性證明 充分性證明 63 計算最小覆蓋的算法 算法 給定函數(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}等價（引理 ），故以 XBj取代 X； ? 逐一檢查 F中各函數(shù)依賴 X→ A， 令 G=F{X→ A}， 根據(jù)引理 ，如果 ，則 F與 G等價，故從 F中去掉X→ A。 ??? FjBXA )(?? GXA64 例 ：已知 F={A→ B,B→ A,B→ C,A→ C,C→ A}，求 F的最小覆蓋。 逐一檢查 F中的函數(shù)依賴是否多余，如果多余則可以去除之，最后的結(jié)果為： {A → B,B → C,C→ A} 65 注意：算法 3兩步是不可以顛倒的。 66 設(shè) F={C?A,A ? D,CD ? B,B ? A} 依照算法 既約化 令 G=F{CD ? B}?{C ? B} 結(jié)果 G與 F等價 G= {C?A,A ? D,C ? B,B ? A} 無冗余化 結(jié)果所求最小覆蓋為 F’={A ? D,C ? B,B ? A} 67 設(shè) F={C?A,A ? D,CD ? B,B ? A} 先無冗余化后既約化 無冗余化 結(jié)果沒有多余的函數(shù)依賴 既約化 結(jié)果 G= {C?A,A ? D,C ? B,B ? A} 它不是最小覆蓋，因為 C?A這時是多余的函數(shù)依賴。 68 規(guī)范化 規(guī)范化的目的就是要設(shè)計“好”的關(guān)系，使關(guān)系盡量減少操作異常甚至拒絕操作異常現(xiàn)象。 69 第一范式 每個關(guān)系模式都應(yīng)滿足最低要求：所有分量都必須是不可分的最小數(shù)據(jù)項，并把其稱為第一范式（ 1NF） 關(guān)系。 70 非規(guī)范化表格和規(guī)范化表格 71 第二范式 定義 如果 R(U,F) ∈ 1NF， 并且 R中的每個非主屬性都完全函數(shù)依賴于關(guān)鍵字 ，則 R(U,F) ∈ 2NF。 72 庫存 A關(guān)系實例： 倉庫號 設(shè)備號 數(shù)量 地點WH1 D4 675 北京WH1 D7 250 北京WH2 D2 280 上海WH2 D4 200 上海WH2 D9 270 上海WH3 D2 550 廣州WH3 D4 230 廣州WH4 D5 550 北京數(shù)據(jù)冗余 插入異常 更新異常 刪除異常 73 為了解決操
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1