【正文】 I→J ，它們都不能去掉。 三種模式分解的等價(jià)定義 ⒈ 分解具有無(wú)損連接性。 定義 函數(shù)依賴集合 {X→Y | X→Y ? F+∧ XY ?Ui} 的一個(gè) 覆蓋 Fi 叫作 F 在屬性 Ui 上的投影。那么這個(gè)模式分解一定能夠達(dá)到 3NF，但不一定能夠達(dá)到 BCNF。 保持函數(shù)依賴，但丟失信息，是有損連接。 ?進(jìn)行關(guān)系模式分解 將低級(jí)范式的關(guān)系模式分解使其達(dá)到高級(jí)范式。 求 F 的極小函數(shù)依賴集 Fm 解： ： 則 F=﹛ A→B ,A→C， A→D， A→E， D→E， DE→B， AF→G， AF→H， AF→I， I→J﹜ 。 因?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。（引理 ） ? 因此必有 Y 的子集 Y? 滿足 Y?? UXF+， 則 X→Y在 r 中不成立，即X→Y必不為 RU， F 蘊(yùn)含 /* 因?yàn)? F+中的全部函數(shù)依賴在 r上成立。得到兩個(gè)： AB→C， B→D。 證： 設(shè) X→Y及 Y→Z為 F所蘊(yùn)含。 （ X→Y） ? 函數(shù)依賴和多值依賴是兩種最重要的數(shù)據(jù)依賴。每個(gè)保管員保管所在倉(cāng)庫(kù)的所有商品，每種商品被所有保管員保管。 ? 3NF和 BCNF是在函數(shù)依賴的條件下對(duì)模式分解所能達(dá)到的分離程度的測(cè)度。設(shè) R不是 3NF。 (3) 數(shù)據(jù)冗余度大 如果一個(gè)學(xué)生選修了 10門(mén)課程，那么他的 Sdept和 Sloc值就要重復(fù)存儲(chǔ)了 10次。若關(guān)系模式 R有多個(gè)候選碼，則選定其中的一個(gè)做為 主碼 （ Primary key）。 X稱為這個(gè)函數(shù)依賴的 決定屬性集 (決定因素 )。 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)。 3. 數(shù)據(jù)依賴的類型 ? 函數(shù)依賴（ Functional Dependency，簡(jiǎn)記為 FD） ? 多值依賴（ Multivalued Dependency，簡(jiǎn)記為 MVD） ? 其他 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 四、關(guān)系模式的簡(jiǎn)化表示 關(guān)系模式 R（ U, D, DOM, F） 簡(jiǎn)化為一個(gè)三元組： R（ U, F） 當(dāng)且僅當(dāng) U上的一個(gè)關(guān)系 r 滿足 F時(shí)， r稱為關(guān)系 模式 R（ U, F）的一個(gè) 關(guān)系 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 五、數(shù)據(jù)依賴對(duì)關(guān)系模式的影響 例：描述學(xué)校的數(shù)據(jù)庫(kù)： 學(xué)生的學(xué)號(hào)（ Sno）、所在系（ Sdept） 系主任姓名（ Mname）、課程名（ Cname） 成績(jī)（ Grade） 單一 的關(guān)系模式 ： Student U、 F U ＝｛ Sno, Sdept, Mname, Cname, Grade ｝ 學(xué)校數(shù)據(jù)庫(kù)的語(yǔ)義： ⒈ 一個(gè)系有若干學(xué)生， 一個(gè)學(xué)生只屬于一個(gè)系； ⒉ 一個(gè)系只有一名主任； ⒊ 一個(gè)學(xué)生可以選修多門(mén)課程， 每門(mén)課程有若干學(xué)生選修； ⒋ 每個(gè)學(xué)生所學(xué)的每門(mén)課程都有一個(gè)成績(jī)。 Y=f(x) 說(shuō)明： 1. 函數(shù)依賴不是指關(guān)系模式 R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的 所有關(guān)系實(shí)例 均要滿足的約束條件。 ? 主屬性與非主屬性 ? 全碼 (ALL KEY) 定義 關(guān)系模式 R 中屬性或?qū)傩越M X 并非 R的碼，但 X 是另一個(gè)關(guān)系模式的碼，則稱 X 是 R 的 外部碼（ Foreign key） 也稱外碼 ? 主碼又和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。 (4) 修改復(fù)雜 例如學(xué)生轉(zhuǎn)系，在修改此學(xué)生元組的 Sdept值的同時(shí)，還可能需要修改住處（ Sloc）。則必然存在如下條件的函數(shù)依賴，X→Y （ Y?X）， Y→Z ，其中 X是含有碼的屬性， Y是任意屬性組， Z是非主屬性， Z?Y，這樣 Y→Z 函數(shù)依賴的決定因素 Y不包含候選碼，這與BCNF范式的定義相矛盾，所以如果R?BCNF，則 R也是 3NF 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 1 對(duì)關(guān)系模式 C、 SC、 S進(jìn)行分析。 ? 一個(gè)模式中的關(guān)系模式如果都屬于 BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了徹底的分離，已消除了插入和刪除的異常。 倉(cāng)庫(kù)管理關(guān)系 按照語(yǔ)義對(duì)于 W的每一個(gè)值 Wi， S有一個(gè)完整的集合與之對(duì)應(yīng)而不論 C取何值。 ? 如果只考慮 函數(shù)依賴 ，則屬于 BCNF的關(guān)系模式規(guī)范化程度已最高了。 對(duì) RU， F 的任一關(guān)系 r中的任意兩個(gè)元組 t， s。 于是 X（ 1） =AB∪ CD=ABCD。 Armstrong公理的完備性及有效性說(shuō)明 : “蘊(yùn)含” == “導(dǎo)出” 等價(jià)的概念 F+ ==由 F出發(fā)借助 Armstrong公理導(dǎo)出的函數(shù)依賴的集合 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 5. 函數(shù)依賴集等價(jià) 定義 如果 G+=F+，就說(shuō)函數(shù)依賴集 F覆蓋 G（ F是 G的覆蓋，或 G是F的覆蓋），或 F與 G等價(jià) 。 此 Fm稱為 F的最小依賴集 證 :構(gòu)造性證明 ， 依據(jù)定義分三步對(duì) F進(jìn)行 “ 極小化處理 ” ， 找出 F的一個(gè)最小依賴集 。 2. ① A→B：記 G=F﹛ A→B﹜ ， ∴ (A)G+= ﹛ ACDEB﹜ ， ∴ B∈ (A)G+ ， ∴ 去掉 A→B ， F=F﹛ A→B﹜ =﹛ A→C， A→D， A→E， D→E， DE→B，AF→G， AF→H， AF→I， I→J ﹜ 。 Key的求法： X(i) =XF+ X(i) =U，則選出其中的 X， X中選出最簡(jiǎn)的主屬性組 Xi , 4. Xi 就是所求的碼。 沒(méi)有保持函數(shù)依賴，沒(méi)有丟失信息，是無(wú)損連接，但有數(shù)據(jù)冗余。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 分解算法 算法 判別一個(gè)分解的無(wú)損連接性 算法 （ 合成法 ） 轉(zhuǎn)換為 3NF的保持函數(shù)依賴的分解 。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 模式分解的定義 定義 關(guān)系模式 RU,F的一個(gè)分解： ρ={ R1U1,F1， R2U2,F2， … ， RnUn,Fn} U=U1∪ U2∪ … ∪ Un，且 不存在 Ui ? Uj， Fi 為 F在 Ui 上的投影。 ? 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ③ A→E：記 G=F﹛ A→E﹜ ， ∴ (A)G+= ﹛ ACDEB﹜ ， ∴ E∈ (A)G+ ， ∴ 去掉 A→E ， F=F﹛ A→E﹜ =﹛ A→C， A→D， D→E， DE→B， AF→G， AF→H， AF→I， I→J ﹜ 。 引理 F變換前后的等價(jià)性 。 （ 1）若 F?G+ ，則 XF+ ? XG++ 。 (3)因?yàn)?X（ 2） =U，算法終止 所以（ AB） F+ =ABCDE。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 2. 導(dǎo)出規(guī)則 A1， A2， A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則 ：由 X→Y， X→Z，有 X→YZ。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 存在非平凡的多值依賴 C→→T，且 C不是候選碼 ? 用投影分解法把 Teach分解為如下兩個(gè)關(guān)系模式： CT(C, T) ∈ 4NF CB(C, B) ∈ 4NF C→→T， C→→B是平凡多值依賴 ? 同樣的方法可以把 WSC（ W， S， C） 分解為： WS（ W， S） ∈ 4NF WC（ W， C） ∈ 4NF 例： Teach(C,T,B) ∈ 4NF 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 規(guī)范化小結(jié) ? 關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具。 Si1 ， Si2 ， … … Sin Ci1 ， Ci2 ， … … C in Wi S C Wi Wi 于是 {S}Wi與 {C}Wi之間正好形式一個(gè)完全二分圖，如圖 : 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 多值依賴的性質(zhì) （ 1）多值依賴具有對(duì)稱性 若 X→→Y，則 X→→Z，其中 Z＝ U－ X－ Y 多值依賴的對(duì)稱性可以用完全二分圖直觀地表示出來(lái)。 BCNF的關(guān)系模式所具有的性質(zhì) ⒈ 所有 非主屬性 都完全函數(shù)依賴于每個(gè)候選碼 。同時(shí) C中 Cno是唯一的決定因素，所以 C∈ BCNF。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 函數(shù)依賴圖： Sdept Sloc Sno SL Sno Cno Grade SC ? 原因 Sdept、 Sloc部分函數(shù)依賴于碼。 ? 關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿足一定的要求。只能根據(jù)數(shù)據(jù)的語(yǔ)義來(lái)確定函數(shù)依賴。 例，如果一個(gè)系剛成立，尚無(wú)學(xué)生，我們就無(wú)法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫(kù)。 ? 關(guān)系數(shù)據(jù)庫(kù)的模式 ：定義這組關(guān)系的關(guān)系模式的全體。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 函數(shù)依賴 一、函數(shù)依賴 定義 設(shè) R(U)是一個(gè)屬性集 U上的關(guān)系模式， X和 Y是 U的子集。 例 : 在關(guān)系 Std(Sno, Sdept, Mname)中，有： Sno → Sdept， Sdept → Mname Mname傳遞函數(shù)依賴于 Sno 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 碼 定義 設(shè) K為關(guān)系模式 RU,F中的屬性或?qū)傩越M合?，F(xiàn)在因身體不適，他連 3號(hào)課程也不選修了。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 BC范式（ BCNF） 定義 設(shè)關(guān)系模式 RU， F∈ 1NF，如果對(duì)于 R的 每個(gè)函數(shù)依賴X→Y，若 Y不屬于 X，則 X必含有候選碼，那么 R∈ BCNF。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱 。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 平凡多值依賴和非平凡的多值依賴 ? 若 X→→Y，而 Z＝ φ，則稱 X→→Y為 平凡的多值依賴 ? 否則稱 X→→Y為 非平凡的多值依賴 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 2：關(guān)系模式 WSC(W,S,C)中， W表示倉(cāng)庫(kù)，S表示保管員， C表示商品。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 第四范式（ 4NF） ? 如果 R ∈ 4NF， 則 R ∈ BCNF 不允許 有非平凡且非函數(shù)依賴的 多值依賴，允許 的是 函數(shù)依賴（是平凡多值依賴）。 設(shè) RU， F 的任一關(guān)系 r中任意的兩個(gè)元組 t， s； 若 t[XZ]=s[XZ]，則有 t[X]=s[X]和 t[Z]=s[Z]； 由 X→Y，于是有 t[Y]=s[Y]，所以 t[YZ]=