第六章關(guān)系數(shù)據(jù)理論 6 1問題的提出6 2規(guī)范化6 3數(shù)據(jù)依賴的公理系統(tǒng)6 4模式分解 6 1問題的提出 關(guān)系數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)針對(duì)具體問題 如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具 關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論 一 關(guān)系模式的形式化定義 關(guān)系模式由五部分組成 即它是一個(gè)五元組 R U D DOM F R 關(guān)系名U 組成該關(guān)系的屬性名集合D 屬性組U中屬性所來自的域DOM 屬性向域的映象集合F 屬性間數(shù)據(jù)的依賴關(guān)系集合 二 關(guān)系模式的簡(jiǎn)化表示 關(guān)系模式R簡(jiǎn)化為一個(gè)三元組 R當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí) r稱為關(guān)系模式R U F 的一個(gè)關(guān)系 三 數(shù)據(jù)依賴 數(shù)據(jù)依賴數(shù)據(jù)依賴是一個(gè)關(guān)系內(nèi)部屬性與屬性之間的一種約束關(guān)系 這種約束關(guān)系是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系 是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象 是數(shù)據(jù)內(nèi)在的性質(zhì) 是語義的體現(xiàn) 兩種重要的數(shù)據(jù)依賴類型函數(shù)依賴 FunctionalDependency 簡(jiǎn)記FD 多值依賴 MultivaluedDependency 簡(jiǎn)記MVD 四 數(shù)據(jù)依賴對(duì)關(guān)系模式的影響 例 描述學(xué)校的數(shù)據(jù)庫(kù) 學(xué)生的學(xué)號(hào) Sno 所在系 Sdept 系主任姓名 Mname 課程名 Cname 成績(jī) Grade 若只考慮函數(shù)依賴得到的描述學(xué)生的關(guān)系模式 StudentU Sno Sdept Mname Cname Grade 學(xué)校數(shù)據(jù)庫(kù)的語義 一個(gè)系有若干學(xué)生 一個(gè)學(xué)生只屬于一個(gè)系 一個(gè)系只有一名主任 一個(gè)學(xué)生可以選修多門課程 每門課程有若干學(xué)生選修 每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績(jī) 由此得到屬性組U上的一組函數(shù)依賴F F Sno Sdept Sdept Mname Sno Cname Grade 1 數(shù)據(jù)冗余太大浪費(fèi)大量的存儲(chǔ)空間例 每一個(gè)系主任的姓名重復(fù)出現(xiàn)2 更新異常數(shù)據(jù)冗余 更新數(shù)據(jù)時(shí) 維護(hù)數(shù)據(jù)完整性代價(jià)大 例 某系更換系主任后 系統(tǒng)必須修改與該系學(xué)生有關(guān)的每一個(gè)元組 關(guān)系模式Student中存在的問題 3 插入異常該插的數(shù)據(jù)插不進(jìn)去例 如果一個(gè)系剛成立 尚無學(xué)生 無法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫(kù) 4 刪除異常不該刪除的數(shù)據(jù)不得不刪例 如果某個(gè)系的學(xué)生全部畢業(yè)了 在刪除該系學(xué)生信息的同時(shí) 把這個(gè)系及其系主任的信息也丟掉了 Student關(guān)系模式不是一個(gè)好的模式 好 的模式 不會(huì)發(fā)生插入異常 刪除異常 更新異常 數(shù)據(jù)冗余應(yīng)盡可能少 原因 由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法 通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴 結(jié)論 6 2規(guī)范化 規(guī)范化理論致力于解決關(guān)系模式中不合適的數(shù)據(jù)依賴問題 函數(shù)依賴和多值依賴是最重要的數(shù)據(jù)依賴 用規(guī)范化理論來改造關(guān)系模式 通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴 以解決插入異常 刪除異常 更新異常和數(shù)據(jù)冗余問題 6 2 1函數(shù)依賴 函數(shù)依賴平凡函數(shù)依賴與非平凡函數(shù)依賴完全函數(shù)依賴與部分函數(shù)依賴傳遞函數(shù)依賴 一 函數(shù)依賴 定義6 1設(shè)R U 是一個(gè)屬性集U上的關(guān)系模式 X和Y是U的子集 若對(duì)于R U 的任意一個(gè)可能的關(guān)系r r中不可能存在兩個(gè)元組在X上的屬性值相等 而在Y上的屬性值不等 則稱 X函數(shù)確定Y 或 Y函數(shù)依賴于X 記作X Y X稱為這個(gè)函數(shù)依賴的決定屬性集 對(duì)于函數(shù)依賴 需要說明以下幾點(diǎn) 1 函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件 而是指R的所有關(guān)系實(shí)例均要滿足的約束條件 2 函數(shù)依賴是語義范疇的概念 只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴 例如 姓名 年齡 這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立3 數(shù)據(jù)庫(kù)設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定 例如規(guī)定不允許同名人出現(xiàn) 函數(shù)依賴 姓名 年齡 成立 所插入的元組必須滿足規(guī)定的函數(shù)依賴 若發(fā)現(xiàn)有同名人存在 則拒絕裝入該元組 4 若X Y 并且Y X 則記為X Y 5 若Y不函數(shù)依賴于X 則記為X Y 例 Student Sno Sname Ssex Sage Sdept 假設(shè)不允許重名 則有 Sno Ssex Sno Sage Sno Sdept Sno Sname Sname Ssex Sname Sage Sname Sdept但Ssex Sage 二 平凡函數(shù)依賴與非平凡函數(shù)依賴 在關(guān)系模式R U 中 對(duì)于U的子集X和Y 如果X Y 但Y X 則稱X Y是非平凡的函數(shù)依賴若X Y 但Y X 則稱X Y是平凡的函數(shù)依賴?yán)?在關(guān)系SC Sno Cno Grade 中 非平凡函數(shù)依賴 Sno Cno Grade平凡函數(shù)依賴 Sno Cno Sno Sno Cno Cno 對(duì)于任一關(guān)系模式 平凡函數(shù)依賴都是必然成立的 它不反映新的語義 因此若不特別聲明 總是討論非平凡函數(shù)依賴 三 完全函數(shù)依賴與部分函數(shù)依賴 定義6 2在關(guān)系模式R U 中 如果X Y 并且對(duì)于X的任何一個(gè)真子集X 都有X Y 則稱Y完全函數(shù)依賴于X 記作X Y 若X Y 但Y不完全函數(shù)依賴于X 則稱Y部分函數(shù)依賴于X 記作X Y F P 例 在關(guān)系SC Sno Cno Grade 中 由于 Sno Grade Cno Grade 因此 Sno Cno Grade F 四 傳遞函數(shù)依賴 定義6 3在關(guān)系模式R U 中 如果X Y Y Z 且Y X Y X 則稱Z傳遞函數(shù)依賴于X 注 如果Y X 即X Y 則Z直接依賴于X 例 在關(guān)系Std Sno Sdept Mname 中 有 Sno Sdept Sdept MnameMname傳遞函數(shù)依賴于Sno 6 2 2碼 定義6 4設(shè)K為關(guān)系模式R中的屬性或?qū)傩越M合 若K U 則K稱為R的一個(gè)侯選碼 若關(guān)系模式R有多個(gè)候選碼 則選定其中一個(gè)做為主碼 主屬性與非主屬性ALLKEY F 定義6 5關(guān)系模式R中屬性或?qū)傩越MX并非R的碼 但X是另一個(gè)關(guān)系模式的碼 則稱X是R的外部碼 也稱外碼 碼是關(guān)系模式中的一個(gè)重要概念 候選碼能夠唯一地標(biāo)識(shí)關(guān)系的元組 是關(guān)系模式中一組最重要的屬性 另一方面 主碼又和外部碼一起提供了一個(gè)表示關(guān)系間聯(lián)系的手段 6 2 3關(guān)系模型的范式 關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿足一定的規(guī)范化要求 對(duì)于不同的規(guī)范化程度可用范式來衡量 范式是符合某一種級(jí)別的關(guān)系模式的集合 是衡量關(guān)系模式規(guī)范化程度的標(biāo)準(zhǔn) 達(dá)到范式的關(guān)系才是規(guī)范化的 范式的種類 第一范式 1NF 第二范式 2NF 第三范式 3NF BC范式 BCNF 第四范式 4NF 第五范式 5NF 各種范式之間存在聯(lián)系 某一關(guān)系模式R為第n范式 可簡(jiǎn)記為R nNF 6 2 41NF 定義如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng) 則R 1NF 第一范式是對(duì)關(guān)系模式的最起碼的要求 不滿足第一范式的數(shù)據(jù)庫(kù)模式不能稱為關(guān)系數(shù)據(jù)庫(kù) 但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式 例 關(guān)系模式SLC Sno Sdept Sloc Cno Grade Sloc為學(xué)生住處 假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方 函數(shù)依賴包括 Sno Cno FGradeSno Sdept Sno Cno PSdeptSno Sloc Sno Cno PSlocSdept Sloc SLC的碼為 Sno Cno SLC滿足第一范式 非主屬性Sdept和Sloc部分函數(shù)依賴于碼 Sno Cno SLC不是一個(gè)好的關(guān)系模式 存在以下問題 1 插入異常假設(shè)Sno 95102 Sdept IS Sloc N的學(xué)生還未選課 因課程號(hào)是主屬性 因此該學(xué)生的信息無法插入SLC 2 刪除異常假定某個(gè)學(xué)生 如95002 本來只選修了3號(hào)課程這一門課 現(xiàn)在因身體不適 他連3號(hào)課程也不選修了 因課程號(hào)是主屬性 此操作將導(dǎo)致該學(xué)生信息的整個(gè)元組都要?jiǎng)h除 3 數(shù)據(jù)冗余度大如果一個(gè)學(xué)生選修了10門課程 那么他的Sdept和Sloc值就要重復(fù)存儲(chǔ)了10次 4 修改復(fù)雜例如學(xué)生轉(zhuǎn)系 在修改此學(xué)生元組的Sdept值的同時(shí) 還可能需要修改住處 Sloc 如果這個(gè)學(xué)生選修了K門課 則必須無遺漏地修改K個(gè)元組中全部Sdept Sloc信息 原因Sdept Sloc部分函數(shù)依賴于碼 解決方法SLC分解為兩個(gè)關(guān)系模式 以消除這些部分函數(shù)依賴 SC Sno Cno Grade SL Sno Sdept Sloc 函數(shù)依賴圖 6 2 52NF 定義定義6 6若關(guān)系模式R 1NF 并且每一個(gè)非主屬性都完全函數(shù)依賴于R的碼 則R 2NF 例 SLC Sno Sdept Sloc Cno Grade 1NFSLC Sno Sdept Sloc Cno Grade 2NFSC Sno Cno Grade 2NFSL Sno Sdept Sloc 2NF 顯然 在分解后的關(guān)系模式中 非主屬性都完全函數(shù)依賴于碼了 從而使上述問題在一定程度上得到了部分的解決 在SL關(guān)系中可以插入尚未選課的學(xué)生 刪除學(xué)生選課情況涉及的是SC關(guān)系 如果一個(gè)學(xué)生所有的選課記錄全部刪除了 只是SC關(guān)系中沒有關(guān)于該學(xué)生的記錄了 不會(huì)牽涉到SL關(guān)系中關(guān)于該學(xué)生的記錄 由于學(xué)生選修課程的情況與學(xué)生的基本情況是分開存儲(chǔ)在兩個(gè)關(guān)系中的 因此不論該學(xué)生選多少門課程 他的dept和Sloc值都只存儲(chǔ)1次 這就大大降低了數(shù)據(jù)冗余 某個(gè)學(xué)生從數(shù)學(xué)系轉(zhuǎn)到信息系 只需修改SL關(guān)系中該學(xué)生元組的dept值和Sloc值 由于dept Sloc并未重復(fù)存儲(chǔ) 因此減化了修改操作 2NF就是不允許關(guān)系模式的屬性之間有這樣的函數(shù)依賴X Y 其中X是碼的真子集 Y是非主屬性 顯然 碼只包含一個(gè)屬性的關(guān)系模式如果屬于1NF 那么它一定屬于2NF 因?yàn)樗豢赡艽嬖诜侵鲗傩詫?duì)碼的部分函數(shù)依賴 采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系 可以在一定程度上減輕原1NF關(guān)系中存在的插入異常 刪除異常 數(shù)據(jù)冗余度大 修改復(fù)雜等問題 將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系 并不能完全消除關(guān)系模式中各種異常情況和數(shù)據(jù)冗余 也就是說 屬于2NF的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式 例 2NF關(guān)系模式SL Sno Sdept Sloc 中函數(shù)依賴 Sno SdeptSdept SlocSno SlocSloc傳遞函數(shù)依賴于Sno 即SL中存在非主屬性對(duì)碼的傳遞函數(shù)依賴 函數(shù)依賴圖 SL關(guān)系中仍然存在插入異常 刪除異常和數(shù)據(jù)冗余度大的問題 刪除異常 如果某個(gè)系的學(xué)生全部畢業(yè)了 在刪除該系學(xué)生信息的同時(shí) 把這個(gè)系的信息也丟掉了 數(shù)據(jù)冗余度大 每一個(gè)系的學(xué)生都住在同一個(gè)地方 關(guān)于系的住處的信息卻重復(fù)出現(xiàn) 重復(fù)次數(shù)與該系學(xué)生人數(shù)相同 修改復(fù)雜 當(dāng)學(xué)校調(diào)整學(xué)生住處時(shí) 比如信息系的學(xué)生全部遷到另一地方住宿 由于關(guān)于每個(gè)系的住處信息是重復(fù)存儲(chǔ)的 修改時(shí)必須同時(shí)更新該系所有學(xué)生的Sloc屬性值 故SL仍存在操作異常問題 仍不是一個(gè)好的關(guān)系模式 解決方法采用投影分解法 把SL分解為兩個(gè)關(guān)系模式 以消除傳遞函數(shù)依賴 SD Sno Sdept DL Sdept Sloc SD的碼為Sno DL的碼為Sdept 函數(shù)依賴圖 定義如果一個(gè)關(guān)系模式R 2NF 且所有非主屬性不存在對(duì)碼的傳遞函數(shù)依賴 則R 3NF 定義6 7關(guān)系模式R中若不存在這樣的碼X 屬性組Y及非主屬性Z Z Y 使得X Y Y X Y Z成立 則稱R 3NF 例 SL Sno Sdept Sloc 2NF SL Sno Sdept Sloc 3NFSD Sno Sdept 3NFDL Sdept Sloc 3NF 6 2 63NF 顯然 在關(guān)系模式SD DL中既沒有非主屬性對(duì)碼的部分函數(shù)依賴也沒有非主屬性對(duì)碼的傳遞函數(shù)依賴 基本上解決了上述問題 DL關(guān)系中可以插入無在校學(xué)生的系的信息 某個(gè)系的學(xué)生全部畢業(yè)了 只是刪除SD關(guān)系中的相應(yīng)元組 DL關(guān)系中關(guān)于該系的信息仍存在 關(guān)于系的住處的信息只在DL關(guān)系中存儲(chǔ)一次 當(dāng)學(xué)校調(diào)整某個(gè)系的學(xué)生住處時(shí) 只需修改DL關(guān)系中一個(gè)相應(yīng)元組的Sloc屬性值 3NF就是不允許關(guān)系模式的屬性之間有這樣的非平凡函數(shù)依賴X Y 其中X不包含碼 Y是非主屬性 X不包含碼有兩種情況 一種情況X是碼的真子集 這是2NF也不允許的 另一種情況X含有非主屬性 這是3NF進(jìn)一步限制的 如果R 3NF 則R也是2NF 采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系 可以在一定程度上解決原2NF關(guān)系中存在的插入異常 刪除異常 數(shù)據(jù)冗余度大 修改復(fù)雜等問題 將一個(gè)2NF關(guān)系分解為多個(gè)3NF的關(guān)系后 并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余 也就是說 屬于3NF的關(guān)系模式雖然基本解決了大部分異常問題 但解決得并不徹底 仍然存在不足 例如 模型SC SNO SNAME CNO GRADE 如果姓名是惟一的 模型存在兩個(gè)候選碼 SNO CNO 和 SNAME CNO 模型SC只有一個(gè)非主屬性GRADE 對(duì)兩個(gè)候選碼 SNO CNO 和 SNAME CNO 都是完全函數(shù)依賴 并且不存在對(duì)兩個(gè)候選碼的傳遞函數(shù)依賴 因此SC 3NF 但是當(dāng)學(xué)生如果退選了課程 元組被刪除也失去學(xué)生學(xué)號(hào)與姓名的對(duì)應(yīng)關(guān)系 因此仍然存在刪除異常的問題 并且由于學(xué)生選課很多 姓名也將重復(fù)存儲(chǔ) 造成數(shù)據(jù)冗余 因此3NF雖然已經(jīng)是比較好的模型 但仍然存在改進(jìn)的余地 6 2 7BC范式 BCNF 定義關(guān)系模式R 1NF 對(duì)任何非平凡的函數(shù)依賴X Y X均包含碼 則R BCNF 若R BCNF每一個(gè)決定屬性集 因素 都包含 候選 碼R中的所有屬性 主 非主屬性 都完全函數(shù)依賴于碼R中不存在任何屬性傳遞依賴于或部分依賴于任何候選碼 所以必定有R 3NF 證明 若R 3NF則R不一定 BCNF 由BCNF的定義可以看到 每個(gè)BCNF的關(guān)系模式都具有如下3個(gè)性質(zhì) 所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼 所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選碼 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性 例 在關(guān)系模式STJ S T J 中 S表示學(xué)生 T表示教師 J表示課程 每一教師只教一門課 每門課由若干教師教 某一學(xué)生選定某門課 就確定了一個(gè)固定的教師 某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱 S J T S T J T J STJ 3NF S J 和 S T 都可以作為候選碼S T J都是主屬性STJ BCNFT J T是決定屬性集 T不是候選碼 解決方法 將STJ分解為二個(gè)關(guān)系模式 ST S T BCNF TJ T J BCNF 沒有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴 3NF與BCNF的關(guān)系 若關(guān)系模式R BCNF 必定有R 3NF 若R 3NF 且R只有一個(gè)候選碼 則R必屬于BCNF 3NF和BCNF是以函數(shù)依賴為基礎(chǔ)的關(guān)系模式規(guī)范化程度的測(cè)度 如果一個(gè)關(guān)系數(shù)據(jù)庫(kù)中的所有關(guān)系模式都屬于3NF 則已在很大程度上消除了插入異常和刪除異常 但由于可能存在主屬性對(duì)候選碼的部分依賴和傳遞依賴 因此關(guān)系模式的分離仍不夠徹底 如果一個(gè)關(guān)系數(shù)據(jù)庫(kù)中的所有關(guān)系模式都屬于BCNF 那么在函數(shù)依賴范疇內(nèi) 它已實(shí)現(xiàn)了模式的徹底分解 達(dá)到了最高的規(guī)范化程度 消除了插入異常和刪除異常 BCNF是對(duì)3NF的改進(jìn) 但是在具體實(shí)現(xiàn)時(shí)有時(shí)是有問題的 例如下面的模型 SJT U F 其中 U STJ F SJ T ST J T J 碼是 ST和SJ 沒有非主屬性 所以SJT 3NF 但是非平凡的函數(shù)依賴T J中T不包含碼 因此SJT不屬于BCNF 當(dāng)用分解的方法提高規(guī)范化程度時(shí) 將破壞原來模型的函數(shù)依賴關(guān)系 這對(duì)于系統(tǒng)設(shè)計(jì)來說是有問題的 這個(gè)問題涉及模式分解的一系列理論問題 在信息系統(tǒng)的設(shè)計(jì)中 普遍采用的是 基于3NF的系統(tǒng)設(shè)計(jì) 方法 就是由于3NF是無條件何以達(dá)到的 并且基本解決了 異常 的問題 因此這種方法目前在信息系統(tǒng)的設(shè)計(jì)中仍然被廣泛地應(yīng)用 如果僅考慮函數(shù)依賴這一種數(shù)據(jù)依賴 屬于BCNF的關(guān)系模式已經(jīng)很完美了 但如果考慮其他數(shù)據(jù)依賴 例如 多值依賴 屬于BCNF的關(guān)系模式仍存在問題 不能算作是一個(gè)完美的關(guān)系模式 6 2 8多值依賴與第四范式 4NF 實(shí)例 設(shè)學(xué)校中某一門課程由多個(gè)教師講授 他們使用相同的一套參考書 可以用一個(gè)關(guān)系模式Teach C T B 表示課程C 教師T和參考書B之間的關(guān)系 該關(guān)系可用二維表表示 用二維表表示Teaching Teaching BCNF Teach具有唯一候選碼 C T B 即全碼Teaching模式中存在的問題 1 數(shù)據(jù)冗余度大 有多少名任課教師 參考書就要存儲(chǔ)多少次 2 插入操作復(fù)雜 當(dāng)某一課程增加一名任課教師時(shí) 該課程有多少本參照書 就必須插入多少個(gè)元組 如物理課增加一名教師劉關(guān) 需插入兩個(gè)元組 物理 劉關(guān) 普通物理學(xué) 物理 劉關(guān) 光學(xué)原理 3 刪除操作復(fù)雜 某一門課要去掉一本參考書 該課程有多少名教師 就必須刪除多少個(gè)元組 4 修改操作復(fù)雜 某一門課要修改一本參考書 該課程有多少名教師 就必須修改多少個(gè)元組產(chǎn)生原因存在多值依賴 一 多值依賴 定義6 9設(shè)R U 是一個(gè)屬性集U上的一個(gè)關(guān)系模式 X Y和Z是U的子集 并且Z U X Y 多值依賴X Y成立當(dāng)且僅當(dāng)對(duì)R的任一關(guān)系r r在給定的一對(duì) X Z 上對(duì)應(yīng)一組Y的值 這組值僅僅決定于X值而與Z值無關(guān) 例Teaching C T B 對(duì)于C的每一個(gè)值 T有一組值與之對(duì)應(yīng) 而不論B取何值 在R U 的任一關(guān)系r中 如果存在元組t s使得t X s X 那么就必然存在元組w v r w v可以與s t相同 使得w X v X t X 而w Y t Y w Z s Z v Y s Y v Z t Z 即交換s t元組的Y值所得的兩個(gè)新元組必在r中 則Y多值依賴于X 記為X Y 這里 X Y是U的子集 Z U X Y txy1z2sxy2z1wxy1z1vxy2z2 平凡多值依賴和非平凡的多值依賴若X Y 而Z 則稱X Y為平凡的多值依賴否則稱X Y為非平凡的多值依賴 1 多值依賴具有對(duì)稱性若X Y 則X Z 其中Z U X Y多值依賴的對(duì)稱性可以用完全二分圖直觀地表示出來 多值依賴的性質(zhì) 2 多值依賴具有傳遞性若X Y Y Z 則X Z Y 3 函數(shù)依賴是多值依賴的特殊情況 若X Y 則X Y 4 若X Y X Z 則X Y Z 5 若X Y X Z 則X Y Z 6 若X Y X Z 則X Y Z X Z Y 1 有效性多值依賴的有效性與屬性集的范圍有關(guān)若X Y在U上成立 則在W XY W U 上一定成立 反之則不然 即X Y在W W U 上成立 在U上并不一定成立多值依賴的定義中不僅涉及屬性組X和Y 而且涉及U中其余屬性Z 多值依賴與函數(shù)依賴的區(qū)別 只要在R U 的任何一個(gè)關(guān)系r中 元組在X和Y上的值滿足定義6 l 函數(shù)依賴 則函數(shù)依賴X Y在任何屬性集W XY W U 上成立 2 若函數(shù)依賴X Y在R U 上成立 則對(duì)于任何Y Y均有X Y 成立多值依賴X Y若在R U 上成立 不能斷言對(duì)于任何Y Y有X Y 成立 二 第四范式 4NF 定義5 10關(guān)系模式R 1NF 如果對(duì)于R的每個(gè)非平凡多值依賴X Y Y X X都含有候選碼 則R 4NF 4NF不允許有非平凡且非函數(shù)依賴的多值依賴 允許的是函數(shù)依賴 是非平凡多值依賴 如果R 4NF 則R BCNF 例 Teach C T B 4NF 存在非平凡的多值依賴C T 且C不是候選碼 這正是它之所以存在數(shù)據(jù)冗余度大 插入和刪除操作復(fù)雜等弊病的根源 用投影分解法把Teach分解為如下兩個(gè)關(guān)系模式 CT C T 4NFCB C B 4NFC T C B是平凡多值依賴 分解后Teach關(guān)系中的幾個(gè)問題可以得到解決 參考書只需要在CB關(guān)系中存儲(chǔ)一次 當(dāng)某一課程增加一名任課教師時(shí) 只需要在CT關(guān)系中增加一個(gè)元組 某一門課要去掉一本參考書 只需要在CB關(guān)系中刪除一個(gè)相應(yīng)的元組 6 2 9關(guān)系模式規(guī)范化的步驟 關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具 一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng) 它就是規(guī)范化的關(guān)系 但這只是最基本的規(guī)范化 規(guī)范化程度可以有多個(gè)不同的級(jí)別 規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界 可能會(huì)存在插入導(dǎo)演 刪除異常 修改復(fù)雜 數(shù)據(jù)冗余等問題 解決方法就是對(duì)其進(jìn)行規(guī)范化 轉(zhuǎn)換成高級(jí)范式 一個(gè)低一級(jí)范式的關(guān)系模式 通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合 這種過程就叫關(guān)系模式的規(guī)范化 消除不合適的數(shù)據(jù)依賴使各關(guān)系模式達(dá)到某種程度的 分離 采用 一事一地 的模式設(shè)計(jì)原則讓一個(gè)關(guān)系描述一個(gè)概念 一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系 若多于一個(gè)概念就把它 分離 出去所謂規(guī)范化實(shí)質(zhì)上是概念的單一化 規(guī)范化的基本思想 1NF 消除非主屬性對(duì)碼的部分函數(shù)依賴消除決定屬性2NF集非碼的非平 消除非主屬性對(duì)碼的傳遞函數(shù)依賴凡函數(shù)依賴3NF 消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴BCNF 消除非平凡且非函數(shù)依賴的多值依賴4NF 消除不是由候選碼所蘊(yùn)含的連接依賴5NF 關(guān)系模式規(guī)范化的基本步驟 設(shè)計(jì)數(shù)據(jù)庫(kù)模式時(shí)不能說規(guī)范化程度越高的關(guān)系模式就越好在設(shè)計(jì)數(shù)據(jù)庫(kù)模式結(jié)構(gòu)時(shí) 必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析 確定一個(gè)合適的 能夠反映現(xiàn)實(shí)世界的模式上面的規(guī)范化步驟可以在其中任何一步終止 成績(jī)管理 學(xué)號(hào) 姓名 生日 性別 所在城市 長(zhǎng)途區(qū)號(hào) 課程 學(xué)期 學(xué)分 成績(jī) 消除非主屬性對(duì)碼的部分函數(shù)依賴學(xué)生 學(xué)號(hào) 姓名 生日 性別 所在城市 長(zhǎng)途區(qū)號(hào) 課程 課程 學(xué)期 學(xué)分 成績(jī) 學(xué)號(hào) 課程 成績(jī) 消除非主屬性對(duì)碼的傳遞函數(shù)依賴學(xué)生 學(xué)號(hào) 姓名 生日 性別 所在城市 城市 所在城市 長(zhǎng)途區(qū)號(hào) 課程 課程 學(xué)期 學(xué)分 成績(jī) 學(xué)號(hào) 課程 成績(jī) 實(shí)例 已知學(xué)生情況表Student如下所示 Student表符合1NF要求嗎 如不符合 將其規(guī)范化為1NF 將其規(guī)范化為2NF 將其規(guī)范化為3NF Student表不符合1NF要求 因?yàn)樵谕槐碇型愋偷淖侄沃貜?fù)出現(xiàn) 將其規(guī)范化為1NF Student 學(xué)號(hào) 姓名 專業(yè) 班級(jí) 課程編號(hào) 課程名稱 課程成績(jī) 家庭住址 郵政編碼 將其規(guī)范化為2NF Student 學(xué)號(hào) 姓名 專業(yè) 班級(jí) 家庭住址 郵政編碼 Course 課程編號(hào) 課程名稱 Score 學(xué)號(hào) 課程編號(hào) 課程成績(jī) 將其規(guī)范化為3NF Student 學(xué)號(hào) 姓名 專業(yè) 班級(jí) 家庭住址 Course 課程編號(hào) 課程名稱 Address 家庭住址 郵政編碼 Score 學(xué)號(hào) 課程編號(hào) 課程成績(jī) 6 3數(shù)據(jù)依賴的公理系統(tǒng) 6 3 1函數(shù)依賴集合的規(guī)范化函數(shù)依賴集合的邏輯蘊(yùn)涵Armstrong推理規(guī)則屬性集閉包的概念和計(jì)算函數(shù)依賴集等價(jià)最小函數(shù)依賴集6 3 2關(guān)系模型的分析 6 3 1函數(shù)依賴集合的規(guī)范化 邏輯蘊(yùn)涵定義 如果F是關(guān)系模型R的函數(shù)依賴集合 X Y是R的屬性集 如果從F中可以推出函數(shù)依賴關(guān)系X Y 就稱X Y被F邏輯蘊(yùn)涵 如果X Y被F邏輯蘊(yùn)涵 可以記作X Y F 一 函數(shù)依賴集合的邏輯蘊(yùn)涵 F的閉包 定義6 12 在關(guān)系模式R中為F所邏輯蘊(yùn)涵的函數(shù)依賴的全體叫作F的閉包 記為F Armstrong推理規(guī)則一套推理規(guī)則 是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴Armstrong推理規(guī)則也稱為Armstrong公理系統(tǒng) 二 Armstrong推理規(guī)則 關(guān)系R中 X Y Z是U的子集 推理規(guī)則是 A1 自反律若Y X U 則X Y為F所蘊(yùn)含 A2 增廣律若X Y為F所蘊(yùn)含 且Z U 則XZ YZ為F所蘊(yùn)含 A3 傳遞律若X Y及Y Z為F所蘊(yùn)含 則X Z為F所蘊(yùn)含 定理6 l Armstrong推理規(guī)則是正確的 l 自反律 若Y X U 則X Y為F所蘊(yùn)含 證 設(shè)Y X U對(duì)R的任一關(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)含 證 設(shè)X Y為F所蘊(yùn)含 且Z U 設(shè)R的任一關(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 s YZ 所以XZ YZ為F所蘊(yùn)含 增廣律得證 3 傳遞律 若X Y及Y Z為F所蘊(yùn)含 則X Z為F所蘊(yùn)含 證 設(shè)X Y及Y Z為F所蘊(yùn)含 對(duì)R的任一關(guān)系r中的任意兩個(gè)元組t s 若t X s X 由于X Y 有t Y s Y 再由Y Z 有t Z s Z 所以X Z為F所蘊(yùn)含 傳遞律得證 導(dǎo)出規(guī)則 1 根據(jù)A1 A2 A3這三條推理規(guī)則可以得到下面三條推理規(guī)則 合并規(guī)則 由X Y X Z 有X YZ A2 A3 偽傳遞規(guī)則 由X Y WY Z 有XW Z A2 A3 分解規(guī)則 由X Y及Z Y 有X Z A1 A3 2 根據(jù)合并規(guī)則和分解規(guī)則 可得引理6 1引理6 lX A1A2 Ak成立的充分必要條件是X Ai成立 i l 2 k 可以證明 Armstrong公理系統(tǒng)是有效的 完備的 有效性指的是 由F出發(fā)根據(jù)Armstrong推理規(guī)則推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F 中 完備性指的是 F 中的每一個(gè)函數(shù)依賴必定可以由F出發(fā)根據(jù)Armstrong推理規(guī)則推導(dǎo)出來 就是說 從F出發(fā)應(yīng)用Armstrong推理規(guī)則得出的函數(shù)依賴集合的全體就是F 問題 如何求出F 中的一切函數(shù)依賴 例如 F X A1 X An 至少可以推導(dǎo)出多少個(gè)函數(shù)依賴 這個(gè)問題屬于計(jì)算復(fù)雜性問題 NP完全問題 但是我們可以找到判斷X Z F 是否成立的有效辦法 至少可以推導(dǎo)出2n個(gè)函數(shù)依賴 世界七大數(shù)學(xué)難題 NP完全問題 霍奇猜想 龐加萊猜想 黎曼假設(shè) 楊 米爾斯理論 納衛(wèi)爾 斯托可方程 BSD猜想 定義6 13在關(guān)系模式R中 X Y是U的子集 屬性集X關(guān)于函數(shù)依賴集F的閉包定義為 XF Y Y U 且X Y F 關(guān)于屬性閉包的引理 即判斷規(guī)則 引理6 2 設(shè)F為屬性集U上的一組函數(shù)依賴 X Y U X Y F 的充分必要條件是Y XF 用途 將判定X Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題 就轉(zhuǎn)化為求出XF 判定Y是否為XF 的子集的問題 這個(gè)規(guī)則提供了判斷函數(shù)依賴是否成立的有效方法 三 屬性閉包的概念和計(jì)算 求屬性集閉包的算法算法6 l求屬性集X X U 關(guān)于U上的函數(shù)依賴集F的閉包XF 輸入 X F輸出 XF 步驟 1 令X 0 X i 0 2 計(jì)算 B A 一切WX i 且W A F 3 令X i 1 X i B 4 判斷X i 1 X i 是否成立 5 若成立或X i U 則XF X i 算法終止 6 若不成立 則i i l 返回第 2 步 例 已知關(guān)系模式R 其中U ABCDE F AB C B D C E EC B AC B 求 AB F 解 設(shè)X 0 AB 1 計(jì)算X 1 逐一的掃描F集合中各個(gè)函數(shù)依賴 找左部為A B或AB的函數(shù)依賴 AB C B D X 1 AB CD ABCD 2 因?yàn)閄 0 X 1 所以再找出左部為ABCD子集的那些函數(shù)依賴 得到AB C B D C E AC B X 2 X 1 BCDE ABCDE 3 因?yàn)閄 2 U 算法終止 所以 AB F ABCDE 例 關(guān)系R中 U ABCDEF AB C B D C E E C A C 求 BC F 解 設(shè)X 0 BC 計(jì)算F中 B C決定的D E 加入X 0 中 X 1 BCDE 不等于X 0 還需計(jì)算 再計(jì)算F中 B C D E決定的屬性 加入X 1 中 X 2 BCDE 等于X 1 算法結(jié)束 BC F BCDE 例 關(guān)系R中 U ABCD F A B BC D AF ABCF C AC F ABCD AC B AC D B 定理6 2Armstrong公理系統(tǒng)是有效的 完備的有效性 由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F 中 Armstrong正確 完備性 F 中的每一個(gè)函數(shù)依賴 必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來 Armstrong公理夠用 完全 所有不能用Armstrong公理推導(dǎo)出來f都不為真 f F 有效性與完備性的證明 1 有效性 可由定理6 1得證2 完備性只需證明逆否命題 若函數(shù)依賴X Y不能由F從Armstrong公理導(dǎo)出 那么它必然不為F所蘊(yùn)含 分三步證明 1 引理 若V W成立 且V XF 則W XF 證因?yàn)閂 XF 所以有X V成立 因?yàn)閄 V V W 于是X W成立所以W XF 2 若f不能用Armstrong公理推導(dǎo)出來 f F 若存在r F 中的全部函數(shù)依賴在r上成立 而不能用Armstrong公理推導(dǎo)出來的f 在r上不成立 構(gòu)造一張二維表r 它由下列兩個(gè)元組構(gòu)成 可證明r必是R U F 的一個(gè)關(guān)系 即F 中的全部函數(shù)依賴在r上成立 XF U XF 11 100 011 111 1若r不是R的關(guān)系 則必由于F中有函數(shù)依賴V W在r上不成立所致 由r的構(gòu)成可知 V必定是XF 的子集 而W不是XF 的子集 可是由第 1 步 W XF 矛盾 所以r必是R的一個(gè)關(guān)系 3 若f不能用Armstrong公理推導(dǎo)出來 f F 而不能用Armstrong公理推導(dǎo)出來的f在r上不成立 若X Y不能由F從Armstrong公理導(dǎo)出 則Y不是XF 的子集 引理5 2 因此必有Y的子集Y 滿足Y U XF 則X Y在r中不成立 即X Y必不為R蘊(yùn)含 因?yàn)镕 中的全部函數(shù)依賴在r上成立 函數(shù)依賴集的等價(jià)對(duì)函數(shù)依賴集合進(jìn)行變換的目的是尋找最合理的函數(shù)依賴集合 但每次變換后 必須與原來的集合具有相同的含義 這就是函數(shù)依賴集合的等價(jià) 或互相覆蓋 定義6 14 兩個(gè)函數(shù)依賴集合F G 如果G F 就稱函數(shù)依賴集合F與G等價(jià) 或互相覆蓋 引理6 3 判定兩個(gè)函數(shù)依賴集等價(jià)的算法 F G 的充分必要條件是 F G 且G F 四 函數(shù)依賴集等價(jià) 證明 F G 的充分必要條件是F G 和G F 要判定F G 只須逐一對(duì)F中的函數(shù)依賴X Y 考察Y是否屬于XG 就行了 證 必要性顯然 只證充分性 1 若F G 則XF XG 2 任取X Y F 則有Y XF XG 所以X Y G G 即F G 3 同理可證G F 所以F G 定義6 15如果函數(shù)依賴集F滿足下列條件 則稱F為一個(gè)極小函數(shù)依賴集 亦稱為最小依賴集或最小覆蓋 記為Fmin 或Fm 1 F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性 即把F中每個(gè)函數(shù)依賴的右端分成單屬性 2 F中不存在這樣的函數(shù)依賴X A 使得F與F X A 等價(jià) 即F中無多余的函數(shù)依賴 3 F中不存在這樣的函數(shù)依賴X A X有真子集Z使得F X A Z A 與F等價(jià) 即F中每個(gè)函數(shù)依賴的左端無多余的屬性 五 最小函數(shù)依賴集 例 對(duì)于6 l節(jié)中的關(guān)系模式S 其中 U SNO SDEPT MNAME CNAME GRADE F SNO SDEPT SDEPT MNAME SNO CNAME GRADE 設(shè)F SNO SDEPT SNO MNAME SDEPT MNAME SNO CNAME GRADE SNO SDEPT SDEPT F是最小覆蓋 而F 不是 因?yàn)?F SNO MNAME 與F 等價(jià)F SNO SDEPT SDEPT 也與F 等價(jià)F SNO SDEPT SDEPT SNO SDEPT 也與F 等價(jià) Fmin算法 分三步進(jìn)行 利用分解規(guī)則 把右端多屬性 n個(gè) 的函數(shù)依賴變成左端不變的n個(gè)函數(shù)依賴 即把右端分解成單屬性 對(duì)于F中每個(gè)X A 設(shè)G F X A 如果A XG 則將X A從F中刪除 否則保留 對(duì)于F中每個(gè)包含多屬性X有X A 選擇X的每個(gè)子集Z 如果A ZF 則用Z A代替X A 例 F A BC B AC C A 求Fmin 解 先分解右端 F A B A C B A B C C A 判斷每個(gè)函數(shù)依賴 設(shè)G F A B AG AC 不包含B 故A B保留 G F A C AG ABC 包含C 故A C刪除 令F G F A B B A B C C A G F B A BG BAC 包含A 故B A刪除 令F G F A B B C C A G F B C BG B 不包含C 故B C保留 G F C A CG C 不包含A 故C A保留 F中函數(shù)依賴的左端都是單屬性 算法結(jié)束 Fmin A B B C C A 注意 Fmin不是惟一的 本例如果改變考察次序 從右向左 將得到 Fmin A B A C B A C A 例 F BE G BD G CDE AB CD A CE G BC A B D C D 求Fmin 解 先分解右端 F BE G BD G CDE A CDE B CD A CE G BC A B D C D 判斷每個(gè)函數(shù)依賴 過程略 F BD G CDE B CD A B D C D BF BDG 包含G 用B G代替BD G CE F CEBDGA 包含B 用CE B代替CDE B CF CDA 包含A 用C A代替CD A Fmin B G CE B C A B D C D 定理6 3每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm 此Fm稱為F的最小依賴集 1 逐一檢查F中各函數(shù)依賴FDi X Y 若Y A1A2 Ak k 2 則用 X Aj j 1 2 k 來取代X Y 引理6 1保證了F變換前后的等價(jià)性 2 逐一檢查F中各函數(shù)依賴FDi X A 令G F X A 若A XG 則從F中去掉此函數(shù)依賴 由于F與G F X A 等價(jià)的充要條件是A XG 因此F變換前后是等價(jià)的 證 構(gòu)造性證明 依據(jù)定義分三步對(duì)F進(jìn)行 極小化處理 找出F的一個(gè)最小依賴集 3 逐一取出F中各函數(shù)依賴FDi X A 設(shè)X B1B2 Bm 逐一考查Bi i l 2 m 若A X Bi F 則以X Bi取代X 由于F與F X A Z A 等價(jià)的充要條件是A ZF 其中Z X Bi因此F變換前后是等價(jià)的 由定義 最后剩下的F就一定是極小依賴集 因?yàn)閷?duì)F的每一次 改造 都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià) 因此剩下的F與原來的F等價(jià) 證畢 6 3 2關(guān)系模型的分析 確定關(guān)系模式的候選碼是進(jìn)行規(guī)范化分析的出發(fā)點(diǎn) 有下述準(zhǔn)則可以使用 關(guān)系R U F 中 F是最小函數(shù)依賴集 準(zhǔn)則1 如果屬性A只在F中各個(gè)函數(shù)依賴的左端出現(xiàn) 則A必是碼中的屬性 準(zhǔn)則2 如果屬性A不在F的各個(gè)函數(shù)依賴中出現(xiàn) 則A必是碼中的屬性 準(zhǔn)則3 如果屬性A只在F中各個(gè)函數(shù)依賴的右端出現(xiàn) 則A必不是碼中的屬性 一 候選碼的確定 根據(jù)以上準(zhǔn)則 確定候選碼的步驟是 先根據(jù)準(zhǔn)則2 把不在F的各個(gè)函數(shù)依賴中出現(xiàn)屬性去掉 因這些屬性一般對(duì)模型沒有什么意義 根據(jù)準(zhǔn)則1 確定碼中必須有的屬性集 設(shè)為M 根據(jù)準(zhǔn)則3 去掉碼中肯定沒有的屬性集 確定余下的屬性集 設(shè)為W 從屬性集M開始 令K M 如果KF U K就是候選碼 否則從W選擇屬性加入到K中 直至KF U K就是候選碼 注意可能有多個(gè)候選碼 例如 F BE G BD G CDE AB CD A CE G BC A B D C D Fmin B G CE B C A B D C D 只在左端出現(xiàn)的屬性 CE M CE 只在右端出現(xiàn)的屬性 ADG 余下的屬性 B W B R的候選碼只可能是 CE CEB 經(jīng)計(jì)算 CE F ABCDEG 因此R的碼是CE 根據(jù)規(guī)范化定義判斷所處理的模型是第幾范式 例如 F BE G BD G CDE AB CD A CE G BC A B D C D 二 對(duì)關(guān)系模式規(guī)范化 Fmin B G CE B C A B D C D 存在對(duì)碼CE的部分函數(shù)依賴C D 所以R 1NF 利用模式分解的規(guī)則 對(duì)關(guān)系模式進(jìn)行分解 達(dá)到規(guī)范化的要求 6 4模式的分解 一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng) 它就是規(guī)范化的關(guān)系 但這只是最基本的規(guī)范化 規(guī)范化程度可以有6個(gè)不同的級(jí)別 即6個(gè)范式 一個(gè)低一級(jí)范式的關(guān)系模式 通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合 這種過程就叫關(guān)系模式的規(guī)范化 關(guān)系模式規(guī)范化時(shí)一般應(yīng)遵循以下原則 1 關(guān)系模式進(jìn)行無損連接分解 關(guān)系模式分解過程中數(shù)據(jù)不能丟失或增加 必須把全局關(guān)系模式中的所有數(shù)據(jù)無損地分解到各個(gè)子關(guān)系模式中 以保證數(shù)據(jù)的完整性 2 保持原來模型的函數(shù)依賴關(guān)系 因?yàn)檫@些函數(shù)依賴關(guān)系是數(shù)據(jù)模型反映的客觀事物的固有屬性 一般是不能舍棄的 3 合理選擇規(guī)范化程度 考慮到存取效率 低級(jí)模式造成的冗余度很大 既浪費(fèi)了存儲(chǔ)空間 又影響了數(shù)據(jù)的一致行 因此希望一個(gè)子模式的屬性越少越好 即取高級(jí)范式 若考慮到查詢效率 低級(jí)范式又比高級(jí)范式好 此時(shí)連接運(yùn)算的代價(jià)較小 這是一對(duì)矛盾 所以應(yīng)根據(jù)情況 合理選擇規(guī)范化程度 模式分解可以提高關(guān)系模式的規(guī)范化程度 但是必須考慮如下問題 避免信息丟失 簡(jiǎn)單地說 就是模式R分解為R1 R2 Rn后 將R1 R2 Rn自然連接還應(yīng)該等于模式R 這就是 無損失連接 準(zhǔn)則 避免數(shù)據(jù)關(guān)系丟失 模式R分解為R1 R2 Rn后 函數(shù)依賴集合F也被對(duì)應(yīng)分解為F1 F2 Fn 應(yīng)滿足F與各Fi i 1 2 n 的并集等價(jià) 即滿足這就是 保持函數(shù)依賴 準(zhǔn)則 一 對(duì)模式分解的兩個(gè)基本要求 例 R U F 中 U ABC F A B B C 設(shè)模型中各屬性的值如下 有三種可能的分解方法 1 方法一 R1 U1 AB F1 A B R2 U2 BC F2 B C 函數(shù)依賴集 F1 F2 A B B C F 保持函數(shù)依賴 自然連接后 分解后情況 符合無損失連接規(guī)則 2 方法二 R1 U1 AB F1 A B R2 U2 AC F2 A C F1 F2 A B A C B C F1 F2 不滿足保持函數(shù)依賴 自然連接后 分解后情況 符合無損失連接規(guī)則 3 方法三 R1 U1 AC F1 A C R2 U2 BC F2 B C F1 F2 A C B C 而 A B F1 F2 不滿足保持函數(shù)依賴 自然連接后 分解后情況 不符合無損失連接規(guī)則 從上面例題可以發(fā)現(xiàn) 分解具有無損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn) 具有無損連接的分解不一定能夠保持函數(shù)依賴 同樣 保持函數(shù)依賴的分解也不一定具有無損連接 例如 上面的第一種分解方法既具有無損連接性 又保持了函數(shù)依賴 第二種分解方法保具有無損連接性 但未保持函數(shù)依賴 第三種分解方法既不具有無損連接性 也未保持函數(shù)依賴 它不是原關(guān)系模式的一個(gè)等價(jià)分解 把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià) 分解方法才有意義 關(guān)系模式分解的三個(gè)定義 1 分解具有 無損連接性 2 分解要 保持函數(shù)依賴 3 分解既要 保持函數(shù)依賴 又要具有 無損連接性 二 模式分解的原則 規(guī)范化理論提供了一套完整的模式分解算法 按照這套算法可以做到 若要求分解具有無損連接性 那么模式分解一定能夠達(dá)到4NF 若要求分解保持函數(shù)依賴 那么模式分解一定能夠達(dá)到3NF 但不定能夠達(dá)到BCNF 若要求分解既具有無損連接性 又保持函數(shù)依賴 則模式分解一定能夠達(dá)到3NF 但不一定能夠達(dá)到BCNF 三 模式分解的方法 達(dá)到3NF保持函數(shù)依賴分解的方法 設(shè)關(guān)系模式R U F 將F化為最小函數(shù)依賴集 令F Fmin 把在F中不出現(xiàn)的屬性從U中去掉 屬性集合仍然為U 對(duì)照F中的函數(shù)依賴集 將所有函數(shù)依賴左端相同的劃為一組 相應(yīng)的右端以及函數(shù)依賴均歸入該組 這些分組就是分解后的模式組成 這種分解方法得到的就是達(dá)到3NF且保持函數(shù)依賴的分解 例如 F B G CE B C A B D C D 碼是CE 分解成三個(gè)模式 R1 U1 BDG F1 B G B D R2 U2 ACD F2 C A C D R3 U3 BCE F3 CE B 分解后 R1 R2 R3均達(dá)到3NF 且分解符合保持函數(shù)依賴的規(guī)則 達(dá)到3NF既符合無損失連接并保持函數(shù)依賴分解的方法 設(shè)關(guān)系模式R U F 先按上述方法 將R分解為R1 R1 Rn 選取R的主碼 將主碼與函數(shù)依賴相關(guān)的屬性組成一個(gè)關(guān)系Rn 1 如果Rn 1就是R1 R2 中一個(gè) 就將它們合并 否則加入到分解系列中 這個(gè)分解系列就是既符合無損失連接又保持函數(shù)依賴的分解系列 例如 前面的例題 F B G CE B C A B D C D 碼是CE 分解成三個(gè)模式 R1 U1 BDG F1 B G B D R2 U2 ACD F2 C A C D R3 U3 BCE F3 CE B R3就是包含碼CE的模式 所以分解符合無損失連接規(guī)則 達(dá)到BCNF無損失連接分解的方法 設(shè)關(guān)系模式R U F 置初值 R 如果 中所有關(guān)系模式均已達(dá)到BCNF則轉(zhuǎn) 否則在 中選非BCNF的模式S 在S中必存在X A X不包含S的碼 也不包含A 這時(shí)S必存在A之外且不包含在X中的屬性集Y 用S1和S2代替S 其中S1 XA S2 XY 用 S1 S2 代替 中的S 轉(zhuǎn) 算法結(jié)束 就是分解結(jié)果 例如 R U F U ABCDEF AB C B D D E 碼是AB 分解過程如下 先分出DE R1 ABCD R2 DE 再?gòu)腞1中分出BD R1 ABC R2 DE R3 BD R1 R2 R3都屬于BCNF 分解完成 達(dá)到4NF無損失連接分解的方法 設(shè)關(guān)系模式R U F 置初值 R 如果 中所有關(guān)系模式均已達(dá)到4NF則轉(zhuǎn) 否則在 中選非4NF的模式S 在S中必存在X Y X不包含S的碼 Y X XY S 令Z Y X 設(shè)S1 XZ S2 S Z 用 S1 S2 代替 中的S 轉(zhuǎn) 算法結(jié)束 就是分解結(jié)果 例如 R U F U ABCEFG F A BCG B AC C G A EF 置初值 R ABCEFG 從A BCG分解 R1 ABCG R2 AEF 從B AC分解 R1 ABC R2 AEF R3 BG 或從C G分解 R1 ABC R2 AEF R3 CG 在步驟 中的兩種分解都使每個(gè)模式達(dá)到了4NF 但是從B AC分解后丟失了函數(shù)依賴C G 而從C G分解可以保持全部函數(shù)依賴 思考 SL Sno Sdept Sloc F Sno Sdept Sdept Sloc Sno Sloc SL 2NF存在插入異常 刪除異常 冗余度大和修改復(fù)雜等問題 存在哪些分解方法 1 SL分解為下面三個(gè)關(guān)系模式 SN Sno SD Sdept SO Sloc 分解后的數(shù)據(jù)庫(kù)丟失了許多信息 例如無法查詢95001學(xué)生所在系或所在宿舍 如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系 那么這種分解就沒有丟失信息 2 SL分解為下面二個(gè)關(guān)系模式 NL Sno Sloc DL Sdept Sloc 分解后的關(guān)系為 3 將SL分解為下面二個(gè)關(guān)系模式 ND Sno Sdept NL Sno Sloc 分解后的關(guān)系為 與SL關(guān)系一樣 因此沒有丟失信息 第三種分解方法具有無損連接性 但這種分解方法沒有保持原關(guān)系中的函數(shù)依賴Sdept Sloc 4 將SL分解為下面二個(gè)關(guān)系模式 ND Sno Sdept DL Sdept Sloc 這種分解方法就保持了函數(shù)依賴 如果一個(gè)分解具有無損連接性 則它能夠保證不丟失信息 如果一個(gè)分解保持了函數(shù)依賴 則它可以減輕或解決各種異常情況 分解具有無損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn) 具有無損連接性的分解不一定能夠保持函數(shù)依賴 同樣 保持函數(shù)依賴的分解也不一定具有無損連接性 連接依賴與5NF 例如 設(shè)關(guān)系模式SPJ SNO PNO JNO 它顯然達(dá)到了4NF SPJ分別在SP PJ SJ上的投影 一 連接依賴 SP與PJ自然連接 PJ與SJ自然連接 SP與SJ自然連接 關(guān)系SPJ分解為其中兩個(gè)屬性的關(guān)系后 無論哪兩個(gè)自