第六章關系數據理論劉潔liujie@2第六章關系數據理論6.1問題的提出6.2規范化6.3數據依賴的公理系統*6.4模式的分解6.5小結36.1問題的提出關系數據庫邏輯設計針對一個具體問題，如何構造一個適合于它的數據模式（構造幾個關系模式？每個關系由哪些屬性組成？）數據庫邏輯設計的有力工具─關系數據庫的規范化理論4問題的提出概念回顧關系模式的形式化定義什么是數據依賴關系模式的簡化定義數據依賴對關系模式影響5一、概念回顧關系描述實體、屬性、實體間的聯系從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集關系模式關系數據庫基于關系模型的數據庫，利用關系來描述現實世界關系數據庫的模式6二、關系模式的形式化定義關系模式由五部分組成，是一個五元組R(U,D,DOM,F)R：關系名U：一組屬性D：屬性組U中屬性所來自的域DOM：屬性到域的映射F：屬性組U上的一組數據依賴F7完整性約束的表現形式限定屬性取值范圍：例如學生成績必須在0-100之間定義屬性值間的相互關連（主要體現在值的相等與否），這就是數據依賴，它是數據庫模式設計的關鍵8三、什么是數據依賴一個關系內部屬性與屬性之間的一種約束關系通過屬性間值的相等與否體現出來的數據間相關聯系現實世界屬性間相互聯系的抽象數據內在的性質語義的體現9數據依賴的類型函數依賴

(FunctionalDependency，簡記為FD)多值依賴

(Multi-valuedDependency，簡記為MVD)其他,e.g.連接依賴，CFD,CIND10四、關系模式的簡化表示關系模式R(U,D,DOM,F)簡化為一個三元組：R<U,F>當且僅當U上的一個關系r滿足F時，r稱為關系模式R<U,F>的一個關系11五、數據依賴對關系模式的影響例1.建立一個描述學校教務的數據庫：學生的學號(Sno)、所在系(Sdept)系主任姓名(Mname)、課程號(Cno)、成績(Grade)單一的關系模式：Student<U,F>U＝｛Sno,Sdept,Mname,Cno,Grade｝12屬性組U上的一組函數依賴F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cno)→Grade｝SnoSdeptMnameCnoGrade13關系模式Student<U,F>中存在的問題數據冗余太大更新異常SnoSdeptMnameCnoGradeS1CS張明C195S2CS張明C190S3CS張明C188S4CS張明C170S5CS張明C178………插入異常刪除異常14結論Student關系模式不是一個好的模式“好”的模式不會發生插入異常、刪除異常、更新異常，數據冗余應盡可能少原因：由存在于模式中的某些數據依賴引起解決方法：通過分解關系模式來消除其中不合適的數據依賴15分解關系模式把這個單一模式分解為3個關系模式S(Sno,Sdept,Sno→Sdept)SC(Sno，Cno,Grade,(Sno，Cno)

→Grade);DEPT(Sdept,Mname,Sdept→Mname)166.2規范化規范化理論是用來改造關系模式，通過分解關系模式來消除其中不合適的數據依賴，以解決插入異常、刪除異常、更新異常和數據冗余問題。176.2規范化6.2.1 函數依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規范化小結186.2.1函數依賴函數依賴非平凡的函數依賴vs.平凡的函數依賴完全函數依賴vs.部分函數依賴傳遞函數依賴19一、函數依賴定義6.1設R(U)是屬性集U上的關系模式。X,Y是U的子集。若對于R(U)的任意一個可能的關系r，r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數確定Y”或“Y函數依賴于X”，記作X→Y。20關于函數依賴的幾點說明所有關系實例均要滿足函數依賴是語義范疇的概念，只能根據語義來確定一個函數依賴數據庫設計者可以對現實世界作強制的規定21二、非平凡的函數依賴vs.平凡的函數依賴在關系模式R(U)中，對于U的子集X和Y，如果X→Y，但Y

X，則稱X→Y是非平凡的函數依賴若X→Y，但YX,則稱X→Y是平凡的函數依賴例：在關系SC(Sno,Cno,Grade)中，非平凡的函數依賴：(Sno,Cno)→Grade平凡函數的依賴：(Sno,Cno)→Sno(Sno,Cno)→Cno22非平凡的函數依賴vs.平凡的函數依賴若X→Y，則X稱為這個函數依賴的決定屬性組，也稱為決定因素（Determinant）若X→Y，Y→X，則記作X←→Y若Y不函數依賴于X，則記作X

Y→23三、完全函數依賴與部分函數依賴定義6.2在關系模式R(U)中，如果X→Y，并且對于X的任何一個真子集X’，都有X’Y,則稱Y對X完全函數依賴，記作X

Y。若X→Y，但Y不完全函數依賴于X，則稱Y對X部分函數依賴，記作X

Y→FP24四、傳遞函數依賴定義6.3在關系模式R(U)中，如果X→Y,(YX)，Y→X,Y→Z，ZY，則稱Z對X傳遞函數依賴

(transitivefunctionaldependency)。注:如果Y→X，即X←→Y，則Z直接依賴于X例:在關系Student(Sno,Sdept,Mname)中Sno→Sdept，Sdept→MnameMname傳遞函數依賴于Sno256.2.2碼定義6.4設K為R<U,F>中的屬性或屬性組合。若，則K為R的侯選碼

(CandidateKey)若候選碼多于一個，則選定其中的一個為主碼(PrimaryKey)26主屬性與非主屬性包含在任何一個候選碼中的屬性，稱為主屬性

(Primeattribute)不包含在任何碼中的屬性稱為非主屬性(Nonprimeattribute)或非碼屬性(Non-keyattribute)全碼整個屬性組是碼，稱為全碼(All-key)27例2.關系模式S(Sno,Sdept,Sage)，Sno是碼SC(Sno，Cno，Grade)，(Sno，Cno)是碼例3.關系模式R(P，W，A)P：演奏者,W：作品,A：聽眾一個演奏者可以演奏多個作品某一作品可被多個演奏者演奏聽眾可以欣賞不同演奏者的不同作品碼為(P，W，A)，即All-Key28外部碼定義6.5關系模式R中屬性或屬性組X并非R的碼，但X是另一個關系模式的碼，則稱X是R的外部碼

(Foreignkey)，也稱外碼E.g.在SC(Sno，Cno，Grade)中，Sno不是碼，但Sno是關系模式S(Sno，Sdept，Sage)的碼。Sno是關系模式SC的外部碼主碼與外部碼一起提供了表示關系間聯系的手段296.2.3范式范式是符合某一種級別的關系模式的集合關系數據庫中的關系必須滿足一定的要求。滿足不同程度要求的為不同范式范式的種類第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)30各種范式之間的聯系1NF5NF4NFBCNF3NF2NF一個低一級范式的關系模式，通過模式分解可以轉換為若干個高一級范式的關系模式的集合，這種過程就叫規范化(normalization)5NF4NFBCNF3NF2NF1NF316.2.42NF1NF的定義如果一個關系模式R的所有屬性都是不可分的基本數據項，則R∈1NF第一范式是對關系模式的最起碼的要求。不滿足第一范式的數據庫模式不能稱為關系數據庫但是滿足第一范式的關系模式并不一定是一個好的關系模式32例4.關系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)Sloc為學生住處，假設每個系的學生住在同一個地方S-L-C的碼為(Sno,Cno)S-L-C滿足第一范式非主屬性Sdept和Sloc部分函數依賴于碼插入異常刪除異常數據冗余度大修改復雜33S-L-C不是一個好的關系模式原因Sdept,Sloc部分函數依賴于碼解決方法S-L-C分解為兩個關系模式，以消除這些部分函數依賴SC(Sno,Cno,Grade)S-L(Sno,Sdept,Sloc)34關系模式SC的碼為(Sno，Cno)關系模式S-L的碼為Sno非主屬性對碼都是完全函數依賴352NF定義6.6若R∈1NF，且每一個非主屬性完全函數依賴于碼，則R∈2NFExample362NF采用投影分解法將一個1NF的關系分解為多個2NF的關系，可以在一定程度上減輕原1NF關系中存在的插入異常、刪除異常、數據冗余度大、修改復雜等問題將一個1NF關系分解為多個2NF的關系，并不能完全消除關系模式中的各種異常情況和數據冗余376.2.53NF定義6.7關系模式R<U,F>中若不存在這樣的碼X，屬性組Y及非主屬性Z(ZY),使得X→Y，Y→Z成立，Y→X，則稱R<U,F>∈3NF若R∈3NF，則每一個非主屬性既不部分依賴于碼也不傳遞依賴于碼38例：2NF關系模式S-L(Sno,Sdept,Sloc)中存在非主屬性對碼的傳遞函數依賴，S-L3NF393NF采用投影分解法將一個2NF的關系分解為多個3NF關系，可以在一定程度上解決原2NF關系中存在插入異常、刪除異常、數據冗余度大、修改復雜等問題。將一個2NF關系分解為多個3NF的關系后，仍然不能完全消除關系模式中的各種異常情況和數據冗余。406.2.6BCNF定義6.8關系模式R<U,F>∈1NF，

若X→Y且YX時X必含有碼，

則R<U,F>∈BCNF等價于：每一個決定因素都包含碼41BCNF若R∈BCNF所有非主屬性對每一個碼都是完全函數依賴所有的主屬性對每一個不包含它的碼，也是完全函數依賴沒有任何屬性完全函數依賴于非碼的任何一組屬性42BCNFvs.3NFRBCNFR3NF43BCNF例5.關系模式C(Cno，Cname，Pcno)C∈3NFC∈BCNF例6.關系模式S(Sno，Sname，Sdept，Sage)假定S有兩個碼Sno，SnameS∈3NFS∈BCNF44例7.關系模式SJP(S，J，P)S:學生，J:課程,P:名次函數依賴：(S，J)→P；(J，P)→S(S，J)與(J，P)都可以作為候選碼,屬性相交SJP∈3NFSJP∈BCNF45例8.在關系模式STJ(S，T，J)中，S表示學生，T表示教師，J表示課程函數依賴：(S，J)→T，(S，T)→J，T→J候選碼：(S，J)和(S，T)

STJ3NF，沒有任何非主屬性對碼部分依賴或傳遞依賴STJBCNF，T是決定因素，T不包含碼46解決方法：將STJ分解為二個關系模式ST(S，T)∈BCNF，TJ(T，J)∈BCNF沒有任何非主屬性對碼的部分函數依賴和傳遞函數依賴476.2.7多值依賴例9.學校中某一門課程由多個教師講授，他們使用相同的一套參考書。每個教員可以講授多門課程，每種參考書可以供多門課程使用。48Teaching∈BCNFTeaching具有唯一候選碼(C，T，B)，即全碼刪除復雜插入復雜數據冗余度大修改復雜49多值依賴定義6.9設R(U)是屬性集U上的一個關系模式。X,Y,Z是U的子集，并且Z=U-X-Y。關系模式R(U)中多值依賴XY成立，當且僅當對R(U)的任一關系r，給定的一對(x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關。50多值依賴等價的形式化定義在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。51平凡的多值依賴vs.非平凡的多值依賴若X→→Y，而Z＝φ(即Z為空)，則稱X→→Y為平凡的多值依賴否則稱X→→Y為非平凡的多值依賴52例10.關系模式WSC（W，S，C）W表示倉庫，S表示保管員，C表示商品假設每個倉庫有若干個保管員，若干種商品每個保管員保管所在的倉庫的所有商品每種商品被所有保管員保管53WS且WC54多值依賴的性質多值依賴具有對稱性若X→→Y，則X→→Z，其中Z＝U－X－Y多值依賴具有傳遞性若X→→Y，Y→→Z，則X→→Z–Y函數依賴是多值依賴的特殊情況若X→Y，則X→→Y若X→→Y，X→→Z，則X→→YZ若X→→Y，X→→Z，則X→→Y∩Z若X→→Y，X→→Z，則X→→Y-Z，X→→Z-Y55多值依賴與函數依賴的區別多值依賴的有效性與屬性集的范圍有關若X→→Y在U上成立則在W(XYWU)上一定成立反之不然，若X→→Y在W(WU)上成立，在U上并不一定成立若函數依賴X→Y在R(U)上成立，則對于任何Y'Y均有X→Y’成立。而多值依賴X→→Y若在R(U)上成立，不能斷言對于任何Y'Y有X→→Y'成立566.2.84NF定義6.10關系模式R<U,F>∈1NF，如果對于R的每個非平凡多值依賴X→→Y(YX)，X都含有碼，則R∈4NF如果R∈4NF，則R∈BCNF不允許有非平凡且非函數依賴的多值依賴允許的非平凡多值依賴是函數依賴57例：Teaching(C,T,B)∈4NF存在非平凡的多值依賴C→→T，且C不是碼用投影分解法把Teaching分解為如下兩個關系模式：CT(C,T)∈4NFCB(C,B)∈4NFC→→T，C→→B是平凡多值依賴586.2.9規范化小結關系數據庫的規范化理論是數據庫邏輯設計的工具目的：盡量消除插入、刪除異常，修改復雜，數據冗余基本思想：逐步消除數據依賴中不合適的部分實質：概念的單一化59關系模式的規范化過程1NF↓2NF↓3NF↓BCNF↓4NF消除非主屬性對碼的部分函數依賴消除非主屬性對碼的傳遞函數依賴消除主屬性對碼的部分和傳遞函數依賴消除非平凡且非函數依賴的多值依賴消除決定因素非碼的非平凡函數依賴60規范化小結不能說規范化程度越高的關系模式越好在設計數據庫模式結構時，必須對現實世界的實際情況和用戶應用需求作進一步分析，確定一個合適的、能夠反映現實世界的模式上面的規范化步驟可以在其中任何一步終止616.3數據依賴的公理系統定義6.11對于滿足一組函數依賴F的關系模式R<U,F>，其任何一個關系r，若函數依賴X→Y都成立,(即r中任意兩元組t，s，

若t[X]=s[X]，則t[Y]=s[Y])，則稱

F邏輯蘊含X→Y62Armstrong公理系統設U為屬性集總體，F是U上的一組函數依賴，對關系模式R<U,F>有以下推理規則A1.自反律

(Reflexivityrule)：若Y

XU，則X→Y為F所蘊含A2.增廣律

(Augmentationrule)：若X→Y為F所蘊含，且ZU，則XZ→YZ為F所蘊含A3.傳遞律

(Transitivityrule)：若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含63定理6.1Armstrong推理規則是正確的自反律:若YX

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

U對R<U，F>的任一關系r中的任意兩個元組t，s若t[X]=s[X]，由于Y

X，有t[Y]=s[Y]所以X→Y成立，自反律得證。64增廣律:若X→Y為F所蘊含，且ZU，則XZ→YZ為F所蘊含證明：設X→Y為F所蘊含，且ZU設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所蘊含，增廣律得證。65傳遞律：若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所蘊含，傳遞律得證。66Armstrong公理的推理規則合并規則：由X→Y，X→Z，有X→YZ偽傳遞規則：由X→Y，WY→Z，有XW→Z分解規則：由X→Y及ZY，有X→Z67根據合并規則和分解規則，可得引理6.1，即

X→A1A2…Ak成立的充分必要條件是X→Ai成立(i=l，2，…，k)68Armstrong公理系統是有效的、完備的有效性：由F出發根據Armstrong公理推導出來的每一個函數依賴一定在F+中完備性：F+中的每一個函數依賴，必定可以由F出發根據Armstrong公理推導出來69函數依賴閉包定義6.l2在關系模式R<U,F>中為F所邏輯蘊含的函數依賴的全體叫作F的閉包(closure)，記為F+定義6.13設F為屬性集U上的一組函數依賴，XU，XF+={A|X→A能由F根據Armstrong公理導出}，XF+稱為屬性集X關于函數依賴集F的閉包70關于閉包的引理引理6.2.設F為屬性集U上的一組函數依賴，X,YU，X→Y能由F根據Armstrong公理導出的充分必要條件是YXF+用途：將判定X→Y是否能由F根據Armstrong公理導出的問題，轉化為求出XF+

，判定Y是否為XF+的子集的問題71算法6.1求屬性集X(XU)關于U上的函數依賴集F的閉包XF+Input：X，FOutput：XF+Steps:(1)

令X

(0)=X，i=0(2)

求B，這里B={A|(V)(W)(VWFVX(i)AW

)}(3)

X(i+1)=B∪X(i)(4)

判斷X(i+1)=

X(i)嗎?(5)

若相等或X(i)

=U,則X(i)就是XF+,Stop(6)

若否，則i=i+l，返回第（2）步72算法6.1對于算法6.1，令ai

=|X(i)|，{ai

}形成一個步長大于1的嚴格遞增的序列，序列的上界是|U|，因此該算法最多|U|-|X|次循環就會終止。73函數依賴閉包例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；X(1)=AB∪CD=ABCDX(0)≠X(1)X(2)=X(1)∪BE=ABCDEX(2)=U，算法終止(AB)F+

=ABCDE74Armstrong公理系統的有效性與完備性定理6.2.Armstrong公理系統是

有效的、完備的證明：有效性：可由定理6.1得證完備性：只需證明逆否命題:若函數依賴X→Y不能由F從Armstrong公理導出，那么它必然不為F所蘊含75函數依賴集等價定義6.14如果G+=F+，就說函數依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價76引理6.3F+=G+

的充分必要條件是FG+，