數(shù)據(jù)庫原理與應用第四章

數(shù)據(jù)庫原理與應用第四章第一頁，共一百三十七頁，編輯于2023年，星期三4.1問題的提出關系數(shù)據(jù)庫邏輯設計針對具體問題，如何構造一個適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設計的工具──關系數(shù)據(jù)庫的規(guī)范化理論第二頁，共一百三十七頁，編輯于2023年，星期三

問題的提出一、概念回顧二、關系模式的形式化定義三、什么是數(shù)據(jù)依賴四、關系模式的簡化定義五、數(shù)據(jù)依賴對關系模式影響第三頁，共一百三十七頁，編輯于2023年，星期三一、概念回顧關系：描述實體、屬性、實體間的聯(lián)系。從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。關系模式：用來定義關系。關系數(shù)據(jù)庫：基于關系模型的數(shù)據(jù)庫，利用關系來描述現(xiàn)實世界。從形式上看，它由一組關系組成。關系數(shù)據(jù)庫的模式：定義這組關系的關系模式的全體。第四頁，共一百三十七頁，編輯于2023年，星期三二、關系模式的形式化定義關系模式由五部分組成，即它是一個五元組：

R(U,D,DOM,F)R：關系名U：組成該關系的屬性名集合D：屬性組U中屬性所來自的域DOM：屬性向域的映象集合F：屬性間數(shù)據(jù)的依賴關系集合第五頁，共一百三十七頁，編輯于2023年，星期三三、什么是數(shù)據(jù)依賴1.完整性約束的表現(xiàn)形式限定屬性取值范圍：例如學生成績必須在0-100之間定義屬性值間的相互關連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設計的關鍵第六頁，共一百三十七頁，編輯于2023年，星期三什么是數(shù)據(jù)依賴（續(xù)）2.數(shù)據(jù)依賴是通過一個關系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關系是現(xiàn)實世界屬性間相互聯(lián)系的抽象是數(shù)據(jù)內在的性質是語義的體現(xiàn)第七頁，共一百三十七頁，編輯于2023年，星期三什么是數(shù)據(jù)依賴（續(xù)）3.數(shù)據(jù)依賴的類型函數(shù)依賴（FunctionalDependency，簡記為FD）多值依賴（MultivaluedDependency，簡記為MVD）其他第八頁，共一百三十七頁，編輯于2023年，星期三四、關系模式的簡化表示關系模式R（U,D,DOM,F）簡化為一個三元組：

R（U,F）當且僅當U上的一個關系r

滿足F時，r稱為關系模式R（U,F）的一個關系第九頁，共一百三十七頁，編輯于2023年，星期三五、數(shù)據(jù)依賴對關系模式的影響例：描述學校的數(shù)據(jù)庫：

學生的學號（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績（Grade）單一的關系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cname,Grade｝第十頁，共一百三十七頁，編輯于2023年，星期三數(shù)據(jù)依賴對關系模式的影響（續(xù)）學校數(shù)據(jù)庫的語義：

⒈一個系有若干學生，一個學生只屬于一個系；⒉一個系只有一名主任；⒊一個學生可以選修多門課程，每門課程有若干學生選修；⒋每個學生所學的每門課程都有一個成績。

第十一頁，共一百三十七頁，編輯于2023年，星期三數(shù)據(jù)依賴對關系模式的影響（續(xù)）

屬性組U上的一組函數(shù)依賴F：

F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝

SnoCnameSdeptMnameGrade第十二頁，共一百三十七頁，編輯于2023年，星期三關系模式Student<U,F>中存在的問題⒈數(shù)據(jù)冗余太大浪費大量的存儲空間

例：每一個系主任的姓名重復出現(xiàn)⒉更新異常（UpdateAnomalies）數(shù)據(jù)冗余，更新數(shù)據(jù)時，維護數(shù)據(jù)完整性代價大。 例：某系更換系主任后，系統(tǒng)必須修改與該系學生有關的每一個元組第十三頁，共一百三十七頁，編輯于2023年，星期三關系模式Student<U,F>中存在的問題⒊插入異常（InsertionAnomalies）該插的數(shù)據(jù)插不進去例，如果一個系剛成立，尚無學生，我們就無法把這個系及其系主任的信息存入數(shù)據(jù)庫。⒋刪除異常（DeletionAnomalies）不該刪除的數(shù)據(jù)不得不刪 例，如果某個系的學生全部畢業(yè)了，我們在刪除該系學生信息的同時，把這個系及其系主任的信息也丟掉了。第十四頁，共一百三十七頁，編輯于2023年，星期三數(shù)據(jù)依賴對關系模式的影響（續(xù)）結論：Student關系模式不是一個好的模式?！昂谩钡哪Ｊ剑翰粫l(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應盡可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關系模式來消除其中不合適的數(shù)據(jù)依賴。第十五頁，共一百三十七頁，編輯于2023年，星期三4.2規(guī)范化

規(guī)范化理論正是用來改造關系模式，通過分解關系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。第十六頁，共一百三十七頁，編輯于2023年，星期三4.2.1函數(shù)依賴一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴第十七頁，共一百三十七頁，編輯于2023年，星期三一、函數(shù)依賴定義5.1設R(U)是一個屬性集U上的關系模式，X和Y是U的子集。若對于R(U)的任意一個可能的關系r，r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數(shù)確定Y”

或“Y函數(shù)依賴于X”，記作X→Y。

X稱為這個函數(shù)依賴的決定屬性集(Determinant)。

Y=f(x)第十八頁，共一百三十七頁，編輯于2023年，星期三說明：

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

假設不允許重名，則有: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。第二十頁，共一百三十七頁，編輯于2023年，星期三二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關系模式R(U)中，對于U的子集X和Y，如果X→Y，但YX，則稱X→Y是非平凡的函數(shù)依賴若X→Y，但YX,則稱X→Y是平凡的函數(shù)依賴例：在關系SC(Sno,Cno,Grade)中，非平凡函數(shù)依賴：(Sno,Cno)→

Grade

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

Sno(Sno,Cno)→Cno第二十一頁，共一百三十七頁，編輯于2023年，星期三平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）

對于任一關系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明，我們總是討論非平凡函數(shù)依賴。第二十二頁，共一百三十七頁，編輯于2023年，星期三三、完全函數(shù)依賴與部分函數(shù)依賴定義5.2在關系模式R(U)中，如果X→Y，并且對于X的任何一個真子集X’，都有

X’Y,則稱Y完全函數(shù)依賴于X，記作Xｆ

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

第二十三頁，共一百三十七頁，編輯于2023年，星期三完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）例:在關系SC(Sno,Cno,Grade)中，由于：Sno→Grade，Cno→Grade，因此：(Sno,Cno)ｆGrade

第二十四頁，共一百三十七頁，編輯于2023年，星期三四、傳遞函數(shù)依賴定義5.3在關系模式R(U)中，如果X→Y，Y→Z，且YX，Y→X，則稱Z傳遞函數(shù)依賴于X。注:如果Y→X，即X←→Y，則Z直接依賴于X。例:在關系Std(Sno,Sdept,Mname)中，有：

Sno→Sdept，Sdept→MnameMname傳遞函數(shù)依賴于Sno第二十五頁，共一百三十七頁，編輯于2023年，星期三4.2.2碼定義5.4設K為關系模式R<U,F>中的屬性或屬性組合。若KｆU，則K稱為R的一個侯選碼（CandidateKey）。若關系模式R有多個候選碼，則選定其中的一個做為主碼（Primarykey）。主屬性與非主屬性ALLKEY第二十六頁，共一百三十七頁，編輯于2023年，星期三外部碼定義5.5關系模式R中屬性或屬性組X并非R的碼，但X是另一個關系模式的碼，則稱X是R的外部碼（Foreignkey）也稱外碼主碼又和外部碼一起提供了表示關系間聯(lián)系的手段。第二十七頁，共一百三十七頁，編輯于2023年，星期三4.2.3范式范式是符合某一種級別的關系模式的集合。關系數(shù)據(jù)庫中的關系必須滿足一定的要求。滿足不同程度要求的為不同范式。范式的種類：

第一范式(1NF)

第二范式(2NF)

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

第四范式(4NF)

第五范式(5NF)第二十八頁，共一百三十七頁，編輯于2023年，星期三4.2.3范式各種范式之間存在聯(lián)系：某一關系模式R為第n范式，可簡記為R∈nNF。第二十九頁，共一百三十七頁，編輯于2023年，星期三4.2.42NF1NF的定義 如果一個關系模式R的所有屬性都是不可分的基本數(shù)據(jù)項，則R∈1NF。第一范式是對關系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關系數(shù)據(jù)庫。但是滿足第一范式的關系模式并不一定是一個好的關系模式。第三十頁，共一百三十七頁，編輯于2023年，星期三2NF例:關系模式SLC(Sno,Sdept,Sloc,Cno,Grade)Sloc為學生住處，假設每個系的學生住在同一個地方。函數(shù)依賴包括：

(Sno,Cno)fGradeSno→Sdept(Sno,Cno)PSdeptSno→Sloc(Sno,Cno)PSlocSdept→Sloc第三十一頁，共一百三十七頁，編輯于2023年，星期三2NFSLC的碼為(Sno,Cno)SLC滿足第一范式。非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno,Cno)SnoCnoGradeSdeptSlocSLC第三十二頁，共一百三十七頁，編輯于2023年，星期三SLC不是一個好的關系模式(1)插入異常 假設Sno＝95102，Sdept＝IS，Sloc＝N的學生還未選課，因課程號是主屬性，因此該學生的信息無法插入SLC。(2)刪除異常假定某個學生本來只選修了3號課程這一門課。現(xiàn)在因身體不適，他連3號課程也不選修了。因課程號是主屬性，此操作將導致該學生信息的整個元組都要刪除。

第三十三頁，共一百三十七頁，編輯于2023年，星期三SLC不是一個好的關系模式(3)數(shù)據(jù)冗余度大如果一個學生選修了10門課程，那么他的Sdept和Sloc值就要重復存儲了10次。(4)修改復雜例如學生轉系，在修改此學生元組的Sdept值的同時，還可能需要修改住處（Sloc）。如果這個學生選修了K門課，則必須無遺漏地修改K個元組中全部Sdept、Sloc信息。

第三十四頁，共一百三十七頁，編輯于2023年，星期三2NF原因

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

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

SC（Sno，Cno，Grade）

SL（Sno，Sdept，Sloc）第三十五頁，共一百三十七頁，編輯于2023年，星期三2NFSLC的碼為(Sno,Cno)SLC滿足第一范式。非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno,Cno)SnoCnoGradeSdeptSlocSLC第三十六頁，共一百三十七頁，編輯于2023年，星期三2NF函數(shù)依賴圖：SnoCnoGradeSCSLSnoSdeptSloc第三十七頁，共一百三十七頁，編輯于2023年，星期三2NF2NF的定義 定義5.6若關系模式R∈1NF，并且每一個非主屬性都完全函數(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第三十八頁，共一百三十七頁，編輯于2023年，星期三

第二范式（續(xù)）采用投影分解法將一個1NF的關系分解為多個2NF的關系，可以在一定程度上減輕原1NF關系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。將一個1NF關系分解為多個2NF的關系，并不能完全消除關系模式中的各種異常情況和數(shù)據(jù)冗余。第三十九頁，共一百三十七頁，編輯于2023年，星期三4.2.53NF例：2NF關系模式SL(Sno,Sdept,Sloc)中函數(shù)依賴：

Sno→SdeptSdept→SlocSno→Sloc Sloc傳遞函數(shù)依賴于Sno，即SL中存在非主屬性對碼的傳遞函數(shù)依賴。第四十頁，共一百三十七頁，編輯于2023年，星期三3NF函數(shù)依賴圖：SLSnoSdeptSloc第四十一頁，共一百三十七頁，編輯于2023年，星期三3NF解決方法采用投影分解法，把SL分解為兩個關系模式，以消除傳遞函數(shù)依賴：SD（Sno，Sdept）

DL（Sdept，Sloc）SD的碼為Sno，DL的碼為Sdept。第四十二頁，共一百三十七頁，編輯于2023年，星期三3NFSD的碼為Sno，DL的碼為Sdept。SnoSdeptSDSdeptSlocDL第四十三頁，共一百三十七頁，編輯于2023年，星期三3NF3NF的定義 定義5.8關系模式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第四十四頁，共一百三十七頁，編輯于2023年，星期三3NF若R∈3NF，則R的每一個非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。如果R∈3NF，則R也是2NF。采用投影分解法將一個2NF的關系分解為多個3NF的關系，可以在一定程度上解決原2NF關系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復雜等問題。將一個2NF關系分解為多個3NF的關系后，并不能完全消除關系模式中的各種異常情況和數(shù)據(jù)冗余。第四十五頁，共一百三十七頁，編輯于2023年，星期三4.2.6BC范式（BCNF）定義5.9設關系模式R<U，F(xiàn)>∈1NF，如果對于R的每個函數(shù)依賴X→Y，若Y不屬于X，則X必含有候選碼，那么R∈BCNF。若R∈BCNF每一個決定屬性集（因素）都包含（候選）碼R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼R∈3NF（證明）若R∈3NF則R不一定∈BCNF第四十六頁，共一百三十七頁，編輯于2023年，星期三BCNF例：在關系模式STJ（S，T，J）中，S表示學生，T表示教師，J表示課程。每一教師只教一門課。每門課由若干教師教，某一學生選定某門課，就確定了一個固定的教師。某個學生選修某個教師的課就確定了所選課的名稱：

(S，J)→T，(S，T)→J，T→J第四十七頁，共一百三十七頁，編輯于2023年，星期三4.2.6BCNF

SJTSTJSTJ第四十八頁，共一百三十七頁，編輯于2023年，星期三BCNFSTJ∈3NF

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

S、T、J都是主屬性STJ∈BCNFT→J，T是決定屬性集，T不是候選碼第四十九頁，共一百三十七頁，編輯于2023年，星期三BCNF

解決方法：將STJ分解為二個關系模式：

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

沒有任何屬性對碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJ第五十頁，共一百三十七頁，編輯于2023年，星期三3NF與BCNF的關系如果關系模式R∈BCNF，必定有R∈3NF如果R∈3NF，且R只有一個候選碼，則R必屬于BCNF。第五十一頁，共一百三十七頁，編輯于2023年，星期三BCNF的關系模式所具有的性質⒈所有非主屬性都完全函數(shù)依賴于每個候選碼⒉所有主屬性都完全函數(shù)依賴于每個不包含它的候選碼⒊沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性第五十二頁，共一百三十七頁，編輯于2023年，星期三4.2.5多值依賴與第四范式（4NF）例:學校中某一門課程由多個教師講授，他們使用相同的一套參考書。 關系模式Teaching(C,T,B)

課程C、教師T和參考書B第五十三頁，共一百三十七頁，編輯于2023年，星期三………課程C教員T參考書B

物理

數(shù)學

計算數(shù)學李勇王軍

李勇張平

張平周峰

普通物理學光學原理物理習題集

數(shù)學分析微分方程高等代數(shù)

數(shù)學分析

表4.1第五十四頁，共一百三十七頁，編輯于2023年，星期三普通物理學光學原理物理習題集普通物理學光學原理物理習題集數(shù)學分析微分方程高等代數(shù)數(shù)學分析微分方程高等代數(shù)…李勇李勇李勇王軍王軍王軍李勇李勇李勇張平張平張平

…物理物理物理物理物理物理數(shù)學數(shù)學數(shù)學數(shù)學數(shù)學數(shù)學

…參考書B教員T課程C用二維表表示Teaching

第五十五頁，共一百三十七頁，編輯于2023年，星期三多值依賴與第四范式（續(xù)）Teaching∈BCNF:Teach具有唯一候選碼(C，T，B)，即全碼Teaching模式中存在的問題

(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲多少次

第五十六頁，共一百三十七頁，編輯于2023年，星期三多值依賴與第四范式（續(xù)）

(2)插入操作復雜：當某一課程增加一名任課教師時，該課程有多少本參照書，就必須插入多少個元組例如物理課增加一名教師劉關，需要插入兩個元組：

（物理，劉關，普通物理學）（物理，劉關，光學原理）第五十七頁，共一百三十七頁，編輯于2023年，星期三多值依賴與第四范式（續(xù)）(3)刪除操作復雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個元組(4)修改操作復雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個元組產(chǎn)生原因 存在多值依賴第五十八頁，共一百三十七頁，編輯于2023年，星期三一、多值依賴定義5.10

設R(U)是一個屬性集U上的一個關系模式，X、Y和Z是U的子集，并且Z＝U－X－Y，多值依賴X→→Y成立當且僅當對R的任一關系r，r在（X，Z）上的每個值對應一組Y的值，這組值僅僅決定于X值而與Z值無關 例Teaching（C,T,B）

對于C的每一個值，T有一組值與之對應，而不論B取何值第五十九頁，共一百三十七頁，編輯于2023年，星期三一、多值依賴在R（U）的任一關系r中，如果存在元組t，s使得t[X]=s[X]，那么就必然存在元組w，vr，（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值所得的兩個新元組必在r中），則Y多值依賴于X，記為X→→Y。這里，X，Y是U的子集，Z=U-X-Y。

txy1z2sxy2z1wxy1z1vxy2z2第六十頁，共一百三十七頁，編輯于2023年，星期三多值依賴（續(xù)）平凡多值依賴和非平凡的多值依賴

若X→→Y，而Z＝φ，則稱

X→→Y為平凡的多值依賴 否則稱X→→Y為非平凡的多值依賴第六十一頁，共一百三十七頁，編輯于2023年，星期三多值依賴的性質（1）多值依賴具有對稱性若X→→Y，則X→→Z，其中Z＝U－X－Y

多值依賴的對稱性可以用完全二分圖直觀地表示出來。（2）多值依賴具有傳遞性若X→→Y，Y→→Z，則X→→Z-Y第六十二頁，共一百三十七頁，編輯于2023年，星期三多值依賴的對稱性

XiZi1Zi2…ZimYi1Yi2…Yin第六十三頁，共一百三十七頁，編輯于2023年，星期三多值依賴的對稱性

物理普通物理學光學原理物理習題集李勇王軍第六十四頁，共一百三十七頁，編輯于2023年，星期三多值依賴（續(xù)）（3）函數(shù)依賴是多值依賴的特殊情況。 若X→Y，則X→→Y。（4）若X→→Y，X→→Z，則X→→YZ。（5）若X→→Y，X→→Z，則X→→Y∩Z。（6）若X→→Y，X→→Z，則X→→Y-Z， X→→Z-Y。第六十五頁，共一百三十七頁，編輯于2023年，星期三多值依賴與函數(shù)依賴的區(qū)別(1)有效性多值依賴的有效性與屬性集的范圍有關若X→→Y在U上成立，則在W（XYWU）上一定成立；反之則不然，即X→→Y在W（WU）上成立，在U上并不一定成立多值依賴的定義中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。一般地，在R（U）上若有X→→Y在W（WU）上成立，則稱X→→Y為R（U）的嵌入型多值依賴第六十六頁，共一百三十七頁，編輯于2023年，星期三多值依賴與函數(shù)依賴的區(qū)別只要在R（U）的任何一個關系r中，元組在X和Y上的值滿足定義5.l（函數(shù)依賴），則函數(shù)依賴X→Y在任何屬性集W（XYWU）上成立。第六十七頁，共一百三十七頁，編輯于2023年，星期三多值依賴（續(xù)）(2)

若函數(shù)依賴X→Y在R（U）上成立，則對于任何Y'Y均有X→Y'成立多值依賴X→→Y若在R(U)上成立，不能斷言對于任何Y'Y有X→→Y'成立第六十八頁，共一百三十七頁，編輯于2023年，星期三二、第四范式（4NF）定義4.10關系模式R<U，F(xiàn)>∈1NF，如果對于R的每個非平凡多值依賴X→→Y（YX），X都含有候選碼，則R∈4NF。（X→Y）如果R∈4NF，則R∈BCNF

不允許有非平凡且非函數(shù)依賴的多值依賴

允許的是函數(shù)依賴（是非平凡多值依賴）第六十九頁，共一百三十七頁，編輯于2023年，星期三第四范式（續(xù)）例：Teach(C,T,B)∈4NF

存在非平凡的多值依賴C→→T，且C不是候選碼用投影分解法把Teach分解為如下兩個關系模式：

CT(C,T)∈4NF CB(C,B)∈4NF

C→→T，C→→B是平凡多值依賴

第七十頁，共一百三十七頁，編輯于2023年，星期三4.2規(guī)范化4.2.1第一范式（1NF）4.2.2第二范式（2NF）4.2.3第三范式（3NF）4.2.4BC范式（BCNF）4.2.5多值依賴與第四范式（4NF）4.2.6規(guī)范化第七十一頁，共一百三十七頁，編輯于2023年，星期三5.2.6規(guī)范化關系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設計的工具。一個關系只要其分量都是不可分的數(shù)據(jù)項，它就是規(guī)范化的關系，但這只是最基本的規(guī)范化。規(guī)范化程度可以有多個不同的級別第七十二頁，共一百三十七頁，編輯于2023年，星期三規(guī)范化（續(xù)）規(guī)范化程度過低的關系不一定能夠很好地描述現(xiàn)實世界，可能會存在插入異常、刪除異常、修改復雜、數(shù)據(jù)冗余等問題一個低一級范式的關系模式，通過模式分解可以轉換為若干個高一級范式的關系模式集合，這種過程就叫關系模式的規(guī)范化第七十三頁，共一百三十七頁，編輯于2023年，星期三規(guī)范化（續(xù)）關系模式規(guī)范化的基本步驟

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

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

4NF第七十四頁，共一百三十七頁，編輯于2023年，星期三規(guī)范化的基本思想消除不合適的數(shù)據(jù)依賴的各關系模式達到某種程度的“分離”采用“一事一地”的模式設計原則讓一個關系描述一個概念、一個實體或者實體間的一種聯(lián)系。若多于一個概念就把它“分離”出去所謂規(guī)范化實質上是概念的單一化第七十五頁，共一百三十七頁，編輯于2023年，星期三規(guī)范化（續(xù)）不能說規(guī)范化程度越高的關系模式就越好在設計數(shù)據(jù)庫模式結構時，必須對現(xiàn)實世界的實際情況和用戶應用需求作進一步分析，確定一個合適的、能夠反映現(xiàn)實世界的模式上面的規(guī)范化步驟可以在其中任何一步終止第七十六頁，共一百三十七頁，編輯于2023年，星期三第四章關系數(shù)據(jù)理論4.1數(shù)據(jù)依賴4.2規(guī)范化4.3數(shù)據(jù)依賴的公理系統(tǒng)4.4模式的分解第七十七頁，共一百三十七頁，編輯于2023年，星期三4.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊含 定義5.11對于滿足一組函數(shù)依賴F的關系模式R<U，F(xiàn)>，其任何一個關系r，若函數(shù)依賴X→Y都成立,則稱

F邏輯蘊含X→Y第七十八頁，共一百三十七頁，編輯于2023年，星期三Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎用途求給定關系模式的碼從一組函數(shù)依賴求得蘊含的函數(shù)依賴第七十九頁，共一百三十七頁，編輯于2023年，星期三1.Armstrong公理系統(tǒng)

關系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：Al.自反律（Reflexivity）：若Y

X

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

U，則XZ→YZ為F所蘊含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含。

注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F第八十頁，共一百三十七頁，編輯于2023年，星期三（l）自反律:若Y

X

U，則X→Y為F所蘊含證:設Y

X

U

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

的任一關系r中的任意兩個元組t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得證定理4.1Armstrong推理規(guī)則是正確的第八十一頁，共一百三十七頁，編輯于2023年，星期三(2)增廣律:若X→Y為F所蘊含，且Z

U，則XZ→YZ為F所蘊含。證：設X→Y為F所蘊含，且Z

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

的任一關系r中任意的兩個元組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所蘊含.增廣律得證。第八十二頁，共一百三十七頁，編輯于2023年，星期三(3)傳遞律：若X→Y及Y→Z為F所蘊含，則

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

的任一關系r中的任意兩個元組t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊含.傳遞律得證。第八十三頁，共一百三十七頁，編輯于2023年，星期三2.導出規(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及ZY，有X→Z。（A1，A3）第八十四頁，共一百三十七頁，編輯于2023年，星期三導出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理5.1

引理5.lX→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）。第八十五頁，共一百三十七頁，編輯于2023年，星期三3.函數(shù)依賴閉包定義4.l2在關系模式R<U，F(xiàn)>中為F所邏輯蘊含的函數(shù)依賴的全體叫作F的閉包，記為F+。定義4.13設F為屬性集U上的一組函數(shù)依賴，X

U，

XF+={A|X→A能由F根據(jù)Armstrong公理導出}，XF+稱為屬性集X關于函數(shù)依賴集F的閉包第八十六頁，共一百三十七頁，編輯于2023年，星期三關于閉包的引理引理4.2

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

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

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

，判定Y是否為XF+的子集的問題第八十七頁，共一百三十七頁，編輯于2023年，星期三求閉包的算法算法4.l求屬性集X（X

U）關于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）

第八十八頁，共一百三十七頁，編輯于2023年，星期三算法4.l（4）判斷X（i+1）=X

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

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

}形成一個步長大于1的嚴格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環(huán)就會終止。第八十九頁，共一百三十七頁，編輯于2023年，星期三DefineXF+=closureofX=setofattributesfunctionallydeterminedbyXBasis:XF+:=XInduction:IfYXF+,andYAisagivenFD,thenaddAtoXF+EndwhenXF+cannotbechanged.AlgorithmyX+NewX+A第九十頁，共一百三十七頁，編輯于2023年，星期三

U={A,B,C,D};F={AB,BCD};A+=AB.C+=C.(AC)+=ABCD.ExampleACB第九十一頁，共一百三十七頁，編輯于2023年，星期三

ExampleACDBU={A,B,C,D};AB,BCD.(AC)+=ABCD.第九十二頁，共一百三十七頁，編輯于2023年，星期三函數(shù)依賴閉包[例1]已知關系模式R<U，F(xiàn)>，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+

。解設X（0）=AB；(1)計算X（1）:逐一的掃描F集合中各個函數(shù)依賴，找左部為A，B或AB的函數(shù)依賴。得到兩個：

AB→C，B→D。于是X（1）=AB∪CD=ABCD。第九十三頁，共一百三十七頁，編輯于2023年，星期三函數(shù)依賴閉包(2)因為X（0）≠X（1），所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到AB→C，B→D，C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。(3)因為X（2）=U，算法終止所以（AB）F+=ABCDE。第九十四頁，共一百三十七頁，編輯于2023年，星期三4.Armstrong公理系統(tǒng)的有效性與完備性有效性：由F出發(fā)根據(jù)Armstrong公理推導出來的每一個函數(shù)依賴一定在F+中

/*Armstrong正確完備性：F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導出來

/*Armstrong公理夠用，完全完備性：所有不能用Armstrong公理推導出來f,都不為真

若

f不能用Armstrong公理推導出來，

f∈F+第九十五頁，共一百三十七頁，編輯于2023年，星期三有效性與完備性的證明證明： 1.有效性可由定理5.l得證2.完備性 只需證明逆否命題:若函數(shù)依賴X→Y不能由F從Armstrong公理導出，那么它必然不為F所蘊含分三步證明：第九十六頁，共一百三十七頁，編輯于2023年，星期三有效性與完備性的證明(1)引理:若V→W成立，且V

XF+，則W

XF+

證因為V

XF+，所以有X→V成立；因為X→V，V→W，于是X→W成立所以W

XF+(2)/*若f不能用Armstrong公理推導出來，f∈F+/*若存在r，F(xiàn)+中的全部函數(shù)依賴在r上成立。

/*而不能用Armstrong公理推導出來的f,在r上不成立。構造一張二維表r，它由下列兩個元組構成，可以證明r必是R（U，F(xiàn)）的一個關系，即F+中的全部函數(shù)依賴在r上成立。

第九十七頁，共一百三十七頁，編輯于2023年，星期三Armstrong公理系統(tǒng)的有效性與完備性(續(xù)) XF+

U-XF+

11......100......0

11......111......1

若r不是R<U，F(xiàn)>的關系，則必由于F中有函數(shù)依賴V→W在r上不成立所致。由r的構成可知，V必定是XF+的子集，而W不是XF+的子集，可是由第（1）步，W

XF+，矛盾。所以r必是R<U，F(xiàn)>的一個關系。第九十八頁，共一百三十七頁，編輯于2023年，星期三Armstrong公理系統(tǒng)的有效性與完備性(續(xù))(3))/*若f不能用Armstrong公理推導出來，f∈F+/*而不能用Armstrong公理推導出來的f,在r上不成立。若X→Y不能由F從Armstrong公理導出，則Y不是

XF+的子集。（引理5.2）因此必有Y的子集Y’

滿足Y’U-XF+，則X→Y在r中不成立，即X→Y必不為R<U，F(xiàn)>蘊含

/*因為

F+中的全部函數(shù)依賴在r上成立。第九十九頁，共一百三十七頁，編輯于2023年，星期三Armstrong公理系統(tǒng)的有效性與完備性(續(xù))Armstrong公理的完備性及有效性說明:“蘊含”

==“導出”等價的概念

F+==由F出發(fā)借助Armstrong公理導出的函數(shù)依賴的集合第一百頁，共一百三十七頁，編輯于2023年，星期三5.函數(shù)依賴集等價

定義4.14如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。第一百零一頁，共一百三十七頁，編輯于2023年，星期三函數(shù)依賴集等價的充要條件

引理4.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+。第一百零二頁，共一百三十七頁，編輯于2023年，星期三函數(shù)依賴集等價要判定F

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

就行了。因此引理5.3給出了判斷兩個函數(shù)依賴集等價的可行算法。第一百零三頁，共一百三十七頁，編輯于2023年，星期三6.最小依賴集

定義4.15如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。

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

(2)F中不存在這樣的函數(shù)依賴X→A，使得F與

F-{X→A}等價。

(3)F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價。第一百零四頁，共一百三十七頁，編輯于2023年，星期三最小依賴集[例2]對于5.l節(jié)中的關系模式S<U，F(xiàn)>，其中：

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

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

設F’={SNO→SDEPT，SNO→MN，

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

(SNO，SDEPT)→SDEPT}F是最小覆蓋，而F’不是。因為：F’-{SNO→MN}與F’等價

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

F’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也與F’等價第一百零五頁，共一百三十七頁，編輯于2023年，星期三7.極小化過程定理4.3每一個函數(shù)依賴集F均等價于一個極小函數(shù)依賴集Fm。此Fm稱為F的最小依賴集證:構造性證明，依據(jù)定義分三步對F進行“極小化處理”，找出F的一個最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：X→Y，若Y=A1A2

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

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

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

因此F變換前后是等價的。第一百零七頁，共一百三十七頁，編輯于2023年，星期三極小化過程(3)逐一取出F中各函數(shù)依賴FDi：X→A，設X=B1B2…Bm，逐一考查Bi

（i=l，2，…，m），若A（X-Bi

）F+，則以X-Bi

取代X。由于F與F-{X→A}∪{Z→A}等價的充要條件是AZF+，其中Z=X-Bi

因此F變換前后是等價的。第一百零八頁，共一百三十七頁，編輯于2023年，星期三極小化過程

由定義，最后剩下的F就一定是極小依賴集。因為對F的每一次“改造”都保證了改造前后的兩個函數(shù)依賴集等價，因此剩下的F與原來的F等價。證畢定理5.3的證明過程也是求F極小依賴集的過程第一百零九頁，共一百三十七頁，編輯于2023年，星期三極小化過程[例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各屬性的處置順序有關第一百一十頁，共一百三十七頁，編輯于2023年，星期三極小化過程極小化過程(定理4.3的證明)也是檢驗F是否為極小依賴集的一個算法若改造后的F與原來的F相同，說明F本身就是一個最小依賴集第一百一十一頁，共一百三十七頁，編輯于2023年，星期三極小化過程在R<U，F(xiàn)>中可以用與F等價的依賴集G來取代F原因：兩個關系模式R1<U，F(xiàn)>，R2<U，G>，如果F與G等價，那么R1的關系一定是R2的關系。反過來，R2的關系也一定是R1的關系。第一百一十二頁，共一百三十七頁，編輯于2023年，星期三第四章關系數(shù)據(jù)理論4.1數(shù)據(jù)依賴4.2規(guī)范化4.3數(shù)據(jù)依賴的公理系統(tǒng)4.4模式的分解第一百一十三頁，共一百三十七頁，編輯于2023年，星期三4.4模式的分解把低一級的關系模式分解為若干個高一級的關系模式的方法并不是唯一的只有能夠保證分解后的關系模式與原關系模式等價，分解方法才有意義第一百一十四頁，共一百三十七頁，編輯于2023年，星期三關系模式分解的標準三種模式分解的等價定義⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性第一百一十五頁，共一百三十七頁，編輯于2023年，星期三模式的分解（續(xù)）定義4.16關系模式R<U,F>的一個分解：ρ={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}的一個覆蓋

Fi叫作F在屬性Ui上的投影第一百一十六頁，共一百三十七頁，編輯于2023年，星期三模式的分解（續(xù)）例:SL（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入異常、刪除異常、冗余度大和修改復雜等問題分解方法可以有多種第一百一十七頁，共一百三十七頁，編輯于2023年，星期三模式的分解（續(xù)）SL──────────────────Sno Sdept Sloc──────────────────95001CSA95002ISB95003MAC95004ISB95005 PH B──────────────────第一百一十八頁，共一百三十七頁，編輯于2023年，星期三模式的分解（續(xù)）1.SL分解為下面三個關系模式：

SN(Sno)SD(Sdept)SO(Sloc)第一百一十九頁，共一百三十七頁，編輯于2023年，星期三分解后的關系為：

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

──────────────────95001CSA95002ISB95003MAC95004PH─────95005────────────第一百二十頁，共一百三十七頁，編輯于2023年，星期三模式的分解（續(xù)）

分解后的數(shù)據(jù)庫丟失了許多信息例如無法查詢95001學生所在系或所在宿舍。如果分解后的關系可以通過自然連接恢復為原來的關系，那么這種分解就沒有丟失信息第一百二十一頁，共一百三十七頁，編輯于2023年，星期三模式的分解（續(xù)）2.SL分解為下面二個關系模式：

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

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

────────────────────────95001ACSA95002B ISB95003C MAC95004B PHB95005B──────────────────────第一百二十二頁，共一百三十七頁，編輯于2023年，星期三模式的分解（續(xù)）NLDL─────────────SnoSlocSdept─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH第一百二十三頁，共一百三十七頁，編輯于2023年，星期三模式的分解（續(xù)） NLDL比原來的SL關系多了3個元組

無法知道95002、95004、95005

究竟是哪個系的學生

元組增加了，信息丟失了第一百二十四頁，共一百三十七頁，編輯于2023年，星期三第三種分解方法3.將SL分解為下面二個關系模式：

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

分解后的關系為：

第一百二十五頁，共一百三十七頁，編輯于2023年，星期三模式的分解（續(xù)）ND────────────NL──────────SnoSdeptSnoSloc