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