【文章內(nèi)容簡介】 OK模式分解成 B1（ BISBN， BNAME） 和 B2（ BISBN， AUTHOR） ， 能解決上述的問題 ， 且B1和 B2都是 BCNF。 但是這個分解把 （ BNAME， AUTHOR） → BISBN函數(shù)決定關(guān)系丟掉了 ， 數(shù)據(jù)語義將會引起新的矛盾 。 怎樣分解成 BCNF范式呢？ 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 范式 5． 多值依賴和 4NF （ 1） 多值依賴 前面都是在函數(shù)依賴的范圍內(nèi)討論問題 ， 屬于BCNF的關(guān)系模式就一定很完美了嗎 ？ 下面來看一個例子： 【 例 44】 學(xué)校運(yùn)動會設(shè)置了多個運(yùn)動項目 ， 每個運(yùn)動項目配備有多個裁判 ， 并且有多個運(yùn)動員參加同一個項目的比賽 。 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 范式 表 45 運(yùn)動項目 裁判 運(yùn)動員實體之間的關(guān)系 這張表顯然不滿足 1NF，將其進(jìn)行規(guī)范化后得到下表。 運(yùn)動項目 裁判 運(yùn)動員 男子 100米跨欄 石建明 劉開福 劉飛翔 張鐵軍 男子 100米 劉開福 劉飛翔 女子 3米跳水 羅小娟 宋軍 周瑞 李利君 郭晶景 付敏瑕 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 范式 運(yùn)動項目 裁判 運(yùn)動員 男子 100米跨欄 石建明 劉飛翔 男子 100米跨欄 石建明 張鐵軍 男子 100米跨欄 劉開福 劉飛翔 男子 100米跨欄 劉開福 張鐵軍 男子 100米 劉開福 劉飛翔 女子 3米跳水 羅小娟 李利君 女子 3米跳水 羅小娟 郭晶景 女子 3米跳水 羅小娟 付敏瑕 女子 3米跳水 宋軍 李利君 女子 3米跳水 宋軍 郭晶景 女子 3米跳水 宋軍 付敏瑕 女子 3米跳水 周瑞 李利君 表 46 滿足 1NF運(yùn)動項目 裁判 運(yùn)動員實體之間的關(guān)系 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 范式 運(yùn)動項目 裁判 運(yùn)動員關(guān)系模式 （ 運(yùn)動項目 ， 裁判員 ， 運(yùn)動員 ） 的碼是全碼 ， 因而 BCNF。 然而 ，該關(guān)系模式仍然存在以下異常： ① 插入異常 。 當(dāng)某一運(yùn)動項目 （ 如男子 100米跨欄 ）增加一名裁判 （ 劉光明 ） ， 則必須插入 2個元組 。 ② 刪除異常 。 同樣 ， 某一個運(yùn)動項目 （ 如女子 3米跳水 ） 要減少一個運(yùn)動員 （ 郭晶景 ） ， 要同時刪除 3個元組 。 ?仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 范式 ③ 冗余。每個項目有 m個裁判員裁定， n個運(yùn)動員參與，關(guān)系中有該課程的元組數(shù)目一定有 mn個，故需存儲多次，造成大量冗余。 ④ 更新異常。修改一個項目的裁判員，涉及到這個項目的多個運(yùn)動員，故須修改多個元組。 在于裁判員的取值與運(yùn)動員的取值，彼此沒有聯(lián)系、相互獨(dú)立，他們都取決于項目名稱。此即為一種新的數(shù)據(jù)依賴 — 多值依賴 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 范式 定義 設(shè)有 R（ U） ， X、 Y是 U的子集 ，Z=U?X?Y。 多值依賴 X→→ Y成立 ， 當(dāng)且僅當(dāng)對 R的任一具體關(guān)系 r， 給定一對 （ X、 Z） 值 ， 有一組Y值與之對應(yīng) ， 且這種對應(yīng)關(guān)系與 Z值無關(guān) 。 一般來說 ， 多值依賴是成對出現(xiàn)的 。 例如 ， 對于一個關(guān)系模式 T（ W， S， L） ， 多值依賴 W→→ S存在 ，當(dāng)且僅當(dāng)多值依賴 W→→ L也成立 。 這時 ， 可用W→→ S|L這種形式來表示它們 。 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 范式 （ 2） 第四范式 （ 4NF） ?定義 關(guān)系模式 R（ U） ∈ 1NF，若 R的每個非平凡多值依賴 X→→ Y（ Y非空且 Y?X， XY不包含 R的全部屬性）， X一定包含 R的關(guān)鍵字，則稱 R（ U）滿足 第四范式 ，簡記為 R∈ 4NF。 ?一個關(guān)系模式若屬于 4NF，則必然屬于 BCNF， R中所有非平凡的多值依賴實際就是函數(shù)依賴。BCNF關(guān)系向 4NF轉(zhuǎn)換的方法是，消除非平凡多值依賴，以減少數(shù)據(jù)冗余，即將 BCNF關(guān)系分解成多個 4NF關(guān)系模式。 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 范式 【 例 45】 BCNF分解的例子 SJA（運(yùn)動項目，裁判，運(yùn)動員），運(yùn)動項目→→ 裁判，運(yùn)動項目 →→ 運(yùn)動員。它們都是非平凡的多值依賴，而 SJA的碼是全碼，即碼是（運(yùn)動項目，裁判，運(yùn)動員），運(yùn)動項目不是碼，所以SJA 4NF。 ?通過消除非平凡多值依賴，可將 SJA分解為如下兩個關(guān)系： SJ（運(yùn)動項目，裁判） SA（運(yùn)動項目，運(yùn)動員） ?仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 規(guī)范化理論 ? 函數(shù)依賴 ? 碼的形式化定義 ? 范式 ? 數(shù)據(jù)依賴的公理系統(tǒng) 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 數(shù)據(jù)依賴的公理系統(tǒng) 本節(jié)介紹分解算法的理論基礎(chǔ) —— 數(shù)據(jù)依賴的公理系統(tǒng) 。 數(shù)據(jù)依賴的公理體系是 1974 年由 ， 它給出了一套形式推理規(guī)則 ， 利用這些規(guī)則 ， 可以從關(guān)系模式的一組已知函數(shù)依賴出發(fā) ， 推理求出它所蘊(yùn)含的所有函數(shù)依賴等 。 1． 邏輯蘊(yùn)含與 Armstrong公理系統(tǒng) 2． 函數(shù)依賴集閉包和屬性集閉包 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 1．邏輯蘊(yùn)含與 Armstrong公理系統(tǒng) 定義 對于滿足一組函數(shù)依賴 F的關(guān)系模式 R（ U， F），其任何一個關(guān)系 r，若函數(shù)依賴 X → Y都成立，則稱 F邏輯蘊(yùn)含 X → Y。 例如：關(guān)系模式 Student（ Sno,Sname,Sage, Ssex,Sdept），其屬性組上的函數(shù)依賴集為F={Sno→ Sname， Sno→ Sage， Sno→ Ssex，Sno→ Sdept}， Sno→ Sdept就是 F所邏輯蘊(yùn)含的一個函數(shù)依賴。 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 1．邏輯蘊(yùn)含與 Armstrong公理系統(tǒng) Armstrong公理系統(tǒng) 設(shè)有關(guān)系模式 R（ U）及它上面的一個函數(shù)依賴集 F（ U為屬性集總體）， X、 Y、Z、 W是 U的子集。有如下彼此獨(dú)立的推理規(guī)則： ? 自反律：如果 Y?X?U，則 X→ Y為 F所蘊(yùn)含。 ? 增廣律：如果 X→ Y為 F所蘊(yùn)含，且 Z?U，則XZ→ YZ為 F所蘊(yùn)含。 ? 傳遞律：如果 X→ Y及 Y→ Z為 F所蘊(yùn)含，則 X→ Z為F所蘊(yùn)含。 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 1．邏輯蘊(yùn)含與 Armstrong公理系統(tǒng) 【 例 46】 設(shè) R＝ ABC， F={C → A}，利用 Armstrong公理系統(tǒng)的推理規(guī)則，證明（ B,C） → （ A,B,C） 證明： 因為 C → A，所以（ B,C） → （ A,B） （利用增廣律，即在函數(shù)依賴兩端加 B） 所以（ B,C） → （ A,B,C） （利用增廣律，即在函數(shù)依賴兩端加 C） 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 1．邏輯蘊(yùn)含與 Armstrong公理系統(tǒng) 由上面的三條推理規(guī)則，又得到三條推論（可作為定理使用），但它們不是獨(dú)立的。 ?合并規(guī)則：若 X→ Y， X→ Z，有 X→ YZ ?分解規(guī)則：若 X→ Y， Z?Y，有 X→ Z ?偽傳遞規(guī)則：若 X→ Y， WY → Z有 XW→ Z 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 2．函數(shù)依賴集閉包和屬性集閉包 定義 在關(guān)系模式 R(U,F)中，為函數(shù)依賴集 F所邏輯蘊(yùn)涵的全體函數(shù)依賴的集合，稱為 F的閉包（ Closure），記為 F 。 + 定義 設(shè)有關(guān)系模式 R（ U）， F是 U上的一個函數(shù)依賴集， X ? U， XF ＝｛ A|X → A能由 F根據(jù)Armstrong 公理導(dǎo)出｝， XF 稱為屬性集 X關(guān)于函數(shù)依賴集 F的閉包。 ＋ ＋ 例如：對 R(U)，設(shè)有屬性集合 U={A,B,C,D,E,F}，假設(shè)此關(guān)系模式的一個函數(shù)依賴集 F包含有函數(shù)依賴：{AB → C,BC → AD,D → E,CF → B}，那么，對X={A,B}， 屬性集 X關(guān)于函數(shù)依賴集 F的閉包是什么？ 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 通過屬性集合的閉包： 可以找到所有正確的函數(shù)依賴！ 例如：對 R(U)，其屬性集合 U={A,B,C,D,E,F}，F(xiàn)＝ {AB → C,BC → AD,D → E,CF → B}，那么，是否有： （ 1）從 F集合可以推斷 AB → D ？ （ 2）從 F集合可以推斷 D → A ？ 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 2．函數(shù)依賴集閉包和屬性集閉包 算法 求屬性集 X（ X ? U） 關(guān)于 U上的函數(shù)依賴集F的閉包 XF＋ 。 ?輸入：屬性全集 U={A1,A2,…,An}， U上的函數(shù)依賴集 F，以及屬性集 X ? U。 ?輸出： X= {A1,A2,…,Am}關(guān)于 F的閉包 XF+ ，即{A1,A2,…,Am}F+。 (m=n) ?方法： X是屬性集合，也就是閉包，首先 X= {A1,A2,…,Am},反復(fù)尋找這樣的函數(shù)依賴： B1,B2,…,Bm → C,使得B1,B2,…,Bm 在 X中，而 C不在 X中，則把 C加入 X，并重復(fù)這個過程。因為集合 X只能增長，而任何一個關(guān)系模式中的屬性都是有限的，所以最終沒有任何函數(shù)能再加入 X時，本步驟結(jié)束，當(dāng)不能再添加任何屬性時，集合 X就是所求。 仲愷農(nóng)業(yè)工程學(xué)院 計算機(jī)科學(xué)與工程學(xué)院 2．函數(shù)依賴集閉包和屬性集閉包 具體而言，根據(jù)下列步驟計算一系列屬性集合 X (0)， X (1)， … ： （ 1）令 X(0)=X， i=0； （ 2）令 X(i+1) =X(i) ∪ B。其中， B={A| (?V)(?W)（ V→W ?F∧ V ? X(i) ∧ A?W） }； （ 3）判斷 X(i+1) =X(i) 嗎？ （ 4）若 X(i+1)≠X(i)，則用 i+1取代 i，返回（ 2）； （ 5）若 X(i+1)=X(i)，則即為 XF＋ ，算法終止 【 例 47】 對 R(U)，有屬性集合 U={A,B,C,D,E,F},假設(shè)此關(guān)系模式的一個函數(shù)依賴集 F包含有函數(shù)依賴：{AB → C,BC → AD,D → E,CF → B}，那么，對