【正文】 ? 如果一個模式分解 保持了函數(shù)依賴 ，則它可以減輕或解決各種異常情況。 如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系 ， 那么這種分解就沒有 丟失信息 。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 極小化過程 ( 定理 )也是檢驗 F是否為極小依賴集的一個算法 若改造后的 F與原來的 F相同，說明 F本身就是一個最小依賴集 ? 在 RU， F中可以用與 F等價的依賴集 G來取代 F 原因：兩個關(guān)系模式 R1 U， F， R2U， G，如果 F與 G等價，那么 R1的關(guān)系一定是 R2的關(guān)系。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 [例 3]已知： F = {A→B， B→A， B→C， A→C， C→A}， 求 F 的極小函數(shù)依賴集 Fm 解： ： F=﹛ A→B， B→A， B→C， A→C， C→A﹜ 2. ① 在 F中去掉 A→B， (A)F+={AC}， ∵ B ? (A)F+ ， ∴ 不去掉。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 6. 最小依賴集 定義 如果函數(shù)依賴集 F滿足下列條件 ， 則稱 F為一個 極小函數(shù)依賴集 。 構(gòu)造一張二維表 r，它由下列兩個元組構(gòu)成，可以證明 r必是 R（ U， F）的一個關(guān)系 ，即 F+中的全部函數(shù)依賴在 r上成立。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 求閉包的算法 算法 求屬性集 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+ , 算法終止。 （ Augmentation）：若 X→Y為 F所蘊含，且 Z ? U，則XZ→YZ為 F所蘊含。 ? 一般地，在 R（ U）上若有 X→→Y在 W（ W ? U）上成立，則稱 X→→Y為 R（ U）的嵌入型多值依賴 ? 只要在 R（ U）的任何一個關(guān)系 r中，元組在 X和 Y上的值滿足定義 （函數(shù)依賴），則函數(shù)依賴 X→Y在任何屬性集 W（ X Y ? W ?U）上成立。 ? 產(chǎn)生原因： 存在多值依賴 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴的定義 定義 設(shè) R(U)是一個屬性集 U上的一個關(guān)系模式， X、 Y和 Z是 U的子集，并且 Z＝ U－ X－ Y， 多值依賴 X→→Y成立當(dāng)且僅當(dāng)對 R的 任一關(guān)系 r，r在（ X， Z）上的每個值對應(yīng)一組 Y的值，這組值僅僅決定于 X值而與Z值無關(guān)。這個關(guān)系模式中顯然沒有屬性對碼傳遞依賴或部分依賴。 ? 若 R∈ 3NF，則 R的每一個 非主屬性 既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。 例 : 關(guān)系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc為學(xué)生住處，假設(shè)每個系的學(xué)生住在同一個地方。 若 X→Y，但 Y ? X, 則稱 X→Y是 非平凡的函數(shù)依賴 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 三、完全函數(shù)依賴與部分函數(shù)依賴 定義 在關(guān)系模式 R(U)中，如果 X→Y，并且對于 X的任何一個真子集 X?，都有 X? Y, 則稱 Y完全函數(shù)依賴于 X，記作 X F Y。 分解成三個關(guān)系模式 : S (SNO, SDEPT, SNO → DEPT)。 從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 結(jié)論： ? Student關(guān)系模式不是一個好的模式。 規(guī)范化 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 : Student(Sno, Sname, Ssex, Sage, Sdept) 假設(shè)不允許重名，則有 : Sno → Ssex， Sno → Sage , Sno → Sdept， Sno ←→ Sname, Sname → Ssex， Sname → Sage Sname → Sdept 若 X→Y，并且 Y→X, 則記為 X←→ Y。 ? 第一范式是對關(guān)系模式的最起碼的要求。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 3NF 例： 2NF關(guān)系模式 SL(Sno, Sdept, Sloc)中 函數(shù)依賴： Sno→Sdept， Sno→Sloc， Sdept→Sloc Sloc傳遞函數(shù)依賴于 Sno，即 SL中存在非主屬性對碼的傳遞函數(shù)依賴。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 2：關(guān)系模式 SJP(S,J,P)中， S是學(xué)生， J表示課程， P表示名次。 (2) 插入操作復(fù)雜： 當(dāng)某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組。 （ 5）若 X→→Y， X→→Z，則 X→→Y∩Z。 ? 在設(shè)計數(shù)據(jù)庫模式結(jié)構(gòu)時，必須對現(xiàn)實世界的實際情況和用戶應(yīng)用需求作進一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 3. 函數(shù)依賴閉包 定義 在關(guān)系模式 RU， F中為 F所邏輯蘊含的函數(shù)依賴的全體叫作 F的閉包 ，記為 F+。 /* Armstrong正確 完備性 ： F+中的每一個函數(shù)依賴，必定可以由 F出發(fā)根據(jù) Armstrong公理推導(dǎo)出來 。 （ 3）同理可證 G+ ? F+ ，所以 F+ = G+。 定理 也是求 F極小依賴集的過程 (3)逐一取出 F中各函數(shù)依賴 FDi： X→A， 設(shè) X=B1B2… Bm， 逐一考查 Bi （ i=l， 2， … ， m） ， 若 A ?（ XBi ） F+ ， 則以 XBi 取代 X。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ② .AF→G： ∴ (A)F+= ﹛ ACDEB﹜ ， ∴ (F)F+= ﹛ ACDEB﹜ ， ∵ G ? (A)F+ ； G ? (F)F+ ， ∴ 不能用 A→G或 F→G代替 AF→G ， 記 F=﹛ A→C， A→D， D→E， D→B ， AF→G， AF→H， AF→I， I→J ﹜ 。 以上也是模式分解的原則。 定義 519 設(shè) ρ={R1U1,F1, R2U2,F2,...RnUn,Fn}是 RU,F的一個分解， 若F+ =( F1∪ F2∪ … ∪ Fn ) +,則稱關(guān)系模式 R的這個分解 ρ是保持函數(shù)依賴的 。具有無損連接性的分解不一定能夠保持函數(shù)依賴。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 第三種分解 Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B SD SL Sno 95001 95002 95003 95004 95005 Sdept CS IS MA IS PH SD Sloc A B C B B Sno 95001 95002 95003 95004 95005 SL 沒有丟失信息 ， 但原關(guān)系 SL中的函數(shù)依賴 Sdept→Sloc 在關(guān)系模式 SD和 SL上不見了。 ?設(shè)計數(shù)據(jù)庫的標(biāo)準(zhǔn) 不存在插入異常、刪除異常、修改異常和冗余度大等問題。 ④在 F中去掉 A→C， (A)F+={ABC}， ∵ C∈ (A)F+ ， ∴ 應(yīng)去掉 ⑤在 F中去掉 C→A， (C)F+={C}， ∵ A ? (C)F+ ， ∴ 不去掉。 (2) F中不存在這樣的函數(shù)依賴 X→A， 使得 F與 F{X→A}等價 。 所以 r必是 RU， F的一個關(guān)系 。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 求閉包的算法 [例 1] 已知關(guān)系模式 RU， F，其中 U={A， B， C， D， E}； F={AB→C， B→D， C→E， EC→B， AC→B}。 證： 設(shè) X→Y為 F所蘊含，且 Z ? U。 成立 ? 多值依賴 X→→Y若在 R(U)上成立，不能斷言對于任何 Y? ? Y有 X→→Y? 成立。 這里， X， Y是 U的子集， Z=UXY。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個固定的教師。 ? 將一個 2NF關(guān)系分解為多個 3NF的關(guān)系后，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。 (2) 刪除異常 假定某個學(xué)生本來只選修了 3號課程這一門課。 定義 在關(guān)系模式 R(U)中，如果 X→Y， Y→Z，且 Y ?X，Y→X，則稱 Z傳遞函數(shù)依賴 于 X。 數(shù)據(jù)庫系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 規(guī)范化 規(guī)范化理論 正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。 從形式上看，它由一組關(guān)系組成。 。 例如“姓名 →年齡”這個函數(shù)依賴只有在不允許有同名人的條件下成立 3. 數(shù)據(jù)庫設(shè)計者可以對現(xiàn)實世界作強制的規(guī)定。滿足不同程度要求的為不同范式。 ? 解決方法 SLC分解為兩個關(guān)系模式，以消除這些部分函數(shù)依賴 SC（ Sno， Cno， Grade） SL（ Sno， Sdept， Sloc） 數(shù)據(jù)庫系統(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，并且每一個 非主 屬性都 完全 函數(shù)依賴于 R的碼，則 R∈ 2NF。 假定 Sname也具有唯一性，那么 S就有兩個碼，這兩個碼都由單個屬性組成，彼此不相交。 ⒉ 所有 主屬性 都完全函數(shù)依賴于每個不包含它的候選碼 。 （ 2）多值依賴具有傳遞性 若 X→→Y， Y→→Z， 則 X→→Z Y Xi Zi1 Zi2 … Zim Yi1 Yi2 … Yin （ 3）函數(shù)依賴是多值依賴的特殊情況。 ? 一個關(guān)系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。 偽傳遞規(guī)則 ：由 X→Y， WY→Z，有 XW→Z。 數(shù)據(jù)庫系統(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﹜ 。 （ 2）任取 X→Y?F+ 則有 Y ? XF+ ? XG++ 。 (2)逐一檢查 F中各函數(shù)依賴 FDi： X→A， 令 G=F{X→A}，若 A?XG+， 則從 F中去掉此函數(shù)依賴。 ④ 同理考察： A→D， D→E， DE→B， AF→G， AF→H， AF→I，