【正文】 ； ③ 當(dāng) X＝ C時(shí) ， XF+＝ C。 數(shù)據(jù)庫(kù)系統(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+ , 算法終止。 對(duì)于算法 ， 令 ai =|X（ i） |， {ai }形成一個(gè)步長(zhǎng)大于 1的嚴(yán)格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| |X| 次循環(huán)就會(huì)終止。 求（ AB） F+ 。得到兩個(gè)： AB→C， B→D。 (2)因?yàn)?X（ 0） ≠ X（ 1） ，所以再找出左部為 ABCD子集的那些函數(shù)依賴，又得到 AB→C， B→D， C→E， AC→B， 于是 X（ 2） =X（ 1） ∪ BCDE=ABCDE。 數(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﹜ 。 具體解為： (AB)F+=﹛ ABCDE﹜ (B)F+=﹛ BD﹜ (C)F+=﹛ CBDE﹜ (EC)F+=﹛ CBDE﹜ (AC)F+=﹛ ABCDE﹜ (ABC)F+=﹛ ABCDE﹜ (ABCE)F+=﹛ ABCDE﹜ (BC)F+=﹛ BCDE﹜ (BEC)F+=﹛ BCDE﹜ (AEC)F+=﹛ ABCDE﹜ 包含 全部屬性 的有 (AB)F+ ， (AC)F+ ， (ABC)F+ ， (ABCE)F+ ， (AEC)F+ 挑選出 最簡(jiǎn) 的是： (AB)F+ ， (AC)F+ 所以 R 的 碼 為： AB 和 AC 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 證明： 1. 有效性： 可由定理 2. 完備性： 只需證明 逆否命題 : 若函數(shù)依賴 X→Y不能由 F從 Armstrong公理導(dǎo)出，那么它必然不為 F所蘊(yùn)含 分三步證明： 4. Armstrong公理系統(tǒng)的有效性與完備性 有效性： 由 F出發(fā)根據(jù) Armstrong公理推導(dǎo)出來(lái)的每一個(gè)函數(shù)依賴一定在 F+中。 /* 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上成立。 構(gòu)造一張二維表 r，它由下列兩個(gè)元組構(gòu)成，可以證明 r必是 R（ U， F）的一個(gè)關(guān)系 ，即 F+中的全部函數(shù)依賴在 r上成立。 由 r的構(gòu)成可知 ， V必定是 XF+ 的子集 ， 而 W不是 XF+ 的子集 ， 可是由第 （ 1） 步 ， W ? XF+， 矛盾 。 XF+ UXF+ 11......1 00......0 11......1 11......1 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 (3) /* 若 f 不能用 Armstrong公理推導(dǎo)出來(lái)， f∈ F+ /* 而不能用 Armstrong公理推導(dǎo)出來(lái)的 f , 在 r上不成立。（引理 ） ? 因此必有 Y 的子集 Y? 滿足 Y?? UXF+， 則 X→Y在 r 中不成立，即X→Y必不為 RU， F 蘊(yùn)含 /* 因?yàn)? F+中的全部函數(shù)依賴在 r上成立。 引理 F+ = G+ 的充分必要條件是： F ? G+ ， 和 G ? F+ 證 : 必要性顯然，只證充分性。 （ 2）任取 X→Y?F+ 則有 Y ? XF+ ? XG++ 。即 F+ ? G+。 要判定 F ? G+， 只須逐一對(duì) F中的函數(shù)依賴 X→Y， 考察 Y 是否屬于XG++ 就行了 。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 6. 最小依賴集 定義 如果函數(shù)依賴集 F滿足下列條件 ， 則稱 F為一個(gè) 極小函數(shù)依賴集 。 (1) F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性 。 (3) F中不存在這樣的函數(shù)依賴 X→A， X有真子集 Z 使得 F{X→A}∪ {Z→A}與 F等價(jià) 。 因?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。 (1)逐一檢查 F中各函數(shù)依賴 FDi： X→Y， 若 Y=A1A2 … Ak， k 2， 則用 { X→Aj |j=1， 2， … ， k} 來(lái)取代 X→Y。 (2)逐一檢查 F中各函數(shù)依賴 FDi： X→A， 令 G=F{X→A}，若 A?XG+， 則從 F中去掉此函數(shù)依賴。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 因?yàn)閷?duì) F的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)，因此剩下的 F與原來(lái)的 F等價(jià)。 由于 F與 F{X→A}∪ {Z→A}等價(jià)的充要條件是 A?ZF+ ， 其中 Z=XBi 因此 F變換前后是等價(jià)的。 數(shù)據(jù)庫(kù)系統(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+ ， ∴ 不去掉。 ③在 F中去掉 B→C ， (B)F+={B}， ∵ C ? (B)F+ ， ∴ 不去掉。 ，故不用再取其子集去考察。 求 F 的極小函數(shù)依賴集 Fm 解： ： 則 F=﹛ A→B ,A→C， A→D， A→E， D→E， DE→B， AF→G， AF→H， AF→I， I→J﹜ 。 ② A→C：記 G=F﹛ A→C ﹜ ， ∴ (A)G+= ﹛ ADEB﹜ ， ∴ C ? (A)G+ ， ∴ 不去掉 A→C ， F=﹛ A→C， A→D， A→E， D→E， DE→B， AF→G， AF→H， AF→I， I→J ﹜ 。 ④ 同理考察： A→D， D→E， DE→B， AF→G， AF→H， AF→I，I→J ，它們都不能去掉。 3. 函數(shù)依賴左部的分解 ① .DE→B： ∴ (D)F+= ﹛ DEB﹜ ， ∴ B∈ (D)F+ ， ∴ 用 D→B代替 DE→B ， 記 F=﹛ A→C， A→D， D→E， D→B ， AF→G， AF→H， AF→I， I→J ﹜ 。 同理，可考察 AF→H， AF→I，它們都應(yīng)保留。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 極小化過(guò)程 ( 定理 )也是檢驗(yàn) F是否為極小依賴集的一個(gè)算法 若改造后的 F與原來(lái)的 F相同，說(shuō)明 F本身就是一個(gè)最小依賴集 ? 在 RU， F中可以用與 F等價(jià)的依賴集 G來(lái)取代 F 原因：兩個(gè)關(guān)系模式 R1 U， F， R2U， G，如果 F與 G等價(jià)，那么 R1的關(guān)系一定是 R2的關(guān)系。 數(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ì)提供了理論的指南和工具 。 ?設(shè)計(jì)數(shù)據(jù)庫(kù)方法 概念模型 →關(guān)系數(shù)據(jù)模型 → 關(guān)系數(shù)據(jù)規(guī)范化 （將數(shù)據(jù)庫(kù)中的各關(guān)系盡量達(dá)到高一級(jí)的范式）。 ?進(jìn)行關(guān)系模式分解 將低級(jí)范式的關(guān)系模式分解使其達(dá)到高級(jí)范式。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 模式的分解 ? 把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的。 三種模式分解的等價(jià)定義 ⒈ 分解具有無(wú)損連接性。 ⒊ 分解既要保持函數(shù)依賴，又要具有無(wú)損連接性。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 例 : SL（ Sno， Sdept， Sloc） F={ Sno→Sdept,Sdept→Sloc,Sno→Sloc} SL∈ 2NF 存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題 分解方法可以有多種 : 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ù) 丟失了許多信息 。 如果分解后的關(guān)系可以通過(guò)自然連接恢復(fù)為原來(lái)的關(guān)系 ， 那么這種分解就沒有 丟失信息 。 元組增加了，信息丟失了。 有數(shù)據(jù)冗余。 保持函數(shù)依賴，但丟失信息，是有損連接。 既保持函數(shù)依賴，又能無(wú)損連接。 定義 函數(shù)依賴集合 {X→Y | X→Y ? F+∧ XY ?Ui} 的一個(gè) 覆蓋 Fi 叫作 F 在屬性 Ui 上的投影。 其中： mρ(r) 是 r在 ρ中各關(guān)系模式上的投影的連接。 數(shù)據(jù)庫(kù)系統(tǒng)概論 第六章 關(guān)系數(shù)據(jù)理論 ? 如果一個(gè)模式分解 具有無(wú)損連接性 ，則它能夠保證不丟失信息。 ? 如果一個(gè)模式分解 保持了函數(shù)依賴 ，則它可以減輕或解決各種異常情況。 ? 分解具有無(wú)損連接性和分解保持函數(shù)依賴是兩個(gè) 互相獨(dú)立 的標(biāo)準(zhǔn)。同樣，保持函數(shù)依賴的分解也不一定具有無(wú)損連接性。那么這個(gè)模式分解一定能夠達(dá)到 3NF，但不一定能夠達(dá)到 BCNF。 算法 轉(zhuǎn)換為 3NF既有無(wú)損連接性又保持函數(shù)依賴的分解 算法 轉(zhuǎn)換為 BCNF的無(wú)損連接分解 （ 分解法 ） 算法 達(dá)到 4NF的具有無(wú)損連接性的分解