數據庫系統概論第六章關系數據理論第1頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第六章關系數據理論6.1問題的提出6.2規范化6.3數據依賴的公理系統*6.4模式的分解6.5小結第2頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.1問題的提出關系數據庫邏輯設計針對具體問題，如何構造一個適合于它的數據模式數據庫邏輯設計的工具──關系數據庫的規范化理論第3頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第4頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem關系模式的優劣第5頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第6頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第7頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第8頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem結論1、不是所有的關系都一樣好2、關系模式設計的好壞影響數據庫的實用效率第9頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem問題的提出一、概念回顧二、關系模式的形式化定義三、什么是數據依賴四、關系模式的簡化定義五、數據依賴對關系模式影響第10頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem一、概念回顧關系：描述實體、屬性、實體間的聯系。從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。關系模式：用來定義關系。關系數據庫：基于關系模型的數據庫，利用關系來描述現實世界。從形式上看，它由一組關系組成。關系數據庫的模式：定義這組關系的關系模式的全體。第11頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem二、關系模式的形式化定義關系模式由五部分組成，即它是一個五元組：

R(U,D,DOM,F)第12頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem三、什么是數據依賴1.完整性約束的表現形式限定屬性取值范圍：例如學生成績必須在0-100之間定義屬性值間的相互關連（主要體現于值的相等與否），這就是數據依賴，它是數據庫模式設計的關鍵2.數據依賴一個關系內部屬性與屬性之間的約束關系現實世界屬性間相互聯系的抽象數據內在的性質語義的體現第13頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem什么是數據依賴（續）3.數據依賴的類型函數依賴（FunctionalDependency，簡記為FD）.舉例：學生關系學號值確定之后，姓名和所在系的值也被唯一的確定Sname=f(Sno),Sdept=f(Sno)Sno->Sname,Sno->Sdept第14頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem3.數據依賴的類型多值依賴（MultivaluedDependency，簡記為MVD）第15頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem函數依賴的定義第16頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第17頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第18頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第19頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem四、關系模式的簡化表示關系模式R（U,D,DOM,F）簡化為一個三元組：

R（U,F）當且僅當U上的一個關系r滿足F時，r稱為關系模式R（U,F）的一個關系第20頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem五、數據依賴對關系模式的影響[例1]建立一個描述學校教務的數據庫： 學生的學號（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程號（Cno） 成績（Grade）單一的關系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cno,Grade｝第21頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem數據依賴對關系模式的影響（續）學校數據庫的語義：⒈一個系有若干學生，一個學生只屬于一個系；⒉一個系只有一名主任；⒊一個學生可以選修多門課程，每門課程有若干學生選修；⒋每個學生所學的每門課程都有一個成績。

第22頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem數據依賴對關系模式的影響（續）屬性組U上的一組函數依賴F：

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

SnoCnoSdeptMnameGrade第23頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem關系模式Student<U,F>中存在的問題⒈數據冗余太大浪費大量的存儲空間

例：每一個系主任的姓名重復出現⒉更新異常（UpdateAnomalies）數據冗余，更新數據時，維護數據完整性代價大。

例：某系更換系主任后，系統必須修改與該系學生有關的每一個元組第24頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem關系模式Student<U,F>中存在的問題⒊插入異常（InsertionAnomalies）該插入的數據無法存入數據庫

例，如果一個系剛成立，尚無學生，我們就無法把這個系及其系主任的信息存入數據庫。⒋刪除異常（DeletionAnomalies）不該刪除的數據不得不刪

例，如果某個系的學生全部畢業了，我們在刪除該系學生信息的同時，把這個系及其系主任的信息也丟掉了。第25頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem數據依賴對關系模式的影響（續）結論：Student關系模式不是一個好的模式。“好”的模式：不會發生插入異常、刪除異常、更新異常數據冗余應盡可能少原因：由存在于模式中的某些數據依賴引起的解決方法：通過分解關系模式來消除其中不合適的數據依賴第26頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem分解關系模式把這個單一模式分成3個關系模式：

S（Sno，Sdept，Sno→Sdept）;SC（Sno，Cno，Grade，（Sno，Cno）→Grade）;DEPT（Sdept，Mname，Sdept→Mname）;第27頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第六章關系數據理論6.1問題的提出6.2規范化6.3數據依賴的公理系統*6.4模式的分解6.5小結第28頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第29頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化

規范化理論正是用來改造關系模式，通過分解關系模式來消除其中不合適的數據依賴，以解決插入異常、刪除異常、更新異常和數據冗余問題。第30頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化6.2.1函數依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規范化小結第31頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2.1函數依賴函數依賴平凡函數依賴與非平凡函數依賴完全函數依賴與部分函數依賴傳遞函數依賴第32頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem一、函數依賴定義6.1

設R(U)是一個屬性集U上的關系模式，X和Y是U的子集。若對于R(U)的任意一個可能的關系r，r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數確定Y”或“Y函數依賴于X”，記作X→Y。

第33頁，課件共147頁，創作于2023年2月SnoSdeptMnameCnoGradeS1計算機系張明C195S1自動化系張明C190S3計算機系張明C188S4計算機系張明C170S5計算機系張明C178……………

在任何時刻Student的關系實例中，不可能存在兩個元組在Sno上的值相等，而在Sdept上的值不等第34頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem說明：

1.函數依賴不是指關系模式R的某個或某些關系實例滿足的約束條件，而是指R的所有關系實例均要滿足的約束條件。2.函數依賴是語義范疇的概念。只能根據數據的語義來確定函數依賴。

例如“姓名→年齡”這個函數依賴只有在不允許有同名人的條件下成立3.數據庫設計者可以對現實世界作強制的規定。

例如：規定不允許同名人出現，函數依賴“姓名→年齡”成立。所插入的元組必須滿足規定的函數依賴，若發現有同名人存在，則拒絕裝入該元組。第35頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem二、平凡函數依賴與非平凡函數依賴在關系模式R(U)中，對于U的子集X和Y，如果X→Y，但YX，則稱X→Y是非平凡的函數依賴若X→Y，但YX,則稱X→Y是平凡的函數依賴例：在關系SC(Sno,Cno,Grade)中，非平凡函數依賴：(Sno,Cno)→

Grade

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

Sno(Sno,Cno)→Cno第36頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem平凡函數依賴與非平凡函數依賴（續）若X→Y，則X稱為這個函數依賴的決定屬性組，也稱為決定因素（Determinant）。若X→Y，Y→X，則記作X←→Y。若Y不函數依賴于X，則記作X→Y。第37頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem三、完全函數依賴與部分函數依賴定義6.2

在R(U)中，如果X→Y，并且對于X的任何一個真子集X’，都有X’Y,則稱Y對X完全函數依賴，記作

XFY。若X→Y，但Y不完全函數依賴于X，則稱Y對X部分函數依賴，記作XPY。[例1]中(Sno,Cno)→Grade是完全函數依賴，

(Sno,Cno)→Sdept是部分函數依賴因為Sno→Sdept成立，且Sno是（Sno，Cno）的真子集FP第38頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem四、傳遞函數依賴定義6.3

在R(U)中，如果X→Y，(YX),Y→XY→Z，則稱Z對X傳遞函數依賴。記為：X→Z

注:如果Y→X，即X←→Y，則Z直接依賴于X。例:在關系Std(Sno,Sdept,Mname)中，有：

Sno→Sdept，Sdept→MnameMname傳遞函數依賴于Sno傳遞第39頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化6.2.1函數依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規范化小結第40頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2.2碼定義6.4

設K為R<U,F>中的屬性或屬性組合。若K

U，則K稱為R的侯選碼（CandidateKey）。若候選碼多于一個，則選定其中的一個做為主碼（PrimaryKey）。F主屬性與非主屬性包含在任何一個候選碼中的屬性，稱為主屬性（Primeattribute）不包含在任何碼中的屬性稱為非主屬性（Nonprimeattribute）或非碼屬性（Non-keyattribute）全碼整個屬性組是碼，稱為全碼（All-key）第41頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem碼（續）[例2]

關系模式S(Sno,Sdept,Sage)，單個屬性Sno是碼，

SC（Sno，Cno，Grade）中，（Sno，Cno）是碼[例3]

關系模式R（P，W，A）

P：演奏者W：作品A：聽眾一個演奏者可以演奏多個作品某一作品可被多個演奏者演奏聽眾可以欣賞不同演奏者的不同作品碼為(P，W，A)，即All-Key第42頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem外部碼定義6.5

關系模式R中屬性或屬性組X并非R的碼，但X是另一個關系模式的碼，則稱X是R的外部碼（Foreignkey）也稱外碼如在SC（Sno，Cno，Grade）中，Sno不是碼，但Sno是關系模式S（Sno，Sdept，Sage）的碼，則Sno是關系模式SC的外部碼

主碼與外部碼一起提供了表示關系間聯系的手段第43頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化6.2.1函數依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規范化小結第44頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第45頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2.3范式范式是符合某一種級別的關系模式的集合關系數據庫中的關系必須滿足一定的要求。滿足不同程度要求的為不同范式范式的種類：

第一范式(1NF)

第二范式(2NF)

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

第四范式(4NF)

第五范式(5NF)第46頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第47頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2.3范式各種范式之間存在聯系：某一關系模式R為第n范式，可簡記為R∈nNF。一個低一級范式的關系模式，通過模式分解可以轉換為若干個高一級范式的關系模式的集合，這種過程就叫規范化

第48頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化6.2.1函數依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規范化小結第49頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2.42NF1NF的定義 如果一個關系模式R的所有屬性都是不可分的基本數據項，則R∈1NF。即，不允許如下表的存在： 第一范式是對關系模式的最起碼的要求。不滿足第一范式的數據庫模式不能稱為關系數據庫但是滿足第一范式的關系模式并不一定是一個好的關系模式第50頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem2NF（續）[例4]關系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)S1計算機中南樓C190S1計算機中南樓C296S2電子中北樓C188Sloc為學生住處，假設每個系的學生住在同一個地方函數依賴包括：

(Sno,Cno)FGradeSno→Sdept(Sno,Cno)PSdeptSno→Sloc(Sno,Cno)PSlocSdept→Sloc第51頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem

2NF（續）S-L-C的碼為(Sno,Cno)S-L-C滿足第一范式。非主屬性Sdept和Sloc部分函數依賴于碼(Sno,Cno)SnoCnoGradeSdeptSlocS-L-C第52頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystemSLC不是一個好的關系模式(1)插入異常

假設Sno＝95102，Sdept＝IS，Sloc＝N的學生還未選課，因課程號是主屬性，因此該學生的信息無法插入SLC。(2)刪除異常

假定某個學生本來只選修了3號課程這一門課。現在因身體不適，他連3號課程也不選修了。因課程號是主屬性，此操作將導致該學生信息的整個元組都要刪除。

第53頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystemSLC不是一個好的關系模式(3)數據冗余度大如果一個學生選修了10門課程，那么他的Sdept和Sloc值就要重復存儲了10次。(4)修改復雜

例如學生轉系，在修改此學生元組的Sdept值的同時，還可能需要修改住處（Sloc）。如果這個學生選修了K門課，則必須無遺漏地修改K個元組中全部Sdept、Sloc信息。

第54頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem2NF原因

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

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

SC（Sno，Cno，Grade）

SL（Sno，Sdept，Sloc）第55頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem2NF函數依賴圖：SnoCnoGradeSCSLSnoSdeptSloc第56頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem

2NF（續）2NF的定義

定義6.6

若R∈1NF，且每一個非主屬性完全函數依賴于碼（完全依賴于碼，消除了部分依賴），則R∈2NF。 例：S-L-C(Sno,Sdept,Sloc,Cno,Grade)∈1NFS-L-C(Sno,Sdept,Sloc,Cno,Grade)∈2NF SC（Sno，Cno，Grade）∈

2NF S-L（Sno，Sdept，Sloc）∈

2NF第57頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem

2NF（續）采用投影分解法將一個1NF的關系分解為多個2NF的關系，可以在一定程度上減輕原1NF關系中存在的插入異常、刪除異常、數據冗余度大、修改復雜等問題。將一個1NF關系分解為多個2NF的關系，并不能完全消除關系模式中的各種異常情況和數據冗余。第58頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化6.2.1函數依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規范化小結第59頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem

6.2.53NF3NF的定義

定義6.7

關系模式R<U，F>

中若不存在這樣的碼X、屬性組Y及非主屬性Z（ZY）,使得X→Y，Y→Z成立，

Y→X，則稱R<U，F>∈3NF。若R∈3NF，則每一個非主屬性既不部分依賴于碼也不傳遞依賴于碼。第60頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem3NF（續）數據冗余問題沒有得到解決，原因是：

Sno→SdeptSdept→SlocSdept→Sno

可得：

Sno→Sloc，即S-L中存在非主屬性對碼的傳遞函數依賴，S-L∈3NF傳遞例：2NF關系模式S-L(Sno,Sdept,Sloc)中

S1計算機中南樓

S2計算機中南樓

S3計算機中南樓

S4計算機中南樓第61頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem

3NF（續）函數依賴圖：S-LSnoSdeptSloc第62頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem3NF（續）解決方法采用投影分解法，把S-L分解為兩個關系模式，以消除傳遞函數依賴：S-D（Sno，Sdept）

D-L（Sdept，Sloc）S-D的碼為Sno，D-L的碼為Sdept。分解后的關系模式S-D與D-L中不再存在傳遞依賴第63頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemSnoSdeptS-DSdeptSlocD-LS-D的碼為Sno，D-L的碼為Sdept第64頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem3NF（續）采用投影分解法將一個2NF的關系分解為多個3NF的關系，可以在一定程度上解決原2NF關系中存在的插入異常、刪除異常、數據冗余度大、修改復雜等問題。將一個2NF關系分解為多個3NF的關系后，仍然不能完全消除關系模式中的各種異常情況和數據冗余。第65頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第66頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第三范式第67頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第68頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化6.2.1函數依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規范化小結第69頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第三范式還有問題嗎？第70頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第71頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第72頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem

6.2.6BC范式（BCNF）定義6.8

關系模式R<U，F>∈1NF，若X→Y且YX時X必含有碼，則R<U，F>∈BCNF。等價于：每一個決定屬性因素都包含碼第73頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第74頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemBCNF（續）[例5]關系模式C（Cno，Cname，Pcno）C∈3NF(沒有任何屬性對Cno部分函數依賴或傳遞函數依賴)C∈BCNF(Cno是唯一的決定因素)[例6]關系模式S（Sno，Sname，Sdept，Sage）假定S有兩個碼Sno，SnameS∈3NFS∈BCNF第75頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemBCNF（續）［例7］關系模式SJP（S，J，P）中，S表示學生，學生課程名次。語義：每個學生可以選修多門課程，每個學生選修每門課程的成績有一定的名次，每門課程中的每一名次只有一個學生。函數依賴：（S，J）→P；(J，P）→S（S，J）與（J，P）都可以作為候選碼，屬性相交第76頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemBCNF（續）第77頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化6.2.1函數依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規范化小結第78頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2.7多值依賴[例9]某一門課程由多個教師講授，使用多本不同的參考書。多值依賴：對于一個屬性值，另一個屬性有多個值與其對應。而多值屬性之間無關第79頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem多值依賴（續）Teaching∈BCNFTeaching具有唯一候選碼(C，T，B)，即全碼

Teaching模式中存在的問題(1)數據冗余度大(2)插入操作復雜：(當某一個課程增加一名教員，必須插入多個元組)(3)刪除操作復雜：(某一門課去掉一本參考書，必須刪除多個元組)(4)修改操作復雜存在多值依賴第80頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem多值依賴（續）定義6.9

設R(U)是一個屬性集U上的一個關系模式，X、Y和Z是U的子集，并且Z＝U－X－Y。關系模式R(U)中多值依賴

X→→Y成立，當且僅當對R(U)的任一關系r，給定的一對（x，z）值，有一組Y的值，這組值僅僅決定于x值而與z值無關例Teaching（C,T,B）

對于C的每一個值，T有一組值與之對應，而不論B取何值第81頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem多值依賴（續）多值依賴的另一個等價的形式化的定義：在R（U）的任一關系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值所得的兩個新元組必在r中），則Y多值依賴于X，記為X→→Y。這里，X，Y是U的子集，Z=U-X-Y。第82頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem多值依賴（續）平凡多值依賴和非平凡的多值依賴

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

X→→Y為平凡的多值依賴 否則稱X→→Y為非平凡的多值依賴第83頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem多值依賴（續）［例10］關系模式WSC（W，S，C）W表示倉庫，S表示保管員，C表示商品假設每個倉庫有若干個保管員，有若干種商品每個保管員保管所在的倉庫的所有商品每種商品被所有保管員保管WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C5第84頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem多值依賴（續）W→→S且W→→C對于W的每一個值Wi，S有一個完整的集合與之對應而不問C取何值，故W→→S。用下圖表示這種對應

此倉庫工作的全部保管員此倉庫中存放的所有商品第85頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem多值依賴的性質（1）多值依賴具有對稱性 若X→→Y，則X→→Z，其中Z＝U－X－Y（2）多值依賴具有傳遞性 若X→→Y，Y→→Z，則X→→Z–Y（3）函數依賴是多值依賴的特殊情況。 若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。第86頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem多值依賴的問題和解決方法用二維表表示第87頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第88頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化6.2.1函數依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規范化小結第89頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2.84NF定義6.10

關系模式R<U，F>∈1NF，如果對于R的每個非平凡多值依賴X→→Y（YX），X都含有碼，則R∈4NF。如果R∈4NF，則R∈BCNF不允許有非平凡且非函數依賴的多值依賴允許的非平凡多值依賴是函數依賴第90頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem4NF（續）例：Teaching(C,T,B)∈4NF

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

CT(C,T)∈4NF CB(C,B)∈4NFC→→T，C→→B是平凡多值依賴

第91頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem多值依賴與函數依賴的區別第92頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem多值依賴與函數依賴的區別(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）的嵌入型多值依賴第93頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem多值依賴與函數依賴的區別只要在R（U）的任何一個關系r中，元組在X和Y上的值滿足定義6.l（函數依賴），則函數依賴X→Y在任何屬性集W（XYWU）上成立。第94頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemAnIntroductiontoDatabaseSystem多值依賴與函數依賴的區別(2)

若函數依賴X→Y在R（U）上成立，則對于任何Y'Y均有X→Y'成立多值依賴X→→Y若在R(U)上成立，不能斷言對于任何Y'Y有X→→Y'成立第95頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem關系的三分解性第96頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem聯接依賴和第五范式第97頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2規范化6.2.1函數依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規范化小結第98頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.2.9規范化小結關系數據庫的規范化理論是數據庫邏輯設計的工具目的：盡量消除插入、刪除異常，修改復雜，數據冗余基本思想：逐步消除數據依賴中不合適的部分實質：概念的單一化第99頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem規范化小結（續）關系模式規范化的基本步驟

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

BCNF依賴 ↓消除非平凡且非函數依賴的多值依賴

4NF規范化的實質：“一事一地”，讓一個關系只描述一個實體或聯系，使關系單一化，以利于處理簡單化。第100頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem規范化小結（續）不能說規范化程度越高的關系模式就越好在設計數據庫模式結構時，必須對現實世界的實際情況和用戶應用需求作進一步分析，確定一個合適的、能夠反映現實世界的模式上面的規范化步驟可以在其中任何一步終止第101頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem范式對數據庫應用系統開發的作用需求分析概念結構設計邏輯機構設計數據庫物理設計數據庫實施數據庫運行維護實體、對象、聯系，了解工作過程語義對象、E-R圖R(A1,A2…An)UF={A1->A2…A1->An}規范化，構造好的關系模式第102頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem模式研究第103頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第104頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第105頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第六章關系數據理論6.1問題的提出6.2規范化6.3數據依賴的公理系統*6.4模式的分解6.5小結第106頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.3數據依賴的公理系統邏輯蘊含

定義6.11

對于滿足一組函數依賴F的關系模式R<U，F>，其任何一個關系r，若函數依賴X→Y都成立,（即r中任意兩元組t，s，若t[X]=s[X]，則t[Y]=s[Y]），則稱F邏輯蘊含X→Y第107頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem1.Armstrong公理系統關系模式R<U，F>來說有以下的推理規則：A1.自反律（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所蘊含。第108頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem定理6.1Armstrong推理規則是正確的（l）自反律:若Y

X

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

X

U

對R<U，F>

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

X，有t[y]=s[y]，所以X→Y成立，自反律得證第109頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem定理6.lArmstrong推理規則是正確的（續）(2)增廣律:若X→Y為F所蘊含，且Z

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

U。設R<U，F>

的任一關系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所蘊含，增廣律得證。第110頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem定理6.lArmstrong推理規則是正確的（續）(3)傳遞律：若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含。證：設X→Y及Y→Z為F所蘊含。對R<U，F>

的任一關系r中的任意兩個元組t，s：若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊含，傳遞律得證。第111頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem2.導出規則1.根據A1，A2，A3這三條推理規則可以得到下面三條推理規則：

合并規則：由X→Y，X→Z，有X→YZ。（A2，A3）

偽傳遞規則：由X→Y，WY→Z，有XW→Z。（A2，A3）

分解規則：由X→Y及ZY，有X→Z。（A1，A3）第112頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem導出規則2.根據合并規則和分解規則，可得引理6.1

引理6.lX→A1A2…Ak成立的充分必要條件是X→Ai成立（i=l，2，…，k）第113頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemArmstrong公理系統Armstrong公理系統是有效的、完備的有效性：由F出發根據Armstrong公理推導出來的每一個函數依賴一定在F+中；完備性：F+中的每一個函數依賴，必定可以由F出發根據Armstrong公理推導出來第114頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem3.函數依賴閉包定義6.l2

在關系模式R<U，F>中為F所邏輯蘊含的函數依賴的全體叫作F的閉包，記為F+。定義6.13

設F為屬性集U上的一組函數依賴，X

U，XF+={A|X→A能由F根據Armstrong公理導出}，XF+稱為屬性集X關于函數依賴集F的閉包第115頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemF的閉包F={XY,YZ}F+={Xφ, Yφ, Zφ, XYφ, XZφ, YZφ, XYZφ,XX, YY, ZZ, XYX, XZX, YZY, XYZX,XY, YZ, XYY, XZY, YZZ, XYZY,XZ, YYZ, XYZ, XZZ, YZYZ,XYZZ,XXY, XYXY,XZXY, XYZXY,XXZ, XYYZ,XZXZ, XYZYZ,XYZ, XYXZ,XZXY, XYZXZ,XZYZ, XYXYZ,XZXYZ, XYZXYZ}F={XA1,……,XAn}的閉包F+計算是一個NP完全問題第116頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem關于閉包的引理引理6.2

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

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

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

、判定Y是否為XF+的子集的問題第117頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem求閉包的算法算法6.1

求屬性集X（X

U）關于U上的函數依賴集F的閉包XF+

輸入：X，F 輸出：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）

（4）判斷X（i+1）=X

（i）嗎?（5）若相等或X（i）=U,則X（i）就是XF+,算法終止。（6）若否，則i=i+l，返回第（2）步。第118頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem算法6.1 對于算法6.1，令ai=|X（i）|，{ai

}形成一個步長大于1的嚴格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環就會終止。第119頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem函數依賴閉包[例1]已知關系模式R<U，F>，其中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）=AB∪CD=ABCD。(2)X（0）≠X（1）

X（2）=X（1）∪BE=ABCDE。(3)X（2）=U，算法終止

（AB）F+=ABCDE。第120頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem4.Armstrong公理系統的有效性與完備性定理6.2Armstrong公理系統是有效的、完備的證明：

1.有效性 可由定理6.1得證

2.完備性 只需證明逆否命題:

若函數依賴X→Y不能由F從Armstrong公理導出，那么它必然不為F所蘊含第121頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystemArmstrong公理系統完備性證明(1)引理:若V→W成立，且V

XF+，則W

XF+

(2)構造一張二維表r，它由下列兩個元組構成，可以證明r必是R（U，F）的一個關系，即F+中的全部函數依賴在r上成立。

XF+

U-XF+

11......1 00......0

11......1 11......1

(3)若X→Y不能由F從Armstrong公理導出，則Y不是XF+的子集。第122頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem5.函數依賴集等價定義6.14

如果G+=F+，就說函數依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價。引理6.3

F+=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+。第123頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.最小依賴集定義6.15

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

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

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

(3)F中不存在這樣的函數依賴X→A，X有真子集Z使得F-{X→A}∪{Z→A}與F等價。第124頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem最小依賴集[例2]關系模式S<U，F>，其中：

U={Sno，Sdept，Mname，Cno，Grade}，

F={Sno→Sdept，Sdept→Mname，(Sno，Cno)→Grade}

設F’={Sno→Sdept，Sno→Mname，Sdept→Mname，

(Sno，Cno)→Grade，(Sno，Sdept)→Sdept}F是最小覆蓋，而F’不是。因為：F’-{Sno→Mname}與F’等價

F’-{(Sno，Sdept)→Sdept}也與F’等價

第125頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem7.極小化過程定理6.3

每一個函數依賴集F均等價于一個極小函數依賴集Fm。此Fm稱為F的最小依賴集。證明:構造性證明，找出F的一個最小依賴集。

第126頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem極小化過程（續）(1)逐一檢查F中各函數依賴FDi：X→Y，若Y=A1A2…Ak，k>2，則用{X→Aj

|j=1，2，…，k}來取代X→Y。(2)逐一檢查F中各函數依賴FDi：X→A，令G=F-{X→A}，若AXG+，則從F中去掉此函數依賴。(3)逐一取出F中各函數依賴FDi：X→A，設X=B1B2…Bm，逐一考查Bi

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

）F+，則以X-Bi

取代X。第127頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem極小化過程（續）[例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不唯一極小化過程(定理6.3的證明)也是檢驗F是否為極小依賴集的一個算法第128頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem第六章關系數據理論6.1問題的提出6.2規范化6.3數據依賴的公理系統*6.4模式的分解6.5小結第129頁，課件共147頁，創作于2023年2月AnIntroductiontoDatabaseSystem6.4模式的分解模式分解不唯一R(Sno,Sdept,Dean)S1d1 羅

S2d2姚

S3d2姚第一種分解：F={Sno->Sdept,Sdept->Dean}SnoS1S2S3Sdeptd1d2Dean羅姚S1是哪個系的學生？羅是哪個系的系主任？D1系的系主任是誰？S1d1羅S1d1姚S1d2羅S1d2姚S2d1羅S2d1姚S2d2羅S2d2姚S3d1羅S3d1姚S3d2羅S3d2