數(shù)據(jù)庫概論課件database

第8章關(guān)系數(shù)據(jù)庫的規(guī)范化理論22007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

在關(guān)系數(shù)據(jù)庫系統(tǒng)的建立過程中，如何構(gòu)造一個(gè)合適的關(guān)系數(shù)據(jù)模式？關(guān)系數(shù)據(jù)庫的設(shè)計(jì)理論關(guān)系數(shù)據(jù)庫的規(guī)范化理論32007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

本章的內(nèi)容8.1概述8.2規(guī)范化理論8.2.1函數(shù)依賴8.2.2與函數(shù)依賴有關(guān)的范式8.2.3多值依賴與第四范式8.3規(guī)范化所引起的一些問題函數(shù)依賴?yán)碚摰难芯磕Ｊ椒纸獾难芯浚簾o損聯(lián)接性，依賴保持性42007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

第八章關(guān)系數(shù)據(jù)庫規(guī)范化理論8.1概述8.2規(guī)范化理論8.3規(guī)范化所引起的一些問題52007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.1概述1模式設(shè)計(jì)同一個(gè)數(shù)據(jù)庫系統(tǒng)可以有多種不同的模式設(shè)計(jì)方案。如：假設(shè)一個(gè)學(xué)生數(shù)據(jù)庫中有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)62007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.1概述2不同模式設(shè)計(jì)方案的比較不同的模式設(shè)計(jì)方案對(duì)數(shù)據(jù)庫的影響是否相同？例：根據(jù)方案1所建立的數(shù)據(jù)庫如表8-2所示根據(jù)方案2所建立的數(shù)據(jù)庫如表8-3所示我們從下面三個(gè)方面來比較這兩個(gè)數(shù)據(jù)庫：數(shù)據(jù)冗余度元組插入操作元組刪除操作72007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.1概述表8-2根據(jù)方案1所建立的數(shù)據(jù)庫(關(guān)系SCG)82007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.1概述表8-3根據(jù)方案2所建立的數(shù)據(jù)庫(關(guān)系S,C和SC)92007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.1概述經(jīng)過比較發(fā)現(xiàn)，表8-2具有如下缺點(diǎn)：數(shù)據(jù)冗余度大插入異常如果需要新開設(shè)一門尚未有學(xué)生選修的課程(104,DB,103)，則無法構(gòu)造出一個(gè)由S#,Sn,Sd,Sa等屬性值所組成的新元組，在表8-2中就無法執(zhí)行元組的插入操作。在表8-3中，我們可以直接將元組(104,DB,103)插入到課程關(guān)系C中。102007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.1概述刪除異常在表8-2中，107號(hào)課程僅有0003號(hào)學(xué)生選修，如果該學(xué)生因故退學(xué)，就必須將與該學(xué)生有關(guān)的元組從表8-2中刪除掉，這樣就必然也將107號(hào)這門課程也從數(shù)據(jù)庫中刪除掉了。在表8-3中，我們可以僅在學(xué)生關(guān)系S和選課關(guān)系SC中刪除0003號(hào)學(xué)生的元組及其選課信息，但不會(huì)誤刪除掉107號(hào)課程，其所對(duì)應(yīng)的元組仍然保留在課程關(guān)系C中。112007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.1概述因此，不同的模式設(shè)計(jì)方案有好壞的區(qū)分。好的設(shè)計(jì)方案應(yīng)該是：既具有合理的數(shù)據(jù)冗余度，又沒有插入和刪除等異?，F(xiàn)象的出現(xiàn)。122007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.1概述3在不同的設(shè)計(jì)結(jié)果之間產(chǎn)生區(qū)別的原因數(shù)據(jù)庫的各屬性之間是互相關(guān)聯(lián)的，它們互相依賴、互相制約，構(gòu)成一個(gè)結(jié)構(gòu)嚴(yán)密的整體。要設(shè)計(jì)出一個(gè)好的關(guān)系模式，必須從數(shù)據(jù)庫中所有屬性的語義上進(jìn)行分析，從語義上入手分清每個(gè)屬性的語義含義及其相互之間的依存關(guān)系。進(jìn)而將那些相互依賴密切的屬性組合在一起構(gòu)成一個(gè)關(guān)系模式，避免對(duì)屬性的松散組合所引起的‘排它性’，從而可以降低數(shù)據(jù)冗余度，避免上述異?，F(xiàn)象的產(chǎn)生。132007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.1概述4關(guān)系的規(guī)范化在一個(gè)關(guān)系中，屬性與屬性之間的內(nèi)在語義聯(lián)系有兩種：函數(shù)依賴&多值依賴關(guān)系的規(guī)范化在每個(gè)關(guān)系中，屬性與屬性之間一定要滿足某種內(nèi)在的語義聯(lián)系，這被稱為關(guān)系的規(guī)范化。根據(jù)對(duì)屬性間所存在的內(nèi)在語義聯(lián)系要求的不同，又可以將關(guān)系的規(guī)范化分為若干個(gè)級(jí)別，這被稱為范式。上述相關(guān)的理論被稱為關(guān)系規(guī)范化理論。142007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

第八章關(guān)系數(shù)據(jù)庫規(guī)范化理論8.1概述8.2規(guī)范化理論8.3規(guī)范化所引起的一些問題152007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2規(guī)范化理論數(shù)據(jù)依賴?yán)碚摵瘮?shù)依賴（FD–FunctionalDependency）1970年，E.F.Codd1972–1974年，Codd,Casey,Bernstein,Armstrong完全/部分FD，平凡/非平凡FD，直接/傳遞FD鍵（key）1974年，Armstrong公理系統(tǒng)FD的邏輯蘊(yùn)涵FD的形式化推理規(guī)則集多值依賴（MVD–Multi-ValuedDependency）1976–1978年，Zaniolo,Fagin,Delobel162007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

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ù)庫的規(guī)范化理論模式分解理論：無損聯(lián)接性，依賴保持性水平規(guī)范化采用‘選擇’和‘并’運(yùn)算將一個(gè)關(guān)系的元組集合分解成若干個(gè)子集，從而構(gòu)成若干個(gè)與原來的關(guān)系具有相同關(guān)系模式的子關(guān)系尚未形成一個(gè)成熟的規(guī)范化理論172007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2規(guī)范化理論8.2.1函數(shù)依賴函數(shù)依賴完全/部分FD，平凡/非平凡FD，直接/傳遞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ī)則4NF182007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

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的取值依賴于另一部分屬性X的取值，則在屬性集X和屬性集Y之間存在著一種數(shù)據(jù)依賴關(guān)系，我們稱之為函數(shù)依賴。192007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.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，并記為X→Y。其中：X稱為決定因素Y稱為依賴因素202007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴定義8.1：函數(shù)依賴(cont.)假設(shè)在關(guān)系模式R(U)上存在函數(shù)依賴關(guān)系：X→Y

r是依據(jù)關(guān)系模式R(U)建立起來的任意一個(gè)關(guān)系，那么關(guān)系r必滿足：從關(guān)系r中任取兩個(gè)元組t1和t2，如果元組t1在X這組屬性上的取值t1[X]等于元組t2在X這組屬性上的取值t2[X]，即：t1[X]=t2[X]則它們?cè)赮這組屬性上的取值也必定相等，即：t1[Y]=t2[Y]212007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴函數(shù)依賴是語義范疇上的概念，只有根據(jù)屬性間固有的語義聯(lián)系才能歸納出與客觀事實(shí)相符合的函數(shù)依賴關(guān)系，而不是僅從現(xiàn)有的一個(gè)或若干個(gè)關(guān)系實(shí)例中得出的結(jié)論。特定的關(guān)系實(shí)例雖然不能用于函數(shù)依賴的發(fā)現(xiàn)，但可以用于否定某些函數(shù)依賴。222007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴在關(guān)系模式S(S#,Sn,Sd,Sa)上，可能存在的函數(shù)依賴有很多，例如：S#→Sn，Sn→Sd，Sd→Sn，{S#,Sn}→Sd，……但是，根據(jù)下面的關(guān)系S（依據(jù)上述的關(guān)系模式而建）：可以否認(rèn)以下的函數(shù)依賴：Sd→S#，Sd→Sn，…雖然不能否定，但也不能確認(rèn)以下的函數(shù)依賴成立：

S#→Sn，Sd→Sa，……232007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴[例]根據(jù)下列具體的關(guān)系實(shí)例，判斷其中可能存在哪些函數(shù)依賴關(guān)系？y2x6y2x5y1x4y1x3y2x2y1x1BAT1A→B?B→A?y3x4y4x2y2x3y1x1y4x2y1x1BAT2A→B?B→A?y3x2y4x2y2x3y1x1y4x2y1x1BAT3A→B?B→A?

?

?

242007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴設(shè)有如下所示的關(guān)系RABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4其中可能成立的函數(shù)依賴關(guān)系有哪些？其中又有哪些函數(shù)依賴關(guān)系是不可能成立的？252007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴首先考慮決定因素和依賴因素都是單個(gè)屬性的情況：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A→B

A→C

A→D

B→AB→CB→DC→AC→BC→DD→AD→BD→C???????√√√√√262007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴也可以按照如下順序考慮可能存在的函數(shù)依賴情況：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A→B

A→C

A→D

B→AB→CB→DC→AC→BC→DD→AD→BD→C???????√√√√√272007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

其次，再考慮決定因素是多個(gè)屬性的情況：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A→B C→BD→A D→B D→C在FD的左邊不需要考慮含有屬性D的情況，why?在FD的左邊不需要考慮含有屬性B的情況，why?AC→B? AC→D?因此只需要考慮下述的FD是否成立：282007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A→B C→BD→A D→B D→C因此，最后只需要考慮下面的一個(gè)FD是否可能成立？

AC→D?在上述的FD關(guān)系中，我們不用考慮AC→B，why?AC→B? AC→D?√292007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴該關(guān)系上可能存在的函數(shù)依賴：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A→B C→BD→A D→B D→CAC→D302007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

該關(guān)系上可能存在的函數(shù)依賴：ABCDa1b1c1d1a1b1c2d2a2b1c1d3a2b1c3d4A→B C→B AC→DD→A D→B D→C思考問題：為什么沒有寫出左邊含有屬性D的其它的那些可能的FD？右邊為單個(gè)屬性B的其它的那些可能的FD？右邊為多個(gè)屬性的那些可能的FD？形如1)和2)這兩種情況的函數(shù)依賴，都屬于是可能成立的，并且可以從已寫出的這六個(gè)函數(shù)依賴中推導(dǎo)出來。在情況3)中，可以用已寫出的這六個(gè)函數(shù)依賴來證明它是否成立。312007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴函數(shù)依賴反映的是同一個(gè)關(guān)系中的兩個(gè)屬性子集之間在取值上的依存關(guān)系，這種依存關(guān)系實(shí)際上也是一種數(shù)據(jù)完整性約束。因此，我們也可以通過對(duì)數(shù)據(jù)完整性約束條件的分析來尋找屬性之間的函數(shù)依賴關(guān)系。例3：有一個(gè)學(xué)生關(guān)系R(S#,Sn,Sd,Ss,C#,G)，其中Ss表示學(xué)生所學(xué)專業(yè)。該關(guān)系模式中的語義約束如下：每個(gè)學(xué)生均只屬一個(gè)系與一個(gè)專業(yè)每個(gè)學(xué)生修讀之每門課有且僅有一個(gè)成績各系無相同專業(yè)322007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴?yán)?：學(xué)生關(guān)系R(S#,Sn,Sd,Ss,C#,G)每個(gè)學(xué)生有唯一的一個(gè)學(xué)號(hào)，每個(gè)學(xué)生只有一個(gè)姓名（基本常識(shí)） S#→Sn每個(gè)學(xué)生均只屬一個(gè)系與一個(gè)專業(yè) S#→Sd S#→Ss每個(gè)學(xué)生修讀之每門課有且僅有一個(gè)成績 (S#，C#)→G各系無相同專業(yè) Ss→Sd332007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

定義8.2：平凡/非平凡函數(shù)依賴一個(gè)函數(shù)依賴關(guān)系X→Y如滿足Y

X，則稱此函數(shù)依賴是非平凡的函數(shù)依賴。否則，我們稱其為平凡函數(shù)依賴。如無特殊聲明，凡提到函數(shù)依賴時(shí)總認(rèn)為指的是非平凡的函數(shù)依賴。8.2.1函數(shù)依賴342007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

定義8.3：完全函數(shù)依賴在關(guān)系模式R(U)中，如有X

U，Y

U，滿足X→Y，且對(duì)任何X的真子集X'都有X'→Y，則稱Y完全函數(shù)依賴于X，并記作：XY定義8.4：部分函數(shù)依賴在關(guān)系模式R(U)中，如有X

U，Y

U，滿足X→Y，但Y不完全函數(shù)依賴于X，則稱Y部分依賴于X，并記作：XY8.2.1函數(shù)依賴pf352007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

同樣也會(huì)有(S#，Sn)Sd(S#，Sa)Sdpp8.2.1函數(shù)依賴?yán)纾涸趯W(xué)生S(S#,Sn,Sd,Ss,C#,G)中我們有：S#→Sd我們有：S#→Sd Ss→Sd同樣也會(huì)有(S#，Ss)Sdp362007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴定義8.5：傳遞函數(shù)依賴在關(guān)系模式R(U)中，如有X

U，Y

U，Z

U且滿足：X→Y，Y

X，Y→X，Y→Z，則稱Z傳遞函數(shù)依賴于X；否則，稱為非傳遞函數(shù)依賴（直接函數(shù)依賴）。為了使得函數(shù)依賴在表示形式上的簡單化，傳遞函數(shù)依賴與非傳遞函數(shù)依賴在表示形式上沒有區(qū)別。372007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

例如：在學(xué)生關(guān)系中增加一個(gè)屬性‘系的電話號(hào)碼Dt’S(S#,Sn,Sd,Ss,C#,G,Dt)每個(gè)系只登記唯一的一個(gè)電話號(hào)碼，則我們有：Sd→Dt8.2.1函數(shù)依賴由S#→Sd和Sd→Dt可得到傳遞FD：S#→Dt由S#→Ss和Ss→Sd可得到傳遞FD：S#→Sd382007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴Armstrong公理系統(tǒng)有關(guān)函數(shù)依賴的六條推理規(guī)則基本規(guī)則（3條）自反規(guī)則，增廣規(guī)則，傳遞規(guī)則擴(kuò)充規(guī)則（3條）分解規(guī)則，合并規(guī)則，偽傳遞規(guī)則FD的邏輯蘊(yùn)涵概念函數(shù)依賴集F的閉包：F+392007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

Armstrong公理系統(tǒng)基本推理規(guī)則規(guī)則R1：自反規(guī)則如果Y是X的子集，則：X→Y證明：設(shè)t1,t2是關(guān)系R中的兩個(gè)元組(t1R,t2R),且它們?cè)趯傩约疿上的值相等(t1[X]=t2[X])由于Y是X的子集，即Y

X因此必有t1[Y]=t2[Y]證畢.402007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

Armstrong公理系統(tǒng)基本推理規(guī)則規(guī)則R2：增廣規(guī)則如果X→Y，則：XZ→YZ證明：設(shè)t1R,t2R,如果t1[XZ]=t2[XZ],則：t1[X]=t2[X]………………(1)t1[Z]=t2[Z]………………(2)由(1)及X→Y得：

t1[Y]=t2[Y]………………(3)由(2)及(3)得：t1[YZ]=t2[YZ]證畢.412007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

Armstrong公理系統(tǒng)基本推理規(guī)則規(guī)則R3：傳遞規(guī)則如果X→Y，Y→Z，則：X→Z證明：設(shè)t1R,t2R,如果t1[X]=t2[X]……………(1)由(1)及X→Y得：t1[Y]=t2[Y]……………...(2)由(2)及Y→Z得：t1[Z]=t2[Z]證畢.422007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

Armstrong公理系統(tǒng)擴(kuò)充推理規(guī)則規(guī)則R4：分解規(guī)則如果X→YZ，則：X→Y證明：由自反規(guī)則R1得：YZ→Y由X→YZ,YZ→Y,根據(jù)傳遞規(guī)則R3得:X→Y證畢.432007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

Armstrong公理系統(tǒng)擴(kuò)充推理規(guī)則規(guī)則R5：合并規(guī)則如果X→Y且X→Z，則：X→YZ證明：使用增廣規(guī)則R2可作如下推導(dǎo)：由X→Y可得：XX→XY即X→XY………(1)由X→Z可得：XY→YZ……(2)由(1),(2)根據(jù)傳遞規(guī)則R3可得:X→YZ證畢.442007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

Armstrong公理系統(tǒng)擴(kuò)充推理規(guī)則規(guī)則R6：偽傳遞規(guī)則如果X→Y且WY→Z，則：WX→Z證明：使用增廣規(guī)則R2，由X→Y可得：WX→WY

………………(1)使用傳遞規(guī)則R3，由(1)及WY→Z可得:WX→Z證畢.452007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

Armstrong公理系統(tǒng)練習(xí)：請(qǐng)利用Armstrong公理系統(tǒng)證明下面的推導(dǎo)過程是否成立？如果不成立，請(qǐng)給出具體的例子關(guān)系。{WY,XZ}

{WXY}{XY}andZY

{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}參考答案462007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

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)能夠推出X→Y，則稱F邏輯蘊(yùn)涵X→Y，并記為：FX→Y函數(shù)依賴集F的閉包F+由被F邏輯蘊(yùn)涵的所有函數(shù)依賴關(guān)系構(gòu)成的集合被稱為函數(shù)依賴集F的閉包，并記為F+F+={X→Y│FX→Y}472007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴計(jì)算函數(shù)依賴集F={A→B,B→C}的閉包F+根據(jù)自反規(guī)則，下述函數(shù)依賴也是其閉包中的元素A→AB→BC→CAB→AAB→BAB→ABAC→AAC→CAC→ACBC→BBC→CBC→BCABC→AABC→BABC→CABC→ABABC→ACABC→BCABC→ABCF中的所有函數(shù)依賴都是其閉包中的元素，即：A→B∈F+B→C∈F+482007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

由A→B,B→C及傳遞規(guī)則可得到閉包中的下列元素A→C由A→B,A→C及合并規(guī)則可得到閉包中的下列元素A→BC由A→B及增廣規(guī)則可得到閉包中的下列元素A→ABAC→BCAC→ABC由B→C及增廣規(guī)則可得到閉包中的下列元素AB→ACB→BCAB→ABC由A→C及增廣規(guī)則可得到閉包中的下列元素A→ACAB→BC由A→BC及增廣規(guī)則可得到閉包中的下列元素A→ABC492007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

由AB→B,B→C及傳遞規(guī)則可得到閉包中的下列元素AB→C由AC→A,A→B及傳遞規(guī)則可得到閉包中的下列元素AC→B由AC→B及增廣規(guī)則可得到閉包中的下列元素AC→AB計(jì)算結(jié)果502007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴定義8.6：關(guān)鍵字（也稱為碼或key）在關(guān)系模式R(U,F)中，如有K

U且滿足：KU則稱K為R的關(guān)鍵字。f幾種不同的關(guān)鍵字候選關(guān)鍵字主關(guān)鍵字全關(guān)鍵字512007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.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的非主屬性522007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴如何尋找一個(gè)關(guān)系模式R(U,F)的關(guān)鍵字？fKU方法一：利用Armstrong公理系統(tǒng)中的推導(dǎo)規(guī)則，從已知的函數(shù)依賴集F中推導(dǎo)得到如下的函數(shù)依賴關(guān)系：缺點(diǎn)：依賴于對(duì)推導(dǎo)規(guī)則的熟練使用532007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

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)鍵字的定義來尋找關(guān)系的關(guān)鍵字可縮短算法8-2的計(jì)算過程542007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(1)

R(A,B,C,D)， F:{B

D,AB

C}解：由B→D及增廣規(guī)則R2可得：AB→AD……(1)由(1),AB→C及合并規(guī)則R5可得:AB→ACD…………………(2)由(2)及增廣規(guī)則R2可得：AB→ABCD完.552007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(2)

R(A,B,C)，F(xiàn):{A

B,B

A,A

C}解1：由A→B,A→C及合并規(guī)則R5可得：A→BC由A→BC及增廣規(guī)則R2可得：A→ABC完.解2：由B→A,A→C及傳遞規(guī)則R3可得：B→C由B→A,B→C及合并規(guī)則R5可得：B→AC由B→AC及增廣規(guī)則R2可得B→ABC完.562007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(3)

R(A,B,C,D)， F:{A

C,D

B}解：由A→C及增廣規(guī)則R2可得：AD→CD…(1)由D→B及增廣規(guī)則R2可得：AD→AB……(2)由(1),(2)及合并規(guī)則R5可得：AD→ABCD完.572007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴習(xí)題：尋找下述關(guān)系模式的關(guān)鍵字(4)

R(A,B,C,D)， F:{A

C,CD

B}解：由A→C及增廣規(guī)則R2可得：AD→CD…(1)由(1),CD→B及傳遞規(guī)則R3可得：AD→B由AD→B及增廣規(guī)則R2可得：AD→AB…………………(2)由(1),(2)及合并規(guī)則R5可得：AD→ABCD完.582007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴屬性集的閉包XF+（可以簡寫為X+）設(shè)F是關(guān)系模式R(U)上的函數(shù)依賴集，X是關(guān)系模式R(U)的屬性子集，由所有函數(shù)依賴于X的屬性所構(gòu)成的集合被稱為屬性集X在函數(shù)依賴集F上的閉包。X+={A│FX→A}592007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴算法8-1：計(jì)算屬性集X在函數(shù)依賴集F上的閉包XF+(簡寫為X+）X+:=X;repeatoldX+:=X+;foreachfunctionaldependencyYZinFdoifY

X+thenX+:=X+

Z;until(oldX+=X+)602007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

例：設(shè)

F={(f1)B→CD,(f2)AD→E,(f3)B→A}，請(qǐng)計(jì)算{B}F+?初始化：{B}F+={B}第一遍循環(huán)X=

{B}F+={B}f1

的決定因素是{B}F+的一個(gè)子集，所以{B}F+={B}F+∪{C,D}={B,C,D}f2的決定因素不是{B}F+的子集,因此f2

不影響本次循環(huán)的計(jì)算結(jié)果f3的決定因素是{B}F+的一個(gè)子集，所以{B}F+={B}F+∪{A}={A,B,C,D}X

{B}F+,回到步驟1)開始執(zhí)行第二遍循環(huán)612007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

第二遍循環(huán)X={B}F+={A,B,C,D}跳過在第一遍循環(huán)中已經(jīng)處理過的函數(shù)依賴(f1和f3)f2的決定因素是{B}F+的子集,所以{B}F+={B}F+∪{E}={A,B,C,D,E}X

{B}F+,回到步驟1)開始執(zhí)行第三遍循環(huán)F={(f1)B→CD,(f2)AD→E,(f3)B→A}622007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

第三遍循環(huán)X={B}F+={A,B,C,D,E}F中的所有函數(shù)依賴都已處理過（其依賴因素都已經(jīng)被并入到{B}F+中）因此在本次循環(huán)中{B}F+將不再發(fā)生變化，算法執(zhí)行結(jié)束返回{B}F+F={(f1)B→CD,(f2)AD→E,(f3)B→A}632007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

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è)真子集Z，都有：ZF+

U642007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

習(xí)題8.6–(1)：尋找下述關(guān)系模式的關(guān)鍵字 R(A,B,C,D) F:{B

D,AB

C};解：（方法一的計(jì)算過程）由B→D及增廣規(guī)則R2可得：AB→AD………(1)由(1),AB→C及合并規(guī)則R5可得:AB→ACD……(2)由(2)及增廣規(guī)則R2可得：AB→ABCD因?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)鍵字。 完.652007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴算法8-2：尋找關(guān)系模式R(U,F)的關(guān)鍵字KsetK:=R;foreachattributeAinK{compute(K–A)F+

;if(K–A)F+containsalltheattributesinR,then{setK:=K–{A};}}優(yōu)化算法662007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

習(xí)題8.6–(2)：尋找下述關(guān)系模式的關(guān)鍵字 R(A,B,C) F:{A

B,B

A,A

C};解1：K={A,B,C}∵{K–A}+={A,B,C}=U∴K=K–A={B,C}∵{K–B}+={C}U∴該關(guān)鍵字中必定含有屬性B∵{K–C}+={A,B,C}=U∴K=K–C={B} 最后得到該關(guān)系的一個(gè)關(guān)鍵字{B}解2：K={A,B,C}∵{K–B}+={A,B,C}=U∴K=K–B={A,C}∵{K–A}+={C}U∴該關(guān)鍵字中必定含有屬性A∵{K–C}+={A,B,C}=U∴K=K–C={A}最后得到該關(guān)系的另一個(gè)關(guān)鍵字{

A}672007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

習(xí)題8.6–(4)：尋找下述關(guān)系模式的關(guān)鍵字 R(A,B,C,D)

F:{A

C,CD

B}解1：K={A,B,C,D}∵(K–{A})+=({B,C,D})+={B,C,D}

U∴該關(guān)鍵字中必定含有屬性A∵(K–{B})+=({A,C,D})+=

{A,B,C,D}=U∴K=K–{B}={A,C,D}∵(K–{C})+=({A,D})+=

{A,B,C,D}=U∴K=K–{C}={A,D}∵(K–{D})+=({A})+=

{A,C}

U∴該關(guān)鍵字中必定含有屬性D最后得到該關(guān)系的一個(gè)關(guān)鍵字{A,D}682007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.1函數(shù)依賴習(xí)題8.6：692007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2規(guī)范化理論8.2.1函數(shù)依賴8.2.2與函數(shù)依賴有關(guān)的范式范式及模式分解方法1NF2NF3NFBCNF8.2.3多值依賴與第四范式702007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式定義：第一范式（1NF）如果關(guān)系模式R(U)中的每個(gè)屬性值都是一個(gè)不可分割的數(shù)據(jù)量，則稱該關(guān)系模式滿足第一范式，并記為：R1NF定義8.9：第二范式(2NF)設(shè)有關(guān)系模式R(U)∈1NF，且其每個(gè)非主屬性都完全函數(shù)依賴于關(guān)鍵字，則稱關(guān)系模式R(U)滿足第二范式，并記作：R∈2NF712007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式例：有一個(gè)學(xué)生關(guān)系SCG(S#,Sn,Sd,Ss,C#,G)，根據(jù)用戶給定的語義約束得到如下的函數(shù)依賴關(guān)系：基本常識(shí)：S#→Sn每個(gè)學(xué)生均只屬一個(gè)系與一個(gè)專業(yè)；S#→SdS#→Ss每個(gè)學(xué)生修讀之每門課有且僅有一個(gè)成績；(S#，C#)→G各系無相同專業(yè)。Ss→Sd722007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

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,Ss→Sd該關(guān)系模式是否滿足第二范式的要求？解題方法如下：找出該關(guān)系模式的所有(候選)關(guān)鍵字據(jù)此確定該關(guān)系的主屬性集和非主屬性集判斷每一個(gè)非主屬性和關(guān)鍵字之間的函數(shù)依賴關(guān)系是否滿足2NF的要求如果不存在非主屬性對(duì)關(guān)鍵字的部分依賴，那么SCG

2NF732007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

關(guān)系模式SCG(S#,Sn,Sd,Ss,C#,G)，函數(shù)依賴集為：S#→Sn,S#→Sd,S#→Ss,(S#,C#)→G,Ss→Sd找出該關(guān)系模式的所有(候選)關(guān)鍵字據(jù)此確定該關(guān)系的主屬性集和非主屬性集判斷每一個(gè)非主屬性和關(guān)鍵字之間的函數(shù)依賴關(guān)系是否滿足2NF的要求。(S#,

C#)主屬性集：{S#,C#}非主屬性集：{Sn,Sd,Ss,G}存在非主屬性對(duì)關(guān)鍵字的部分依賴，如：(S#,C#)→Sn因此，該關(guān)系不滿足2NF（只能滿足到1NF）742007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式采用SCG(S#,Sn,Sd,Ss,C#,G)的模式設(shè)計(jì)方案（僅滿足1NF的關(guān)系模式）會(huì)帶來什么樣的問題？數(shù)據(jù)冗余因數(shù)據(jù)冗余而產(chǎn)生更新異常為什么出現(xiàn)數(shù)據(jù)冗余現(xiàn)象？存在非主屬性對(duì)關(guān)鍵字的部分函數(shù)依賴如何避免上述的數(shù)據(jù)冗余現(xiàn)象？按照更高范式的要求設(shè)計(jì)關(guān)系模式：模式分解752007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式圖1：根據(jù)關(guān)系模式SCG所建立的數(shù)據(jù)庫（僅滿足1NF）762007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式為了使最終的模式設(shè)計(jì)結(jié)果能夠滿足到2NF，我們可以對(duì)關(guān)系SCG進(jìn)行模式分解，將其屬性集合分解構(gòu)成若干個(gè)小的關(guān)系模式。隨著對(duì)原有關(guān)系模式的分解，原來在關(guān)系模式SCG上存在的函數(shù)依賴集合也被分解到若干個(gè)小的關(guān)系模式上去。模式分解的目標(biāo)使得分解得到的每個(gè)小的關(guān)系模式都能夠滿足2NF的要求。從而消除因非主屬性對(duì)關(guān)鍵字的部分函數(shù)依賴而產(chǎn)生的數(shù)據(jù)冗余現(xiàn)象.772007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

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è)分解(position)Head(R)=Head(R1)∪Head(R2)∪…∪Head(Rk)

設(shè)子關(guān)系Ri上的函數(shù)依賴集為Fi(i=1,2,…,k),則：Fi={XYXYF+且(X∪Y)Head(Ri)}782007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式關(guān)系的規(guī)范化過程就是一個(gè)不斷進(jìn)行模式分解的過程。通過模式分解可以消除原有關(guān)系模式中那些不好的函數(shù)依賴關(guān)系（即不滿足更高范式要求的函數(shù)依賴關(guān)系），以盡可能地解決原有模式中所存在的數(shù)據(jù)冗余和各種插入、刪除異?，F(xiàn)象。792007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式模式分解的方法設(shè)存在一個(gè)關(guān)系模式R,其屬性集合為Head(R),F是其函數(shù)依賴集。將其分解到滿足范式M的步驟如下：找出所有不滿足范式M要求的函數(shù)依賴關(guān)系選擇一個(gè)不符合要求的函數(shù)依賴關(guān)系作如下的分解：假設(shè)XYF+且不滿足范式M的要求，則我們將關(guān)系模式R分解為如下的兩個(gè)子關(guān)系：R1(XY,{XY})R2(Head(R)–Y,F2)，其中：F2={ABABF+且(A∪B)Head(R2)}f802007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式模式分解的方法(cont.)對(duì)于分解得到的子關(guān)系模式R2重復(fù)上述的步驟1)和步驟2)，直到所有的子關(guān)系模式都能滿足范式M的要求合并那些具有相同關(guān)鍵字的子關(guān)系模式812007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式利用前面介紹的分解方法對(duì)關(guān)系模式SCG進(jìn)行規(guī)范化（分解到滿足2NF）f不符合2NF要求的函數(shù)依賴關(guān)系具有以下特征：XY，Y是關(guān)系SCG的非主屬性，而X則是其某個(gè)候選關(guān)鍵字的真子集函數(shù)依賴集Ff1:S#→Snf2:S#→Sdf3:S#→Ssf4:(S#,C#)→Gf5:Ss→Sd非主屬性集{

Sn,Sd,Ss,G

}主屬性集{

S#,C#}關(guān)鍵字K(S#,C#)822007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式分解過程(1)在關(guān)系SCG(U={S#,Sn,Sd,Ss,C#,G})中找出所有不滿足2NF要求的函數(shù)依賴f1:S#→Snf2:S#→Sdf3: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:Ss→Sd})832007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式分解過程(2)在關(guān)系R0(U0={S#,Sd,Ss,C#,G},F0)中找出所有不滿足2NF要求的函數(shù)依賴f2:S#→Sdf3: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})842007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式分解過程(3)在關(guān)系R0(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})852007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式綜合前面的分解結(jié)果R1(U1={S#,Sn},F1={f1:S#→Sn})R2(U2={S#,Sd},F2={f2: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)滿足2NF862007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

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,

f5:

Ss→Sd }872007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式圖2：根據(jù)關(guān)系模式SCG1和SCG2所建立的數(shù)據(jù)庫（可以滿足到2NF）882007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式在關(guān)系SCG2中仍然存在數(shù)據(jù)冗余（專業(yè)Ss與系別Sd之間的對(duì)應(yīng)關(guān)系），以及因此而產(chǎn)生的更新異?，F(xiàn)象原因：存在非主屬性對(duì)關(guān)鍵字的傳遞依賴892007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式定義8.10：第三范式(3NF)設(shè)有關(guān)系模式R(U)∈2NF，且其每個(gè)非主屬性都不傳遞函數(shù)依賴于關(guān)鍵字，則稱關(guān)系模式R(U)滿足第三范式，并記作：R∈3NF不符合3NF要求的函數(shù)依賴關(guān)系具有如下特征：XY，Y是關(guān)系SCG的非主屬性，而X并不是關(guān)鍵字，或者X只是關(guān)鍵字的一個(gè)真子集f902007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式分解到滿足3NFSCG1({S#,C#,G},{(S#,C#)→G})已滿足3NFSCG2({S#,Sn,Sd,Ss}, {S#→Sn,S#→Ss,Ss→Sd})關(guān)鍵字：S#存在非主屬性Sd對(duì)關(guān)鍵字的傳遞依賴：S#→Ss,Ss→S#,Ss→Sd?S#→Sd912007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式將SCG2分解到滿足3NFSCG2(S#,Sn,Sd,Ss)的分解結(jié)果如下：SCG21(S#,Sn,Ss),其函數(shù)依賴集是：{S#→Sn,S#→Ss}SCG22(Sd,Ss),其函數(shù)依賴集是：{Ss→Sd}922007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式圖3：符合3NF要求的模式設(shè)計(jì)932007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式定義8.11：BCNF設(shè)關(guān)系模式R(U)滿足1NF，且若X

Y時(shí)X必包含有該關(guān)系模式的關(guān)鍵字，則稱關(guān)系模式R(U)滿足BCNF范式，并記作：R∈BCNF942007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式例8.1設(shè)有關(guān)系模式R(S,C,T)，其中S,C含義同前,T表示教師，R有下列語義信息：每個(gè)教師僅上一門課T→C學(xué)生與課程確定后，教師即惟一確定(S,C)→T思考題：關(guān)系模式R的關(guān)鍵字是什么？關(guān)系模式R的主屬性集是什么？非主屬性集又是什么？該關(guān)系模式R最高能夠滿足到第幾范式？952007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式關(guān)系R最高能夠滿足到第幾范式？R({S,C,T},{T→C,(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范式要求的函數(shù)依賴，因此該關(guān)系模式一定可以滿足到3NF。962007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式關(guān)系模式R是否能夠滿足BCNF？R({S,C,T},{T→C,(S,C)→T})候選關(guān)鍵字：{

S,C}和{

S,T}存在不滿足BCNF要求的函數(shù)依賴:T→C因此不滿足BCNF分解到滿足BCNF范式R1(C,T) 函數(shù)依賴集：{

T→C

}R2(S,T) 函數(shù)依賴集：{

}972007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.2與函數(shù)依賴有關(guān)的范式定理8-1如果關(guān)系模式R(U)

BCNF，則R(U)

3NF證明：假設(shè)R(U)3NF,則有三種可能性：R(U)1NFR(U)2NF，即：存在一個(gè)非主屬性部分依賴于關(guān)鍵字R(U)3NF，即：存在一個(gè)非主屬性傳遞依賴于關(guān)鍵字982007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

定理8-1之證明(2)假設(shè)存在一個(gè)非主屬性A部分依賴于關(guān)鍵字K，即：KA（AK）p假設(shè)R(U)1NF由R(U)BCNF可知：R(U)1NF。與假設(shè)相矛盾。由部分依賴的定義可知：必存在K的某個(gè)真子集W，且滿足：W→A（AW）由R(U)BCNF及BCNF定義可知：W中必含有關(guān)鍵字，即關(guān)鍵字K中含有另一個(gè)關(guān)鍵字W，且WK，這與關(guān)鍵字的定義相矛盾。由W→A及R(U)BCNF可知：W中必含有關(guān)鍵字Z由關(guān)鍵字的定義可知：Z→U因?yàn)閆W,K

U，故W→K。992007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

(3)假設(shè)存在一個(gè)非主屬性A傳遞依賴于關(guān)鍵字K，即存在一個(gè)屬性集合W，并滿足：K→W，WK，W→K，W→A這與W→K相矛盾。綜上所述，假設(shè)不成立，即R(U)3NF證畢.定理8-1之證明1002007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2規(guī)范化理論8.2.1函數(shù)依賴8.2.2與函數(shù)依賴有關(guān)的范式8.2.3多值依賴與第四范式多值依賴與MVD有關(guān)的推理規(guī)則4NF1012007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.3多值依賴與第四范式1.一個(gè)多值依賴的例子 例子8.2：設(shè)有一個(gè)課程關(guān)系R，其示意圖用表8.5表示。此表表示‘高等數(shù)學(xué)’這門課(C)的任課教師(T)有3個(gè)，它的參考書(L)可以有2本；‘普通物理’這門課(C)的任課教師(T)也有3個(gè)，它的參考書(L)可以有3本。課程名C教師名T選用參考書L高等數(shù)學(xué)李華民王天華林靜高等數(shù)學(xué)高等數(shù)學(xué)教程普通物理吳鐵鋼謝曉芳徐秋芳物理學(xué)普通物理普通物理基礎(chǔ)表8.5關(guān)系R的示意圖1022007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

CTL高等數(shù)學(xué)李華民高等數(shù)學(xué)高等數(shù)學(xué)李華民高等數(shù)學(xué)教程高等數(shù)學(xué)王天華高等數(shù)學(xué)高等數(shù)學(xué)王天華高等數(shù)學(xué)教程高等數(shù)學(xué)林靜高等數(shù)學(xué)高等數(shù)學(xué)林靜高等數(shù)學(xué)教程普通物理吳鐵鋼物理學(xué)普通物理吳鐵鋼普通物理普通物理吳鐵鋼普通物理基礎(chǔ)普通物理謝曉芳物理學(xué)普通物理謝曉芳普通物理普通物理謝曉芳普通物理基礎(chǔ)普通物理徐秋芳物理學(xué)普通物理徐秋芳普通物理普通物理徐秋芳普通物理基礎(chǔ)缺點(diǎn)數(shù)據(jù)大量冗余存儲(chǔ)表8.6關(guān)系Ｒ特點(diǎn)一個(gè)C的值與一組T的值相對(duì)應(yīng)這組T的值與其它屬性(L)的值無關(guān)如果將表8.5用標(biāo)準(zhǔn)的關(guān)系形式來表示，如表8.6所示。1032007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

特點(diǎn)1)一個(gè)C的值與一組T的值相對(duì)應(yīng)2)這組T的值與該關(guān)系中的其它屬性（L）的值無關(guān)‘高等數(shù)學(xué)’對(duì)應(yīng){‘李華民’，‘王天華’，‘林靜’}‘普通物理’對(duì)應(yīng){‘吳鐵鋼’，‘謝曉芳’，‘徐秋芳’}即：設(shè)t1,

t2是關(guān)系R中的兩個(gè)元組(t1R,t2R)，且t1[C]=t2[C]，則互換這兩個(gè)元組在屬性L上的取值所構(gòu)成的兩個(gè)新的元組：t3：(t1[C],t1[T],t2[L])t4：(

t2[C],t2[T],t1[L])也必定是關(guān)系R中的元組(即：t3R,t4R)在這里并沒有區(qū)別t1,t2,t3,t4是不是相同的元組。1042007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.3多值依賴與第四范式2.【定義8-12】多值依賴(MVD)設(shè)有關(guān)系模式R(U)，X,Y是U的子集(X,Y

U)，若對(duì)R(U)的任何一個(gè)關(guān)系r，對(duì)X的一個(gè)確定值，存在Y的一組值與之對(duì)應(yīng)，且Y的這組值又與Z=U-X-Y中的屬性值不相關(guān)，此時(shí)稱Y多值依賴于X，并記為：X→→Y1052007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.3多值依賴與第四范式多值依賴產(chǎn)生的原因在一個(gè)關(guān)系模式中，若存在兩個(gè)相互獨(dú)立的屬性之間的‘一對(duì)多’函數(shù)對(duì)應(yīng)關(guān)系，如：C與T的‘一對(duì)多’函數(shù)對(duì)應(yīng)關(guān)系C與L之間的‘一對(duì)多’函數(shù)對(duì)應(yīng)關(guān)系而T和L之間又沒有任何依賴關(guān)系，此時(shí)若把它們合并起來構(gòu)成一個(gè)關(guān)系，即R(C,T,L)，則就會(huì)產(chǎn)生多值依賴現(xiàn)象。1062007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

CTL高等數(shù)學(xué)李華民高等數(shù)學(xué)高等數(shù)學(xué)李華民高等數(shù)學(xué)教程高等數(shù)學(xué)王天華高等數(shù)學(xué)高等數(shù)學(xué)王天華高等數(shù)學(xué)教程高等數(shù)學(xué)林靜高等數(shù)學(xué)高等數(shù)學(xué)林靜高等數(shù)學(xué)教程………在表8.6中我們可以看到：若存在兩個(gè)元組(第2和第3個(gè)元組)，它們?cè)贑上的取值相同(高等數(shù)學(xué))，但在T上的取值不同(李華民,王天華)1072007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

CTL高等數(shù)學(xué)李華民高等數(shù)學(xué)高等數(shù)學(xué)李華民高等數(shù)學(xué)教程高等數(shù)學(xué)王天華高等數(shù)學(xué)高等數(shù)學(xué)王天華高等數(shù)學(xué)教程高等數(shù)學(xué)林靜高等數(shù)學(xué)高等數(shù)學(xué)林靜高等數(shù)學(xué)教程………那么：互換它們?cè)贚上的取值(高等數(shù)學(xué),高等數(shù)學(xué)教程)，產(chǎn)生的新元組（元組1和元組4）一定也出現(xiàn)在關(guān)系R中。1082007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

CTL高等數(shù)學(xué)李華民高等數(shù)學(xué)高等數(shù)學(xué)李華民高等數(shù)學(xué)教程高等數(shù)學(xué)王天華高等數(shù)學(xué)高等數(shù)學(xué)王天華高等數(shù)學(xué)教程高等數(shù)學(xué)林靜高等數(shù)學(xué)高等數(shù)學(xué)林靜高等數(shù)學(xué)教程普通物理吳鐵鋼物理學(xué)普通物理吳鐵鋼普通物理普通物理吳鐵鋼普通物理基礎(chǔ)普通物理謝曉芳物理學(xué)普通物理謝曉芳普通物理普通物理謝曉芳普通物理基礎(chǔ)普通物理徐秋芳物理學(xué)普通物理徐秋芳普通物理普通物理徐秋芳普通物理基礎(chǔ)表8.6關(guān)系Ｒ在表8.6中我們可以看到：每一門課程C（高等數(shù)學(xué)）都對(duì)應(yīng)著一組教師T（李華民，王天華，林靜）。那么對(duì)于T的每個(gè)取值，都必須重復(fù)地與同這個(gè)C上的值相關(guān)的L上的每個(gè)值(高等數(shù)學(xué),高等數(shù)學(xué)教程)相匹配，因此在關(guān)系R內(nèi)出現(xiàn)了一個(gè)多值屬性，產(chǎn)生了數(shù)據(jù)冗余。1092007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

如果如例8.2那樣，用表8.5來表示上述的關(guān)系，那么就不會(huì)出現(xiàn)前述的數(shù)據(jù)冗余現(xiàn)象。但表8.5是不符合1NF的要求的。因此，在關(guān)系數(shù)據(jù)庫中，因?yàn)?NF的要求而產(chǎn)生了多值依賴！課程名C教師名T選用參考書L高等數(shù)學(xué)李華民王天華林靜高等數(shù)學(xué)高等數(shù)學(xué)教程普通物理吳鐵鋼謝曉芳徐秋芳物理學(xué)普通物理普通物理基礎(chǔ)表8.5關(guān)系R的示意圖1102007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

8.2.3多值依賴與第四范式3非平凡的多值依賴【定義】設(shè)在關(guān)系模式R(U)中，X→→Y且U-X-Y，則稱X→→Y是非平凡的多值依賴，否則稱為平凡的多值依賴?！纠吭陉P(guān)系模式S(S#,Sn,Sd)中，三個(gè)屬性分別是學(xué)號(hào)、姓名和學(xué)生所在的系。請(qǐng)問：在該關(guān)系模式中存在哪些MVD？如果存在MVD，請(qǐng)指出是平凡的MVD，還是非平凡的MVD？1112007年度-教育部-IBM精品課程-南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系

關(guān)系模式：S(S#,Sn,Sd)S#→→SnS#→→SdSn→→S#Sn→→SdSd→→S#Sd→→SnS#→→(Sn,Sd)Sn→→(S#,Sd)Sd→→(S#,Sn)(S#,