【正文】 理論 問題的提出 規(guī)范化 數據依賴的公理系統(tǒng) * 模式的分解 數據庫系統(tǒng)概論 第六章 關系數據理論 問題的提出 關系數據庫邏輯設計 ? 針對具體問題 ， 如何構造一個適合于它的數據模式 ? 數據庫邏輯設計的工具 ──關系數據庫的規(guī)范化理論 ? 關系 ：描述實體、屬性、實體間的聯(lián)系。 2. 數據依賴 ? 是通過一個關系中屬性間值的相等與否體現(xiàn)出來的數據間的相互關系； ? 是現(xiàn)實世界屬性間相互聯(lián)系的抽象是數據內在的性質是 語義 的體現(xiàn)。 ? “好”的模式： 不會發(fā)生插入異常、刪除異常、更新異常，數據冗余應盡可能少。 X稱為這個函數依賴的 決定屬性集 (決定因素 )。 若 Y不函數依賴于 X, 則記為 X─→Y。若關系模式 R有多個候選碼，則選定其中的一個做為 主碼 （ Primary key）。不滿足第一范式的數據庫模式不能稱為關系數據庫。 (3) 數據冗余度大 如果一個學生選修了 10門課程，那么他的 Sdept和 Sloc值就要重復存儲了 10次。 Sdept Sloc Sno SL 解決方法： 采用投影分解法，把 SL分解為兩個關系模式，以消除傳遞函數依賴： SD（ Sno， Sdept） DL（ Sdept， Sloc） SD的碼為 Sno， DL的碼為 Sdept。設 R不是 3NF。 每一個學生選修每門課程的成績有一定的名次，每門課程中每一名次只有一個學生（即沒有并列名次）。 ? 3NF和 BCNF是在函數依賴的條件下對模式分解所能達到的分離程度的測度。 (3) 刪除操作復雜： 某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組。每個保管員保管所在倉庫的所有商品，每種商品被所有保管員保管。 （ 6）若 X→→Y， X→→Z，則 X→→YZ， X→→Z Y。 （ X→Y） ? 函數依賴和多值依賴是兩種最重要的數據依賴。 ? 上面的規(guī)范化步驟可以在其中任何一步終止。 證： 設 X→Y及 Y→Z為 F所蘊含。 定義 設 F為屬性集 U上的一組函數依賴， X ?U， XF+ ={ A|X→A能由 F 根據 Armstrong公理導出 }， XF+稱為屬性集 X關于函數依賴集 F 的閉包 例 :設 RU， F， U={A， B， C)， F＝ {A→B， B→C}， 則： ① 當 X＝ A時 ， XF+＝ ABC； ② 當 X＝ B時 ， XF+＝ BC； ③ 當 X＝ C時 ， XF+＝ C。得到兩個： AB→C， B→D。 /* Armstrong公理夠用，完全 若 f 不能用 Armstrong公理推導出來， f∈ F+ 有效性與完備性的證明 數據庫系統(tǒng)概論 第六章 關系數據理論 (1)引理 : 若 V→W成立 ， 且 V ? XF+， 則 W ? XF+ 證 因為 V ? XF+ ， 所以有 X→V成立； 因為 X →V， V→W，于是 X→W成立 所以 W ? XF+ (2)/* 若 f 不能用 Armstrong公理推導出來， f∈ F+ /* 若存在 r， F+中的全部函數依賴在 r上成立。（引理 ） ? 因此必有 Y 的子集 Y? 滿足 Y?? UXF+， 則 X→Y在 r 中不成立，即X→Y必不為 RU， F 蘊含 /* 因為 F+中的全部函數依賴在 r上成立。 要判定 F ? G+， 只須逐一對 F中的函數依賴 X→Y， 考察 Y 是否屬于XG++ 就行了 。 因為： F ’{SNO→MN}與 F ?等價 F ’{(SNO， SDEPT)→SDEPT}也與 F ?等價 F ’{(SNO， SDEPT)→SDEPT} ∪ {SNO→SDEPT}也與 F ?等價 數據庫系統(tǒng)概論 第六章 關系數據理論 7. 極小化過程 定理 每一個函數依賴集 F均等價于一個極小函數依賴集 Fm。 由于 F與 F{X→A}∪ {Z→A}等價的充要條件是 A?ZF+ ， 其中 Z=XBi 因此 F變換前后是等價的。 求 F 的極小函數依賴集 Fm 解： ： 則 F=﹛ A→B ,A→C， A→D， A→E， D→E， DE→B， AF→G， AF→H， AF→I， I→J﹜ 。 同理，可考察 AF→H， AF→I，它們都應保留。 ?進行關系模式分解 將低級范式的關系模式分解使其達到高級范式。 數據庫系統(tǒng)概論 第六章 關系數據理論 例 : SL（ Sno， Sdept， Sloc） F={ Sno→Sdept,Sdept→Sloc,Sno→Sloc} SL∈ 2NF 存在插入異常、刪除異常、冗余度大和修改復雜等問題 分解方法可以有多種 : SD(Sno， Sdept) DL (Sdept， Sloc) 4. SD(Sno， Sdept) SL (Sno， Sloc) 3. SL(Sno， Sloc) DL (Sdept， Sloc) 2. S (Sno) D (Sdept) L(Sloc) 1. Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B SL 數據庫系統(tǒng)概論 第六章 關系數據理論 第一種分解 Sno 95001 95002 95003 95004 95005 S Sdept CS IS MA PH D Sloc A B C L S D L 無法連接 分解后的數據庫 丟失了許多信息 。 保持函數依賴，但丟失信息，是有損連接。 數據庫系統(tǒng)概論 第六章 關系數據理論 ? 如果一個模式分解 具有無損連接性 ，則它能夠保證不丟失信息。那么這個模式分解一定能夠達到 3NF，但不一定能夠達到 BCNF。 ? 分解具有無損連接性和分解保持函數依賴是兩個 互相獨立 的標準。 定義 函數依賴集合 {X→Y | X→Y ? F+∧ XY ?Ui} 的一個 覆蓋 Fi 叫作 F 在屬性 Ui 上的投影。 元組增加了，信息丟失了。 三種模式分解的等價定義 ⒈ 分解具有無損連接性。 數據庫系統(tǒng)概論 第六章 關系數據理論 關系數據理論小結 ?關系數據理論 為關系數據庫設計提供了理論的指南和工具 。 ④ 同理考察： A→D， D→E， DE→B， AF→G， AF→H， AF→I，I→J ，它們都不能去掉。 ③在 F中去掉 B→C ， (B)F+={B}， ∵ C ? (B)F+ ， ∴ 不去掉。 (2)逐一檢查 F中各函數依賴 FDi： X→A， 令 G=F{X→A}，若 A?XG+， 則從 F中去掉此函數依賴。 (1) F中任一函數依賴的右部僅含有一個屬性 。 （ 2）任取 X→Y?F+ 則有 Y ? XF+ ? XG++ 。 由 r的構成可知 ， V必定是 XF+ 的子集 ， 而 W不是 XF+ 的子集 ， 可是由第 （ 1） 步 ， W ? XF+， 矛盾 。 數據庫系統(tǒng)概論 第六章 關系數據理論 求關系模式的碼 [例 2] 已知關系 R U， F， U=﹛ A， B， C， D， E﹜ ， F=﹛ AB→C， B→D， C→E， EC→B， AC→B﹜ 。 對于算法 ， 令 ai =|X（ i） |， {ai }形成一個步長大于 1的嚴格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| |X| 次循環(huán)就會終止。 偽傳遞規(guī)則 ：由 X→Y， WY→Z，有 XW→Z。 注意：由自反律所得到的函數依賴均是平凡的函數依賴，自反律的使用并不依賴于 F 數據庫系統(tǒng)概論 第六章 關系數據理論 定理 Armstrong推理規(guī)則是正確的 (l)自反律 :若 Y ? X ? U，則 X →Y為 F所蘊含 證 : 設 Y ? X ? U 對 R U， F 的任一關系 r中的任意兩個元組 t， s： 若 t[X]=s[X]，由于 Y ? X，有 t[y]=s[y]， 所以 X→Y成立 . 自反律得證 (2)增廣律 : 若 X→Y為 F所蘊含，且 Z ? U，則 XZ→YZ 為 F所蘊含。 ? 一個關系只要其分量都是不可分的數據項，它就是規(guī)范化的關系，但這只是最基本的規(guī)范化。 ? Y均有 X→Y39。 （ 2）多值依賴具有傳遞性 若 X→→Y， Y→→Z， 則 X→→Z Y Xi Zi1 Zi2 … Zim Yi1 Yi2 … Yin （ 3）函數依賴是多值依賴的特殊情況。 另一等價定義 在 R（ U）的任一關系 r中，如果存在元組 t， s 使得 t[X]=s[X]，那么就必然存在元組 w,v? r，（ w,v可以與 s， t相同），使得： (1) w[X]=v[X]=t[X]=s[X] ， (2) w[Y]=t[Y]， w[Z]=s[Z]， (3) v[Y]=s[Y]， v[Z]=t[Z] （即交換 s， t元組的 Y值所得的兩個新元組必在 r中）， 則 Y多值依賴于 X，記為 X→→Y。 ⒉ 所有 主屬性 都完全函數依賴于每個不包含它的候選碼 。 每一教師只教一門課。 假定 Sname也具有唯一性，那么 S就有兩個碼，這兩個碼都由單個屬性組成，彼此不相交。 ? 采用投影分解法將一個 2NF的關系分解為多個 3NF的關系，可以在一定程度上解決原 2NF關系中存在的插入異常、刪除異常、數據冗余度大、修改復雜等問題。 ? 解決方法 SLC分解為兩個關系模式，以消除這些部分函數依賴 SC（ Sno， Cno， Grade） SL（ Sno， Sdept， Sloc） 數據庫系統(tǒng)概論 第六章 關系數據理論 例： SLC(Sno, Sdept, Sloc, Cno, Grade) ∈ 1NF SLC(Sno, Sdept, Sloc, Cno, Grade) ? 2NF SC（ Sno， Cno， Grade） ∈ 2NF SL（ Sno， Sdept， Sloc） ∈ 2NF 2NF定義 定義 若關系模式 R∈ 1NF，并且每一個 非主 屬性都 完全 函數依賴于 R的碼，則 R∈ 2NF。 非主屬性 Sdept和 Sloc部分函數依賴于碼 (Sno, Cno) 數據庫系統(tǒng)概論 第六章 關系數據理論 SLC (Sno, Sdept, Sloc, Cno, Grade)不是一個好的關系模式 (1) 插入異常 假設 Sno＝ 95102， Sdept＝ IS， Sloc＝ N的學生還未選課，因課程號是主屬性，因此該學生的信息無法插入 SLC。滿足不同程度要求的為不同范式。 例 : 在關系 SC(Sno, Cno, Grade)中， 由于： Sno →Grade， Cno → Grade， 因此： (Sno, Cno) F Grade 數據庫系統(tǒng)概論 第六章