關(guān)系模式設(shè)計(jì)理論

關(guān)系模式設(shè)計(jì)理論第一頁，共一百零二頁，2022年，8月28日第三章關(guān)系模式設(shè)計(jì)理論教學(xué)重點(diǎn)：概念模式轉(zhuǎn)換成關(guān)系模式的的方法，數(shù)據(jù)依賴，關(guān)系規(guī)范化理論，關(guān)系模式的分解方法。教學(xué)難點(diǎn)：關(guān)系規(guī)范化理論，關(guān)系模式的分解方法。教學(xué)時(shí)數(shù)：8學(xué)時(shí)。第二頁，共一百零二頁，2022年，8月28日教學(xué)內(nèi)容一、數(shù)據(jù)依賴二、數(shù)據(jù)依賴的公理系統(tǒng)三、關(guān)系模式的規(guī)范形式四、關(guān)系模式規(guī)范化方法第三頁，共一百零二頁，2022年，8月28日一、關(guān)系數(shù)據(jù)庫設(shè)計(jì)理論(一)問題的提出針對具體問題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設(shè)計(jì)的工具──關(guān)系數(shù)據(jù)庫的規(guī)范化理論一個(gè)初始的邏輯關(guān)系模式存在著很多問題舉例：第四頁，共一百零二頁，2022年，8月28日S#(*)C#(*)CnameTname01C1C語言張一02C1C語言張一03C3B語言張三04C4Java張四異常問題:1、數(shù)據(jù)冗余2、修改異常3、插入異常4、刪除異常分解是解決冗余的主要方法第五頁，共一百零二頁，2022年，8月28日(二)函數(shù)依賴一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴第六頁，共一百零二頁，2022年，8月28日一、函數(shù)依賴定義:設(shè)R(U)是一個(gè)屬性集U上的關(guān)系模式，X和Y是U的子集。若對于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數(shù)確定Y”

或“Y函數(shù)依賴于X”，記作X→Y。X稱為這個(gè)函數(shù)依賴的決定屬性集(Determinant)。第七頁，共一百零二頁，2022年，8月28日說明：

1.函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。2.函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。例如“姓名→年齡”這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立3.數(shù)據(jù)庫設(shè)計(jì)者可以對現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名→年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在，則拒絕裝入該元組。第八頁，共一百零二頁，2022年，8月28日函數(shù)依賴（續(xù)）例:Student(Sno,Sname,Ssex,Sage,Sdept)

假設(shè)不允許重名，則有:Sno→Ssex，Sno→Sage,Sno→Sdept，Sno←→Sname,Sname→Ssex，Sname→SageSname→Sdept但Ssex→Sage若X→Y，并且Y→X,則記為X←→Y。若Y不函數(shù)依賴于X,則記為X─→Y。第九頁，共一百零二頁，2022年，8月28日二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對于U的子集X和Y，如果X→Y，但YX，則稱X→Y是非平凡的函數(shù)依賴若X→Y，但YX,則稱X→Y是平凡的函數(shù)依賴?yán)涸陉P(guān)系SC(Sno,Cno,Grade)中，非平凡函數(shù)依賴：(Sno,Cno)→

Grade

平凡函數(shù)依賴：(Sno,Cno)→

Sno(Sno,Cno)→Cno第十頁，共一百零二頁，2022年，8月28日平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）對于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明，我們總是討論非平凡函數(shù)依賴。第十一頁，共一百零二頁，2022年，8月28日三、完全函數(shù)依賴與部分函數(shù)依賴定義在關(guān)系模式R(U)中，如果X→Y，并且對于X的任何一個(gè)真子集X’，都有X’Y,則稱Y完全函數(shù)依賴于X，記作Xｆ

Y。若X→Y，但Y不完全函數(shù)依賴于X，則稱Y部分函數(shù)依賴于X，記作XPY。

第十二頁，共一百零二頁，2022年，8月28日完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）例:在關(guān)系SC(Sno,Cno,Grade)中，由于：Sno→Grade，Cno→Grade，因此：(Sno,Cno)ｆGrade

第十三頁，共一百零二頁，2022年，8月28日四、傳遞函數(shù)依賴定義5.3在關(guān)系模式R(U)中，如果X→Y，Y→Z，且YX，Y→X，則稱Z傳遞函數(shù)依賴于X。注:如果Y→X，即X←→Y，則Z直接依賴于X。例:在關(guān)系Std(Sno,Sdept,Mname)中，有：

Sno→Sdept，Sdept→MnameMname傳遞函數(shù)依賴于Sno第十四頁，共一百零二頁，2022年，8月28日碼定義5.4設(shè)K為關(guān)系模式R<U,F>中的屬性或?qū)傩越M合。若KｆU，則K稱為R的一個(gè)侯選碼（CandidateKey）。若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼（Primarykey）。主屬性與非主屬性ALLKEY第十五頁，共一百零二頁，2022年，8月28日外部碼關(guān)系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的外部碼（Foreignkey）也稱外碼主碼又和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。第十六頁，共一百零二頁，2022年，8月28日四、關(guān)系模式的規(guī)范形式范式是符合某一種級別的關(guān)系模式的集合。關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式。范式的種類：

第一范式(1NF)

第二范式(2NF)

第三范式(3NF) BC范式(BCNF)

第四范式(4NF)

第五范式(5NF)第十七頁，共一百零二頁，2022年，8月28日四、關(guān)系模式的規(guī)范形式各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡記為R∈nNF。第十八頁，共一百零二頁，2022年，8月28日四、關(guān)系模式的規(guī)范形式1、第一范式（1NF）2、第二范式（2NF）3、第三范式（3NF）4、BC范式（BCNF）5、多值依賴與第四范式（4NF）6、規(guī)范化第十九頁，共一百零二頁，2022年，8月28日第一范式1NF1NF的定義 如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R∈1NF。第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫。但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。第二十頁，共一百零二頁，2022年，8月28日1NF例:關(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第二十一頁，共一百零二頁，2022年，8月28日

1NFSLC的碼為(Sno,Cno)SLC滿足第一范式。非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno,Cno)SnoCnoGradeSdeptSlocSLC第二十二頁，共一百零二頁，2022年，8月28日SLC不是一個(gè)好的關(guān)系模式存在的問題:插入異常刪除異常數(shù)據(jù)冗余度大(4)修改復(fù)雜

第二十三頁，共一百零二頁，2022年，8月28日

1NF原因

Sdept、Sloc部分函數(shù)依賴于碼。解決方法

SLC分解為兩個(gè)關(guān)系模式，以消除這些部分函數(shù)依賴

SC（Sno，Cno，Grade）

SL（Sno，Sdept，Sloc）第二十四頁，共一百零二頁，2022年，8月28日2NF函數(shù)依賴圖：SnoCnoGradeSCSLSnoSdeptSloc第二十五頁，共一百零二頁，2022年，8月28日第二范式2NF2NF的定義 定義若關(guān)系模式R∈1NF，并且每一個(gè)非主屬性都完全函數(shù)依賴于R的碼，則R∈2NF。 例：SLC(Sno,Sdept,Sloc,Cno,Grade)∈1NFSLC(Sno,Sdept,Sloc,Cno,Grade)∈2NF SC（Sno，Cno，Grade）∈2NF SL（Sno，Sdept，Sloc）∈2NF第二十六頁，共一百零二頁，2022年，8月28日第二范式（續(xù)）采用投影分解法將一個(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ù)冗余。第二十七頁，共一百零二頁，2022年，8月28日2NF例：2NF關(guān)系模式SL(Sno,Sdept,Sloc)中函數(shù)依賴：

Sno→SdeptSdept→SlocSno→Sloc Sloc傳遞函數(shù)依賴于Sno，即SL中存在非主屬性對碼的傳遞函數(shù)依賴。第二十八頁，共一百零二頁，2022年，8月28日

2NF函數(shù)依賴圖：SLSnoSdeptSloc第二十九頁，共一百零二頁，2022年，8月28日

2NF解決方法采用投影分解法，把SL分解為兩個(gè)關(guān)系模式，以消除傳遞函數(shù)依賴：SD（Sno，Sdept）

DL（Sdept，Sloc）SD的碼為Sno，DL的碼為Sdept。第三十頁，共一百零二頁，2022年，8月28日

3NFSD的碼為Sno，DL的碼為Sdept。SnoSdeptSDSdeptSlocDL第三十一頁，共一百零二頁，2022年，8月28日第三范式3NF3NF的定義 定義關(guān)系模式R<U，F(xiàn)>

中若不存在這樣的碼X、屬性組Y及非主屬性Z（ZY）,使得X→Y，Y→X，Y→Z，成立，則稱R<U，F(xiàn)>∈3NF。例，SL(Sno,Sdept,Sloc)∈2NFSL(Sno,Sdept,Sloc)∈3NFSD（Sno，Sdept）∈3NFDL（Sdept，Sloc）∈3NF第三十二頁，共一百零二頁，2022年，8月28日

3NF若R∈3NF，則R的每一個(gè)非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。如果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ù)冗余。第三十三頁，共一百零二頁，2022年，8月28日以下數(shù)據(jù)表為幾范式S(sno,sname,cno,cname,grade)圖書表(書號,名字,書類別,類別名字)學(xué)生表(學(xué)號,姓名,班級,輔導(dǎo)員)第三十四頁，共一百零二頁，2022年，8月28日BC范式（BCNF）定義5.9設(shè)關(guān)系模式R<U，F(xiàn)>∈1NF，如果對于R的每個(gè)函數(shù)依賴X→Y，若Y不屬于X，則X必含有候選碼，那么R∈BCNF。若R∈BCNF每一個(gè)決定屬性集（因素）都包含（候選）碼R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼R∈3NF（證明）若R∈3NF則R不一定∈BCNF第三十五頁，共一百零二頁，2022年，8月28日

BCNF例：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱：

(S，J)→T，(S，T)→J，T→J第三十六頁，共一百零二頁，2022年，8月28日

BCNF

SJTSTJSTJ第三十七頁，共一百零二頁，2022年，8月28日BCNFSTJ∈3NF

(S，J)和(S，T)都可以作為候選碼

S、T、J都是主屬性STJ∈BCNFT→J，T是決定屬性集，T不是候選碼第三十八頁，共一百零二頁，2022年，8月28日BCNF

解決方法：將STJ分解為二個(gè)關(guān)系模式：

SJ(S，J)∈BCNF，TJ(T，J)∈BCNF

沒有任何屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJ第三十九頁，共一百零二頁，2022年，8月28日3NF與BCNF的關(guān)系如果關(guān)系模式R∈BCNF，必定有R∈3NF如果R∈3NF，且R只有一個(gè)候選碼，則R必屬于BCNF。第四十頁，共一百零二頁，2022年，8月28日復(fù)習(xí)1NF:每個(gè)表的每個(gè)屬性是不可再分的”最小列名”2NF:屬于1NF,且表中不存在”非主屬性”對碼的”部分函數(shù)依賴”3NF:屬于2NF且不存在”非主屬性”對碼的”傳遞函數(shù)依賴”第四十一頁，共一百零二頁，2022年，8月28日判定范式的技巧1.主碼為單列屬性的表一定是2NF2.屬于2NF且非主屬性只有0-1個(gè)，一定是3NF3.二元關(guān)系一定是3NF4.只要是抽象的關(guān)系一定是1NF第四十二頁，共一百零二頁，2022年，8月28日

例:2004年數(shù)據(jù)庫系統(tǒng)工程師考試題：答：D第四十三頁，共一百零二頁，2022年，8月28日BCNF的關(guān)系模式所具有的性質(zhì)⒈所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼⒉所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選碼⒊沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性第四十四頁，共一百零二頁，2022年，8月28日三、數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含 定義5.11對于滿足一組函數(shù)依賴

F的關(guān)系模式R<U，F(xiàn)>，其任何一個(gè)關(guān)系r，若函數(shù)依賴X→Y都成立,則稱

F邏輯蘊(yùn)含X→Y第四十五頁，共一百零二頁，2022年，8月28日Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴第四十六頁，共一百零二頁，2022年，8月28日1.Armstrong公理系統(tǒng)關(guān)系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：Al.自反律（Reflexivity）：若Y

X

U，則X→Y為F所蘊(yùn)含。A2.增廣律（Augmentation）：若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F第四十七頁，共一百零二頁，2022年，8月28日（l）自反律:若Y

X

U，則X→Y為F所蘊(yùn)含證:設(shè)Y

X

U

對R<U，F(xiàn)>

的任一關(guān)系r中的任意兩個(gè)元組t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得證Armstrong推理規(guī)則是正確的第四十八頁，共一百零二頁，2022年，8月28日(2)增廣律:若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。證：設(shè)X→Y為F所蘊(yùn)含，且Z

U。設(shè)R<U，F(xiàn)>

的任一關(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)含.增廣律得證。第四十九頁，共一百零二頁，2022年，8月28日(3)傳遞律：若X→Y及Y→Z為F所蘊(yùn)含，則

X→Z為F所蘊(yùn)含。證：設(shè)X→Y及Y→Z為F所蘊(yùn)含。對R<U，F(xiàn)>

的任一關(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)含.傳遞律得證。第五十頁，共一百零二頁，2022年，8月28日2.導(dǎo)出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則：合并規(guī)則：由X→Y，X→Z，有X→YZ。偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。分解規(guī)則：由X→Y及ZY，有X→Z。第五十一頁，共一百零二頁，2022年，8月28日設(shè)關(guān)系模式R（ABCDE），F(xiàn)是R上成立的FD集，F(xiàn)=（AB→C,CD→E,DE→B),試判斷AB是R的候選碼？ABD呢？第五十二頁，共一百零二頁，2022年，8月28日有關(guān)系模式R（ABC），F(xiàn)是R上成立的FD集，F(xiàn)=(C→B,B→A),該關(guān)系是幾范式第五十三頁，共一百零二頁，2022年，8月28日3.函數(shù)依賴閉包定義3.7在關(guān)系模式R<U，F(xiàn)>中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作F的閉包，記為F+。定義4.13設(shè)F為屬性集U上的一組函數(shù)依賴，X

U，

XF+={A|X→A能由F根據(jù)Armstrong公理導(dǎo)出}，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包第五十四頁，共一百零二頁，2022年，8月28日關(guān)于閉包的引理引理3.4

設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y

U，X→Y能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y

XF+用途將判定X→Y是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+

，判定Y是否為XF+的子集的問題第五十五頁，共一百零二頁，2022年，8月28日求閉包的算法算法3.1求屬性集X（X

U）關(guān)于U上的函數(shù)依賴集F的閉包XF+

輸入：X，F(xiàn)輸出：XF+步驟：（1）令X（0）=X，i=0（2）求B，這里B={A|(

V)(

W)(V→WF∧VX（i）∧A

W)}；（3）X（i+1）=B∪X（i）

第五十六頁，共一百零二頁，2022年，8月28日算法3.1（4）判斷X（i+1）=X

（i）嗎?（5）若相等或X（i）=U,則X（i）就是XF+,

算法終止。（6）若否，則i=i+l，返回第（2）步。對于算法3.l，令ai=|X（i）|，{ai

}形成一個(gè)步長大于1的嚴(yán)格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會終止。第五十七頁，共一百零二頁，2022年，8月28日函數(shù)依賴閉包[例1]已知關(guān)系模式R<U，F(xiàn)>，其中U={A，B，C，D，E}；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ù)依賴。得到兩個(gè)：

AB→C，B→D。于是X（1）=AB∪CD=ABCD。第五十八頁，共一百零二頁，2022年，8月28日函數(shù)依賴閉包(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。第五十九頁，共一百零二頁，2022年，8月28日函數(shù)依賴閉包練習(xí)：給定關(guān)系模式R（U，F(xiàn)），U={A，B，C，D，E}，F(xiàn)={B->A,D->A,A->E,AC->B},其屬性AD的閉包為______,其候選關(guān)鍵字為___.答案：AD的閉包為：ADE其候選關(guān)鍵字為：CD

第六十頁，共一百零二頁，2022年，8月28日4.Armstrong公理系統(tǒng)的有效性與完備性定理3.4Armstrong的公理系統(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不能用Armstrong公理推導(dǎo)出來，

f∈F+第六十一頁，共一百零二頁，2022年，8月28日有效性與完備性的證明證明： 1.有效性2.完備性 只需證明逆否命題:若函數(shù)依賴X→Y不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含分三步證明：第六十二頁，共一百零二頁，2022年，8月28日5.函數(shù)依賴集等價(jià) 定義6.2.9如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。第六十三頁，共一百零二頁，2022年，8月28日函數(shù)依賴集等價(jià)的充要條件 引理6.2.3F+=G+的充分必要條件是

F

G+，和G

F+證:必要性顯然，只證充分性。（1）若FG+，則XF+

XG++。（2）任取X→YF+則有Y

XF+

XG++。 所以X→Y(G+）+=G+。即F+

G+。（3）同理可證G+

F+，所以F+=G+。第六十四頁，共一百零二頁，2022年，8月28日函數(shù)依賴集等價(jià)要判定F

G+，只須逐一對F中的函數(shù)依賴X→Y，考察Y是否屬于XG++

就行了。因此引理5.3給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。第六十五頁，共一百零二頁，2022年，8月28日6.最小依賴集定義3.10如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。

(1)F中任一函數(shù)依賴的右部僅含有一個(gè)屬性。

(2)F中不存在這樣的函數(shù)依賴X→A，使得F與 F-{X→A}等價(jià)。

(3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價(jià)。第六十六頁，共一百零二頁，2022年，8月28日最小依賴集[例2]對于關(guān)系模式S<U，F(xiàn)>，其中：

U={SNO，SDEPT，MN，CNAME，G}，

F={SNO→SDEPT，SDEPT→MN，（SNO，CNAME）→G}

設(shè)F’={SNO→SDEPT，SNO→MN，

SDEPT→MN，(SNO，CNAME)→G，

(SNO，SDEPT)→SDEPT}F是最小覆蓋，而F’不是。因?yàn)椋篎’-{SNO→MN}與F’等價(jià)

F’-{(SNO，SDEPT)→SDEPT}也與F’等價(jià)

F’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也與F’等價(jià)第六十七頁，共一百零二頁，2022年，8月28日7.極小化過程定理6.2.5每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集證:構(gòu)造性證明，依據(jù)定義分三步對F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2

…Ak，k>2，則用{X→Aj

|j=1，2，…，k}來取代X→Y。

引理5.1保證了F變換前后的等價(jià)性。第六十八頁，共一百零二頁，2022年，8月28日極小化過程(2)逐一檢查F中各函數(shù)依賴FDi：X→A，令G=F-{X→A}，若AXG+，則從F中去掉此函數(shù)依賴。由于F與G=F-{X→A}等價(jià)的充要條件是AXG+

因此F變換前后是等價(jià)的。第六十九頁，共一百零二頁，2022年，8月28日極小化過程(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à)的充要條件是AZF+，其中Z=X-Bi

因此F變換前后是等價(jià)的。第七十頁，共一百零二頁，2022年，8月28日極小化過程 由定義，最后剩下的F就一定是極小依賴集。因?yàn)閷的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)，因此剩下的F與原來的F等價(jià)。證畢定理5.3的證明過程也是求F極小依賴集的過程第七十一頁，共一百零二頁，2022年，8月28日極小化過程[例3]F={A→B，B→A，B→C，

A→C，C→A}Fm1、Fm2都是F的最小依賴集：

Fm1={A→B，B→C，C→A}

Fm2={A→B，B→A，A→C，C→A}F的最小依賴集Fm不一定是唯一的它與對各函數(shù)依賴FDi

及X→A中X各屬性的處置順序有關(guān)第七十二頁，共一百零二頁，2022年，8月28日極小化過程極小化過程(定理6.2.5的證明)也是檢驗(yàn)F是否為極小依賴集的一個(gè)算法若改造后的F與原來的F相同，說明F本身就是一個(gè)最小依賴集第七十三頁，共一百零二頁，2022年，8月28日極小化過程在R<U，F(xiàn)>中可以用與F等價(jià)的依賴集G來取代F原因：兩個(gè)關(guān)系模式R1<U，F(xiàn)>，R2<U，G>，如果F與G等價(jià)，那么R1的關(guān)系一定是R2的關(guān)系。反過來，R2的關(guān)系也一定是R1的關(guān)系。第七十四頁，共一百零二頁，2022年，8月28日五、關(guān)系模式規(guī)范化方法關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具。一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng)，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有多個(gè)不同的級別第七十五頁，共一百零二頁，2022年，8月28日規(guī)范化（續(xù)）規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界，可能會存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題一個(gè)低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化第七十六頁，共一百零二頁，2022年，8月28日規(guī)范化（續(xù)）關(guān)系模式規(guī)范化的基本步驟

1NF ↓消除非主屬性對碼的部分函數(shù)依賴消除決定屬性2NF集非碼的非平↓消除非主屬性對碼的傳遞函數(shù)依賴凡函數(shù)依賴3NF ↓消除主屬性對碼的部分和傳遞函數(shù)依賴

BCNF ↓消除非平凡且非函數(shù)依賴的多值依賴

4NF第七十七頁，共一百零二頁，2022年，8月28日規(guī)范化的基本思想消除不合適的數(shù)據(jù)依賴的各關(guān)系模式達(dá)到某種程度的“分離”采用“一事一地”的模式設(shè)計(jì)原則讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去所謂規(guī)范化實(shí)質(zhì)上是概念的單一化第七十八頁，共一百零二頁，2022年，8月28日規(guī)范化（續(xù)）不能說規(guī)范化程度越高的關(guān)系模式就越好在設(shè)計(jì)數(shù)據(jù)庫模式結(jié)構(gòu)時(shí)，必須對現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式上面的規(guī)范化步驟可以在其中任何一步終止第七十九頁，共一百零二頁，2022年，8月28日3.3模式的分解把低一級的關(guān)系模式分解為若干個(gè)高一級的關(guān)系模式的方法并不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義第八十頁，共一百零二頁，2022年，8月28日關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解的等價(jià)定義⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性第八十一頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)）定義4.16關(guān)系模式R<U,F>的一個(gè)分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=U1∪U2∪…∪Un，且不存在Ui

Uj，F(xiàn)i為F在Ui上的投影定義4.17函數(shù)依賴集合{X→Y|X→Y

F+∧XY

Ui}的一個(gè)覆蓋Fi叫作F在屬性Ui上的投影第八十二頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)）例:SL（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題分解方法可以有多種第八十三頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)）SL──────────────────Sno Sdept Sloc──────────────────95001CS A95002IS B95003MA C95004IS B95005 PH B──────────────────第八十四頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)）1.SL分解為下面三個(gè)關(guān)系模式：

SN(Sno)SD(Sdept)SO(Sloc)第八十五頁，共一百零二頁，2022年，8月28日分解后的關(guān)系為：

SN──────SD──────SO──────SnoSdeptSloc

──────────────────95001CSA95002ISB95003MAC95004PH─────95005────────────第八十六頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)） 分解后的數(shù)據(jù)庫丟失了許多信息例如無法查詢95001學(xué)生所在系或所在宿舍。如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息第八十七頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)）2.SL分解為下面二個(gè)關(guān)系模式：

NL(Sno,Sloc)DL(Sdept,Sloc)分解后的關(guān)系為：

NL────────────DL────────────SnoSlocSdeptSloc

────────────────────────95001ACSA95002B ISB95003C MAC95004B PHB95005B──────────────────────第八十八頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)）NLDL─────────────SnoSlocSdept─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH第八十九頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)）

NLDL比原來的SL關(guān)系多了3個(gè)元組

無法知道95002、95004、95005

究竟是哪個(gè)系的學(xué)生

元組增加了，信息丟失了第九十頁，共一百零二頁，2022年，8月28日第三種分解方法3.將SL分解為下面二個(gè)關(guān)系模式：

ND(Sno,Sdept)NL(Sno,Sloc)

分解后的關(guān)系為：

第九十一頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)）ND────────────NL──────────SnoSdeptSnoSloc

──────────────────────95001CS95001A95002IS95002B95003MA95003C95004IS95004B95005PH95005B

───────────────────────第九十二頁，共一百零二頁，2022年，8月28日模式的分解（續(xù)）

NDNL──────────────