1、An Introduction to Database System數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論An Introduction to Database System第六章第六章 關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論An Introduction to Database System第六章第六章 關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論6.1 問(wèn)題的提出問(wèn)題的提出6.2 規(guī)范化規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解模式的分解6.5 小結(jié)小結(jié)An Introduction to Database System6.1 問(wèn)題的提出問(wèn)題的提出關(guān)系數(shù)據(jù)庫(kù)邏輯設(shè)計(jì) 針對(duì)具體問(wèn)題，如何構(gòu)造一個(gè)適合于它的數(shù)

2、據(jù)模式 數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論An Introduction to Database System問(wèn)題的提出問(wèn)題的提出一、概念回顧二、關(guān)系模式的形式化定義三、什么是數(shù)據(jù)依賴四、關(guān)系模式的簡(jiǎn)化定義五、數(shù)據(jù)依賴對(duì)關(guān)系模式影響An Introduction to Database System一、概念回顧一、概念回顧v 關(guān)系v 關(guān)系模式v 關(guān)系數(shù)據(jù)庫(kù)v 關(guān)系數(shù)據(jù)庫(kù)的模式An Introduction to Database System二、關(guān)系模式的形式化定義二、關(guān)系模式的形式化定義關(guān)系模式由五部分組成，即它是一個(gè)五元組： R(U, D, DOM, F)R： 關(guān)系名U： 組成該關(guān)

3、系的屬性名集合D： 屬性組U中屬性所來(lái)自的域DOM： 屬性向域的映象集合F： 屬性間數(shù)據(jù)的依賴關(guān)系集合An Introduction to Database System三、什么是數(shù)據(jù)依賴三、什么是數(shù)據(jù)依賴1. 完整性約束的表現(xiàn)形式v 限定屬性取值范圍：例如學(xué)生成績(jī)必須在0-100之間v 定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫(kù)模式設(shè)計(jì)的關(guān)鍵An Introduction to Database System什么是數(shù)據(jù)依賴（續(xù)）什么是數(shù)據(jù)依賴（續(xù)）2. 數(shù)據(jù)依賴v一個(gè)關(guān)系內(nèi)部屬性與屬性之間的約束關(guān)系v現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象v數(shù)據(jù)內(nèi)在的性質(zhì)v語(yǔ)義的體現(xiàn)A

4、n Introduction to Database System什么是數(shù)據(jù)依賴（續(xù)）什么是數(shù)據(jù)依賴（續(xù)）3. 數(shù)據(jù)依賴的類型v 函數(shù)依賴（Functional Dependency，簡(jiǎn)記為FD）v 多值依賴（Multivalued Dependency，簡(jiǎn)記為MVD）v 其他An Introduction to Database System四、關(guān)系模式的簡(jiǎn)化表示四、關(guān)系模式的簡(jiǎn)化表示v 關(guān)系模式R（U, D, DOM, F） 簡(jiǎn)化為一個(gè)三元組： R（U, F）v 當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r滿足F時(shí)，r稱為關(guān)系模式 R（U, F）的一個(gè)關(guān)系A(chǔ)n Introduction to Database

5、 System五、五、數(shù)據(jù)依賴對(duì)關(guān)系模式的影響數(shù)據(jù)依賴對(duì)關(guān)系模式的影響例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 An Introduction to Database System數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)） 屬性組U上的一組函數(shù)依賴F： F Sno Sdept, Sdept Mname, (Sno, Cname) Grade SnoCnameSdeptMname

6、GradeAn Introduction to Database System關(guān)系模式關(guān)系模式Student中存在的問(wèn)題中存在的問(wèn)題1. 數(shù)據(jù)冗余太大2. 更新異常（Update Anomalies）3. 插入異常（Insertion Anomalies）4. 刪除異常（Deletion Anomalies）An Introduction to Database System數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）結(jié)論：nStudent關(guān)系模式不是一個(gè)好的模式。n“好”的模式：不會(huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解

7、決方法：通過(guò)分解關(guān)系模式來(lái)消除其中不合適 的數(shù)據(jù)依賴An Introduction to Database System分解關(guān)系模式分解關(guān)系模式v把這個(gè)單一模式分成3個(gè)關(guān)系模式： S（Sno，Sdept，Sno Sdept）; SC（Sno，Cno，Grade，（Sno，Cno） Grade）; DEPT（Sdept，Mname，Sdept Mname）An Introduction to Database System第六章第六章 關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論6.1 問(wèn)題的提出問(wèn)題的提出6.2 規(guī)范化規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解模式的分解6.5 小結(jié)小結(jié)

8、An Introduction to Database System6.2 規(guī)范化規(guī)范化 規(guī)范化理論正是用來(lái)改造關(guān)系模式，通過(guò)分解關(guān)系模式來(lái)消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問(wèn)題。An Introduction to Database System6.2 規(guī)范化規(guī)范化6.2.1 函數(shù)依賴函數(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é)規(guī)范化小結(jié)An Introduction to Database System6.2.1 函數(shù)依賴函數(shù)依賴v

9、函數(shù)依賴v平凡函數(shù)依賴與非平凡函數(shù)依賴v完全函數(shù)依賴與部分函數(shù)依賴v傳遞函數(shù)依賴An Introduction to Database System一、函數(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。 An Introduction to Database System說(shuō)明說(shuō)明 1. 所有關(guān)系實(shí)例均要滿足2. 語(yǔ)義范疇的概念3. 數(shù)據(jù)庫(kù)設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定An Introdu

10、ction to Database System二、平凡函數(shù)依賴與非平凡函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴若XY，但Y X, 則稱XY是平凡的函數(shù)依賴v 例：在關(guān)系SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno (Sno, Cno) CnoAn Introduction to Database System平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)） 若XY，則X稱為這個(gè)函數(shù)依賴的決定

11、屬性組，也稱為決定因素（Determinant）。 若XY，YX，則記作XY。 若Y不函數(shù)依賴于X，則記作XY。An Introduction to Database System三、完全函數(shù)依賴與部分函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴定義定義6.2 在R(U)中，如果XY，并且對(duì)于X的任何一個(gè)真子集X，都有X Y, 則稱Y對(duì)X完全函數(shù)依賴，記作 X F Y。 若XY，但Y不完全函數(shù)依賴于X，則稱Y對(duì)X部分函數(shù)依賴，記作X P Y。 An Introduction to Database System完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）例1 中(Sno,Cno)

12、Grade是完全函數(shù)依賴， (Sno,Cno)Sdept是部分函數(shù)依賴 因?yàn)镾no Sdept成立，且Sno是（Sno，Cno）的真子集 FPAn Introduction to Database System四、傳遞函數(shù)依賴四、傳遞函數(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傳遞An Introduction to Database Sys

13、tem6.2 規(guī)范化規(guī)范化6.2.1 函數(shù)依賴函數(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é)規(guī)范化小結(jié)An Introduction to Database System6.2.2 碼碼定義定義6.4 設(shè)K為R中的屬性或?qū)傩越M合。若K U， 則K稱為R的侯選碼（Candidate Key）。 若候選碼多于一個(gè)，則選定其中的一個(gè)做為主碼（Primary Key）。FAn Introduction to Database System碼（續(xù)）碼（續(xù)）v 主屬性與非主屬性 包含在

14、任何一個(gè)候選碼中的屬性 ，稱為主屬性（Prime attribute） 不包含在任何碼中的屬性稱為非主屬性（Nonprime attribute）或非碼屬性（Non-key attribute） v 全碼 整個(gè)屬性組是碼，稱為全碼（All-key） An Introduction to Database System碼（續(xù)）碼（續(xù)）例2 關(guān)系模式S(Sno,Sdept,Sage)，單個(gè)屬性Sno是碼， SC（Sno，Cno，Grade）中，（Sno，Cno）是碼例3 關(guān)系模式R（P，W，A） P：演奏者 W：作品 A：聽(tīng)眾 一個(gè)演奏者可以演奏多個(gè)作品 某一作品可被多個(gè)演奏者演奏 聽(tīng)眾可以欣賞不

15、同演奏者的不同作品 碼為(P，W，A)，即All-Key An Introduction to Database System外部碼外部碼定義定義6.5 關(guān)系模式 R 中屬性或?qū)傩越MX 并非 R的碼，但 X 是另一個(gè)關(guān)系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼v 如在SC（Sno，Cno，Grade）中，Sno不是碼，但Sno是關(guān)系模式S（Sno，Sdept，Sage）的碼，則Sno是關(guān)系模式SC的外部碼 v 主碼與外部碼一起提供了表示關(guān)系間聯(lián)系的手段An Introduction to Database System6.2 規(guī)范化規(guī)范化6.2.1 函數(shù)依賴函數(shù)依賴

16、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é)規(guī)范化小結(jié)An Introduction to Database System6.2.3 范式范式v 范式是符合某一種級(jí)別的關(guān)系模式的集合v 關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式v 范式的種類：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)An Introduction to Database System6.2.3 范式范式v各種范式之間存在

17、聯(lián)系：v某一關(guān)系模式R為第n范式，可簡(jiǎn)記為RnNF。v 一個(gè)低一級(jí)范式的關(guān)系模式，通過(guò)模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過(guò)程就叫規(guī)范化 NF5NF4BCNFNF3NF2NF1An Introduction to Database System6.2 規(guī)范化規(guī)范化6.2.1 函數(shù)依賴函數(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é)規(guī)范化小結(jié)An Introduction to Database System6.2.4 2NFv 1NF的定義如果一個(gè)關(guān)系模式

18、R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R1NFv 第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫(kù)模式不能稱為關(guān)系數(shù)據(jù)庫(kù)v 但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式An Introduction to Database System2NF（續(xù)）（續(xù)）例4 關(guān)系模式 S-L-C(Sno, Sdept, Sloc, Cno, Grade) Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方v 函數(shù)依賴包括： (Sno, Cno) F Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc

19、An Introduction to Database System 2NF（續(xù)）（續(xù)）v S-L-C的碼為(Sno, Cno)v S-L-C滿足第一范式。v 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno)SnoCnoGradeSdeptSlocS-L-CAn Introduction to Database SystemS-L-C不是一個(gè)好的關(guān)系模式（續(xù)）不是一個(gè)好的關(guān)系模式（續(xù)）(1) 插入異常(2) 刪除異常(3) 數(shù)據(jù)冗余度大(4) 修改復(fù)雜An Introduction to Database SystemS-L-C不是一個(gè)好的關(guān)系模式（續(xù)）不是一個(gè)好的關(guān)系模式（續(xù)

20、）v 原因 Sdept、 Sloc部分函數(shù)依賴于碼。v 解決方法 S-L-C分解為兩個(gè)關(guān)系模式，以消除這些部分函數(shù)依賴 SC（Sno， Cno， Grade） S-L（Sno， Sdept， Sloc）An Introduction to Database System2NF（續(xù)）（續(xù)）函數(shù)依賴圖：SnoCnoGradeSCS-LSnoSdeptSlocv關(guān)系模式SC的碼為（Sno，Cno）v關(guān)系模式S-L的碼為Snov這樣非主屬性對(duì)碼都是完全函數(shù)依賴 An Introduction to Database System 2NF（續(xù)）（續(xù)）v2NF的定義定義定義6.6 若R1NF，且每一個(gè)非主

21、屬性完全函數(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） 2NFAn Introduction to Database System 2NF（續(xù)）（續(xù)）v 采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。v 將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除關(guān)系模式

22、中的各種異常情況和數(shù)據(jù)冗余。An Introduction to Database System6.2 規(guī)范化規(guī)范化6.2.1 函數(shù)依賴函數(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é)規(guī)范化小結(jié)An Introduction to Database System 6.2.5 3NFv3NF的定義定義定義6.7 關(guān)系模式R 中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，YZ成立， Y X，則稱R 3NF。n若R3NF，則每一個(gè)非主屬性既不部分依賴于碼也不傳遞

23、依賴于碼。 An Introduction to Database System3NF（續(xù)）（續(xù)）例：2NF關(guān)系模式S-L(Sno, Sdept, Sloc)中 函數(shù)依賴： SnoSdept Sdept Sno SdeptSloc 可得： SnoSloc，即S-L中存在非主屬性對(duì)碼的傳遞函數(shù)依 賴，S-L 3NF傳遞An Introduction to Database System 3NF（續(xù)）（續(xù)）函數(shù)依賴圖：S-LSnoSdeptSlocAn Introduction to Database System3NF（續(xù)）（續(xù)）v 解決方法 采用投影分解法，把S-L分解為兩個(gè)關(guān)系模式，以消除傳

24、遞函數(shù)依賴： S-D（Sno， Sdept） D-L（Sdept，Sloc）S-D的碼為Sno， D-L的碼為Sdept。n分解后的關(guān)系模式S-D與D-L中不再存在傳遞依賴 An Introduction to Database System3NF（續(xù)）（續(xù)）S-D的碼為Sno， D-L的碼為SdeptSnoSdeptS-DSdeptSlocD-Lv S-L(Sno, Sdept, Sloc) 2NF S-L(Sno, Sdept, Sloc) 3NF S-D(Sno，Sdept) 3NFD-L(Sdept， Sloc) 3NFAn Introduction to Database Syste

25、m3NF（續(xù)）（續(xù)）v 采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。v 將一個(gè)2NF關(guān)系分解為多個(gè)3NF的關(guān)系后，仍然不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。An Introduction to Database System6.2 規(guī)范化規(guī)范化6.2.1 函數(shù)依賴函數(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é)規(guī)范化小結(jié)An Introduction to Data

26、base System 6.2.6 BC范式（范式（BCNF）v定義定義6.8 關(guān)系模式R1NF，若XY且Y X時(shí)X必含有碼，則R BCNF。v等價(jià)于：每一個(gè)決定屬性因素都包含碼An Introduction to Database SystemBCNF（續(xù)）（續(xù)）v若RBCNF 所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴 所有的主屬性對(duì)每一個(gè)不包含它的碼，也是完全函數(shù)依賴 沒(méi)有任何屬性完全函數(shù)依賴于非碼的任何一組屬性vR BCNF R 3NF充分不必要An Introduction to Database SystemBCNF（續(xù)）（續(xù)）例5 關(guān)系模式C（Cno，Cname，Pcno）n C3N

27、Fn CBCNF例6 關(guān)系模式S（Sno，Sname，Sdept，Sage）n 假定S有兩個(gè)碼Sno，Snamen S3NF。n S BCNFAn Introduction to Database SystemBCNF（續(xù)）（續(xù)）例7關(guān)系模式SJP（S，J，P）n函數(shù)依賴：（S，J）P；(J，P）Sn（S，J）與（J，P）都可以作為候選碼,屬性相交nSJP3NF，nSJPBCNFAn Introduction to Database System BCNF（續(xù)）（續(xù)）例8在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。 函數(shù)依賴： (S，J)T，(S，T)J，TJ (S，

28、J)和(S，T)都是候選碼An Introduction to Database System BCNF（續(xù)）（續(xù)） JSJTSTSTJ中的函數(shù)依賴中的函數(shù)依賴An Introduction to Database SystemBCNF（續(xù)）（續(xù)）vSTJ3NF 沒(méi)有任何非主屬性對(duì)碼傳遞依賴或部分依賴 vSTJBCNF T是決定因素，T不包含碼An Introduction to Database SystemBCNF（續(xù)）（續(xù)）v解決方法：將STJ分解為二個(gè)關(guān)系模式： ST(S，T) BCNF， TJ(T，J) BCNF 沒(méi)有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJAn In

29、troduction to Database System3NF與與BCNF的關(guān)系的關(guān)系vR BCNF R 3NFv如果R3NF，且R只有一個(gè)候選碼 R BCNF R 3NF充分不必要充分必要An Introduction to Database System6.2 規(guī)范化規(guī)范化6.2.1 函數(shù)依賴函數(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é)規(guī)范化小結(jié)An Introduction to Database System6.2.7 多值依賴多值依賴?yán)? 學(xué)校中某一門課程由多

30、個(gè)教師講授，他們使用相同的一套參考書。每個(gè)教員可以講授多門課程，每種參考書可以供多門課程使用。An Introduction to Database System課課 程程 C教教 員員 T參參 考考 書書 B 物理物理數(shù)學(xué)數(shù)學(xué) 計(jì)算數(shù)學(xué)計(jì)算數(shù)學(xué)李李 勇勇王王 軍軍 李李 勇勇張張 平平 張張 平平 周周 峰峰 普通物理學(xué)普通物理學(xué)光學(xué)原理光學(xué)原理 物理習(xí)題集物理習(xí)題集數(shù)學(xué)分析數(shù)學(xué)分析微分方程微分方程高等代數(shù)高等代數(shù)數(shù)學(xué)分析數(shù)學(xué)分析. 多值依賴（續(xù)）多值依賴（續(xù)）v 非規(guī)范化關(guān)系A(chǔ)n Introduction to Database System普通物理學(xué)普通物理學(xué)光學(xué)原理光學(xué)原理物理習(xí)題集物

31、理習(xí)題集普通物理學(xué)普通物理學(xué)光學(xué)原理光學(xué)原理物理習(xí)題集物理習(xí)題集數(shù)學(xué)分析數(shù)學(xué)分析微分方程微分方程高等代數(shù)高等代數(shù)數(shù)學(xué)分析數(shù)學(xué)分析微分方程微分方程高等代數(shù)高等代數(shù)李李 勇勇李李 勇勇李李 勇勇王王 軍軍王王 軍軍王王 軍軍李李 勇勇李李 勇勇李李 勇勇張張 平平張張 平平張張 平平 物物 理理物物 理理物物 理理物物 理理物物 理理物物 理理數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué)數(shù)數(shù) 學(xué)學(xué) 參考書B(niǎo)教員T課程C多值依賴（續(xù)）多值依賴（續(xù)）v 用二維表表示TeachingAn Introduction to Database System多值依賴（續(xù)）多值依賴（續(xù)）v Teaching

32、BCNFv Teaching具有唯一候選碼(C，T，B)， 即全碼 An Introduction to Database System多值依賴（續(xù)）多值依賴（續(xù)） Teaching模式中存在的問(wèn)題(1)數(shù)據(jù)冗余度大 (2)插入操作復(fù)雜(3) 刪除操作復(fù)雜(4) 修改操作復(fù)雜存在多值依賴An Introduction to Database System多值依賴（續(xù)）多值依賴（續(xù)）v 定義定義6.9 設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式， X、 Y和Z是U的子集，并且ZUXY。關(guān)系模式R(U)中多值依賴 XY成立，當(dāng)且僅當(dāng)對(duì)R(U)的任一關(guān)系r，給定的一對(duì)（x，z）值，有一組Y的值，這組值

33、僅僅決定于x值而與z值無(wú)關(guān)v 例 Teaching（C, T, B）An Introduction to Database System多值依賴（續(xù)）多值依賴（續(xù)）v多值依賴的另一個(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。An Introduction to Database System多值依賴（續(xù)）

34、多值依賴（續(xù)）v平凡多值依賴和非平凡的多值依賴若XY，而Z，則稱 XY為平凡的多值依賴否則稱XY為非平凡的多值依賴An Introduction to Database System多值依賴（續(xù)）多值依賴（續(xù)）例10關(guān)系模式WSC（W，S，C）n W表示倉(cāng)庫(kù)，S表示保管員，C表示商品n 假設(shè)每個(gè)倉(cāng)庫(kù)有若干個(gè)保管員，有若干種商品 n 每個(gè)保管員保管所在的倉(cāng)庫(kù)的所有商品n 每種商品被所有保管員保管 An Introduction to Database System多值依賴（續(xù)）多值依賴（續(xù)）WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2

35、S4C4W2S4C5An Introduction to Database System多值依賴（續(xù)）多值依賴（續(xù)）WS且WC用下圖表示這種對(duì)應(yīng) An Introduction to Database System多值依賴的性質(zhì)多值依賴的性質(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。An Introduction to Database System多值依賴與函數(shù)依賴的區(qū)別多值依

36、賴與函數(shù)依賴的區(qū)別(1) 多值依賴的有效性與屬性集的范圍有關(guān)(2) 若函數(shù)依賴XY在R（U）上成立，則對(duì)于任何Y Y均有XY 成立多值依賴XY若在R(U)上成立，不能斷言對(duì)于任何Y Y有XY 成立An Introduction to Database System6.2 規(guī)范化規(guī)范化6.2.1 函數(shù)依賴函數(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é)規(guī)范化小結(jié)An Introduction to Database System6.2.8 4NFv 定義定義6.10 關(guān)系模式R

37、1NF，如果對(duì)于R的每個(gè)非平凡多值依賴XY（Y X），X都含有碼，則R4NF。v 如果R 4NF， 則R BCNFn不允許有非平凡且非函數(shù)依賴的多值依賴n允許的非平凡多值依賴是函數(shù)依賴An Introduction to Database System4NF（續(xù)（續(xù)）例： Teaching(C,T,B) 4NF 存在非平凡的多值依賴CT，且C不是碼n 用投影分解法把Teaching分解為如下兩個(gè)關(guān)系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依賴 An Introduction to Database System6.2 規(guī)范化規(guī)范化6.2.1 函數(shù)依賴函

38、數(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é)規(guī)范化小結(jié)An Introduction to Database System6.2.9 規(guī)范化小結(jié)規(guī)范化小結(jié)v 關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具v 目的：盡量消除插入、刪除一場(chǎng)，修改復(fù)雜，數(shù)據(jù)冗余v 基本思想：逐步消除數(shù)據(jù)依賴中不合適的部分 實(shí)質(zhì)：概念的單一化An Introduction to Database System規(guī)范化小結(jié)（續(xù)）規(guī)范化小結(jié)（續(xù)）v 關(guān)系模式規(guī)范化的基本步驟 1NF 消除非主屬性對(duì)碼的部分

39、函數(shù)依賴消除決定屬性 2NF集非碼的非平 消除非主屬性對(duì)碼的傳遞函數(shù)依賴凡函數(shù)依賴 3NF 消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴 BCNF 消除非平凡且非函數(shù)依賴的多值依賴 4NFAn Introduction to Database System規(guī)范化小結(jié)（續(xù)）規(guī)范化小結(jié)（續(xù)）v 不能說(shuō)規(guī)范化程度越高的關(guān)系模式就越好v 在設(shè)計(jì)數(shù)據(jù)庫(kù)模式結(jié)構(gòu)時(shí)，必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式v 上面的規(guī)范化步驟可以在其中任何一步終止An Introduction to Database System第六章第六章 關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論6.1 問(wèn)題的提

40、出問(wèn)題的提出6.2 規(guī)范化規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解模式的分解6.5 小結(jié)小結(jié)An Introduction to Database System6.3 數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)v邏輯蘊(yùn)含定義定義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 YAn Introduction to Database System1. Armstrong公理系統(tǒng)公理系統(tǒng) 關(guān)系模式R 來(lái)說(shuō)有以下的推理規(guī)則： A1.自反律（Reflexivi

41、ty）：若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)含。An Introduction to Database System定理定理 6.1 Armstrong推理規(guī)則是正確的推理規(guī)則是正確的（l）自反律: 若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成立，自反律得證An Introduction to Database Syste

42、m定理定理 6.l Armstrong推理規(guī)則是正確的（續(xù)）推理規(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)含，增廣律得證。An Introduction to Database System定理定理 6.l Armstrong推理規(guī)則是正確的（續(xù)）推理規(guī)則是正確的（續(xù)）(3) 傳遞律：若XY及YZ為F所蘊(yùn)含，則 XZ為 F所蘊(yùn)含。證：設(shè)XY及YZ為F所蘊(yùn)含。對(duì)R

43、的任一關(guān)系 r中的任意兩個(gè)元組 t，s：若tX=sX，由于XY，有 tY=sY；再由YZ，有tZ=sZ，所以XZ為F所蘊(yùn)含，傳遞律得證。An Introduction to Database System2. 導(dǎo)出規(guī)則導(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）An Introduction to Database System導(dǎo)出規(guī)則導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理6.1 引理6.l XA

44、1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）An Introduction to Database SystemArmstrong公理系統(tǒng)公理系統(tǒng)vArmstrong公理系統(tǒng)是有效的、完備的n有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)的每一個(gè)函數(shù)依賴一定在F+中；n完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái)An Introduction to Database System3. 函數(shù)依賴閉包函數(shù)依賴閉包定義定義6.l2 在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包，記為F+。定義定義6.13 設(shè)F為屬性集U上的一組函

45、數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包An Introduction to Database System關(guān)于閉包的引理關(guān)于閉包的引理v 引理引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴，X，Y U，XY能 由F 根據(jù)Armstrong公理導(dǎo)出的充分必要條件是Y XF+v 用途 將判定XY是否能由F根據(jù)Armstrong公理導(dǎo)出的問(wèn)題，轉(zhuǎn)化為求出XF+ 、判定Y是否為XF+的子集的問(wèn)題An Introduction to Database System求閉包的算法求閉包的算法算法算法6.1 求屬性集X（X U）關(guān)于

46、U上的函數(shù)依賴集F 的閉包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）步。An Introduction to Database System算法算法6.1對(duì)于算法6.1， 令ai =|X（i）|，ai 形成一個(gè)步長(zhǎng)大于1的嚴(yán)格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| - |X| 次循環(huán)就 會(huì)終止。A

47、n Introduction to Database Systemv 例 設(shè)關(guān)系模式R（U,F）,其中,v U=A,B,C,D,E,I,F=AD,ABC,BIC,EDI,CE,求（AC）F+ 。 v 解：解： (1) 令令X=AC,則則X(0)=AC。 (2) 在在F中找出左邊是中找出左邊是AC子集的函數(shù)依賴：子集的函數(shù)依賴： AD,CE。 (3) X(1)=X(0)DE=ACDE。An Introduction to Database Systemv (4) 很明顯X(1)X(0),所以X(i)=X(1),并轉(zhuǎn)向算法中的步驟(2)。 v(5) 在F中找出左邊是ACDE子集的函數(shù)依賴： EDI

48、。v(6) X(2)=X(1)I=ACDEI。v(7) 雖然X(2)X(1),但是F中未用過(guò)的函數(shù)依賴的左邊屬性已沒(méi)有X(2)的子集,所以,可停止計(jì)算,輸出（AC）F+ = X(2)=ACDEI。An Introduction to Database System4. Armstrong公理系統(tǒng)的有效性與完備性公理系統(tǒng)的有效性與完備性v定理6.2 Armstrong公理系統(tǒng)是有效的、完備的 v證明：1. 有效性 可由定理6.1得證2. 完備性只需證明逆否命題: 若函數(shù)依賴XY不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含An Introduction to Database Sy

49、stemArmstrong公理系統(tǒng)完備性證明公理系統(tǒng)完備性證明(1) 引理: 若VW成立，且V XF+，則W XF+ (2) 構(gòu)造一張二維表r，它由下列兩個(gè)元組構(gòu)成，可以證明r必是R（U，F(xiàn)）的一個(gè)關(guān)系，即F+中的全部函數(shù)依賴在 r上成立。 XF+ U-XF+ 11.1 00.0 11.1 11.1 (3) 若XY 不能由F從Armstrong公理導(dǎo)出，則Y 不是XF+ 的子集。An Introduction to Database System5. 函數(shù)依賴集等價(jià)函數(shù)依賴集等價(jià)定義定義6.14 如果G+=F+，就說(shuō)函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。引理引理6.

50、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+。An Introduction to Database System6. 最小依賴集最小依賴集定義定義6.15 如果函數(shù)依賴集F滿足下列條件，則稱F為一個(gè)極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。 (1) F中任一函數(shù)依賴的右部?jī)H含有一個(gè)屬性。 (2) F中不存在這樣的函數(shù)依賴XA，使得F與F-XA等價(jià)。 (3) F中不存在這

51、樣的函數(shù)依賴XA， X有真子集Z使得F-XAZA與F等價(jià)。 An Introduction to Database System最小依賴集最小依賴集例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)SdeptF是最小覆蓋，而F不是。因?yàn)椋篎 - SnoMname與F 等價(jià) F - (Sno，Sdept)Sdept也與F 等價(jià) An Introduction to D

52、atabase System7. 極小化過(guò)程極小化過(guò)程定理定理6.3 每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小函數(shù)依賴 集Fm。此Fm稱為F的最小依賴集。證明: 構(gòu)造性證明，找出F的一個(gè)最小依賴集。 An Introduction to Database System極小化過(guò)程（續(xù)）極小化過(guò)程（續(xù)）(1) 應(yīng)用分解規(guī)則,使F的每個(gè)函數(shù)依賴的右部屬性都為單屬性。 (2) 依次去除F的每個(gè)函數(shù)依賴左部多余的屬性。 設(shè)XYA是F的任一函數(shù)依賴,在F中求出X的閉包X+。 如果X+包含了Y,則Y為多余屬性,該函數(shù)依賴變?yōu)閄A。 (3) 依次去除多余的函數(shù)依賴。 設(shè)XA是F的任一函數(shù)依賴,在F-XA中求出X的閉

53、包X+。 如果X+包含了A,則XA為多余的函數(shù)依賴,應(yīng)該去除； 否則,不能去除。An Introduction to Database System極小化過(guò)程（續(xù)）極小化過(guò)程（續(xù)）例3 F = AB，BA，BC，AC，CAFm1、Fm2都是F的最小依賴集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA v F的最小依賴集Fm不唯一v 極小化過(guò)程( 定理6.3的證明 )也是檢驗(yàn)F是否為極小依賴集的一個(gè)算法An Introduction to Database System 例 6.5 設(shè)有函數(shù)依賴集F=AC,CA,BAC,DAC,BDA,計(jì)算它等價(jià)的最小依賴集。 解： (1) 化

54、單依賴右邊的屬性,結(jié)果為 F1=AC,CA,BA,BC,DA,DC,BDA (2) 去除F1的依賴中左邊多余的屬性。 對(duì)于BDA,由于有BA,所以是多余的。 結(jié)果為 F2= AC,CA,BA,BC,DA,DCAn Introduction to Database System(3) 去除F2中多余的依賴。 因?yàn)椋?AC,CA,所以AC。 故： BA、 BC以及DA、 DC中之一為多余的。 取F3= AC,CA,BA,DA。 在F3中： 對(duì)于AC,F3-AC中A+=A； 對(duì)于CA,F3-CA中C+=C； 對(duì)于BA,F3-BA中B+=B； 對(duì)于DA,F3-DA中D+=D； 所以,F3中已沒(méi)有多余的

55、函數(shù)依賴。 即F的等價(jià)最小依賴集為： AC,CA,BA,DA。 An Introduction to Database System注意： 函數(shù)依賴集的最小集并不是唯一的,本例中還可以有以下幾個(gè)答案： AC,CA,BA,DA 或 AC,CA,BC,DA 或 AC,CA,BC,DC An Introduction to Database System第六章第六章 關(guān)系數(shù)據(jù)理論關(guān)系數(shù)據(jù)理論6.1 問(wèn)題的提出問(wèn)題的提出6.2 規(guī)范化規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)*6.4 模式的分解模式的分解6.5 小結(jié)小結(jié)An Introduction to Database System6.4

56、 模式的分解模式的分解v 把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法不是唯一的v 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義An Introduction to Database System關(guān)系模式分解的標(biāo)準(zhǔn)關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解等價(jià)的定義： 分解具有無(wú)損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無(wú)損連接性An Introduction to Database System模式的分解（續(xù)）模式的分解（續(xù)）定義定義6.16 關(guān)系模式R的一個(gè)分解：= R1，R2，Rn U= Ui，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影定義定義6

57、.17 函數(shù)依賴集合XY | XY F+XY Ui 的一個(gè)覆蓋 Fi 叫作 F 在屬性 Ui 上的投影i=1nAn Introduction to Database System模式的分解（續(xù)）模式的分解（續(xù)）例：S-L（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc S-L2NF 分解方法可以有多種：1. S-L分解為三個(gè)關(guān)系模式：SN(Sno) SD(Sdept) SO(Sloc)2. SL分解為下面二個(gè)關(guān)系模式：NL(Sno, Sloc)DL(Sdept, Sloc)3. 將SL分解為下面二個(gè)關(guān)系模式：ND(Sno, Sdept) NL(Sno, Sloc)An Introduction to Database System具有無(wú)損連接性的模式分解具有無(wú)損連接性的模式分解v 關(guān)系模式R的