關(guān)系數(shù)據(jù)庫的規(guī)范化設(shè)計(編輯修改稿)
2024-09-01 02:58 本頁面
【文章內(nèi)容簡介】 作為候選碼 ? S、 T、 J都是主屬性 STJ ? BCNF ? T→ J ， T是決定屬性集， T不是候選碼 BCNF 解決方法：將 STJ分解為二個關(guān)系模式： SJ(S， J) ? BCNF， TJ(T， J)? BCNF 沒有 任何屬性 對碼的部分函數(shù)依賴和傳遞函數(shù)依賴 S J ST T J TJ BCNF的關(guān)系模式所具有的性質(zhì) ⒈ 所有 非主屬性 都完全函數(shù)依賴于每個候選碼 ⒉ 所有 主屬性 都完全函數(shù)依賴于每個不包含它的候選碼 ⒊ 沒有任何屬性完全函數(shù)依賴于 非碼 的任何一組屬性 關(guān)系模式的 規(guī)范化 ? 關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計的工具。 ? 一個關(guān)系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。 ? 規(guī)范化程度可以有多個不同的級別 規(guī)范化 ? 規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實世界，可能會存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題 ? 一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式集合，這種過程就叫 關(guān)系模式的規(guī)范化 規(guī)范化（續(xù)） ? 關(guān)系模式規(guī)范化的基本步驟 1NF ↓ 消除非主屬性對碼的部分函數(shù)依賴 消除決定屬性 2NF 集非碼的非平 ↓ 消除非主屬性對碼的傳遞函數(shù)依賴 凡函數(shù)依賴 3NF ↓ 消除主屬性對碼的部分和傳遞函數(shù)依 賴 BCNF ↓ 消除非平凡且非函數(shù)依賴的多值依賴 4NF 規(guī)范化的基本思想 ? 消除不合適的數(shù)據(jù)依賴 ? 的各關(guān)系模式達到某種程度的 “ 分離 ” ? 采用 “ 一事一地 ” 的模式設(shè)計原則。讓一個關(guān)系描述一個概念、一個實體或者實體間的一種聯(lián)系。若多于一個概念就把它 “ 分離 ” 出去 ? 所謂規(guī)范化實質(zhì)上是概念的單一化 規(guī)范化（續(xù)） ? 不能說規(guī)范化程度越高的關(guān)系模式就越好 ? 在設(shè)計數(shù)據(jù)庫模式結(jié)構(gòu)時，必須對現(xiàn)實世界的實際情況和用戶應(yīng)用需求作進一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式 ? 上面的規(guī)范化步驟可以在其中任何一步終止 數(shù)據(jù)依賴的公理系統(tǒng) ? 一套推理規(guī)則，是模式分解算法的理論基礎(chǔ) ? 用途 ? 求給定關(guān)系模式的碼 ? 從一組函數(shù)依賴求得蘊含的函數(shù)依賴 數(shù)據(jù)依賴的公理系統(tǒng) ? 邏輯蘊含 有時需要根據(jù)給定的一組函數(shù)依賴來判斷另外一些函數(shù)依賴是否成立，這就是函數(shù)依賴邏輯蘊涵所要研究的內(nèi)容。 比如有關(guān)系模式 R(U,F)， U={A,B,C}，F(xiàn)={A→B,B → C} ，問 A → C 是否也成立？ 邏輯蘊含 ? 定義 ： 設(shè) F是在關(guān)系模式 R上成立的函數(shù)依賴的集合， X→Y 是一個函數(shù)依賴。如果對于 R的每個滿足 F的關(guān)系 r也滿足 X→Y ，那么稱 F邏輯蘊涵 X→Y ，記為 F?X→Y 。 1. Armstrong公理系統(tǒng) 關(guān)系模式 R U， F 來說有以下的推理規(guī)則： ? ： 若 Y ? X ? U，則 X → Y 為 F 所蘊含。 ? ：若 X→ Y 為 F 所蘊含，且 Z ? U，則XZ→ YZ 為 F 所蘊含。 ? ：若 X→ Y 及 Y→ Z 為 F 所蘊含，則 X→ Z 為 F 所蘊含。 注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于 F 定理 Armstrong推理規(guī)則是正確的 （ l）自反律 :若 Y ? X ? U，則 X → Y 為 F 所蘊含 證 : 設(shè) Y ? X ? U 對 R U， F 的任一關(guān)系 r 中的任意兩個元組 t， s： 若 t [X ]=s [X ]，由于 Y ? X，有 t [y ]=s [y ]， 所以 X→ Y 成立 . 自反律得證 ] 定理 (2)增廣律 : 若 X→ Y 為 F 所蘊含，且 Z ? U，則 XZ→ YZ 為 F 所蘊含。 證： 設(shè) X→ Y 為 F 所蘊含，且 Z ? U。 設(shè) RU， F 的任一關(guān)系 r 中任意的兩個元組 t， s； 若 t [XZ]=s [XZ]，則有 t [X]=s [X]和 t [Z]=s [Z]； 由 X→ Y，于是有 t [Y]=s [Y]，所以 t [YZ]=s [YZ]，所以 XZ→ YZ 為 F 所蘊含 . 增廣律得證。 定理 (3) 傳遞律：若 X→ Y 及 Y→ Z 為 F 所蘊含，則 X→ Z為 F 所蘊含。 證： 設(shè) X→ Y及 Y→ Z為 F所蘊含。 對 RU， F 的任一關(guān)系 r中的任意兩個元組 t， s。 若 t [X]=s [X]，由于 X→ Y，有 t [Y]=s [Y]； 再由 Y→ Z，有 t [Z]=s [Z]，所以 X→ Z 為 F 所蘊含 . 傳遞律得證。 2. 導(dǎo)出規(guī)則 A1， A2， A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： ? 合并規(guī)則 ：由 X→ Y， X→ Z，有 X→ YZ。 （ A2， A3） ? 偽傳遞規(guī)則 ：由 X→ Y， WY→ Z，有 XW→ Z。 （ A2， A3） ? 分解規(guī)則 ：由 X→ Y及 Z?Y，有 X→ Z。 （ A1， A3） 導(dǎo)出規(guī)則 ，可得引理 引理 X→ A1 A2…Ak成立的充分必要條件是 X→ Ai 成立（ i=l， 2， … ， k）。 3. 函數(shù)依賴閉包 定義 在關(guān)系模式 RU， F中為 F所邏輯蘊 含的函數(shù)依賴的全體叫作 F 的閉包 ，記為 F +。 定義 設(shè) F 為屬性集 U上的一組函數(shù)依賴， X ?U， XF+ ={ A|X→ A能由 F 根據(jù) Armstrong公理導(dǎo)出 }， XF+稱為屬性集 X 關(guān)于函數(shù)依賴集 F 的閉包 F的閉包 F={X Y,Y Z}, F +計算是 NP完全問題， X A1A2...An F +={ X φ, Y φ, Z φ, XY φ, XZ φ, YZ φ, XYZ φ, X X, Y Y, Z Z, XY X, XZ X, YZ Y, XYZ X, X Y, Y Z , XY Y, XZ Y, YZ Z, XYZ Y, X Z, Y YZ, XY Z, XZ Z, YZ YZ, XYZ Z, X XY, XY XY, XZ XY, XYZ XY, X XZ, XY YZ, XZ XZ, XYZ YZ X YZ, XY XZ, XZ XY, XYZ XZ, X ZYZ, XY XYZ, XZ XYZ, XYZ XYZ } 關(guān)于閉包的引理 ? 引理 設(shè) F 為屬性集 U上的一組函數(shù)依賴， X， Y ? U，X→ Y 能由 F 根據(jù) Armstrong公理導(dǎo)出的充分必要條件是 Y ?XF+ ? 用途 將判定 X→ Y是否能由 F 根據(jù) Armstrong公理導(dǎo)出的問題， 就轉(zhuǎn)化為求出 XF+ ，判定 Y是否為 XF+的子集的問題 求閉包的算法 算法 求屬性集 X（ X ? U）關(guān)于 U上的函數(shù)依 賴集 F 的閉包 XF+ 輸入： X， F 輸出： XF+ 步驟： （ 1）令 X（ 0） =X， i=0 （ 2）求 B，這里 B = { A |(? V)( ? W)(V→ W?F ∧ V ? X（ i） ∧ A? W)}； （ 3） X（ i+1） =B∪ X（ i） 算法 （ 4）判斷 X（ i+1） = X （ i） 嗎 ? （ 5）若相等或 X（ i） =U , 則 X（ i） 就是 XF+ , 算法終止。 （ 6）若否，則 i=i+l，返回第（ 2）步。 對于算法 ， 令 ai =|X（ i） |， {ai }形成一個步長 大于 1的嚴(yán)格遞增的序列，序列的上
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1