數(shù)據(jù)庫(kù)系統(tǒng)實(shí)用教程-課件

1、第8章 關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論1版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系第8章 關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論1版權(quán)所有(C)-南京大學(xué)計(jì)算在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的建立過(guò)程中，如何構(gòu)造一個(gè)合適的關(guān)系數(shù)據(jù)模式？關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)理論關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論2版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的建立過(guò)程中，如何構(gòu)造一個(gè)合適的關(guān)系數(shù)據(jù)模式本章的內(nèi)容8.1 概述8.2 規(guī)范化理論8.2.1 函數(shù)依賴8.2.2 與函數(shù)依賴有關(guān)的范式8.2.3 多值依賴與第四范式8.3 規(guī)范化所引起的一些問(wèn)題函數(shù)依賴?yán)碚摰难芯磕Ｊ椒纸獾难芯浚簾o(wú)損聯(lián)接性，依賴保持性3版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系本章的

2、內(nèi)容3版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.1 概述1 模式設(shè)計(jì)同一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)可以有多種不同的模式設(shè)計(jì)方案。如：假設(shè)一個(gè)學(xué)生數(shù)據(jù)庫(kù)中有8個(gè)屬性：S#, Sn, Sd, Sa, C#, G, CN, P#, 可以采用的模式設(shè)計(jì)方案有多個(gè)。如表8-1所示：方案1：一個(gè)關(guān)系SCG(S#, Sn, Sd, Sa, C#, G, CN, P#)方案2：三個(gè)關(guān)系S(S#, Sn, Sd, Sa)C(C#, CN, P#)SC(S#, C#, G)4版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.1 概述1 模式設(shè)計(jì)如：假設(shè)一個(gè)學(xué)生數(shù)據(jù)庫(kù)中有8個(gè)屬8.1 概述2 不同模式設(shè)計(jì)方案的比較不同的模式設(shè)計(jì)

3、方案對(duì)數(shù)據(jù)庫(kù)的影響是否相同？例：根據(jù)方案1所建立的數(shù)據(jù)庫(kù)如表8-2所示根據(jù)方案2所建立的數(shù)據(jù)庫(kù)如表8-3所示我們從下面三個(gè)方面來(lái)比較這兩個(gè)數(shù)據(jù)庫(kù)：數(shù)據(jù)冗余度元組插入操作元組刪除操作5版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.1 概述2 不同模式設(shè)計(jì)方案的比較5版權(quán)所有(C)-8.1 概述表8-2 根據(jù)方案1所建立的數(shù)據(jù)庫(kù)(關(guān)系SCG)6版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.1 概述表8-2 根據(jù)方案1所建立的數(shù)據(jù)庫(kù)(關(guān)系SC8.1 概述表8-3 根據(jù)方案2所建立的數(shù)據(jù)庫(kù)(關(guān)系S, C和SC)7版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.1 概述表8-3 根據(jù)方案2所建立的數(shù)據(jù)庫(kù)(

4、關(guān)系S,8.1 概述經(jīng)過(guò)比較發(fā)現(xiàn)，表8-2具有如下缺點(diǎn)：數(shù)據(jù)冗余度大插入異常如果需要新開(kāi)設(shè)一門(mén)尚未有學(xué)生選修的課程(104, DB, 103)，則無(wú)法構(gòu)造出一個(gè)由S#, Sn, Sd, Sa等屬性值所組成的新元組，在表8-2中就無(wú)法執(zhí)行元組的插入操作。在表8-3中，我們可以直接將元組(104, DB, 103)插入到課程關(guān)系C中。8版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.1 概述經(jīng)過(guò)比較發(fā)現(xiàn)，表8-2具有如下缺點(diǎn)：插入異常88.1 概述刪除異常在表8-2中，107號(hào)課程僅有0003號(hào)學(xué)生選修，如果該學(xué)生因故退學(xué)，就必須將與該學(xué)生有關(guān)的元組從表8-2中刪除掉，這樣就必然也將107號(hào)這門(mén)課程

5、也從數(shù)據(jù)庫(kù)中刪除掉了。在表8-3中，我們可以僅在學(xué)生關(guān)系S和選課關(guān)系SC中刪除0003號(hào)學(xué)生的元組及其選課信息，但不會(huì)誤刪除掉107號(hào)課程，其所對(duì)應(yīng)的元組仍然保留在課程關(guān)系C中。因此，不同的模式設(shè)計(jì)方案有好壞的區(qū)分。好的設(shè)計(jì)方案應(yīng)該是：既具有合理的數(shù)據(jù)冗余度，又沒(méi)有插入和刪除等異?，F(xiàn)象的出現(xiàn)。9版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.1 概述刪除異常因此，不同的模式設(shè)計(jì)方案有好壞的區(qū)分。8.1 概述3 在不同的設(shè)計(jì)結(jié)果之間產(chǎn)生區(qū)別的原因數(shù)據(jù)庫(kù)的各屬性之間是互相關(guān)聯(lián)的，它們互相依賴、互相制約，構(gòu)成一個(gè)結(jié)構(gòu)嚴(yán)密的整體。要設(shè)計(jì)出一個(gè)好的關(guān)系模式，必須從數(shù)據(jù)庫(kù)中所有屬性的語(yǔ)義上進(jìn)行分析，從語(yǔ)義上

6、入手分清每個(gè)屬性的語(yǔ)義含義及其相互之間的依存關(guān)系。進(jìn)而將那些相互依賴密切的屬性組合在一起構(gòu)成一個(gè)關(guān)系模式，避免對(duì)屬性的松散組合所引起的排它性，從而可以降低數(shù)據(jù)冗余度，避免上述異?，F(xiàn)象的產(chǎn)生。10版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.1 概述3 在不同的設(shè)計(jì)結(jié)果之間產(chǎn)生區(qū)別的原因10版8.1 概述4 關(guān)系的規(guī)范化在一個(gè)關(guān)系中，屬性與屬性之間的內(nèi)在語(yǔ)義聯(lián)系有兩種：函數(shù)依賴多值依賴關(guān)系的規(guī)范化在每個(gè)關(guān)系中，屬性與屬性之間一定要滿足某種內(nèi)在的語(yǔ)義聯(lián)系，這被稱為關(guān)系的規(guī)范化。根據(jù)對(duì)屬性間所存在的內(nèi)在語(yǔ)義聯(lián)系要求的不同，又可以將關(guān)系的規(guī)范化分為若干個(gè)級(jí)別，這被稱為范式。上述相關(guān)的理論被稱為關(guān)系規(guī)范

7、化理論。11版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.1 概述4 關(guān)系的規(guī)范化11版權(quán)所有(C)-南京大學(xué)8.2 規(guī)范化理論數(shù)據(jù)依賴?yán)碚摵瘮?shù)依賴（FD Functional Dependency）1970年，E. F. Codd1972 1974年，Codd, Casey, Bernstein, Armstrong完全/部分FD，平凡/非平凡FD，直接/傳遞FD鍵（key）1974年，Armstrong公理系統(tǒng)FD的邏輯蘊(yùn)涵FD的形式化推理規(guī)則集多值依賴（MVD Multi-Valued Dependency）1976 1978年，Zaniolo, Fagin, Delobel12版權(quán)所有

8、(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2 規(guī)范化理論數(shù)據(jù)依賴?yán)碚?2版權(quán)所有(C)-南京大學(xué)8.2 規(guī)范化理論規(guī)范化理論規(guī)范化的途徑豎向規(guī)范化采用投影和聯(lián)接運(yùn)算將一個(gè)關(guān)系模式的屬性集分解構(gòu)成若干個(gè)關(guān)系模式有關(guān)理論構(gòu)成了關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論模式分解理論：無(wú)損聯(lián)接性，依賴保持性水平規(guī)范化采用選擇和并運(yùn)算將一個(gè)關(guān)系的元組集合分解成若干個(gè)子集，從而構(gòu)成若干個(gè)與原來(lái)的關(guān)系具有相同關(guān)系模式的子關(guān)系尚未形成一個(gè)成熟的規(guī)范化理論13版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2 規(guī)范化理論規(guī)范化理論13版權(quán)所有(C)-南京大學(xué)計(jì)8.2 規(guī)范化理論8.2.1 函數(shù)依賴函數(shù)依賴完全/部分FD，平凡/非平凡FD

9、，直接/傳遞FDArmstrong公理系統(tǒng)鍵（key）兩個(gè)算法屬性集的閉包的計(jì)算關(guān)鍵字的計(jì)算8.2.2 與函數(shù)依賴有關(guān)的范式范式：1NF，2NF，3NF，BCNF8.2.3 多值依賴與第四范式多值依賴與MVD有關(guān)的推理規(guī)則4NF14版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2 規(guī)范化理論8.2.1 函數(shù)依賴14版權(quán)所有(C)8.2.1 函數(shù)依賴?yán)?：在學(xué)生關(guān)系模式S( S#, Sn, Sd, Sa )中就存在下面的幾組依賴關(guān)系： Sn 的取值依賴于 S# 的取值 Sd 的取值依賴于 S# 的取值 Sa 的取值依賴于 S# 的取值在一個(gè)關(guān)系模式R(U)中，如果一部分屬性Y的取值依賴于另一部分

10、屬性X的取值，則在屬性集X和屬性集Y之間存在著一種數(shù)據(jù)依賴關(guān)系，我們稱之為函數(shù)依賴。15版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴?yán)?：在學(xué)生關(guān)系模式S( S#, Sn8.2.1 函數(shù)依賴定義8.1：函數(shù)依賴設(shè)有關(guān)系模式R(U)，U是關(guān)系模式R的屬性集合，X、Y是U的子集。若對(duì)于任一個(gè)符合關(guān)系模式R(U)的關(guān)系 r 中的任一元組 t 在X中的屬性值確定后，則元組 t 在Y中的屬性值也必確定，則稱Y函數(shù)依賴于X，或者X函數(shù)決定Y，并記為XY。其中：X稱為決定因素Y稱為依賴因素16版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴定義8.1：函數(shù)依賴16版權(quán)所有(C

11、)8.2.1 函數(shù)依賴定義8.1：函數(shù)依賴 (cont.)假設(shè)在關(guān)系模式R(U)上存在函數(shù)依賴關(guān)系：XY r 是依據(jù)關(guān)系模式R(U)建立起來(lái)的任意一個(gè)關(guān)系，那么關(guān)系 r 必滿足：從關(guān)系 r 中任取兩個(gè)元組t1和t2，如果t1在X這組屬性上的取值t1X等于t2在X這組屬性上的取值t2X，即：t1X = t2X則它們?cè)赮這組屬性上的取值也必定相等，即：t1Y = t2Y17版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴定義8.1：函數(shù)依賴 (cont.)18.2.1 函數(shù)依賴函數(shù)依賴是語(yǔ)義范疇上的概念，只有根據(jù)屬性間固有的語(yǔ)義聯(lián)系才能歸納出與客觀事實(shí)相符合的函數(shù)依賴關(guān)系，而不是僅從

12、現(xiàn)有的一個(gè)或若干個(gè)關(guān)系實(shí)例中得出的結(jié)論。特定的關(guān)系實(shí)例雖然不能用于函數(shù)依賴的發(fā)現(xiàn)，但可以用于否定某些函數(shù)依賴。18版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴函數(shù)依賴是語(yǔ)義范疇上的概念，只有根據(jù)屬8.2.1 函數(shù)依賴?yán)?根據(jù)下列具體的關(guān)系實(shí)例，判斷其中可能存在哪些函數(shù)依賴關(guān)系？y2x6y2x5y1x4y1x3y2x2y1x1BAT1AB ?BA ?y3x4y4x2y2x3y1x1y4x2y1x1BAT2AB ?BA ?y3x2y4x2y2x3y1x1y4x2y1x1BAT3AB ?BA ?19版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴?yán)?根據(jù)下列具體的關(guān)系

13、實(shí)例，判斷其8.2.1 函數(shù)依賴設(shè)有如下所示的關(guān)系RABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4其中可能成立的函數(shù)依賴關(guān)系有哪些？其中又有哪些函數(shù)依賴關(guān)系是不可能成立的？20版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴設(shè)有如下所示的關(guān)系RABCDa1b1c8.2.1 函數(shù)依賴首先考慮決定因素和依賴因素都是單個(gè)屬性的情況：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A B A C A D B A B C B D C A C B C D D A D B D C 21版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依

14、賴首先考慮決定因素和依賴因素都是單個(gè)屬性其次，再考慮決定因素是多個(gè)屬性的情況：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A B C BD A D B D C在FD的左邊不需要考慮含有屬性 D 的情況，why ?在FD的左邊不需要考慮含有屬性 B 的情況，why ?AC B ?AC D ?因此只需要考慮下述的FD是否成立：22版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系其次，再考慮決定因素是多個(gè)屬性的情況：ABCDa1b1c1dABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A B C BD A D B D C因此，最后只需要考慮下面的一個(gè)FD

15、是否可能成立？AC D ?在上述的FD關(guān)系中，我們不用考慮 AC B，why ?AC B ?AC D ?23版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系A(chǔ)BCDa1b1c1d1a1b1c2d2a2b1c1d3a28.2.1 函數(shù)依賴該關(guān)系上可能存在的函數(shù)依賴：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A B C BD A D B D CAC D24版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴該關(guān)系上可能存在的函數(shù)依賴：ABCDa8.2.1 函數(shù)依賴函數(shù)依賴反映的是同一個(gè)關(guān)系中的兩個(gè)屬性子集之間在取值上的依存關(guān)系，這種依存關(guān)系實(shí)際上也是一種數(shù)據(jù)完整性

16、約束。因此，我們也可以通過(guò)對(duì)數(shù)據(jù)完整性約束條件的分析來(lái)尋找屬性之間的函數(shù)依賴關(guān)系。例3：有一個(gè)學(xué)生關(guān)系R( S#, Sn, Sd, Ss, C#, G )，其中Ss表示學(xué)生所學(xué)專業(yè)。該關(guān)系模式中的語(yǔ)義約束如下：每個(gè)學(xué)生均只屬一個(gè)系與一個(gè)專業(yè)每個(gè)學(xué)生修讀之每門(mén)課有且僅有一個(gè)成績(jī)各系無(wú)相同專業(yè)25版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴函數(shù)依賴反映的是同一個(gè)關(guān)系中的兩個(gè)屬性8.2.1 函數(shù)依賴?yán)?：有一個(gè)學(xué)生關(guān)系R( S#, Sn, Sd, Ss, C#, G )，其中Ss表示學(xué)生所學(xué)專業(yè)。該關(guān)系模式中的語(yǔ)義約束如下：【基本常識(shí)】每個(gè)學(xué)生有唯一的一個(gè)學(xué)號(hào)，每個(gè)學(xué)生只有一個(gè)姓名

17、S# Sn每個(gè)學(xué)生均只屬一個(gè)系與一個(gè)專業(yè)S# SdS# Ss每個(gè)學(xué)生修讀之每門(mén)課有且僅有一個(gè)成績(jī)(S#，C#) G各系無(wú)相同專業(yè)Ss Sd26版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴?yán)?：有一個(gè)學(xué)生關(guān)系R( S#, Sn定義8.2：平凡/非平凡函數(shù)依賴一個(gè)函數(shù)依賴關(guān)系XY如滿足YX，則稱此函數(shù)依賴是非平凡的函數(shù)依賴。否則，我們稱其為平凡函數(shù)依賴。如無(wú)特殊聲明，凡提到函數(shù)依賴時(shí)總認(rèn)為指的是非平凡的函數(shù)依賴。8.2.1 函數(shù)依賴27版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系定義8.2：平凡/非平凡函數(shù)依賴8.2.1 函數(shù)依賴27版定義8.3：完全函數(shù)依賴在關(guān)系模式R( U )

18、中，如有XU，YU，滿足XY，且對(duì)任何X的真子集X 都有XY，則稱Y完全函數(shù)依賴于X，并記作：X Y定義8.4：部分函數(shù)依賴在關(guān)系模式R( U )中，如有XU，YU，滿足XY，但Y不完全函數(shù)依賴于X，則稱Y部分依賴于X，并記作：X Y8.2.1 函數(shù)依賴pf28版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系定義8.3：完全函數(shù)依賴定義8.4：部分函數(shù)依賴8.2.1 同樣也會(huì)有(S#，Sn) Sd(S#，Sa) Sdpp8.2.1 函數(shù)依賴?yán)纾涸趯W(xué)生S( S#, Sn, Sd, Ss, C#, G )中我們有： S# Sd我們有：S# SdSs Sd同樣也會(huì)有(S#，Ss) Sdp29版權(quán)所有(C

19、)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系同樣也會(huì)有pp8.2.1 函數(shù)依賴?yán)纾涸趯W(xué)生S( S#,8.2.1 函數(shù)依賴定義8.5：傳遞函數(shù)依賴在關(guān)系模式R( U )中，如有XU，YU，ZU且滿足：XY，YX，YX，YZ，則稱Z傳遞函數(shù)依賴于X；否則，稱為非傳遞（直接）函數(shù)依賴。為了使得函數(shù)依賴在表示形式上的簡(jiǎn)單化，傳遞函數(shù)依賴與非傳遞函數(shù)依賴在表示形式上沒(méi)有區(qū)別。30版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴定義8.5：傳遞函數(shù)依賴30版權(quán)所有(例如：在學(xué)生關(guān)系中增加一個(gè)屬性系的電話號(hào)碼DtS( S#, Sn, Sd, Ss, C#, G, Dt )每個(gè)系只登記唯一的一個(gè)電話號(hào)碼，則

20、我們有：SdDt8.2.1 函數(shù)依賴由 S#Sd 和 SdDt 可得到傳遞FD： S#Dt由 S#Ss 和 SsSd 可得到傳遞FD： S#Sd31版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系例如：在學(xué)生關(guān)系中增加一個(gè)屬性系的電話號(hào)碼Dt8.2.18.2.1 函數(shù)依賴Armstrong公理系統(tǒng)有關(guān)函數(shù)依賴的六條推理規(guī)則基本規(guī)則（3條）擴(kuò)充規(guī)則（3條）FD的邏輯蘊(yùn)涵概念函數(shù)依賴集F的閉包：F+32版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴Armstrong公理系統(tǒng)32版權(quán)所有Armstrong公理系統(tǒng)基本推理規(guī)則規(guī)則R1：自反規(guī)則如果Y是X的子集，則： X Y證明：設(shè)t1, t

21、2是關(guān)系R中的兩個(gè)元組(t1R, t2R), 且它們?cè)趯傩约疿上的值相等(t1X = t2X)由于Y是X的子集，即X Y因此必有t1Y = t2Y證畢.33版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系A(chǔ)rmstrong公理系統(tǒng)基本推理規(guī)則證明：33版權(quán)所有(CArmstrong公理系統(tǒng)基本推理規(guī)則規(guī)則R2：增廣規(guī)則如果X Y，則：XZ YZ證明：設(shè) t1R, t2R, 如果 t1XZ = t2XZ, 則：t1X = t2X (1)t1Z = t2Z (2)由(1)及XY得： t1Y = t2Y (3)由(2)及(3)得：t1YZ = t2YZ證畢.34版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系A(chǔ)

22、rmstrong公理系統(tǒng)基本推理規(guī)則證明：34版權(quán)所有(CArmstrong公理系統(tǒng)基本推理規(guī)則規(guī)則R3：傳遞規(guī)則如果X Y，Y Z，則：X Z證明：設(shè) t1R, t2R, 如果 t1X = t2X (1)由(1)及XY得：t1Y = t2Y . (2)由(2)及YZ得：t1Z = t2Z證畢.35版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系A(chǔ)rmstrong公理系統(tǒng)基本推理規(guī)則證明：35版權(quán)所有(CArmstrong公理系統(tǒng)擴(kuò)充推理規(guī)則規(guī)則R4：分解規(guī)則如果X YZ，則：X Y證明：由自反規(guī)則R1得：YZY由XYZ,YZY,根據(jù)傳遞規(guī)則R3得:XY證畢.36版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與

23、技術(shù)系A(chǔ)rmstrong公理系統(tǒng)擴(kuò)充推理規(guī)則證明：36版權(quán)所有(CArmstrong公理系統(tǒng)擴(kuò)充推理規(guī)則規(guī)則R5：合并規(guī)則如果X Y且X Z，則：X YZ證明：使用增廣規(guī)則R2可作如下推導(dǎo)：由XY可得：XXXY 即 XXY (1)由XZ可得：XYYZ (2)由(1), (2)根據(jù)傳遞規(guī)則R3可得:XYZ證畢.37版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系A(chǔ)rmstrong公理系統(tǒng)擴(kuò)充推理規(guī)則證明：37版權(quán)所有(CArmstrong公理系統(tǒng)擴(kuò)充推理規(guī)則規(guī)則R6：偽傳遞規(guī)則如果X Y且WY Z，則：WX Z證明：使用增廣規(guī)則R2，由XY可得：WXWY (1)使用傳遞規(guī)則R3，由 (1) 及 WYZ

24、 可得:WXZ證畢.38版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系A(chǔ)rmstrong公理系統(tǒng)擴(kuò)充推理規(guī)則證明：38版權(quán)所有(CArmstrong公理系統(tǒng)課后練習(xí)：請(qǐng)利用Armstrong公理系統(tǒng)證明下面的推導(dǎo)過(guò)程是否成立？如果不成立，請(qǐng)給出具體的例子關(guān)系。 WY, XZ WXY XY and Z Y XZ XY, XW, WYZ XZ XYZ, YW XWZ XZ, YZ XY XY, XYZ XZ XY, ZW XZYW XYZ, ZX ZY XY, YZ XYZ XYZ, ZW XW 39版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系A(chǔ)rmstrong公理系統(tǒng)課后練習(xí)：請(qǐng)利用Armstrong

25、8.2.1 函數(shù)依賴FD的邏輯蘊(yùn)涵概念設(shè) F 是關(guān)系模式 R(U) 的一個(gè)函數(shù)依賴集，X, Y 是關(guān)系模式 R 的屬性子集，如果從 F 中的已有函數(shù)依賴關(guān)系利用 Armstrong 公理系統(tǒng)能夠推出 XY，則稱 F 邏輯蘊(yùn)涵 XY，并記為：F XY函數(shù)依賴集 F 的閉包 F+由被 F 邏輯蘊(yùn)涵的所有函數(shù)依賴關(guān)系構(gòu)成的集合被稱為函數(shù)依賴集 F 的閉包，并記為 F+F+ = XY F XY 40版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴FD的邏輯蘊(yùn)涵概念函數(shù)依賴集 F 的閉8.2.1 函數(shù)依賴計(jì)算函數(shù)依賴集 F = AB, BC 的閉包 F+F中的所有函數(shù)依賴都是其閉包中的元素

26、，即：AB F+ BC F+根據(jù)自反規(guī)則，下述函數(shù)依賴也是其閉包中的元素AA BB CCABA ABB ABABACA ACC ACACBCB BCC BCBCABCA ABCB ABCCABCAB ABCAC ABCBCABCABC41版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴計(jì)算函數(shù)依賴集 F = AB, 8.2.1 函數(shù)依賴由AB, BC及傳遞規(guī)則可得到閉包中的下列元素AC由AB, AC及合并規(guī)則可得到閉包中的下列元素ABC由AB及增廣規(guī)則可得到閉包中的下列元素AAB ACBC ACABC由BC及增廣規(guī)則可得到閉包中的下列元素ABAC BBC ABABC由AC及增廣規(guī)

27、則可得到閉包中的下列元素AAC ABBC由ABC及增廣規(guī)則可得到閉包中的下列元素AABC42版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴由AB, BC及傳遞規(guī)則可得到閉包8.2.1 函數(shù)依賴由ABB, BC及傳遞規(guī)則可得到閉包中的下列元素ABC由ACA, AB及傳遞規(guī)則可得到閉包中的下列元素ACB由ACB及增廣規(guī)則可得到閉包中的下列元素ACAB43版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴由ABB, BC及傳遞規(guī)則可得到閉8.2.1 函數(shù)依賴定義8.6：關(guān)鍵字（也稱為 碼 或 key ）在關(guān)系模式 R(U, F) 中，如有 KU 且滿足：K U則稱 K 為

28、 R 的關(guān)鍵字。f幾種不同的關(guān)鍵字候選關(guān)鍵字主關(guān)鍵字全關(guān)鍵字44版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴定義8.6：關(guān)鍵字（也稱為 碼 或 k8.2.1 函數(shù)依賴定義8.7：主屬性(集)由關(guān)系模式 R 的所有關(guān)鍵字中的屬性所構(gòu)成的集合被稱為關(guān)系模式 R 的 主屬性集主屬性集中的屬性被稱為關(guān)系模式 R 的 主屬性定義8.8：非主屬性(集)由主屬性集之外的其它屬性所構(gòu)成的集合被稱為關(guān)系模式 R 的 非主屬性集非主屬性集中的屬性被稱為關(guān)系模式 R 的 非主屬性45版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴定義8.7：主屬性(集)45版權(quán)所有(8.2.1 函數(shù)

29、依賴如何尋找一個(gè)關(guān)系模式R(U, F)的關(guān)鍵字？fK U方法一：利用Armstrong公理系統(tǒng)中的推導(dǎo)規(guī)則，從已知的函數(shù)依賴集F中推導(dǎo)得到如下的函數(shù)依賴關(guān)系：缺點(diǎn)：依賴于對(duì)推導(dǎo)規(guī)則的熟練使用46版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴如何尋找一個(gè)關(guān)系模式R(U, F)的關(guān)8.2.1 函數(shù)依賴如何尋找一個(gè)關(guān)系模式R(U, F)的關(guān)鍵字？方法二：根據(jù)關(guān)鍵字的定義及屬性集閉包的概念，計(jì)算能夠滿足條件（KF+ = U）的最小屬性集合K算法8-1, 8-2方法三：先計(jì)算函數(shù)依賴集F的最小覆蓋（即與F相等價(jià)的最小函數(shù)依賴集），然后根據(jù)函數(shù)依賴的特性以及關(guān)鍵字的定義來(lái)尋找關(guān)系的關(guān)鍵字可

30、縮短算法8-2的計(jì)算過(guò)程47版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴如何尋找一個(gè)關(guān)系模式R(U, F)的關(guān)8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(1) R (A, B, C, D)，F(xiàn): BD, ABC 解：由 BD 及增廣規(guī)則 R2 可得：ABAD (1)由(1), ABC 及合并規(guī)則 R5 可得:ABACD (2)由 (2) 及增廣規(guī)則 R2 可得：ABABCD完.48版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字解：488.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(2) R (A, B, C)，F(xiàn): A

31、B, BA, AC 解1：由 AB, AC 及合并規(guī)則 R5 可得：ABC由 ABC 及增廣規(guī)則 R2 可得：AABC完.解2：由 BA, AC 及傳遞規(guī)則 R3 可得：BC由 BA, BC 及合并規(guī)則 R5 可得：BAC由 BAC 及增廣規(guī)則 R2 可得 BABC完.49版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字解1：解8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(3) R (A, B, C)，F(xiàn): AC, DB 解：由 AC 及增廣規(guī)則 R2 可得：ADCD (1)由 DB 及增廣規(guī)則 R2 可得：ADAB (2)由 (1), (2)

32、 及合并規(guī)則 R5 可得：ADABCD完.50版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字解：508.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(4) R (A, B, C, D)，F(xiàn): AC, CDB 解：由 AC 及增廣規(guī)則 R2 可得：ADCD (1)由 (1), CDB 及傳遞規(guī)則 R3 可得： ADB由 ADB 及增廣規(guī)則 R2 可得：ADAB (2)由 (1), (2) 及合并規(guī)則 R5 可得：ADABCD完.51版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字解：518.2.1 函數(shù)依

33、賴屬性集的閉包 XF+（可以簡(jiǎn)寫(xiě)為 X+）設(shè) F 是關(guān)系模式 R(U) 上的函數(shù)依賴集，X 是關(guān)系模式 R(U) 的屬性子集，由所有函數(shù)依賴于 X 的屬性所構(gòu)成的集合被稱為屬性集 X 在函數(shù)依賴集 F 上的閉包。X+ = A F XA 52版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴屬性集的閉包 XF+（可以簡(jiǎn)寫(xiě)為 X+8.2.1 函數(shù)依賴算法8-1：計(jì)算屬性集X在函數(shù)依賴集F上的閉包XF+(簡(jiǎn)寫(xiě)為X+）X+ := X;repeatoldX+ := X+;for each functional dependency YZ in F doif Y X+ then X+ := X

34、+ Z;until ( oldX+ = X+ )53版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴算法8-1：計(jì)算屬性集X在函數(shù)依賴集F8.2.1 函數(shù)依賴?yán)涸O(shè) F = (f1) BCD, (f2) ADE, (f3) BA ，請(qǐng)計(jì)算 BF+ ?BF+ = B 第一遍循環(huán) X = BF+ = B f1 的決定因素是BF+的一個(gè)子集，所以BF+ = BF+ C, D = B, C, D f2 的決定因素不是BF+的子集, 因此 f2 不影響本次循環(huán)的計(jì)算結(jié)果 f3 的決定因素是BF+的一個(gè)子集，所以BF+ = BF+ A = A, B, C, D X BF+, 回到步驟1)開(kāi)始

35、執(zhí)行第二遍循環(huán)54版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴?yán)涸O(shè) F = (f1) BCD8.2.1 函數(shù)依賴第二遍循環(huán)X = BF+ = A, B, C, D 跳過(guò)在第一遍循環(huán)中已經(jīng)處理過(guò)的函數(shù)依賴f2 的決定因素是BF+的子集, 所以BF+ = BF+ E = A, B, C, D, EX BF+, 回到步驟1)開(kāi)始執(zhí)行第三遍循環(huán)第三遍循環(huán)X = BF+ = A, B, C, D, EF中的所有函數(shù)依賴都已處理過(guò)（其依賴因素都已經(jīng)被并入到 BF+ 中）因此在本次循環(huán)中BF+將不再發(fā)生變化，算法執(zhí)行結(jié)束返回 BF+55版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1

36、 函數(shù)依賴第二遍循環(huán)55版權(quán)所有(C)-南京大學(xué)8.2.1 函數(shù)依賴關(guān)鍵字 K 與屬性集閉包 XF+ 概念之間的關(guān)系設(shè) F 是關(guān)系模式 R(U) 上的函數(shù)依賴集，K 是關(guān)系模式 R(U) 的一個(gè)關(guān)鍵字，則：KF+ = U對(duì)于 K 的任意一個(gè)真子集 K，都有：KF+ U56版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴關(guān)鍵字 K 與屬性集閉包 XF+ 概念8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(1) R (A, B, C, D)，F(xiàn): BD, ABC ;解：由 BD 及增廣規(guī)則 R2 可得：ABAD (1)由(1), ABC 及合并規(guī)則 R5 可得:ABACD (2)

37、由 (2) 及增廣規(guī)則 R2 可得：ABABCD因?yàn)椋?對(duì)方法一計(jì)算結(jié)果的驗(yàn)證) A F+ = A A, B, C, D B F+ = B, D A, B, C, D 所以 ( A, B ) 是關(guān)系模式 R 的一個(gè)關(guān)鍵字。完.57版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字解：因?yàn)?.2.1 函數(shù)依賴算法8-2：尋找關(guān)系模式 R(U, F) 的關(guān)鍵字 Kset K := R ;for each attribute A in Kcompute (K A)F+ ;if (K A)F+ contains all the attributes in R,

38、 thenset K := K A ;58版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴算法8-2：尋找關(guān)系模式 R(U, F8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(2) R (A, B, C)，F(xiàn): AB, BA, AC ;解1：K = A, B, C KA+ = A,B,C = U K = KA = B,C KB+ = C U 該關(guān)鍵字中必定含有屬性 B KC+ = A,B,C = U K = KC = B最后得到該關(guān)系的一個(gè)關(guān)鍵字 B 解2：K = A, B, C KB+ = A,B,C = U K = KB = A,C KA+ = C U 該關(guān)鍵字中必定含有

39、屬性 A KC+ = A,B,C = U K = KC = A最后得到該關(guān)系的另一個(gè)關(guān)鍵字 A 59版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字解1：K8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(4) R (A, B, C, D)，F(xiàn): AC, CDB 解1：K = A, B, C, D KA+ = A,B,C U 該關(guān)鍵字中必定含有屬性 A KB+ = A,B,C,D = U K = KB = A,C,D KC+ = A,B,C,D = U K = KC = A,D KD+ = A,C U 該關(guān)鍵字中必定含有屬性 D最后得到該關(guān)系的一個(gè)

40、關(guān)鍵字 A, D 60版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字解1：K8.2.1 函數(shù)依賴習(xí)題8.6：61版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.1 函數(shù)依賴習(xí)題8.6：61版權(quán)所有(C)-南京大8.2 規(guī)范化理論8.2.1 函數(shù)依賴8.2.2 與函數(shù)依賴有關(guān)的范式范式及模式分解方法1NF2NF3NFBCNF8.2.3 多值依賴與第四范式62版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2 規(guī)范化理論8.2.1 函數(shù)依賴62版權(quán)所有(C)8.2.2 與函數(shù)依賴有關(guān)的范式定義：第一范式（1NF）如果關(guān)系模式 R(U) 中的每個(gè)屬性值都

41、是一個(gè)不可分割的數(shù)據(jù)量，則稱該關(guān)系模式滿足第一范式，并記為：R 1NF定義8.9：第二范式 ( 2NF )設(shè)有關(guān)系模式 R(U) 1NF，且其每個(gè)非主屬性都完全函數(shù)依賴于關(guān)鍵字，則稱關(guān)系模式 R(U) 滿足第二范式，并記作：R 2NF63版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式定義：第一范式（1NF）定8.2.2 與函數(shù)依賴有關(guān)的范式例：有一個(gè)學(xué)生關(guān)系 SCG( S#, Sn, Sd, Ss, C#, G )，根據(jù)用戶給定的語(yǔ)義約束得到如下的函數(shù)依賴關(guān)系：基本常識(shí)：S#Sn每個(gè)學(xué)生均只屬一個(gè)系與一個(gè)專業(yè)；S#Sd S#Ss每個(gè)學(xué)生修讀之每門(mén)課有且僅有一個(gè)成績(jī)；

42、(S#，C#)G各系無(wú)相同專業(yè)。SsSd64版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式例：有一個(gè)學(xué)生關(guān)系 SCG8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系模式 SCG( S#, Sn, Sd, Ss, C#, G )，函數(shù)依賴集為：S#Sn, S#Sd, S#Ss, (S#,C#)G, SsSd該關(guān)系模式是否滿足第二范式的要求？找出該關(guān)系模式的所有(候選)關(guān)鍵字據(jù)此確定該關(guān)系的主屬性集和非主屬性集判斷每一個(gè)非主屬性和關(guān)鍵字之間的函數(shù)依賴關(guān)系是否滿足2NF的要求。如果不存在非主屬性對(duì)關(guān)鍵字的部分依賴，那么 SCG 2NF(S#,C#)主屬性集： S#,C# 非主屬性集：

43、 Sn, Sd, Ss, G 65版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系模式 SCG( S#,8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系模式 SCG( S#, Sn, Sd, Ss, C#, G )，函數(shù)依賴集為：S#Sn, S#Sd, S#Ss, (S#，C#)G, SsSd關(guān)系模式SCG只能滿足到 1NF采用SCG( S#, Sn, Sd, Ss, C#, G )的模式設(shè)計(jì)方案（僅滿足1NF的關(guān)系模式）會(huì)帶來(lái)什么樣的問(wèn)題？數(shù)據(jù)冗余因數(shù)據(jù)冗余而產(chǎn)生更新異常為什么出現(xiàn)數(shù)據(jù)冗余現(xiàn)象？非主屬性對(duì)關(guān)鍵字的部分函數(shù)依賴如何避免上述的數(shù)據(jù)冗余現(xiàn)象？按照更高范式的要求設(shè)計(jì)

44、關(guān)系模式：模式分解66版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系模式 SCG( S#,8.2.2 與函數(shù)依賴有關(guān)的范式圖1：根據(jù)關(guān)系模式SCG所建立的數(shù)據(jù)庫(kù)（僅滿足1NF）67版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式圖1：根據(jù)關(guān)系模式SCG所8.2.2 與函數(shù)依賴有關(guān)的范式為了使最終的模式設(shè)計(jì)結(jié)果能夠滿足到2NF，我們可以對(duì)關(guān)系SCG進(jìn)行模式分解，將其屬性集合分解構(gòu)成若干個(gè)小的關(guān)系模式。隨著對(duì)原有關(guān)系模式的分解，原來(lái)在關(guān)系模式SCG上存在的函數(shù)依賴集合也被分解到若干個(gè)小的關(guān)系模式上去。模式分解的目標(biāo)使得分解得到的每個(gè)小的關(guān)系

45、模式都能夠滿足2NF的要求。68版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式為了使最終的模式設(shè)計(jì)結(jié)果能8.2.2 與函數(shù)依賴有關(guān)的范式模式分解設(shè)在關(guān)系模式R上成立的函數(shù)依賴集為F, Head(R) 是由關(guān)系R中的所有屬性所構(gòu)成的屬性集合。如果存在一組子關(guān)系模式 R1, R2, , Rk 滿足下述的兩個(gè)條件，則我們稱 R1, R2, , Rk 是關(guān)系模式R的一個(gè)分解 (Decomposition)Head(R) = Head(R1)Head(R2) Head(Rk)設(shè)子關(guān)系Ri上的函數(shù)依賴集為Fi (i=1,2,k), 則：Fi = XY XYF+ 且 (XY)He

46、ad(Ri) 69版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式模式分解69版權(quán)所有(C)8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系的規(guī)范化過(guò)程就是一個(gè)不斷進(jìn)行模式分解的過(guò)程。通過(guò)模式分解可以消除原有關(guān)系模式中那些不好的函數(shù)依賴關(guān)系（即不滿足更高范式要求的函數(shù)依賴關(guān)系），以盡可能地解決原有模式中所存在的數(shù)據(jù)冗余和各種插入、刪除異?，F(xiàn)象。70版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系的規(guī)范化過(guò)程就是一個(gè)不8.2.2 與函數(shù)依賴有關(guān)的范式模式分解的方法設(shè)存在一個(gè)關(guān)系模式R, 其屬性集合為Head(R), F是其函數(shù)依賴集。將其分解到滿足范式

47、M的步驟如下：找出所有不滿足范式M要求的函數(shù)依賴關(guān)系選擇一個(gè)不符合要求的函數(shù)依賴關(guān)系作如下的分解：假設(shè) X Y F+ 且不滿足范式M的要求，則我們將關(guān)系模式R分解為如下的兩個(gè)子關(guān)系：R1 ( XY, XY )R2 ( Head(R) Y, F2 )，其中： F2 = ABABF+ 且 (AB)Head(R2) f71版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式模式分解的方法找出所有不滿8.2.2 與函數(shù)依賴有關(guān)的范式模式分解的方法對(duì)于分解得到的子關(guān)系模式R2重復(fù)上述的步驟1)和步驟2)，直到所有的子關(guān)系模式都能滿足范式M的要求合并那些具有相同關(guān)鍵字的子關(guān)系模式72

48、版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式模式分解的方法對(duì)于分解得到8.2.2 與函數(shù)依賴有關(guān)的范式利用前面介紹的分解方法對(duì)關(guān)系模式 SCG進(jìn)行規(guī)范化（分解到滿足2NF）f不符合2NF要求的函數(shù)依賴關(guān)系具有以下特征：X Y，Y是關(guān)系SCG的非主屬性，而X則是其某個(gè)候選關(guān)鍵字的真子集函數(shù)依賴集Ff1: S#Snf2: S#Sdf3: S#Ssf4: (S#, C#)Gf5: SsSd非主屬性集 Sn, Sd, Ss, G 主屬性集 S#, C# 關(guān)鍵字K(S#, C#)73版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式利用前面介紹的分解

49、方法對(duì)關(guān)8.2.2 與函數(shù)依賴有關(guān)的范式分解過(guò)程(1)在關(guān)系SCG( U=S#, Sn, Sd, Ss, C#, G )中找出所有不滿足2NF要求的函數(shù)依賴f1: S#Sn f2: S#Sd f3: S#Ss從中選擇一個(gè)函數(shù)依賴( f1)進(jìn)行模式分解，分解結(jié)果如下：R1 ( U1 = S#, Sn , F1 = f1: S#Sn )R0 ( U0 = U Sn = S#, Sd, Ss, C#, G , F0 = f2: S#Sd,f3: S#Ss,f4: (S#, C#)G,f5: SsSd )74版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式分解過(guò)程(1)74版

50、權(quán)所有8.2.2 與函數(shù)依賴有關(guān)的范式分解過(guò)程(2)在關(guān)系R0( U0=S#, Sd, Ss, C#, G, F0 )中找出所有不滿足2NF要求的函數(shù)依賴f2: S#Sd f3: S#Ss從中選擇一個(gè)函數(shù)依賴( f2)進(jìn)行模式分解，分解結(jié)果如下：R2 ( U2 = S#, Sd , F2 = f2: S#Sd )R0 ( U0 = U Sd = S#, Ss, C#, G , F0 = f3: S#Ss,f4: (S#, C#)G )75版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式分解過(guò)程(2)75版權(quán)所有8.2.2 與函數(shù)依賴有關(guān)的范式分解過(guò)程(3)在關(guān)系R0(

51、 U0=S#, Ss, C#, G, F0 )中找出所有不滿足2NF要求的函數(shù)依賴f3: S#Ss從中選擇一個(gè)函數(shù)依賴( f3)進(jìn)行模式分解，分解結(jié)果如下：R3 ( U3 = S#, Ss , F3 = f3: S#Ss )R0 ( U0 = U Ss = S#, C#, G , F0 = f4: (S#, C#)G )76版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式分解過(guò)程(3)76版權(quán)所有8.2.2 與函數(shù)依賴有關(guān)的范式綜合前面的分解結(jié)果R1 ( U1 = S#, Sn , F1 = f1: S#Sn )R2 ( U2 = S#, Sd , F2 = f2:

52、S#Sd )R3 ( U3 = S#, Ss , F2 = f3: S#Ss )R0 ( U0 = U Ss = S#, C#, G , F0 = f4: (S#, C#)G )所有的子關(guān)系模式都已經(jīng)滿足2NF77版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式綜合前面的分解結(jié)果77版權(quán)8.2.2 與函數(shù)依賴有關(guān)的范式合并關(guān)鍵字相同的子關(guān)系模式后得到如下的分解結(jié)果SCG1 ( S#, C#, G ), 其函數(shù)依賴集是： f4: ( S#, C# )G SCG2 ( S#, Sn, Sd, Ss ), 其函數(shù)依賴集是：f1: S#Sn,f2: S#Sd,f3: S#Ss

53、,f5: SsSd78版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式合并關(guān)鍵字相同的子關(guān)系模式8.2.2 與函數(shù)依賴有關(guān)的范式圖2：根據(jù)關(guān)系模式SCG1和SCG2所建立的數(shù)據(jù)庫(kù)（可以滿足到 2NF）79版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式圖2：根據(jù)關(guān)系模式SCG18.2.2 與函數(shù)依賴有關(guān)的范式在關(guān)系SCG2中仍然存在數(shù)據(jù)冗余以及因此而產(chǎn)生的更新異?，F(xiàn)象原因：存在非主屬性對(duì)關(guān)鍵字的傳遞依賴80版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式在關(guān)系SCG2中仍然存在數(shù)8.2.2 與函數(shù)依賴有關(guān)的范式定義8

54、.10：第三范式 ( 3NF )設(shè)有關(guān)系模式 R(U) 2NF，且其每個(gè)非主屬性都不傳遞函數(shù)依賴于關(guān)鍵字，則稱關(guān)系模式 R(U) 滿足第三范式，并記作：R 3NF不符合3NF要求的函數(shù)依賴關(guān)系具有如下特征：X Y，Y是關(guān)系SCG的非主屬性，而X并不是關(guān)鍵字，或者X只是關(guān)鍵字的一個(gè)真子集f81版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式定義8.10：第三范式 (8.2.2 與函數(shù)依賴有關(guān)的范式分解到滿足3NFSCG1 ( S#,C#,G, ( S#,C# )G )已滿足3NFSCG2 ( S#, Sn, Sd, Ss, S#Sn, S#Ss, SsSd )關(guān)鍵字：S

55、#存在非主屬性Sd對(duì)關(guān)鍵字的傳遞依賴：S#Ss, SsS#, SsSd S#Sd82版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式分解到滿足3NFSCG2 8.2.2 與函數(shù)依賴有關(guān)的范式分解到滿足3NFSCG2 ( S#, Sn, Sd, Ss )的分解結(jié)果如下：SCG21 ( S#, Sn, Ss ), 其函數(shù)依賴集是： S#Sn, S#Ss SCG22 ( Sd, Ss ), 其函數(shù)依賴集是： SsSd 83版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式分解到滿足3NF83版權(quán)所8.2.2 與函數(shù)依賴有關(guān)的范式圖3：符合3NF要求的

56、模式設(shè)計(jì)84版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式圖3：符合3NF要求的模式8.2.2 與函數(shù)依賴有關(guān)的范式定義8.11：BCNF設(shè)關(guān)系模式 R(U) 滿足 1NF，且若 XY 時(shí) X 必含有該關(guān)系模式的關(guān)鍵字，則稱關(guān)系模式 R(U) 滿足BCNF范式，并記作：R BCNF85版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式定義8.11：BCNF858.2.2 與函數(shù)依賴有關(guān)的范式例 8.1設(shè)有關(guān)系模式 R (S, C, T)，其中 S, C 含義同前, T 表示教師，R 有下列語(yǔ)義信息：每個(gè)教師僅上一門(mén)課TC學(xué)生與課程確定后，教師

57、即惟一確定( S, C )T思考題：關(guān)系模式 R 的關(guān)鍵字是什么？關(guān)系模式 R 的主屬性集是什么？非主屬性集又是什么？該關(guān)系模式 R 最高能夠滿足到第幾范式？86版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式例 8.1思考題：86版權(quán)8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系R最高能夠滿足到第幾范式？R( S, C, T, TC, (S,C)T )候選關(guān)鍵字： S, C 和 S, T 思考題答案有兩個(gè)候選關(guān)鍵字： S, C 和 S, T 主屬性集是： S，C，T 其主屬性集為S, C, T，非主屬性集為空（不存在非主屬性），因此該關(guān)系模式中不存在不滿足2NF和3NF范式要

58、求的函數(shù)依賴，因此該關(guān)系模式一定可以滿足到3NF。87版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系R最高能夠滿足到第幾范8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系模式R是否能夠滿足BCNF？R( S, C, T, TC, (S,C)T )候選關(guān)鍵字： S, C 和 S, T 存在不滿足BCNF要求的函數(shù)依賴:TC因此不滿足BCNF分解到滿足BCNF范式R1 ( C, T )函數(shù)依賴集： TC R2 ( S, T )函數(shù)依賴集： 88版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式關(guān)系模式R是否能夠滿足BC8.2.2 與函數(shù)依賴有關(guān)的范式定理

59、8-1如果關(guān)系模式 R(U) BCNF，則 R(U) 3NF證明：假設(shè) R(U) 3NF, 則有三種可能性：(2) 假設(shè)存在一個(gè)非主屬性 A 部分依賴于關(guān)鍵字 K，即：K A（A K）由部分依賴的定義可知：必存在 K 的某個(gè)真子集 K，且滿足：KA（A K）由 R(U) BCNF 及 BCNF 定義可知：K 中必含有關(guān)鍵字，即關(guān)鍵字 K 中含有另一個(gè)關(guān)鍵字 K，且K K，這與關(guān)鍵字的定義相矛盾。p假設(shè) R(U) 1NF由 R(U) BCNF 可知：R(U) 1NF。與假設(shè)相矛盾。89版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式定理8-1證明：假設(shè) R(8.2.2

60、與函數(shù)依賴有關(guān)的范式(3) 假設(shè)存在一個(gè)非主屬性 A 傳遞依賴于關(guān)鍵字 K，即存在一個(gè)屬性集合 B，并滿足：KB，B K，BK，BA由BA 及 R(U) BCNF 可知：B 中必含有關(guān)鍵字 K由關(guān)鍵字的定義可知：K U因?yàn)?B K, K U，故 BK。這與 BK 相矛盾。綜上所述，假設(shè)不成立，即 R(U) 3NF證畢.90版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系8.2.2 與函數(shù)依賴有關(guān)的范式(3) 假設(shè)存在一個(gè)非主屬8.2 規(guī)范化理論8.2.1 函數(shù)依賴8.2.2 與函數(shù)依賴有關(guān)的范式8.2.3 多值依賴與第四范式多值依賴與MVD有關(guān)的推理規(guī)則4NF91版權(quán)所有(C)-南京大學(xué)計(jì)算機(jī)科學(xué)與