數(shù)據(jù)庫系統(tǒng)概論第六章關(guān)系數(shù)據(jù)理論P(yáng)PT演示課件

1、數(shù)據(jù)庫系統(tǒng)概論 An Introduction to Database System 第六章 關(guān)系數(shù)據(jù)理論,第六章 關(guān)系數(shù)據(jù)理論,6.1 問題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴的公理系統(tǒng) *6.4 模式的分解 6.5 小結(jié),6.1 問題的提出,關(guān)系數(shù)據(jù)庫邏輯設(shè)計(jì) 針對具體問題，如何構(gòu)造一個適合于它的數(shù)據(jù)模式 數(shù)據(jù)庫邏輯設(shè)計(jì)的工具關(guān)系數(shù)據(jù)庫的規(guī)范化理論,關(guān)系模式的優(yōu)劣,結(jié)論 1、不是所有的關(guān)系都一樣好 2、關(guān)系模式設(shè)計(jì)的好壞影響數(shù)據(jù)庫的實(shí)用效率,問題的提出,一、概念回顧 二、關(guān)系模式的形式化定義 三、什么是數(shù)據(jù)依賴 四、關(guān)系模式的簡化定義 五、數(shù)據(jù)依賴對關(guān)系模式影響,一、概念回顧,關(guān)系：描

2、述實(shí)體、屬性、實(shí)體間的聯(lián)系。 從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。 關(guān)系模式：用來定義關(guān)系。 關(guān)系數(shù)據(jù)庫：基于關(guān)系模型的數(shù)據(jù)庫，利用關(guān)系來描述現(xiàn)實(shí)世界。 從形式上看，它由一組關(guān)系組成。 關(guān)系數(shù)據(jù)庫的模式：定義這組關(guān)系的關(guān)系模式的全體。,二、關(guān)系模式的形式化定義,關(guān)系模式由五部分組成，即它是一個五元組： R ( U, D, DOM, F),三、什么是數(shù)據(jù)依賴,1. 完整性約束的表現(xiàn)形式 限定屬性取值范圍：例如學(xué)生成績必須在0-100之間 定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設(shè)計(jì)的關(guān)鍵,2. 數(shù)據(jù)依賴 一個關(guān)系內(nèi)部屬性與屬性之間

3、的約束關(guān)系 現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象 數(shù)據(jù)內(nèi)在的性質(zhì) 語義的體現(xiàn),什么是數(shù)據(jù)依賴（續(xù)）,3. 數(shù)據(jù)依賴的類型 函數(shù)依賴（Functional Dependency，簡記為FD）,. 舉例：學(xué)生關(guān)系 學(xué)號值確定之后，姓名和所在系的值也被唯一的確定 Sname=f(Sno),Sdept=f(Sno) Sno-Sname,Sno-Sdept,3. 數(shù)據(jù)依賴的類型 多值依賴（Multivalued Dependency，簡記為MVD）,函數(shù)依賴的定義,四、關(guān)系模式的簡化表示,關(guān)系模式R（U, D, DOM, F） 簡化為一個三元組： R（U, F） 當(dāng)且僅當(dāng)U上的一個關(guān)系r滿足F時(shí)，r稱為關(guān)系模式

4、 R（U, F）的一個關(guān)系,五、數(shù)據(jù)依賴對關(guān)系模式的影響,例1建立一個描述學(xué)校教務(wù)的數(shù)據(jù)庫： 學(xué)生的學(xué)號（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程號（Cno） 成績（Grade） 單一的關(guān)系模式 ： Student U Sno, Sdept, Mname, Cno, Grade ,An Introduction to Database System,數(shù)據(jù)依賴對關(guān)系模式的影響（續(xù)）,學(xué)校數(shù)據(jù)庫的語義： 一個系有若干學(xué)生， 一個學(xué)生只屬于一個系； 一個系只有一名主任； 一個學(xué)生可以選修多門課程， 每門課程有若干學(xué)生選修； 每個學(xué)生所學(xué)的每門課程都有一個成績。,數(shù)據(jù)依賴對關(guān)系模

5、式的影響（續(xù)）,屬性組U上的一組函數(shù)依賴F： F Sno Sdept, Sdept Mname, (Sno, Cno) Grade ,An Introduction to Database System,關(guān)系模式Student中存在的問題, 數(shù)據(jù)冗余太大 浪費(fèi)大量的存儲空間 例：每一個系主任的姓名重復(fù)出現(xiàn) 更新異常（Update Anomalies） 數(shù)據(jù)冗余 ，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。 例：某系更換系主任后，系統(tǒng)必須修改與該系學(xué)生有關(guān)的每一個元組,An Introduction to Database System,關(guān)系模式Student中存在的問題, 插入異常（Insertion

6、 Anomalies） 該插入的數(shù)據(jù)無法存入數(shù)據(jù)庫 例，如果一個系剛成立，尚無學(xué)生，我們就無法把這個系及其系主任的信息存入數(shù)據(jù)庫。 刪除異常（Deletion Anomalies） 不該刪除的數(shù)據(jù)不得不刪 例，如果某個系的學(xué)生全部畢業(yè)了， 我們在刪除該系學(xué)生信息的同時(shí)，把這個系及其系主任的信息也丟掉了。,數(shù)據(jù)依賴對關(guān)系模式的影響（續(xù)）,結(jié)論： Student關(guān)系模式不是一個好的模式。 “好”的模式： 不會發(fā)生插入異常、刪除異常、更新異常 數(shù)據(jù)冗余應(yīng)盡可能少,原因：由存在于模式中的某些數(shù)據(jù)依賴引起的,解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴,分解關(guān)系模式,把這個單一模式分成3個關(guān)系模

7、式： S（Sno，Sdept，Sno Sdept）; SC（Sno，Cno，Grade，（Sno，Cno） Grade）; DEPT（Sdept，Mname，Sdept Mname）;,第六章 關(guān)系數(shù)據(jù)理論,6.1 問題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴的公理系統(tǒng) *6.4 模式的分解 6.5 小結(jié),6.2 規(guī)范化,規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。,6.2 規(guī)范化,6.2.1 函數(shù)依賴 6.2.2 碼 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多

8、值依賴 6.2.8 4NF 6.2.9 規(guī)范化小結(jié),6.2.1 函數(shù)依賴,函數(shù)依賴 平凡函數(shù)依賴與非平凡函數(shù)依賴 完全函數(shù)依賴與部分函數(shù)依賴 傳遞函數(shù)依賴,一、函數(shù)依賴,定義6.1 設(shè)R(U)是一個屬性集U上的關(guān)系模式，X和Y是U的子集。 若對于R(U)的任意一個可能的關(guān)系r，r中不可能存在兩個元組在X上的屬性值相等， 而在Y上的屬性值不等， 則稱 “X函數(shù)確定Y” 或 “Y函數(shù)依賴于X”，記作XY。,在任何時(shí)刻Student的關(guān)系實(shí)例中，不可能存在兩個元組在Sno上的值相等，而在Sdept上的值不等,An Introduction to Database System,說明：,1. 函數(shù)依賴

9、不是指關(guān)系模式R的某個或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。 2. 函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。 例如“姓名年齡”這個函數(shù)依賴只有在不允許有同名人的條件下成立 3. 數(shù)據(jù)庫設(shè)計(jì)者可以對現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。 例如：規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名年齡”成立。所插入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在， 則拒絕裝入該元組。,二、平凡函數(shù)依賴與非平凡函數(shù)依賴,在關(guān)系模式R(U)中，對于U的子集X和Y， 如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴 若XY，但Y X, 則稱XY是平凡的函數(shù)依賴,例：在關(guān)系SC(Sno

10、, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno (Sno, Cno) Cno,平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）,若XY，則X稱為這個函數(shù)依賴的決定屬性組，也稱為決定因素（Determinant）。 若XY，YX，則記作XY。 若Y不函數(shù)依賴于X，則記作XY。,三、完全函數(shù)依賴與部分函數(shù)依賴,定義6.2 在R(U)中，如果XY，并且對于X的任何一個真子集X，都有X Y, 則稱Y對X完全函數(shù)依賴，記作 X F Y。 若XY，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，記作X P Y。,四、傳遞函數(shù)依賴,定義6.

11、3 在R(U)中，如果XY，(Y X) ,YX YZ， 則稱Z對X傳遞函數(shù)依賴。記為：X Z 注: 如果YX， 即XY，則Z直接依賴于X。 例: 在關(guān)系Std(Sno, Sdept, Mname)中，有： Sno Sdept，Sdept Mname Mname傳遞函數(shù)依賴于Sno,傳遞,6.2 規(guī)范化,6.2.1 函數(shù)依賴 6.2.2 碼 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依賴 6.2.8 4NF 6.2.9 規(guī)范化小結(jié),6.2.2 碼,定義6.4 設(shè)K為R中的屬性或?qū)傩越M合。若K U， 則K稱為R的侯選碼（Candidate Ke

12、y）。 若候選碼多于一個，則選定其中的一個做為主碼（Primary Key）。,F,主屬性與非主屬性 包含在任何一個候選碼中的屬性 ，稱為主屬性（Prime attribute） 不包含在任何碼中的屬性稱為非主屬性（Nonprime attribute）或非碼屬性（Non-key attribute） 全碼 整個屬性組是碼，稱為全碼（All-key）,碼（續(xù)）,例2 關(guān)系模式S(Sno,Sdept,Sage)，單個屬性Sno是碼， SC（Sno，Cno，Grade）中，（Sno，Cno）是碼,例3 關(guān)系模式R（P，W，A） P：演奏者 W：作品 A：聽眾 一個演奏者可以演奏多個作品 某一作品可

13、被多個演奏者演奏 聽眾可以欣賞不同演奏者的不同作品 碼為(P，W，A)，即All-Key,外部碼,定義6.5 關(guān)系模式 R 中屬性或?qū)傩越MX 并非 R的碼，但 X 是另一個關(guān)系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼,如在SC（Sno，Cno，Grade）中，Sno不是碼，但Sno是關(guān)系模式S（Sno，Sdept，Sage）的碼，則Sno是關(guān)系模式SC的外部碼,主碼與外部碼一起提供了表示關(guān)系間聯(lián)系的手段,6.2 規(guī)范化,6.2.1 函數(shù)依賴 6.2.2 碼 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依賴 6.2.

14、8 4NF 6.2.9 規(guī)范化小結(jié),6.2.3 范式,范式是符合某一種級別的關(guān)系模式的集合 關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式,范式的種類： 第一范式(1NF) 第二范式(2NF) 第三范式(3NF) BC范式(BCNF) 第四范式(4NF) 第五范式(5NF),6.2.3 范式,各種范式之間存在聯(lián)系： 某一關(guān)系模式R為第n范式，可簡記為RnNF。 一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式的集合，這種過程就叫規(guī)范化,6.2 規(guī)范化,6.2.1 函數(shù)依賴 6.2.2 碼 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6

15、.2.6 BCNF 6.2.7 多值依賴 6.2.8 4NF 6.2.9 規(guī)范化小結(jié),6.2.4 2NF,1NF的定義 如果一個關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R1NF。即，不允許如下表的存在： 第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫 但是滿足第一范式的關(guān)系模式并不一定是一個好的關(guān)系模式,2NF（續(xù)）,例4 關(guān)系模式 S-L-C(Sno, Sdept, Sloc, Cno, Grade) S1 計(jì)算機(jī) 中南樓 C1 90 S1 計(jì)算機(jī) 中南樓 C2 96 S2 電子 中北樓 C1 88 Sloc為學(xué)生住處，假設(shè)每個系的學(xué)生住在同一個地方,

16、2NF（續(xù)）,S-L-C的碼為(Sno, Cno) S-L-C滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno),Sno,Cno,Grade,Sdept,Sloc,S-L-C,An Introduction to Database System,SLC不是一個好的關(guān)系模式,(1) 插入異常 假設(shè)Sno95102，SdeptIS，SlocN的學(xué)生還未選課，因課程號是主屬性，因此該學(xué)生的信息無法插入SLC。 (2) 刪除異常 假定某個學(xué)生本來只選修了3號課程這一門課?，F(xiàn)在因身體不適，他連3號課程也不選修了。因課程號是主屬性，此操作將導(dǎo)致該學(xué)生信息的整個元組都要刪除。,

17、An Introduction to Database System,SLC不是一個好的關(guān)系模式,(3) 數(shù)據(jù)冗余度大 如果一個學(xué)生選修了10門課程，那么他的Sdept和Sloc值就要重復(fù)存儲了10次。 (4) 修改復(fù)雜 例如學(xué)生轉(zhuǎn)系，在修改此學(xué)生元組的Sdept值的同時(shí)，還可能需要修改住處（Sloc）。如果這個學(xué)生選修了K門課，則必須無遺漏地修改K個元組中全部Sdept、Sloc信息。,An Introduction to Database System,2NF,原因 Sdept、 Sloc部分函數(shù)依賴于碼。 解決方法 SLC分解為兩個關(guān)系模式，以消除這些部分函數(shù)依賴 SC（Sno， Cno

18、， Grade） SL（Sno， Sdept， Sloc）,An Introduction to Database System,2NF,函數(shù)依賴圖：,2NF（續(xù)）,2NF的定義 定義6.6 若R1NF，且每一個非主屬性完全函數(shù)依賴于碼（完全依賴于碼，消除了部分依賴），則R2NF。 例：S-L-C(Sno, Sdept, Sloc, Cno, Grade) 1NF S-L-C(Sno, Sdept, Sloc, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF S-L（Sno， Sdept， Sloc） 2NF,2NF（續(xù)）,采用投影分解法將一個1NF的關(guān)系分解為

19、多個2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個1NF關(guān)系分解為多個2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。,6.2 規(guī)范化,6.2.1 函數(shù)依賴 6.2.2 碼 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依賴 6.2.8 4NF 6.2.9 規(guī)范化小結(jié),6.2.5 3NF,3NF的定義 定義6.7 關(guān)系模式R 中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，YZ成立， Y X，則稱R 3NF。 若R3NF，則每一個非主屬性既不部分

20、依賴于碼也不傳遞依賴于碼。,3NF（續(xù)）,數(shù)據(jù)冗余問題沒有得到解決，原因是： SnoSdept SdeptSloc Sdept Sno 可得： Sno Sloc，即S-L中存在非主屬性對碼的傳遞函數(shù)依 賴，S-L 3NF,傳遞,例：2NF關(guān)系模式S-L(Sno, Sdept, Sloc)中 S1 計(jì)算機(jī) 中南樓 S2 計(jì)算機(jī) 中南樓 S3 計(jì)算機(jī) 中南樓 S4 計(jì)算機(jī) 中南樓,3NF（續(xù)）,函數(shù)依賴圖：,3NF（續(xù)）,解決方法 采用投影分解法，把S-L分解為兩個關(guān)系模式，以消除傳遞函數(shù)依賴： S-D（Sno， Sdept） D-L（Sdept，Sloc） S-D的碼為Sno， D-L的碼為Sd

21、ept。 分解后的關(guān)系模式S-D與D-L中不再存在傳遞依賴,S-D的碼為Sno， D-L的碼為Sdept,3NF（續(xù)）,采用投影分解法將一個2NF的關(guān)系分解為多個3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個2NF關(guān)系分解為多個3NF的關(guān)系后，仍然不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。,第三范式,6.2 規(guī)范化,6.2.1 函數(shù)依賴 6.2.2 碼 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依賴 6.2.8 4NF 6.2.9 規(guī)范化小結(jié),第三范式還有問題嗎？,6.

22、2.6 BC范式（BCNF）,定義6.8 關(guān)系模式R1NF，若XY且Y X時(shí)X必含有碼，則R BCNF。 等價(jià)于：每一個決定屬性因素都包含碼,BCNF（續(xù)）,例5 關(guān)系模式C（Cno，Cname，Pcno） C3NF(沒有任何屬性對Cno部分函數(shù)依賴或傳遞函數(shù)依賴) CBCNF(Cno是唯一的決定因素),例6 關(guān)系模式S（Sno，Sname，Sdept，Sage） 假定S有兩個碼Sno，Sname S3NF S BCNF,BCNF（續(xù)）,例7關(guān)系模式SJP（S， J， P）中，S表示學(xué)生， 學(xué)生 課程 名次 。 語義：每個學(xué)生可以選修多門課程，每個學(xué)生選修每門課程的成績有一定的名次，每門課程中

23、的每一名次只有一個學(xué)生。 函數(shù)依賴：（S，J）P；(J，P）S （S，J）與（J，P）都可以作為候選碼，屬性相交,BCNF（續(xù)）,6.2 規(guī)范化,6.2.1 函數(shù)依賴 6.2.2 碼 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依賴 6.2.8 4NF 6.2.9 規(guī)范化小結(jié),6.2.7 多值依賴,例9 某一門課程由多個教師講授，使用多本不同的參考書。 多值依賴：對于一個屬性值，另一個屬性有多個值與其對應(yīng)。而多值屬性之間無關(guān),多值依賴（續(xù)）,TeachingBCNF Teaching具有唯一候選碼(C，T，B)， 即全碼,Teaching模式

24、中存在的問題 (1) 數(shù)據(jù)冗余度大 (2) 插入操作復(fù)雜：(當(dāng)某一個課程增加一名教員，必須插入多個元組) (3) 刪除操作復(fù)雜：(某一門課去掉一本參考書，必須刪除多個元組) (4) 修改操作復(fù)雜,存在 多值依賴,多值依賴（續(xù)）,定義6.9 設(shè)R(U)是一個屬性集U上的一個關(guān)系模式， X、 Y和Z是U的子集，并且ZUXY。關(guān)系模式R(U)中多值依賴 XY成立，當(dāng)且僅當(dāng)對R(U)的任一關(guān)系r，給定的一對（x，z）值，有一組Y的值，這組值僅僅決定于x值而與z值無關(guān) 例 Teaching（C, T, B） 對于C的每一個值，T有一組值與之對應(yīng)，而不論B取何值,多值依賴（續(xù)）,多值依賴的另一個等價(jià)的形式

25、化的定義： 在R（U）的任一關(guān)系r中，如果存在元組t，s 使得tX=sX，那么就必然存在元組 w，v r，（w，v可以與s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交換s，t元組的Y值所得的兩個新元組必在r中），則Y多值依賴于X，記為XY。 這里，X，Y是U的子集，Z=U-X-Y。,多值依賴（續(xù)）,平凡多值依賴和非平凡的多值依賴 若XY，而Z，則稱 XY為平凡的多值依賴 否則稱XY為非平凡的多值依賴,多值依賴（續(xù)）,例10關(guān)系模式WSC（W，S，C） W表示倉庫，S表示保管員，C表示商品 假設(shè)每個倉庫有若干個保管員，有若干種商品 每個保管員保管所在的

26、倉庫的所有商品 每種商品被所有保管員保管,多值依賴（續(xù)）,WS且WC,對于W的每一個值Wi，S有一個完整的集合與之對應(yīng)而不問C取何值，故 WS 。用下圖表示這種對應(yīng),此倉庫工作的全部保管員,此倉庫中存放的所有商品,多值依賴的性質(zhì),（1）多值依賴具有對稱性 若XY，則XZ，其中ZUXY （2）多值依賴具有傳遞性 若XY，YZ， 則XZ Y （3）函數(shù)依賴是多值依賴的特殊情況。 若XY，則XY。 （4）若XY，XZ，則XY Z。 （5）若XY，XZ，則XYZ。 （6）若XY，XZ，則XY-Z，XZ -Y。,多值依賴的問題和解決方法,用二維表表示,6.2 規(guī)范化,6.2.1 函數(shù)依賴 6.2.2 碼

27、 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依賴 6.2.8 4NF 6.2.9 規(guī)范化小結(jié),6.2.8 4NF,定義6.10 關(guān)系模式R1NF，如果對于R的每個非平凡多值依賴XY（Y X），X都含有碼，則R4NF。 如果R 4NF， 則R BCNF 不允許有非平凡且非函數(shù)依賴的多值依賴 允許的非平凡多值依賴是函數(shù)依賴,4NF（續(xù)）,例： Teaching(C,T,B) 4NF 存在非平凡的多值依賴CT，且C不是碼 用投影分解法把Teaching分解為如下兩個關(guān)系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡

28、多值依賴,多值依賴與函數(shù)依賴的區(qū)別,An Introduction to Database System,多值依賴與函數(shù)依賴的區(qū)別,(1) 有效性 多值依賴的有效性與屬性集的范圍有關(guān) 若XY在U上成立，則在W（X Y W U）上一定成立；反之則不然，即XY在W（W U）上成立，在U上并不一定成立 多值依賴的定義中不僅涉及屬性組 X和 Y，而且涉及U中其余屬性Z。 一般地，在R（U）上若有XY在W（W U）上成立，則稱XY為R（U）的嵌入型多值依賴,An Introduction to Database System,多值依賴與函數(shù)依賴的區(qū)別,只要在R（U）的任何一個關(guān)系r中，元組在X和Y上的值

29、滿足定義6.l（函數(shù)依賴）， 則函數(shù)依賴XY在任何屬性集W（X Y W U）上成立。,An Introduction to Database System,多值依賴與函數(shù)依賴的區(qū)別,(2) 若函數(shù)依賴XY在R（U）上成立，則對于任何Y Y均有XY 成立 多值依賴XY若在R(U)上成立，不能斷言對于任何Y Y有XY 成立,關(guān)系的三分解性,聯(lián)接依賴和第五范式,6.2 規(guī)范化,6.2.1 函數(shù)依賴 6.2.2 碼 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依賴 6.2.8 4NF 6.2.9 規(guī)范化小結(jié),6.2.9 規(guī)范化小結(jié),關(guān)系數(shù)據(jù)庫的規(guī)范化

30、理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具 目的：盡量消除插入、刪除異常，修改復(fù)雜，數(shù)據(jù)冗余 基本思想：逐步消除數(shù)據(jù)依賴中不合適的部分 實(shí)質(zhì)：概念的單一化,規(guī)范化小結(jié)（續(xù)）,關(guān)系模式規(guī)范化的基本步驟 1NF 函數(shù) 消除非主屬性對碼的部分函數(shù)依賴 消除決定屬性 2NF 集非碼的非平 消除非主屬性對碼的傳遞函數(shù)依賴 凡函數(shù)依賴 3NF 消除主屬性對碼的部分和傳遞函數(shù)依賴 BCNF 依賴 消除非平凡且非函數(shù)依賴的多值依賴 4NF 規(guī)范化的實(shí)質(zhì)：“一事一地”，讓一個關(guān)系只描述一個實(shí)體或聯(lián)系，使關(guān)系單一化 ，以利于處理簡單化。,規(guī)范化小結(jié)（續(xù)）,不能說規(guī)范化程度越高的關(guān)系模式就越好 在設(shè)計(jì)數(shù)據(jù)庫模式結(jié)構(gòu)時(shí)，必須對現(xiàn)實(shí)世

31、界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個合適的、能夠反映現(xiàn)實(shí)世界的模式 上面的規(guī)范化步驟可以在其中任何一步終止,范式對數(shù)據(jù)庫應(yīng)用系統(tǒng)開發(fā)的作用,需 求 分 析,概念結(jié)構(gòu)設(shè)計(jì),邏輯機(jī)構(gòu)設(shè)計(jì),數(shù)據(jù)庫物理設(shè)計(jì),數(shù)據(jù)庫實(shí)施,數(shù)據(jù)庫運(yùn)行維護(hù),實(shí)體、對象、聯(lián)系，了解工作過程,語義對象、E-R圖,R(A1,A2An) U F=A1-A2A1-An,規(guī)范化，構(gòu)造好的關(guān)系模式,模式研究,第六章 關(guān)系數(shù)據(jù)理論,6.1 問題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴的公理系統(tǒng) *6.4 模式的分解 6.5 小結(jié),6.3 數(shù)據(jù)依賴的公理系統(tǒng),邏輯蘊(yùn)含 定義6.11 對于滿足一組函數(shù)依賴 F 的關(guān)系模式R ，其任

32、何一個關(guān)系r，若函數(shù)依賴XY都成立, （即r中任意兩元組t，s，若tX=sX，則tY=sY），則稱F邏輯蘊(yùn)含X Y,1. Armstrong公理系統(tǒng),關(guān)系模式R 來說有以下的推理規(guī)則： A1.自反律（Reflexivity）：若Y X U，則X Y為F所蘊(yùn)含。 A2.增廣律（Augmentation）：若XY為F所蘊(yùn)含，且Z U，則XZYZ為F所蘊(yùn)含。 A3.傳遞律（Transitivity）：若XY及YZ為F所蘊(yùn)含，則XZ為F所蘊(yùn)含。,定理 6.1 Armstrong推理規(guī)則是正確的,（l）自反律: 若Y X U，則X Y為F所蘊(yùn)含 證: 設(shè)Y X U 對R 的任一關(guān)系r中的任意兩個元組t，

33、s： 若tX=sX，由于Y X，有ty=sy， 所以XY成立，自反律得證,定理 6.l Armstrong推理規(guī)則是正確的（續(xù)）,(2)增廣律: 若XY為F所蘊(yùn)含，且Z U，則XZYZ 為F所蘊(yùn)含。 證：設(shè)XY為F所蘊(yùn)含，且Z U。 設(shè)R 的任一關(guān)系r中任意的兩個元組t，s： 若tXZ=sXZ，則有tX=sX和tZ=sZ； 由XY，于是有tY=sY，所以tYZ=sYZ，所以 XZYZ為F所蘊(yùn)含，增廣律得證。,定理 6.l Armstrong推理規(guī)則是正確的（續(xù)）,(3) 傳遞律：若XY及YZ為F所蘊(yùn)含，則 XZ為 F所蘊(yùn)含。 證：設(shè)XY及YZ為F所蘊(yùn)含。 對R 的任一關(guān)系 r中的任意兩個元組

34、t，s： 若tX=sX，由于XY，有 tY=sY； 再由YZ，有tZ=sZ，所以XZ為F所蘊(yùn)含，傳遞 律得證。,2. 導(dǎo)出規(guī)則,1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有XYZ。 （A2， A3） 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 （A2， A3） 分解規(guī)則：由XY及 ZY，有XZ。 （A1， A3）,導(dǎo)出規(guī)則,2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1 引理6.l XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）,Armstrong公理系統(tǒng),Armstrong公理系統(tǒng)是有效的、完備的 有效性：由F出發(fā)根據(jù)Armstron

35、g公理推導(dǎo)出來的每一個函數(shù)依賴一定在F+中； 完備性：F+中的每一個函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來,3. 函數(shù)依賴閉包,定義6.l2 在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包，記為F+。 定義6.13 設(shè)F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包,F的閉包,F=XY, YZ F+= X,Y,Z,XY,XZ,YZ,XYZ, XX, YY, ZZ,XYX,XZX,YZY,XYZX, XY,Y Z,XYY,XZY,YZZ,XYZY, XZ,YYZ,XYZ

36、,XZZ,YZYZ,XYZZ, XXY,XYXY,XZXY,XYZXY, XXZ,XYYZ,XZXZ,XYZYZ, XYZ,XYXZ,XZXY,XYZXZ, XZYZ,XYXYZ,XZXYZ,XYZXYZ F=XA1, , XAn的閉包F+計(jì)算是一個NP完全問題,關(guān)于閉包的引理,引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能 由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+ 用途 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，轉(zhuǎn)化為求出XF+ 、判定Y是否為XF+的子集的問題,求閉包的算法,算法6.1 求屬性集X（X U）關(guān)于U上的函數(shù)依賴集F 的閉包

37、XF+ 輸入：X，F(xiàn)輸出：XF+ 步驟： （1）令X（0）=X，i=0 （2）求B，這里B = A |( V)( W)(VWFV X（i）A W)； （3）X（i+1）=BX（i） （4）判斷X（i+1）= X （i）嗎? （5）若相等或X（i）=U , 則X（i）就是XF+ , 算法終止。 （6）若否，則 i=i+l，返回第（2）步。,算法6.1,對于算法6.1， 令ai =|X（i）|，ai 形成一個步長大于1的嚴(yán)格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| - |X| 次循環(huán)就 會終止。,函數(shù)依賴閉包,例1 已知關(guān)系模式R，其中 U=A，B，C，D，E； F=ABC，B

38、D，CE，ECB，ACB。 求（AB）F+ 。 解 設(shè)X（0）=AB； (1) X（1）=ABCD=ABCD。 (2) X（0） X（1） X（2）=X（1）BE=ABCDE。 (3) X（2）=U，算法終止 （AB）F+ =ABCDE。,4. Armstrong公理系統(tǒng)的有效性與完備性,定理6.2 Armstrong公理系統(tǒng)是有效的、完備的 證明： 1. 有效性 可由定理6.1得證 2. 完備性 只需證明逆否命題: 若函數(shù)依賴XY不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含,Armstrong公理系統(tǒng)完備性證明,(1) 引理: 若VW成立，且V XF+，則W XF+ (2)

39、構(gòu)造一張二維表r，它由下列兩個元組構(gòu)成，可以證明r必是R（U，F(xiàn)）的一個關(guān)系，即F+中的全部函數(shù)依賴在 r上成立。 XF+ U-XF+ 11.1 00.0 11.1 11.1 (3) 若XY 不能由F從Armstrong公理導(dǎo)出，則Y 不是XF+ 的子集。,5. 函數(shù)依賴集等價(jià),定義6.14 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。 引理6.3 F+ = G+ 的充分必要條件是F G+ ，和G F+ 證: 必要性顯然，只證充分性。 （1）若FG+ ，則XF+ XG+ 。 （2）任取XYF+ 則有 Y XF+ XG+ 。 所以XY (G+）+= G+

40、。即F+ G+。 （3）同理可證G+ F+ ，所以F+ = G+。,6. 最小依賴集,定義6.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部僅含有一個屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價(jià)。 (3) F中不存在這樣的函數(shù)依賴XA， X有真子集Z使得F-XAZA與F等價(jià)。,最小依賴集,例2 關(guān)系模式S，其中： U= Sno，Sdept，Mname，Cno，Grade ， F= SnoSdept，SdeptMname，(Sno，Cno)Grade 設(shè)F=SnoSdept，SnoMname，Sd

41、eptMname， (Sno，Cno)Grade，(Sno，Sdept)Sdept F是最小覆蓋，而F不是。 因?yàn)椋篎 - SnoMname與F 等價(jià) F - (Sno，Sdept)Sdept也與F 等價(jià),7. 極小化過程,定理6.3 每一個函數(shù)依賴集F均等價(jià)于一個極小函數(shù)依賴 集Fm。此Fm稱為F的最小依賴集。 證明: 構(gòu)造性證明，找出F的一個最小依賴集。,極小化過程（續(xù)）,(1)逐一檢查F中各函數(shù)依賴FDi：XY，若Y=A1A2 Ak，k 2， 則用 XAj |j=1，2， k 來取代XY。 (2)逐一檢查F中各函數(shù)依賴FDi：XA，令G=F-XA， 若AXG+， 則從F中去掉此函數(shù)依賴。

42、 (3)逐一取出F中各函數(shù)依賴FDi：XA，設(shè)X=B1B2Bm， 逐一考查Bi （i=l，2，m），若A （X-Bi ）F+ ， 則以X-Bi 取代X。,極小化過程（續(xù)）,例3 F = AB，BA，BC，AC，CA Fm1、Fm2都是F的最小依賴集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依賴集Fm不唯一 極小化過程( 定理6.3的證明 )也是檢驗(yàn)F是否為極小依賴集的一個算法,第六章 關(guān)系數(shù)據(jù)理論,6.1 問題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴的公理系統(tǒng) *6.4 模式的分解 6.5 小結(jié),6.4 模式的分解,模式分解不唯一 R(Sno,Sdept,Dean) S1 d1 羅 S2 d2 姚 S3 d2 姚 第一種分解：,F=Sno-Sdept,Sdept-Dean,Sno S1 S2 S3,Sdept d1 d2,Dean 羅 姚,S1是哪個系的學(xué)生？,羅是哪個系的系主任？,D1系的系主任是誰？,S1 d1 羅,S1 d1 姚,S1 d2 羅,S1 d2 姚,S2 d1 羅,S2 d1 姚,S2 d2 羅,S2 d2 姚,S3 d1 羅,S3 d1 姚,S3 d2 羅,S3 d2 姚,6.4 模式的分解,6.4 模式的分解,把低一級的關(guān)系模