數(shù)據(jù)庫(kù)系統(tǒng)概論chp06課件

1、 數(shù)據(jù)庫(kù)系統(tǒng)概論第六章 關(guān)系數(shù)據(jù)理論第六章 關(guān)系數(shù)據(jù)理論6.1 問(wèn)題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解6.5 小結(jié)一、概念回顧關(guān)系關(guān)系模式關(guān)系數(shù)據(jù)庫(kù)關(guān)系數(shù)據(jù)庫(kù)的模式關(guān)系模式的形式化定義關(guān)系模式由五部分組成，即它是一個(gè)五元組： R(U, D, DOM, F)R： 關(guān)系名U： 組成該關(guān)系的屬性名集合D： 屬性組U中屬性所來(lái)自的域DOM： 屬性向域的映象集合F： 屬性間數(shù)據(jù)的依賴關(guān)系集合四、關(guān)系模式的簡(jiǎn)化表示關(guān)系模式R（U, D, DOM, F） 簡(jiǎn)化為一個(gè)三元組： R（U, F）當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式 R（U, F）的一個(gè)關(guān)系6.1 問(wèn)題的

2、提出關(guān)系數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)針對(duì)具體問(wèn)題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論例1建立一個(gè)描述學(xué)校教務(wù)的數(shù)據(jù)庫(kù)：學(xué)生的學(xué)號(hào)（Sno）、所在系（Sdept）系主任姓名（Mname）、課程名（Cname）成績(jī)（Grade）單一的關(guān)系模式 ： Student U Sno, Sdept, Mname, Cname, Grade 6.1 問(wèn)題的提出U Sno, Sdept, Mname, Cname, Grade U Sno, Sdept, Mname, Cname, Grade 6.1 問(wèn)題的提出 屬性組U上的一組函數(shù)依賴F： F Sno Sdept, Sdept Mna

3、me, (Sno, Cname) Grade SnoCnameSdeptMnameGrade6.1 問(wèn)題的提出關(guān)系模式中存在的問(wèn)題 數(shù)據(jù)冗余太大浪費(fèi)大量的存儲(chǔ)空間 例：每一個(gè)系主任信息重復(fù)出現(xiàn) 更新異常 數(shù)據(jù)冗余 ，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。例：系主任信息修改U Sno, Sdept, Mname, Cname, Grade 關(guān)系模式中存在的問(wèn)題 插入異常該插的數(shù)據(jù)插不進(jìn)去 例，插入一個(gè)新系信息。 刪除異常不該刪除的數(shù)據(jù)不得不刪例，某系學(xué)生全部畢業(yè)關(guān)系模式Student中存在的問(wèn)題1. 數(shù)據(jù)冗余太大2. 更新異常（Update Anomalies）3. 插入異常（Insertion A

4、nomalies）4. 刪除異常（Deletion Anomalies）數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）結(jié)論：Student關(guān)系模式不是一個(gè)好的模式?！昂谩钡哪Ｊ剑翰粫?huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過(guò)分解關(guān)系模式來(lái)消除其中不合適 的數(shù)據(jù)依賴什么是數(shù)據(jù)依賴（續(xù)）數(shù)據(jù)依賴一個(gè)關(guān)系內(nèi)部屬性與屬性之間的約束關(guān)系現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象數(shù)據(jù)內(nèi)在的性質(zhì)語(yǔ)義的體現(xiàn)什么是數(shù)據(jù)依賴（續(xù)）數(shù)據(jù)依賴的類型函數(shù)依賴（Functional Dependency，簡(jiǎn)記為FD）多值依賴（Multivalued Dependency，簡(jiǎn)記為MVD）其

5、他分解關(guān)系模式把這個(gè)單一模式分成3個(gè)關(guān)系模式： S（Sno，Sdept，Sno Sdept）; SC（Sno，Cno，Grade，（Sno，Cno） Grade）; DEPT（Sdept，Mname，Sdept Mname）第六章 關(guān)系數(shù)據(jù)理論6.1 問(wèn)題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解6.5 小結(jié)6.2 規(guī)范化 規(guī)范化理論正是用來(lái)改造關(guān)系模式，通過(guò)分解關(guān)系模式來(lái)消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問(wèn)題。6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.

6、2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)6.2.1 函數(shù)依賴函數(shù)依賴平凡函數(shù)依賴與非平凡函數(shù)依賴完全函數(shù)依賴與部分函數(shù)依賴傳遞函數(shù)依賴一、函數(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” 或 “Y函數(shù)依賴于X”，記作XY。 說(shuō)明 1. 所有關(guān)系實(shí)例均要滿足2. 語(yǔ)義范疇的概念3. 數(shù)據(jù)庫(kù)設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果XY，但Y X，則稱XY是非

7、平凡的函數(shù)依賴若XY，但Y X, 則稱XY是平凡的函數(shù)依賴?yán)涸陉P(guān)系SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno (Sno, Cno) Cno平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）若XY，則X稱為這個(gè)函數(shù)依賴的決定屬性組，也稱為決定因素（Determinant）。若XY，YX，則記作XY。若Y不函數(shù)依賴于X，則記作XY。三、完全函數(shù)依賴與部分函數(shù)依賴定義6.2 在R(U)中，如果XY，并且對(duì)于X的任何一個(gè)真子集X，都有X Y, 則稱Y對(duì)X完全函數(shù)依賴，記作X F Y。 若XY，但Y不完全函數(shù)依賴于X，則

8、稱Y對(duì)X部分函數(shù)依賴，記作X P Y。 完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）例1 中(Sno,Cno)Grade是完全函數(shù)依賴， (Sno,Cno)Sdept是部分函數(shù)依賴 FP因?yàn)镾noSdept成立，且Sno是（Sno，Cno）的真子集四、傳遞函數(shù)依賴定義6.3 在R(U)中，如果XY，(Y X) ,YX YZ， 則稱Z對(duì)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.

9、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的侯選碼（Candidate Key）。 若候選碼多于一個(gè)，則選定其中的一個(gè)做為主碼（Primary Key）。F碼（續(xù)）主屬性與非主屬性包含在任何一個(gè)候選碼中的屬性 ，稱為主屬性（Prime attribute） 不包含在任何碼中的屬性稱為非主屬性（Nonprime attribute）或非碼屬性（Non-key attribute） 全碼整個(gè)屬性組是碼，稱為全碼（All-key） 碼（續(xù)）例

10、3 關(guān)系模式R（P，W，A） P：演奏者 W：作品 A：聽眾 一個(gè)演奏者可以演奏多個(gè)作品 某一作品可被多個(gè)演奏者演奏 聽眾可以欣賞不同演奏者的不同作品 碼為(P，W，A)，即All-Key 外部碼定義6.5 關(guān)系模式 R 中屬性或?qū)傩越MX 并非 R的碼，但 X 是另一個(gè)關(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)系的手段復(fù) 習(xí)什么是函數(shù)依賴、非平凡函數(shù)依賴、完全函數(shù)依賴什么是碼？不好

11、的關(guān)系模式會(huì)存在哪些問(wè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)系模式的集合范式的種類：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)6.2.3 范式各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡(jiǎn)記為RnNF。一個(gè)低一級(jí)范式的關(guān)系模式，通過(guò)模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過(guò)程就叫規(guī)范化 6.2 規(guī)范化6.2.1 函數(shù)依賴6

12、.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 2NF1NF的定義如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R1NF第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫(kù)模式不能稱為關(guān)系數(shù)據(jù)庫(kù)但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式 2NF（續(xù)）2NF的定義定義6.6 若R1NF，且每一個(gè)非主屬性完全函數(shù)依賴于碼，則R2NF。2NF（續(xù)）例4 關(guān)系模式 S-L-C(Sno, Sdept, Sloc, Cno, Grade) Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生

13、住在同一個(gè)地方函數(shù)依賴包括： (Sno, Cno) F Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc 2NF（續(xù)）S-L-C的碼為(Sno, Cno)S-L-C滿足第一范式。非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno)SnoCnoGradeSdeptSlocS-L-CS-L-C不是一個(gè)好的關(guān)系模式（續(xù)）(1) 插入異常(2) 刪除異常(3) 數(shù)據(jù)冗余度大(4) 修改復(fù)雜S-L-C不是一個(gè)好的關(guān)系模式（續(xù)）原因 Sdept、 Sloc部分函數(shù)依賴于碼。解決方法 S-L-C分解為

14、兩個(gè)關(guān)系模式，以消除這些部分函數(shù)依賴 SC（Sno， Cno， Grade） 2NF S-L（Sno， Sdept， Sloc） 2NF2NF（續(xù)）函數(shù)依賴圖：SnoCnoGradeSCS-LSnoSdeptSloc關(guān)系模式SC的碼為（Sno，Cno）關(guān)系模式S-L的碼為Sno這樣非主屬性對(duì)碼都是完全函數(shù)依賴 2NF（續(xù)）采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。6.2 規(guī)范化6.2.1 函數(shù)依賴6.2

15、.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 3NF3NF的定義定義6.7 關(guān)系模式R 中若不存在這樣的碼X，屬性組Y及非主屬性Z（Z Y）, 使得XY，YZ 成立,Y X，則稱R 3NF。若R3NF，則每一個(gè)非主屬性既不部分依賴于碼也不傳遞依賴于碼。 3NF（續(xù)）例：2NF關(guān)系模式S-L(Sno, Sdept, Sloc)中函數(shù)依賴： SnoSdept Sdept Sno SdeptSloc 可得： SnoSloc， 傳遞所以S-L 3NF 3NF（續(xù)）函數(shù)依賴圖：S-LSnoSdep

16、tSloc3NF（續(xù)）解決方法 采用投影分解法，把S-L分解為兩個(gè)關(guān)系模式，以消除傳遞函數(shù)依賴： S-D（Sno， Sdept） D-L（Sdept，Sloc）S-D的碼為Sno， D-L的碼為Sdept。分解后的關(guān)系模式S-D與D-L中不再存在傳遞依賴 3NF（續(xù)）S-D的碼為Sno， D-L的碼為SdeptSnoSdeptS-DSdeptSlocD-L S-L(Sno, Sdept, Sloc) 2NF S-L(Sno, Sdept, Sloc) 3NF S-D(Sno，Sdept) 3NFD-L(Sdept， Sloc) 3NF6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3

17、范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié) 6.2.6 BC范式（BCNF）定義6.8 關(guān)系模式R1NF，若XY且Y X時(shí)X必含有碼，則RBCNF。等價(jià)于：每一個(gè)決定屬性因素都包含碼BCNF（續(xù)）若RBCNF 所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴所有的主屬性對(duì)每一個(gè)不包含它的碼，也是完全函數(shù)依賴沒(méi)有任何屬性完全函數(shù)依賴于非碼的任何一組屬性R BCNF R 3NF充分不必要BCNF（續(xù)）例5 關(guān)系模式C（Cno，Cname，Pcno）C3NFCBCNF例6 關(guān)系模式S（Sno，Sname，Sdept，Sage）假定S

18、有兩個(gè)碼Sno，SnameS3NF。S BCNFBCNF（續(xù)）例7關(guān)系模式SJP（S， J ， P） 學(xué)生 課程 名次函數(shù)依賴：（S，J）P；(J，P）S（S，J）與（J，P）都可以作為候選碼SJP3NFSJPBCNF BCNF（續(xù)）例8在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。函數(shù)依賴： (S，J)T，(S，T)J，TJ(S，J)和(S，T)都是候選碼 BCNF（續(xù)） JSJTSTSTJ中的函數(shù)依賴BCNF（續(xù)）STJ3NF沒(méi)有任何非主屬性對(duì)碼傳遞依賴或部分依賴STJBCNFT是決定因素，T不包含碼BCNF（續(xù)）解決方法：將STJ分解為二個(gè)關(guān)系模式： ST(S，T

19、) BCNF， TJ(T，J) BCNF 沒(méi)有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴STSTTJTJ3NF與BCNF的關(guān)系R BCNF R 3NF如果R3NF，且R只有一個(gè)候選碼 R BCNF R 3NF充分不必要充分必要判斷下列關(guān)系模式是否滿足BC范式1、R（X,Y,Z）F= Y-Z,Y-X,X-YZ 2、 管理（倉(cāng)庫(kù)號(hào)，設(shè) 備號(hào)，職工號(hào)） (語(yǔ)義：每個(gè)倉(cāng)庫(kù)有多個(gè)職工，一名職工只能在一個(gè)倉(cāng)庫(kù)工作，每個(gè)倉(cāng)庫(kù)一種設(shè)備僅有一名職工保管，每名職工可保管多種設(shè)備)職工號(hào) 倉(cāng)庫(kù)號(hào) （倉(cāng)庫(kù)號(hào),設(shè)備號(hào)） 職工號(hào)6.2 規(guī)范化6.2.1 函數(shù)依賴6.2.2 碼6.2.3 范式6.2.4 2NF6.2.5 3

20、NF6.2.6 BCNF6.2.7 多值依賴6.2.8 4NF6.2.9 規(guī)范化小結(jié)6.2.7 多值依賴?yán)? 學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。每個(gè)教員可以講授多門課程，每種參考書可以供多門課程使用。課 程 C教 員 T參 考 書 B物理數(shù)學(xué)計(jì)算數(shù)學(xué)李 勇王 軍李 勇張 平張 平 周 峰 普通物理學(xué)光學(xué)原理 物理習(xí)題集數(shù)學(xué)分析微分方程高等代數(shù)數(shù)學(xué)分析.多值依賴（續(xù)）非規(guī)范化關(guān)系普通物理學(xué)光學(xué)原理物理習(xí)題集普通物理學(xué)光學(xué)原理物理習(xí)題集數(shù)學(xué)分析微分方程高等代數(shù)數(shù)學(xué)分析微分方程高等代數(shù)李 勇李 勇李 勇王 軍王 軍王 軍李 勇李 勇李 勇張 平張 平張 平 物 理物 理物 理

21、物 理物 理物 理數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué) 參考書B教員T課程C多值依賴（續(xù)）用二維表表示Teaching多值依賴（續(xù)）TeachingBCNFTeaching具有唯一候選碼(C，T，B)， 即全碼 多值依賴（續(xù)） Teaching模式中存在的問(wèn)題(1)數(shù)據(jù)冗余度大 (2)插入操作復(fù)雜(3)刪除操作復(fù)雜(4)修改操作復(fù)雜存在多值依賴多值依賴（續(xù)）定義6.9 設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式， X、 Y和Z是U的子集，并且ZUXY，當(dāng)且僅當(dāng)對(duì)R的任一關(guān)系r，r在（X，Z）上的每個(gè)值對(duì)應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無(wú)關(guān)則多值依賴 XY成立 例 Teaching（C,

22、 T, B）多值依賴（續(xù)）多值依賴的另一個(gè)等價(jià)的形式化的定義： 在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值所得的兩個(gè)新元組必在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表示倉(cāng)庫(kù)，S表示保管員，C表示商品 假設(shè)每個(gè)倉(cāng)庫(kù)有若干個(gè)保

23、管員，有若干種商品 每個(gè)保管員保管所在的倉(cāng)庫(kù)的所有商品 每種商品被所有保管員保管 多值依賴（續(xù)）WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C5WS且WC多值依賴（續(xù)）WS且WC多值依賴的性質(zhì)（1）多值依賴具有對(duì)稱性若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。多值依賴與函數(shù)依賴的區(qū)別(1) 多值依賴的有效性與屬性集的范圍有關(guān)(2

24、) 若函數(shù)依賴XY在R（U）上成立，則對(duì)于任何Y Y均有XY 成立多值依賴XY若在R(U)上成立，不能斷言對(duì)于任何Y Y有XY 成立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.8 4NF定義6.10 關(guān)系模式R1NF，如果對(duì)于R的每個(gè)非平凡多值依賴XY（Y X），X都含有碼，則R4NF。如果R 4NF， 則R BCNF4NF（續(xù)）例： Teaching(C,T,B) 4NF 存在非平凡的多值依賴CT，且C不是碼。用投影分解法把Teaching分解為如下

25、兩個(gè)關(guān)系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依賴 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ù)庫(kù)的規(guī)范化理論是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具目的：盡量消除插入、刪除異常，修改復(fù)雜，數(shù)據(jù)冗余基本思想：逐步消除數(shù)據(jù)依賴中不合適的部分實(shí)質(zhì)：概念的單一化規(guī)范化小結(jié)（續(xù)）關(guān)系模式規(guī)范化的基本步驟 1NF 消除非主屬性對(duì)碼的部分函數(shù)依賴消除決定屬性 2NF集非碼的非平 消除非主屬性對(duì)碼的傳遞函數(shù)依賴凡函數(shù)依

26、賴 3NF 消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴 - BCNF 消除非平凡且非函數(shù)依賴的多值依賴 4NF規(guī)范化小結(jié)（續(xù)）不能說(shuō)規(guī)范化程度越高的關(guān)系模式就越好在設(shè)計(jì)數(shù)據(jù)庫(kù)模式結(jié)構(gòu)時(shí)，必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式上面的規(guī)范化步驟可以在其中任何一步終止第六章 關(guān)系數(shù)據(jù)理論6.1 問(wèn)題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解6.5 小結(jié)6.3 數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含定義6.11 對(duì)于滿足一組函數(shù)依賴 F 的關(guān)系模式R ，其任何一個(gè)關(guān)系r，若函數(shù)依賴XY都成立, 則稱F邏輯蘊(yùn)含X Y 例如，關(guān)系模式Student(

27、Sno，Sname， Sage，SD，SDname) 其屬性組上的函數(shù)依賴集為 F SnoSname，SnoSage，SnoSD， SDSDname ， SnoSDname就是F所邏輯蘊(yùn)含的一個(gè)函數(shù)依賴。函數(shù)依賴的邏輯蘊(yùn)含1. Armstrong公理系統(tǒng) 關(guān)系模式R 來(lái)說(shuō)有以下的推理規(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）自反律

28、: 若Y X U，則X Y為F所蘊(yùn)含 證: 設(shè)Y X U 對(duì)R 的任一關(guān)系r中的任意兩個(gè)元組t，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中任意的兩個(gè)元組t，s：若tXZ=sXZ，則有tX=sX和tZ=sZ；由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ為F所蘊(yùn)含，增廣律得證。2. 導(dǎo)出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有X

29、YZ。 （A2， A3） 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 （A2， A3） 分解規(guī)則：由XY及 ZY，有XZ。 （A1， A3）例：設(shè)有關(guān)系模式R(A,B,C,D,E)及其上的函數(shù)依賴集F=ABCD,AB,DE，求證F必蘊(yùn)涵AE。證明： AB （給定條件） AAB （A2增廣律） ABCD （給定條件） ACD （A3傳遞律） AC，AD （分解規(guī)則） DE （給定條件） AE （A3傳遞律） 證畢。舉例【例】 對(duì)于關(guān)系模式CSZ(CITY，ST， ZIP)，其屬性組上的函數(shù)依賴集為 F (CITY，ST)ZIP，ZIPCITY ，利用 Armstrong公理系統(tǒng)的推理規(guī)則，證明(ST

30、，ZIP)(CITY，ST，ZIP)。舉例證明:根據(jù)題意不難看出只要證明(ST，ZIP)是一個(gè)候選碼即可，證明步驟如下: 因?yàn)閆IPCITY (F中已給出) 所以(ST，ZIP)(CITY，ST) (利用增廣率，即在函數(shù)依賴的兩端加ST) (ST，ZIP)(CITY，ST，ZIP) (用增廣率，加ZIP)Armstrong公理系統(tǒng)Armstrong公理系統(tǒng)是有效的、完備的有效性：由F 出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)的每一個(gè)函數(shù)依賴一定在F+中；完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)3. 函數(shù)依賴閉包定義6.l2 在關(guān)系模式R中為F所邏輯蘊(yùn)含的

31、函數(shù)依賴的全體叫作 F的閉包(closure)，記為F +。定義6.13 設(shè)F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包例：設(shè)關(guān)系模式R(A,B,C)的函數(shù)依賴集為F=AB,BC，分別求A、B、C的閉包。 解：若XA， AB,BC（給定條件） AC （A2傳遞律） AA （A1自反律） =A，B，C （據(jù)定義）若X=B BB （A1自反律） BC （給定條件） =B，C （據(jù)定義） 若X=C CC （自反律） =C （據(jù)定義）例：設(shè)關(guān)系模式R(A,B,C)的函數(shù)依賴集為F=AB,BC，分別求A、B

32、、C的閉包。 舉例【例】已知關(guān)系模式R(U，F(xiàn))，U=A，B，C，D，E，F(xiàn)=AB，DC，BCE，ACB，求 、 。 解: =ABCDE =ABE F的閉包F=XY, YZF+=X,Y,Z,XY,XZ,YZ,XYZ, XX, YY, ZZ,XYX,XZX,YZY,XYZX,XY,Y Z,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+計(jì)算是一個(gè)NP完全問(wèn)題關(guān)

33、于閉包的引理引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+用途 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問(wèn)題，轉(zhuǎn)化為求出XF+ 、判定Y是否為XF+的子集的問(wèn)題5. 函數(shù)依賴集等價(jià)定義6.14 如果G +=F +，就說(shuō)函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。引理6.3 F + = G + 的充分必要條件是F G + ，和G F + 判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法定理6.3每個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴集Fm。6. 最小依賴集 定義6.15 如果函數(shù)依賴集F滿足下列條件

34、，則稱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à)。 最小依賴集例2 關(guān)系模式S，其中： U= Sno，Sdept，Mname，Cno，Grade ， F= SnoSdept，SdeptMname，(Sno， Cno)Grade 設(shè)F=SnoSdept，SnoMname，SdeptMname， (Sno，Cno)Grade，(Sno，Sdept)Sdept F是最小覆蓋，而F不是。 因?yàn)椋篎 -

35、SnoMname與F 等價(jià) F - (Sno，Sdept)Sdept也與F 等價(jià) 6. 最小依賴集 定義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ù)習(xí)1、Armstrong公理系統(tǒng)2、什么是閉包？如何求屬性的閉包？3、什么是最小函數(shù)依賴集？課后作業(yè)1.設(shè)有關(guān)系模式R(A,B,C,D)及R上的函數(shù)依賴集F,F=AB-C,C-D,D-Aa)推導(dǎo)出所有的

36、非平凡函數(shù)依賴b)求出R的所有候選碼a) AB-C,C-D 根據(jù)傳遞律可得 AB-D 又 C-D，D-A C-A 又 D-A ， AB-C 根據(jù)偽傳遞律可得BD-C 根據(jù)F推導(dǎo)的所有非平凡函數(shù)依賴為 AB-D C-A BD-CF=AB-C,C-D,D-Ab) L：B R： N： LR：A C D X=B Y=ACD X+=B (BA)+= ABCD (BC)+=ABCD (BD)+=ABCD AB、 BC 、BD均為候選碼F=AB-C,C-D,D-A算法：求函數(shù)依賴F的最小依賴集F多余，否則不多余，若包含則表示是否包含察是否多余，即考看是非單屬性的依賴，如中左邊的屬性：逐個(gè)檢查去掉各依賴左邊的

37、多余否則不去掉若是則去掉包含是否看，在剩下的依賴中求如掉它個(gè)依賴開始，去中多余的依賴：從第一去掉右邊均改為單屬性依賴用分解規(guī)則將所有依賴YAXYAXYFYXYXXYXF+,)3(,)()2()1(極小化處理= Fmin=求最小的函數(shù)依賴集例：設(shè)F是關(guān)系模式R(ABC)的FD集，F(xiàn)=ABC，BC，AB，ABC ，試求Fmin。F=ABC，BC，AB，ABC 先把F中的FD寫成右邊是單屬性形式：F=AB，AC，BC，AB，ABC 刪去重復(fù)的FD AB，得F=AB，AC，BC，ABC F中AC可從AB和BC推出，因此AC是冗余的，可刪去。得F=AB，BC，ABC F中ABC可從AB和BC推出，因此A

38、BC也可刪去。最后得F=AB,BC,即所求的Fmin。 極小化過(guò)程（續(xù)）例3 F = AB，BA，BC，AC，CA Fm1= AB，BC，CA Fm2= AB，BA，AC，CA Fm1、Fm2都是F的最小依賴集： F的最小依賴集Fm不唯一極小化過(guò)程也是檢驗(yàn)F是否為極小依賴集的一個(gè)算法求候選碼的方法將屬性分為四類L:僅出現(xiàn)在函數(shù)依賴的左邊R:僅出現(xiàn)在函數(shù)依賴的右邊N:兩邊均未出現(xiàn)LR:左右均出現(xiàn)求候選碼的方法1、令X代表L、N類，Y代表LR類2、求X的閉包，若X的閉包含R的全部屬性，則X為R的唯一候選碼，轉(zhuǎn)5，否則轉(zhuǎn)33、在Y中取屬性A,求(XA)的閉包，若它包含R的全部屬性，則轉(zhuǎn)4，否則換一個(gè)

39、屬性反復(fù)進(jìn)行這一過(guò)程，直到測(cè)完Y中的屬性4、如已找到所有候選碼，則轉(zhuǎn)5，否則在Y中依次取2，3個(gè)屬性，直到試完Y中所有組合5、結(jié)束輸出結(jié)果【例】設(shè)關(guān)系模式R(U，F(xiàn))，其中U=A，B，C，D，F(xiàn)=AC， CB， ADB。求R的候選碼。求候選碼的方法解:(1)檢查 F發(fā)現(xiàn)，A，D只出現(xiàn)在函數(shù)依賴的左部，所以為L(zhǎng)類屬性，X=AD,Y=C(2)根據(jù)求屬性閉包的算法，F(xiàn)中AC，ADB可以求得 =ABCD=U，故AD為R唯一的候選碼。 F=AC， CB， ADB例題設(shè)有關(guān)系模式R（A，B，C，D，E），其上的函數(shù)依賴集：F=ABC，CDE，BD，EA 計(jì)算B+。 求出R的所有候選關(guān)鍵字。 B+=BD。

40、R的候選關(guān)鍵字只可能由F中各個(gè)函數(shù)依賴的LR屬性組成，即A，B，C，D，E計(jì)算可知：A+=ABCDE，即AU，A是一個(gè)候選關(guān)鍵字。 B+=BD ,C+=C, D+=D, B、C、D不是候選碼E+=ABCDE，即EU，E是一個(gè)候選碼。F=ABC，CDE，BD，EA計(jì)算可知：（BC）+=ABCDE，即CDU （CD）+=ABCDE，即CDU，（BD）+=BD CD,BC都是候選關(guān)鍵字。R的所有候選關(guān)鍵字是A，BC，CD，E。F=ABC，CDE，BD，EA【例】設(shè)關(guān)系模式R(U，F(xiàn))，其中U=H，I，J，K，L，M，F(xiàn)=HI，KI，LMK，IK，KHM。求R的候選碼。求候選碼的方法解:(1)檢查 F

41、發(fā)現(xiàn)， H，L只出現(xiàn)在函數(shù)依賴的左部，所以為L(zhǎng)類屬性， J為N類的屬性。(2)根據(jù)求屬性閉包的算法，F(xiàn)中HI，IK， KHM可以求得 =HIJKLM=U，故HIJ為R唯一的候選碼。F=HI，KI，LMK，IK，KHM第六章 關(guān)系數(shù)據(jù)理論6.1 問(wèn)題的提出6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解6.5 小結(jié)6.4 模式的分解把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解等價(jià)的定義： 分解具有無(wú)損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無(wú) 損連接性模式的

42、分解（續(xù)）如果一個(gè)分解具有無(wú)損連接性，則它能夠保證不丟失信息如果一個(gè)分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況分解具有無(wú)損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn)。具有無(wú)損連接性的分解不一定能夠保持函數(shù)依賴；同樣，保持函數(shù)依賴的分解也不一定具有無(wú)損連接性。定理6.5:關(guān)系模式R(U，F(xiàn))的一個(gè)分解，= R1 (U1，F(xiàn)1)， R2 (U2，F(xiàn)2)具有無(wú)損連接的充分必要的條件是：U1U2U1-U2 F+ 或U1U2U2-U1 F+ 保持無(wú)損連接的分解【例】對(duì)給定的關(guān)系模式R(U，F(xiàn))，U=A，B，C，F(xiàn)=AB，如下的兩個(gè)分解：（1）1 = AB，BC（2）2 = AB，AC判斷這兩個(gè)

43、分解是否無(wú)損。舉例解:（1）可根據(jù)無(wú)損連接定理判斷本題 ABBC=B AB-BC=A BC-AB=C U=A，B，C，F(xiàn)=AB故1為有損連接。舉例（2）根據(jù)無(wú)損連接定理判斷本題 ABAC=A AB-AC=B AC-AB =C2為無(wú)損連接。(1)構(gòu)造一個(gè)n列k行表，每一行對(duì)應(yīng)于一個(gè)模式Ri（1ik），每一列對(duì)應(yīng)于一個(gè)屬性Aj（1jn），如下表所示。定理6.4判斷分解是無(wú)損連接的測(cè)試方法A1A2AnR1R2Rk(2) 初始表（填表）：若AjRi，則第i行第j列上填入aj，否則空著。(3) 修改表：取F中的某個(gè)函數(shù)依賴XY，在表中尋找與X對(duì)應(yīng)的列中含有相同屬性值的行，然后，將這些行中對(duì)應(yīng)Y的屬性的元

44、素進(jìn)行修改；若這些元素中有aj，則全部改為aj； (4) 這樣反復(fù)進(jìn)行，如發(fā)現(xiàn)某一行變成a1，a2，,ak，則此分解具有連接不失真性。例題已知R(ABCD), =AB,BC,CD, F=B A,C D判斷相對(duì)于F是否無(wú)損分解。=AB,BC,CD,F=B A,C D(a)初始表格 A B C DAB a1 a2BC a2 a3 CD a3 a4(b) 修改后的表格 A B C DAB a1 a2 BC a1 a2 a3 a4CD a3 a4 是無(wú)損分解例：設(shè)有R(U,F)，其中：U =(A,B,C,D,E),F=(AC,BC,CD,DEC,CEA)，R的一個(gè)分解為：R1(AD)，R2 (AB)，

45、R3(BE) ，R4(CDE) ，R5(AE)是否無(wú)損分解？表(a) 初始表格 ABCDER1:ADa1a4R2:ABa1a2R3:BEa2a5R4:CDEa3a4a5R5:AEa1a5表(b) 修改后的表格 ABCDER1:ADa1a3a4R2:ABa1a2a3R3:BEa2a5R4:CDEa3a4a5R5:AEa1a3a5表(b) 修改后的表格 ABCDER1:ADa1a3a4R2:ABa1a2a3R3:BEa2a3a5R4:CDEa3a4a5R5:AEa1a3a5表(b) 修改后的表格 ABCDER1:ADa1a3a4R2:ABa1a2a3a4R3:BEa2a3a4a5R4:CDEa3a

46、4a5R5:AEa1a3a4a5表(b) 修改后的表格 ABCDER1:ADa1a3a4R2:ABa1a2a3a4R3:BEa1a2a3a4a5R4:CDEa1a3a4a5R5:AEa1a3a4a5 是無(wú)損分解判斷分解保持函數(shù)依賴的測(cè)試方法設(shè)關(guān)系模式R的一個(gè)分解=R1,R2，Rk, F是R的依賴集，如果F等價(jià)于 R1（F）U R2（F） U U Rk（F）,則稱分解具有依賴保持性 例 題給定關(guān)系模式R,其中U=A,B,C,D,F=A B,B C,C D,D A,判斷關(guān)系模式R的分解=AB,BC,CD是否具有依賴保持性F=A B,B C,C D,D A=AB,BC,CD解: AB(F)=A B,

47、B A BC(F)=B C, C B CD(F)=CD, DC AB(F) U BC(F) U CD(F)=A B ,B A, B C ,C B,C D,D C從中可以看到A B ,B C,C D均得以保持,又D+=ABCD, D A也得到保持該分解具有依賴保持性分解成2NF模式集的算法設(shè)R(U),主鍵W,若R上存在FD XZ,且Z是非主屬性和XW，則XZ是一個(gè)部分函數(shù)依賴。此時(shí)應(yīng)把R分解成兩個(gè)模式: R1(XZ),主鍵是X； R2(Y),其中Y=U-Z,主鍵仍是W,外鍵是X(參照R1)利用外鍵和主鍵的聯(lián)接可以從R1和R2重新得到R。如果R1和R2還不是2NF，則重復(fù)上述過(guò)程，一直到數(shù)據(jù)庫(kù)模式

48、中每一個(gè)關(guān)系模式都是2NF為止。 算法:分解成3NF模式集的算法 設(shè)R(U)，主鍵W,若R上存在FD XZ。且Z是非主屬性，ZX，X不是候選鍵，則WZ就是一個(gè)傳遞依賴。此時(shí)應(yīng)把R分解成兩個(gè)模式： R1(XZ)，主鍵是X； R2(Y)，其中Y=U-Z,主鍵W,外鍵X(參照R1);利用外鍵和主鍵相匹配機(jī)制，R1和R2通過(guò)聯(lián)接可以重新得到R。如果R1和R2還不是3NF，則重復(fù)上述過(guò)程，一直到數(shù)據(jù)庫(kù)模式中每一個(gè)關(guān)系模式都是3NF為止。 算法6.3：轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解 對(duì) R 中的函數(shù)依賴集F進(jìn)行“極小化處理”，仍記為F。 找出不在F中出現(xiàn)的屬性，把這樣的屬性構(gòu)成一個(gè) 關(guān)系模式。把這些屬性

49、從U中去掉，剩余的屬性仍記為U。 若有 X A F，且XA=U，則 R，算法終止 否則, 每一組函數(shù)依賴Fi所涉及的全部屬性形成一個(gè)屬性集Ui 。若Ui Uj (ij)就去掉Ui 。設(shè)有關(guān)系模式R（A，B，C，D，E），R的函數(shù)依賴集：F=AD，ED，DB，BCD，CDA求R的候選關(guān)鍵字。將R分解為3NF。 例：解： 設(shè)U=（A，B，C，D，E），由于（CE）+=ABCDER的唯一候選關(guān)鍵字是CE。 求出最小依賴集Fm=AD，ED，DB，BCD，CDA將R分解為3NF：=AD，DE，BD，BCD，ACD，化簡(jiǎn)得=DE，BCD，ACD例： F=AD，ED，DB，BCD，CDA設(shè)關(guān)系模式RU，F(xiàn)，

50、U=C，T，H，R，S，G，X，Y，Z，F(xiàn)=CT，CSG，HRC，HSR，THR，CX，將R分解為3NF，且保持函數(shù)依賴。解：該函數(shù)依賴集已經(jīng)是最小化的，則分解為： =YZ，CT，CX，CSG，HRC，HSR，THR.算法：轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解算法6.4： 轉(zhuǎn)換為3NF既有無(wú)損連接性又保持函數(shù)依賴的分解 設(shè) X 是 R 的碼。 R 已由算法分解為R1， R2， ，Rk， 令 Rx 。 若有某個(gè)Ui ，X Ui ,將 Rx 從 中去掉。把這些屬性從U中去掉，剩余的屬性仍記為U。 就是所求的分解。 【例】有關(guān)系模式RU，F(xiàn)，U=C，T，H，R，S，G，F(xiàn)=CT，CSG，HRC，HSR，

51、THR，將R分解為3NF，且既具有無(wú)損連接性又能保持函數(shù)依賴。解：可以求得關(guān)系模式R的碼為HS，它的一個(gè)保持函數(shù)依賴的3NF為： =CT，CSG，HRC，HSR，THR. HS是關(guān)鍵字， HS ，HS是HSR的一個(gè)子集 = CT，CSG，HRC，HSR，THR為滿足要求的分解。算法6.5 轉(zhuǎn)換為BCNF的無(wú)損連接的分解 令R 檢查中各關(guān)系模式是否均屬于BCNF。若是， 則算法終止。 設(shè)中Ri不屬于BCNF,那么必有X A Fi+ (AX)，且X非Ri的碼。因此，XA是Ui的真子集。對(duì)Ri進(jìn)行分解：S1,S2,Us1=XA, Us2=Ui-A，以代替Ri返回第步。【例】設(shè)有關(guān)系模式RU，F(xiàn)，U=CTHRSG，F(xiàn)= CT，