數(shù)據(jù)庫系統(tǒng)概論：第6章 關(guān)系數(shù)據(jù)理論

1、數(shù)據(jù)庫系統(tǒng)概論An Introduction to Database System第六章 關(guān)系數(shù)據(jù)理論基于某個(gè)數(shù)據(jù)庫管理系統(tǒng)設(shè)計(jì)數(shù)據(jù)庫，如何基于數(shù)據(jù)庫系統(tǒng)編程第6章 關(guān)系數(shù)據(jù)理論第7章 數(shù)據(jù)庫設(shè)計(jì)第8章 數(shù)據(jù)庫編程第二篇 設(shè)計(jì)與應(yīng)用開發(fā)篇第六章 關(guān)系數(shù)據(jù)理論6.1 問題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解6.5 小結(jié)An Introduction to Database System6.1 問題的提出關(guān)系數(shù)據(jù)庫邏輯設(shè)計(jì)針對(duì)具體問題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設(shè)計(jì)的工具關(guān)系數(shù)據(jù)庫的規(guī)范化理論*問題的提出（續(xù)）關(guān)系模式由五部分組成，是一個(gè)五元組： R(U

2、, D, DOM, F)關(guān)系名R是符號(hào)化的元組語義U為一組屬性D為屬性組U中的屬性所來自的域DOM為屬性到域的映射F為屬性組U上的一組數(shù)據(jù)依賴問題的提出（續(xù)）由于D、DOM與模式設(shè)計(jì)關(guān)系不大，因此在本章中把關(guān)系模式看作一個(gè)三元組：R當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式R的一個(gè)關(guān)系作為二維表，關(guān)系要符合一個(gè)最基本的條件：每個(gè)分量必須是不可分開的數(shù)據(jù)項(xiàng)。滿足了這個(gè)條件的關(guān)系模式就屬于第一范式（1NF）*問題的提出（續(xù)）數(shù)據(jù)依賴是一個(gè)關(guān)系內(nèi)部屬性與屬性之間的一種約束關(guān)系通過屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間相互聯(lián)系是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象是數(shù)據(jù)內(nèi)在的性質(zhì)是語義的體現(xiàn)*問題的提出（續(xù)

3、）數(shù)據(jù)依賴的主要類型函數(shù)依賴（Functional Dependency，簡(jiǎn)記為FD）多值依賴（Multi-Valued Dependency，簡(jiǎn)記為MVD）*問題的提出（續(xù)）函數(shù)依賴普遍存在于現(xiàn)實(shí)生活中描述一個(gè)學(xué)生關(guān)系，可以有學(xué)號(hào)、姓名、系名等屬性。一個(gè)學(xué)號(hào)只對(duì)應(yīng)一個(gè)學(xué)生，一個(gè)學(xué)生只在一個(gè)系中學(xué)習(xí)“學(xué)號(hào)”值確定后，學(xué)生的姓名及所在系的值就被唯一確定。Sname=f(Sno)，Sdept=f(Sno)即Sno函數(shù)決定SnameSno函數(shù)決定Sdept記作SnoSname，SnoSdept* 問題的提出（續(xù)）例6.1 建立一個(gè)描述學(xué)校教務(wù)的數(shù)據(jù)庫。涉及的對(duì)象包括：學(xué)生的學(xué)號(hào)（Sno）所在系（Sd

4、ept）系主任姓名（Mname）課程號(hào)（Cno）成績(jī)（Grade）*問題的提出（續(xù)）假設(shè)學(xué)校教務(wù)的數(shù)據(jù)庫模式用一個(gè)單一的關(guān)系模式Student來表示，則該關(guān)系模式的屬性集合為： U Sno, Sdept, Mname, Cno, Grade 現(xiàn)實(shí)世界的已知事實(shí)（語義）：一個(gè)系有若干學(xué)生， 但一個(gè)學(xué)生只屬于一個(gè)系；一個(gè)系只有一名（正職）負(fù)責(zé)人；一個(gè)學(xué)生可以選修多門課程，每門課程有若干學(xué)生選修；每個(gè)學(xué)生學(xué)習(xí)每一門課程有一個(gè)成績(jī)。 *問題的提出（續(xù)）由此可得到屬性組U上的一組函數(shù)依賴F： F=SnoSdept, Sdept Mname, (Sno, Cno) Grade SnoCnoSdeptMna

5、meGrade*問題的提出（續(xù)）關(guān)系模式Student中存在的問題：（1）數(shù)據(jù)冗余浪費(fèi)大量的存儲(chǔ)空間每一個(gè)系主任的姓名重復(fù)出現(xiàn)，重復(fù)次數(shù)與該系所有學(xué)生的所有課程成績(jī)出現(xiàn)次數(shù)相同。*問題的提出（續(xù)）（2）更新異常（Update Anomalies）數(shù)據(jù)冗余 ，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。某系更換系主任后，必須修改與該系學(xué)生有關(guān)的每一個(gè)元組。*問題的提出（續(xù)）（3）插入異常（Insertion Anomalies）如果一個(gè)系剛成立，尚無學(xué)生，則無法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫。*問題的提出（續(xù)）（4）刪除異常（Deletion Anomalies）如果某個(gè)系的學(xué)生全部畢業(yè)了， 則在刪除

6、該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。*問題的提出（續(xù)）結(jié)論Student關(guān)系模式不是一個(gè)好的模式。一個(gè)“好”的模式應(yīng)當(dāng)不會(huì)發(fā)生插入異常、刪除異常和更新異常，數(shù)據(jù)冗余應(yīng)盡可能少。原因由存在于模式中的某些數(shù)據(jù)依賴引起的。解決方法用規(guī)范化理論改造關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴*問題的提出（續(xù)）把這個(gè)單一的模式分成三個(gè)關(guān)系模式：S(Sno,Sdept,Sno Sdept);SC(Sno,Cno,Grade,(Sno,Cno) Grade);DEPT(Sdept,Mname,Sdept Mname);這三個(gè)模式都不會(huì)發(fā)生插入異常、刪除異常的問題，數(shù)據(jù)的冗余也得到了控制。第六章 關(guān)系

7、數(shù)據(jù)理論6.1 問題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解6.5 小結(jié)6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)6.2.1 函數(shù)依賴1.函數(shù)依賴2.平凡函數(shù)依賴與非平凡函數(shù)依賴3.完全函數(shù)依賴與部分函數(shù)依賴4.傳遞函數(shù)依賴*1. 函數(shù)依賴定義6.1 設(shè)R(U)是一個(gè)屬性集U上的關(guān)系模式，X和Y是U的子集。若對(duì)于R(U)的任意一個(gè)可能的關(guān)系r，r 中不可能存在兩個(gè)元組在X上的屬性值相等， 而在Y上的屬性值不等， 則稱“X函數(shù)確定Y”

8、或“Y函數(shù)依賴于X”，記作XY。函數(shù)依賴（續(xù)）例 Student(Sno, Sname, Ssex, Sage, Sdept), 假設(shè)不允許重名，則有:Sno Ssex， Sno SageSno Sdept， Sno SnameSname Ssex， Sname SageSname Sdept但Ssex Sage, Ssex Sdept若XY，并且YX, 則記為XY。若Y不函數(shù)依賴于X, 則記為XY。函數(shù)依賴（續(xù)）SnoSnameSsexSageSdeptS1 張三男20計(jì)算機(jī)系S1李四女21自動(dòng)化系S3王五男20計(jì)算機(jī)系S4趙六男21計(jì)算機(jī)系S5田七男20計(jì)算機(jī)系 . . . . . . .

9、 . . . . . . . .違背了Sno Sname函數(shù)依賴（續(xù)）由下面的關(guān)系表, 能否得出Sno SnameSnoSnameSsexSageSdeptS1 張三男20計(jì)算機(jī)系S2李四女21自動(dòng)化系S3王五男20計(jì)算機(jī)系S4趙六男21計(jì)算機(jī)系S5田七男20計(jì)算機(jī)系 . . . . . . . . . . . . . . .函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。*函數(shù)依賴（續(xù)）函數(shù)依賴是語義范疇的概念，只能根據(jù)數(shù)據(jù)的語義來確定一個(gè)函數(shù)依賴。例如“姓名年齡”這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立*2. 平凡函數(shù)依賴與非平凡函

10、數(shù)依賴XY，但YX則稱XY是非平凡的函數(shù)依賴。XY，但YX 則稱XY是平凡的函數(shù)依賴。對(duì)于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義。若不特別聲明， 我們總是討論非平凡函數(shù)依賴。*平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）若XY，則X稱為這個(gè)函數(shù)依賴的決定因素（Determinant）。若XY，YX，則記作XY。若Y不函數(shù)依賴于X，則記作XY。*3. 完全函數(shù)依賴與部分函數(shù)依賴定義6.2 在R(U)中，如果XY，并且對(duì)于X的任何一個(gè)真子集X, 都有 X Y, 則稱Y對(duì)X完全函數(shù)依賴，記作X Y。若XY，但Y不完全函數(shù)依賴于X，則稱Y對(duì)X部分函數(shù)依賴，記作X YFP*完全函數(shù)依賴與部分函

11、數(shù)依賴（續(xù)）例 在關(guān)系SC(Sno, Cno, Grade)中，有： 由于：Sno Grade，Cno Grade， 因此：(Sno, Cno) Grade (Sno, Cno)Sno (Sno, Cno) CnoFPP*4. 傳遞函數(shù)依賴定義6.3 在R(U)中，如果XY(YX)，YX，YZ，ZY, 則稱Z對(duì)X傳遞函數(shù)依賴(transitive functional dependency)。記為：X Z。注: 如果YX, 即XY，則Z直接依賴于X，而不是傳遞函數(shù)依賴。例 在關(guān)系Std(Sno, Sdept, Mname)中，有：Sno Sdept，Sdept Mname，Mname傳遞函數(shù)依

12、賴于Sno傳遞6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)*6.2.2 碼定義6.4 設(shè)K為R中的屬性或?qū)傩越M合。若K U，則K稱為R的一個(gè)候選碼(Candidate Key)。如果U部分函數(shù)依賴于K，即K U,則K稱為超碼 （Surpkey）。候選碼是最小的超碼，即K的任意一個(gè)真子集都不是候選碼。若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼(Primary key)。FP*碼（續(xù)）主屬性與非主屬性包含在任何一個(gè)候選碼中的屬性 ，稱為主屬性 （Prime

13、 attribute） 不包含在任何碼中的屬性稱為非主屬性（Nonprime attribute）或非碼屬性（Non-key attribute） 全碼：整個(gè)屬性組是碼，稱為全碼（All-key） *碼（續(xù)）例6.2S(Sno, Sdept, Sage)，單個(gè)屬性Sno是碼 SC(Sno, Cno, Grade)中，(Sno, Cno)是碼例6.3 R(P,W,A) P：演奏者 W：作品 A：聽眾一個(gè)演奏者可以演奏多個(gè)作品某一作品可被多個(gè)演奏者演奏聽眾可以欣賞不同演奏者的不同作品 碼為(P,W,A)，即All-Key *碼（續(xù)）定義6.5 關(guān)系模式 R中屬性或?qū)傩越MX 并非 R的碼，但 X 是

14、另一個(gè)關(guān)系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼。SC(Sno,Cno,Grade)中，Sno不是碼Sno是 S(Sno,Sdept,Sage)的碼，則Sno是SC的外碼 主碼與外部碼一起提供了表示關(guān)系間聯(lián)系的手段6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)*6.2.3 范式范式是符合某一種級(jí)別的關(guān)系模式的集合。關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足 不同程度要求的為不同范式。范式的種類：第一范式(1NF)第二范式(2NF)第

15、三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)*范式（續(xù)）各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡(jiǎn)記為RnNF。一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解（schema decomposition）可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過程就叫規(guī)范化（normalization）。6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)*6.2.4 2NF定義6.6 若關(guān)系模式R1NF，并且每一個(gè)非主屬性都完全函數(shù)依賴于任何一個(gè)

16、候選碼，則R2NF例6.4 S-L-C(Sno,Sdept,Sloc,Cno,Grade)， Sloc為學(xué)生的住處，并且每個(gè)系的學(xué)生住在同一個(gè)地方。S-L-C的碼為(Sno,Cno)。函數(shù)依賴有(Sno,Cno)GradeSnoSdept, (Sno,Cno)SdeptSnoSloc, (Sno,Cno)SlocSdeptSlocFPP*2NF（續(xù)）SnoCnoGradeSdeptSloc關(guān)系模式S-L-C不屬于2NF非主屬性Sdept、Sloc并不完全依賴于碼*2NF（續(xù)）一個(gè)關(guān)系模式不屬于2NF，會(huì)產(chǎn)生以下問題：插入異常如果插入一個(gè)新學(xué)生，但該生未選課，即該生無Cno，由于插入元組時(shí)，必須

17、給定碼值，因此插入失敗。刪除異常如果S4只選了一門課C3，現(xiàn)在他不再選這門課，則刪除C3后，整個(gè)元組的其他信息也被刪除了。修改復(fù)雜如果一個(gè)學(xué)生選了多門課，則Sdept，Sloc被存儲(chǔ)了多次。如果該生轉(zhuǎn)系，則需要修改所有相關(guān)的Sdept和Sloc，造成修改的復(fù)雜化。*2NF（續(xù)）出現(xiàn)這種問題的原因例子中有兩類非主屬性：一類如Grade，它對(duì)碼完全函數(shù)依賴另一類如Sdept、Sloc，它們對(duì)碼不是完全函數(shù)依賴解決方法：用投影分解把關(guān)系模式S-L-C分解成兩個(gè)關(guān)系模式SC(Sno,Cno,Grade)S-L(Sno,Sdept,Sloc)2NF（續(xù)）SC的碼為(Sno,Cno),SL的碼為Sno，這

18、樣使得非主屬性對(duì)碼都是完全函數(shù)依賴了SnoCnoGradeSnoSdeptSloc圖6.4 SC中的函數(shù)依賴圖6.5 S-L中的函數(shù)依賴6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)* 6.2.5 3NF定義6.7 設(shè)關(guān)系模式R1NF,若R中不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，YZ成立，Y X不成立，則稱R 3NF。SC沒有傳遞依賴，因此SC 3NFS-L中Sno Sdept( Sdept Sno), SdeptSloc，可得Sno S

19、loc。解決的辦法是將S-L分解成S-D(Sno,Sdept) 3NFD-L(Sdept,Sloc) 3NF傳遞6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)* 6.2.6 BCNFBCNF（Boyce Codd Normal Form）由Boyce和Codd提出，比3NF更進(jìn)了一步。通常認(rèn)為BCNF是修正的第三范式，有時(shí)也稱為擴(kuò)充的第三范式。定義6.8 設(shè)關(guān)系模式R1NF，若X Y且Y X時(shí)X必含有碼，則RBCNF。換言之，在關(guān)系模式R中，如果每一個(gè)決定屬性集

20、都包含候選碼，則RBCNF。*BCNF（續(xù)）BCNF的關(guān)系模式所具有的性質(zhì)所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選碼沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性如果一個(gè)關(guān)系數(shù)據(jù)庫中的所有關(guān)系模式都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了模式的徹底分解，達(dá)到了最高的規(guī)范化程度，消除了插入異常和刪除異常。例6.5考察關(guān)系模式C(Cno,Cname,Pcno)它只有一個(gè)碼Cno，沒有任何屬性對(duì)Cno部分依賴或傳遞依賴，所以C3NF。同時(shí)C中Cno是唯一的決定因素，所以CBCNF。對(duì)于關(guān)系模式SC(Sno,Cno,Grade)可作同樣分析。BCNF（續(xù)）

21、例6.6 關(guān)系模式S(Sno,Sname,Sdept,Sage)，假定Sname也具有唯一性，那么S就有兩個(gè)碼，這兩個(gè)碼都由單個(gè)屬性組成，彼此不相交。其他屬性不存在對(duì)碼的傳遞依賴與部分依賴，所以S3NF。同時(shí)S中除Sno，Sname外沒有其他決定因素，所以S也屬于BCNF。BCNF（續(xù)）例6.7 關(guān)系模式SJP(S,J,P)中，S是學(xué)生，J表示 課程，P表示名次。每一個(gè)學(xué)生選修每門課程的 成績(jī)有一定的名次，每門課程中每一名次只有一 個(gè)學(xué)生（即沒有并列名次）。 由語義可得到函數(shù)依賴： (S,J)P；(J,P)S (S,J)與(J,P)都可以作為候選碼。 關(guān)系模式中沒有屬性對(duì)碼傳遞依賴或部分依賴，

22、所以 SJP3NF。 除(S,J)與(J,P)以外沒有其他決定因素，所以 SJPBCNF。BCNF（續(xù)）BCNF（續(xù)）例6.8 關(guān)系模式STJ(S,T,J)中，S表示學(xué)生，T表 示教師，J表示課程。每一教師只教一門課。每 門課有若干教師，某一學(xué)生選定某門課，就對(duì)應(yīng) 一個(gè)固定的教師。 由語義可得到函數(shù)依賴：(S,J)T；(S,T)J；TJ 因?yàn)闆]有任何非主屬性對(duì)碼傳遞依賴或部分依賴， STJ 3NF。 因?yàn)門是決定因素，而T不包含碼，所以STJ BCNF 關(guān)系。圖6.6 STJ中的函數(shù)依賴BCNF（續(xù)）對(duì)于不是BCNF的關(guān)系模式，仍然存在不合適的地方。非BCNF的關(guān)系模式也可以通過分解成為BCN

23、F。例如STJ可分解為ST(S,T)與TJ(T,J)，它們都是BCNF。BCNF（續(xù)）3NF和BCNF是在函數(shù)依賴的條件下對(duì)模式分解所能達(dá)到的分離程度的測(cè)度。一個(gè)模式中的關(guān)系模式如果都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了徹底的分離，已消除了插入和刪除的異常。3NF的“不徹底”性表現(xiàn)在可能存在主屬性對(duì)碼的部分依賴和傳遞依賴。6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)*6.2.7 多值依賴?yán)?.9設(shè)學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考

24、書。每個(gè)教員可以講授多門課程，每種參考書可以供多門課程使用用關(guān)系模式Teaching(C,T,B)來表示課程C、教師T和參考書B之間的關(guān)系。多值依賴（續(xù)）表6.3 非規(guī)范化關(guān)系示例課程 C教員 T參考書 B物理數(shù)學(xué)計(jì)算數(shù)學(xué)李 勇王 軍李 勇張 平張 平周 峰 普通物理學(xué)光學(xué)原理 物理習(xí)題集數(shù)學(xué)分析微分方程 高等代數(shù)數(shù)學(xué)分析*多值依賴（續(xù)）表6.4 規(guī)范化的二維表 Teaching 課程 C教員 T參考書 B物 理李 勇普通物理學(xué)物 理李 勇光學(xué)原理物 理李 勇物理習(xí)題集物 理王 軍普通物理學(xué)物 理王 軍光學(xué)原理物 理王 軍物理習(xí)題集數(shù) 學(xué)李 勇普通物理學(xué)數(shù) 學(xué)李 勇光學(xué)原理數(shù) 學(xué)李 勇物理習(xí)題

25、集數(shù) 學(xué)張 平普通物理學(xué)數(shù) 學(xué)張 平光學(xué)原理數(shù) 學(xué)張 平物理習(xí)題集*多值依賴（續(xù)）Teaching具有唯一候選碼(C,T,B)， 即全碼。TeachingBCNF *多值依賴（續(xù)）課程 C教員 T參考書 B物 理李 勇普通物理學(xué)物 理李 勇光學(xué)原理物 理李 勇物理習(xí)題集物 理王 軍普通物理學(xué)物 理王 軍光學(xué)原理物 理王 軍物理習(xí)題集數(shù) 學(xué)李 勇普通物理學(xué)數(shù) 學(xué)李 勇光學(xué)原理數(shù) 學(xué)李 勇物理習(xí)題集數(shù) 學(xué)張 平普通物理學(xué)數(shù) 學(xué)張 平光學(xué)原理數(shù) 學(xué)張 平物理習(xí)題集(1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲(chǔ)多少次。*多值依賴（續(xù)）課程 C教員 T參考書 B物 理李 勇普通物理學(xué)物 理李 勇光

26、學(xué)原理物 理李 勇物理習(xí)題集物 理王 軍普通物理學(xué)物 理王 軍光學(xué)原理物 理王 軍物理習(xí)題集數(shù) 學(xué)李 勇普通物理學(xué)數(shù) 學(xué)李 勇光學(xué)原理數(shù) 學(xué)李 勇物理習(xí)題集數(shù) 學(xué)張 平普通物理學(xué)數(shù) 學(xué)張 平光學(xué)原理數(shù) 學(xué)張 平物理習(xí)題集(2)增加操作復(fù)雜：當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組。*多值依賴（續(xù)）課程 C教員 T參考書 B物 理李 勇普通物理學(xué)物 理李 勇光學(xué)原理物 理李 勇物理習(xí)題集物 理王 軍普通物理學(xué)物 理王 軍光學(xué)原理物 理王 軍物理習(xí)題集數(shù) 學(xué)李 勇普通物理學(xué)數(shù) 學(xué)李 勇光學(xué)原理數(shù) 學(xué)李 勇物理習(xí)題集數(shù) 學(xué)張 平普通物理學(xué)數(shù) 學(xué)張 平光學(xué)原理數(shù) 學(xué)張

27、平物理習(xí)題集(3)刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組。*多值依賴（續(xù)）課程 C教員 T參考書 B物 理李 勇普通物理學(xué)物 理李 勇光學(xué)原理物 理李 勇物理習(xí)題集物 理王 軍普通物理學(xué)物 理王 軍光學(xué)原理物 理王 軍物理習(xí)題集數(shù) 學(xué)李 勇普通物理學(xué)數(shù) 學(xué)李 勇光學(xué)原理數(shù) 學(xué)李 勇物理習(xí)題集數(shù) 學(xué)張 平普通物理學(xué)數(shù) 學(xué)張 平光學(xué)原理數(shù) 學(xué)張 平物理習(xí)題集(4)修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組。產(chǎn)生原因:存在多值依賴*多值依賴（續(xù)）定義6.9 設(shè)R(U)是屬性集U上的一個(gè)關(guān)系模式。X,Y,Z是U的子集，并且

28、Z=U-X-Y。關(guān)系模式R(U)中多值依賴XY成立，當(dāng)且僅當(dāng)對(duì)R(U)的任一關(guān)系r，給定的一對(duì)(x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關(guān)。例 Teaching（C, T, B） 對(duì)于C的每一個(gè)值，T有一組值與之對(duì)應(yīng)，而不論B取何值。因此T多值依賴于C，即CT。 多值依賴（續(xù)）多值依賴的另一個(gè)等價(jià)的定義在R(U)的任一關(guān)系r中，如果存在元組t，s使得tX=sX，那么就必然存在元組w，vr，（w，v可以與s，t相同）, 使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交換s，t元組的Y值所得的兩個(gè)新元組必在r中則Y多值依賴于X，記為XY。這里X，Y是U的

29、子集，Z=U-X-Y。*多值依賴（續(xù)）平凡多值依賴和非平凡的多值依賴若XY，而Z，即Z為空，則稱XY為平凡的多值依賴。否則稱XY為非平凡的多值依賴。多值依賴（續(xù)）WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C5例6.10關(guān)系模式WSC(W,S,C)中，W表示倉庫，S 表示保管員，C 表示商品。假設(shè)每個(gè)倉庫有若干個(gè)保管員，有若干種商品。每個(gè)保管員保管所在倉庫的所有商品，每種商品被所有保管員保管。多值依賴（續(xù)）按照語義對(duì)于W的每一個(gè)值Wi，S有一個(gè)完整的集合與之對(duì)應(yīng)而不問C取何值。所以WS。如圖6.7所示對(duì)應(yīng)W的某一個(gè)值

30、Wi的全部S值記作SWi（表示此倉庫工作的全部保管員）全部C值記作CWi（表示在此倉庫中存放的所有商品）應(yīng)當(dāng)有SWi中的每一個(gè)值和CWi中的每一個(gè)C值對(duì)應(yīng)于是SWi與CWi之間正好形成一個(gè)完全二分圖，因而WS。多值依賴（續(xù)）由于C與S的完全對(duì)稱性，必然有WC成立。圖6.7 WS且WC多值依賴（續(xù)）多值依賴的性質(zhì)（1）多值依賴具有對(duì)稱性。即若XY，則XZ，其中ZUXY多值依賴的對(duì)稱性可以用完全二分圖直觀地表示出來。從例6.10 容易看出，因?yàn)槊總€(gè)保管員保管所有商品，同時(shí)每種商品被所有保管員保管，顯然若WS，必然有WC。*多值依賴（續(xù)）（2）多值依賴具有傳遞性。即若XY，YZ， 則 XZ -Y。（

31、3）函數(shù)依賴是多值依賴的特殊情況。即若XY，則 XY。（4）若XY，XZ，則XYZ。（5）若XY，XZ，則XYZ。（6）若XY，XZ，則XY-Z，XZ -Y。*多值依賴（續(xù)）多值依賴與函數(shù)依賴的區(qū)別（1）多值依賴的有效性與屬性集的范圍有關(guān)若XY在U上成立，則在W（XY W U）上一定成立；反之則不然，即XY在W（W U）上成立，在U上并不一定成立。原因：多值依賴的定義中不僅涉及屬性組X和Y，而且涉及U中其余屬性Z。*多值依賴（續(xù)） 多值依賴的有效性與屬性集的范圍有關(guān)（續(xù)）一般地，在R(U)上若有XY在W(W U)上成立，則稱XY為R(U)的嵌入型多值依賴。函數(shù)依賴XY的有效性僅決定于X、Y這兩

32、個(gè)屬性集的值只要在R(U)的任何一個(gè)關(guān)系r中，元組在X和Y上的值滿足定義6.l，則函數(shù)依賴XY在任何屬性集W(XY W U)上成立。*多值依賴（續(xù)）（2）若函數(shù)依賴XY在R (U)上成立，則對(duì)于任何Y Y均有XY 成立。多值依賴XY若在R(U)上成立，不能斷言對(duì)于任何Y Y有XY 成立。*多值依賴（續(xù)） 例如，關(guān)系R(A,B,C,D)，ABC成立，當(dāng)然也有AD成立。有R的一個(gè)關(guān)系實(shí)例，在此實(shí)例上AB是不成立的。ABCDa1b1c1d1a1b1c1d2a1b2c2d1a1b2c2d2表6.6 R的一個(gè)實(shí)例6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5

33、 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)*6.2.8 4NF定義6.10 關(guān)系模式R1NF，如果對(duì)于R的每個(gè)非平凡多值依賴XY（Y X），X都含有碼，則R4NF。4NF就是限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴。4NF所允許的非平凡多值依賴實(shí)際上是函數(shù)依賴。*4NF（續(xù)）如果一個(gè)關(guān)系模式是4NF， 則必為BCNF。在例6.10的WSC中，W S, WC,他們都是非平凡多值依賴。而W不是碼，關(guān)系模式WSC的碼是(W,S,C)，即All-key，因此WSC 4NF?？梢园裌SC分解成WS(W,S),WC(W,C)， WS4NF，W

34、C4NF。6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)*6.2.9 規(guī)范化小結(jié)在關(guān)系數(shù)據(jù)庫中，對(duì)關(guān)系模式的基本要求是滿足第一范式。規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界可能存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題解決方法就是對(duì)其進(jìn)行規(guī)范化，轉(zhuǎn)換成高級(jí)范式。*規(guī)范化小結(jié)（續(xù)）一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化。關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具。*規(guī)范化小結(jié)（續(xù)

35、）規(guī)范化的基本思想是逐步消除數(shù)據(jù)依賴中不合適的部分，使模式中的各關(guān)系模式達(dá)到某種程度的“分離”。即采用“一事一地”的模式設(shè)計(jì)原則讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去。因此 規(guī)范化實(shí)質(zhì)上是概念的單一化。*規(guī)范化小結(jié)（續(xù)）關(guān)系模式規(guī)范化的基本步驟 1NF 消除非主屬性對(duì)碼的部分函數(shù)依賴消除決定因素 2NF非碼的非平凡 消除非主屬性對(duì)碼的傳遞函數(shù)依賴函數(shù)依賴 3NF 消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴 BCNF 消除非平凡且非函數(shù)依賴的多值依賴 4NF圖6.8 規(guī)范化過程*規(guī)范化小結(jié)（續(xù)）不能說規(guī)范化程度越高的關(guān)系模式就越好。必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況

36、和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式。上面的規(guī)范化步驟可以在其中任何一步終止。第六章 關(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)定義6.11 對(duì)于滿足一組函數(shù)依賴F的關(guān)系模式 R ，其任何一個(gè)關(guān)系r，若函數(shù)依賴XY都成立（即r中任意兩元組t、s，若tX=sX，則 tY=sY），則稱F邏輯蘊(yùn)涵X Y。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)涵的函數(shù)依賴*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）Armstr

37、ong公理系統(tǒng) 設(shè)U為屬性集總體，F(xiàn)是U上的一組函數(shù)依賴， 于是有關(guān)系模式R 。對(duì)R 來說有以下的推理規(guī)則：A1 自反律（reflexivity rule）：若Y X U，則X Y 為F所蘊(yùn)涵。A2 增廣律（augmentation rule）：若XY為F所蘊(yùn)涵，且Z U，則XZYZ 為F所蘊(yùn)涵。A3 傳遞律（transitivity rule）：若XY及YZ為F所蘊(yùn)涵，則XZ 為F所蘊(yùn)涵。注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴, 自反律的使用并不依賴于F。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）定理6.1 Armstrong推理規(guī)則是正確的。證明A1 自反律 設(shè)Y X U 。對(duì)R 的任一關(guān)系r中

38、的任意兩個(gè)元組t、s：若tX=sX，由于Y X，有tY=sY，所以XY成立，自反律得證。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）A2 增廣律 設(shè)XY為F所蘊(yùn)涵，且Z U。對(duì)R 的任一關(guān)系r中任意的兩個(gè)元組t、s：若tXZ=sXZ，則有tX=sX和tZ=sZ；由XY，于是有tY=sY，所以tYZ=sYZ，XZYZ為F所蘊(yùn)涵，增廣律得證。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）A3 傳遞律 設(shè)XY及YZ為F所蘊(yùn)涵。對(duì)R 的任一關(guān)系r中的任意兩個(gè)元組t、s：若tX=sX，由于XY，有tY=sY；再由YZ，有tZ=sZ，所以XZ為F所蘊(yùn)涵，傳遞律得證。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推

39、理規(guī)則： 合并規(guī)則（union rule）：由XY，XZ，有XYZ。 偽傳遞規(guī)則（pseudo transitivity rule）：由XY，WYZ，有XWZ。 分解規(guī)則（decomposition rule）：由XY及ZY，有XZ。 *數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1引理6.1 XA1 A2Ak成立的充分必要條件是XAi成立（i=1，2，k）。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）定義6.12 在關(guān)系模式R中為F所邏輯蘊(yùn)涵的函數(shù)依賴的全體叫作F的閉包，記為F +。定義6.13 設(shè)F為屬性集U上的一組函數(shù)依賴，X、Y U， XF+= A|XA能由F根據(jù)Armstrong公理導(dǎo)

40、出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X、Y U，XY能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+。引理6.2的用途判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問題，就轉(zhuǎn)化為求出XF+，判定Y是否為XF+的子集的問題。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）求閉包的算法算法6.1 求屬性集X（X U）關(guān)于U上的函數(shù)依賴集F的閉包XF+ 輸入：X，F(xiàn)輸出：XF+步驟：迭代*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）令X(0)=X，i=0求B，這里B = A |( V)( W)(VWF V X(i)A W)。 X(i+1)=BX

41、(i) 。判斷X(i+1)= X(i) 。若X(i+1)與X(i)相等或X(i)=U ，則X(i)就是XF+，算法終止。若否，則i=i+1，返回第步。對(duì)X(i)中的每個(gè)元素，依次檢查相應(yīng)的函數(shù)依賴,將依賴它的屬性加入B *數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）例6.11 已知關(guān)系模式R，其中U=A, B, C, D, E；F=ABC, BD, CE, ECB, ACB。求(AB)F+ 。*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）解 ：由算法6.1，設(shè)X(0)=AB。計(jì)算X(1)：逐一的掃描F集合中各個(gè)函數(shù)依賴，找左部為A、B或AB的函數(shù)依賴。得到兩個(gè)：ABC，BD。于是X(1)=ABCD=ABCD。因?yàn)閄(0) X(1)，

42、所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到CE，ACB，于是X(2)=X(1)BE=ABCDE。因?yàn)閄(2)已等于全部屬性集合，所以(AB)F+ =ABCDE。參見愛課程網(wǎng)數(shù)據(jù)庫系統(tǒng)概論6.3節(jié)動(dòng)畫求閉包*數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）有效性與完備性的含義有效性：由F 出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F +中完備性：F +中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來*定理6.2 Armstrong公理系統(tǒng)是有效的、完備的。證明：1. 有效性有效性實(shí)際上是“正確性”可由定理6.1得證數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*2. 完備性 只需證明逆否命題：

43、若函數(shù)依賴XY不能由F從Armstrong公理導(dǎo)出，那么它必然不為F 所蘊(yùn)涵 分三步證明：（1） 若VW成立，且V XF+，則W XF+ 證：因?yàn)?V XF+，所以有XV成立； 因?yàn)閄 V，VW，于是XW 成立； 所以W XF+ 。 數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*（2）構(gòu)造一張二維表r，它由下列兩個(gè)元組構(gòu)成，可以證明r 必是R的一個(gè)關(guān)系，即F中的全部函數(shù)依賴在 r上成立。 XF+ U-XF+ 11.1 00.0 11.1 11.1 若r 不是R 的關(guān)系，則必由于F中有某一個(gè)函數(shù)依賴VW 在r上 不成立所致。由r 的構(gòu)成可知，V 必定是XF+ 的子集，而W 不是 XF+ 的子集，可是由第（1）步，W

44、 XF+，矛盾。所以r 必是R的一個(gè)關(guān)系。 數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*（3）若XY不能由F從Armstrong公理導(dǎo)出，則Y不是XF+的子集。（引理6.2） 因此必有Y的子集Y 滿足YU-XF+， 則XY 在r 中不成立， 即XY 必不為R 蘊(yùn)涵。數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*Armstrong公理的完備性及有效性說明:“導(dǎo)出”與“蘊(yùn)涵”是兩個(gè)完全等價(jià)的概念F+ ：為F所邏輯蘊(yùn)涵的函數(shù)依賴的全體（定義6.12 ）F+ ：可以說成由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴的集合數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*定義6.14 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與

45、G等價(jià)。兩個(gè)函數(shù)依賴集等價(jià)是指它們的閉包等價(jià)數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）函數(shù)依賴集等價(jià)的充要條件引理6.3 F+ = G+ 的充分必要條件是F G+和G F+ 。證: 必要性顯然，只證充分性。（1）若FG+ ，則XF+ XG+。（2）任取XYF+ 則有 Y XF+ XG+。 所以XY (G +)+=G+。即F+ G+。（3）同理可證G +F+，所以F +=G+。引理6.3給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法如何判定F G+？只需逐一對(duì)F中的函數(shù)依賴XY考察 Y 是否屬于XG+ 數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*定義6.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集，亦稱為最小依賴集或最小覆蓋。（1）F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。（2）F中不存在這樣的函數(shù)依賴XA， 使得F與 F-XA等價(jià)。 （3）F中不存在這樣的函數(shù)依賴XA， X有真 子集Z使得F-XAZA與F等價(jià)。 即F中的函數(shù)依賴均不能由F中其他函數(shù)依賴導(dǎo)出F中各函數(shù)依賴左部均為最小屬性集（不存在冗余屬性）數(shù)據(jù)依賴的公理系統(tǒng)（續(xù)）*例6.12 考察6.1節(jié)中的關(guān)系模式S，其中： U=Sno, Sdept, Mname, Cno, Grade， F=SnoSdept, SdeptM