數(shù)據(jù)庫原理與應(yīng)用第四章PPT課件PPT課件

1、4.1 問題的提出關(guān)系數(shù)據(jù)庫邏輯設(shè)計(jì) 針對(duì)具體問題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式 數(shù)據(jù)庫邏輯設(shè)計(jì)的工具關(guān)系數(shù)據(jù)庫的規(guī)范化理論第1頁/共137頁問題的提出一、概念回顧二、關(guān)系模式的形式化定義三、什么是數(shù)據(jù)依賴四、關(guān)系模式的簡(jiǎn)化定義五、數(shù)據(jù)依賴對(duì)關(guān)系模式影響第2頁/共137頁一、概念回顧 關(guān)系：描述實(shí)體、屬性、實(shí)體間的聯(lián)系。 從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個(gè)子集。 關(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)系模式的全體。第3頁/共137頁二、關(guān)系模式的形式化定義關(guān)

2、系模式由五部分組成，即它是一個(gè)五元組： R(U, D, DOM, F)R： 關(guān)系名U： 組成該關(guān)系的屬性名集合D： 屬性組U中屬性所來自的域DOM：屬性向域的映象集合F： 屬性間數(shù)據(jù)的依賴關(guān)系集合第4頁/共137頁三、什么是數(shù)據(jù)依賴1. 完整性約束的表現(xiàn)形式 限定屬性取值范圍：例如學(xué)生成績(jī)必須在0-100之間 定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設(shè)計(jì)的關(guān)鍵第5頁/共137頁什么是數(shù)據(jù)依賴（續(xù)）2. 數(shù)據(jù)依賴 是通過一個(gè)關(guān)系中屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間的相互關(guān)系 是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象 是數(shù)據(jù)內(nèi)在的性質(zhì) 是語義的體現(xiàn)第6頁/共137頁什

3、么是數(shù)據(jù)依賴（續(xù)）3. 數(shù)據(jù)依賴的類型 函數(shù)依賴（Functional Dependency，簡(jiǎn)記為FD） 多值依賴（Multivalued Dependency，簡(jiǎn)記為MVD） 其他第7頁/共137頁四、關(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)系第8頁/共137頁五、數(shù)據(jù)依賴對(duì)關(guān)系模式的影響例：描述學(xué)校的數(shù)據(jù)庫：學(xué)生的學(xué)號(hào)（Sno）、所在系（Sdept）系主任姓名（Mname）、課程名（Cname）成績(jī)（Grade）單一的關(guān)系模式 ： Student U Sno, S

4、dept, Mname, Cname, Grade 第9頁/共137頁數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）學(xué)校數(shù)據(jù)庫的語義： 一個(gè)系有若干學(xué)生， 一個(gè)學(xué)生只屬于一個(gè)系； 一個(gè)系只有一名主任； 一個(gè)學(xué)生可以選修多門課程， 每門課程有若干學(xué)生選修； 每個(gè)學(xué)生所學(xué)的每門課程都有一個(gè)成績(jī)。 第10頁/共137頁數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）屬性組U上的一組函數(shù)依賴F： F Sno Sdept, Sdept Mname, (Sno, Cname) Grade SnoCnameSdeptMnameGrade第11頁/共137頁關(guān)系模式Student中存在的問題 數(shù)據(jù)冗余太大 浪費(fèi)大量的存儲(chǔ)空間 例：每一個(gè)系主任

5、的姓名重復(fù)出現(xiàn) 更新異常（Update Anomalies） 數(shù)據(jù)冗余 ，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。例：某系更換系主任后，系統(tǒng)必須修改與該系學(xué)生有關(guān)的每一個(gè)元組第12頁/共137頁關(guān)系模式Student中存在的問題 插入異常（Insertion Anomalies） 該插的數(shù)據(jù)插不進(jìn)去 例，如果一個(gè)系剛成立，尚無學(xué)生，我們就無法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫。 刪除異常（Deletion Anomalies） 不該刪除的數(shù)據(jù)不得不刪例，如果某個(gè)系的學(xué)生全部畢業(yè)了， 我們?cè)趧h除該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。第13頁/共137頁數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）結(jié)論

6、： Student關(guān)系模式不是一個(gè)好的模式。 “好”的模式：不會(huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少。原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關(guān)系模式來消除其中不合適 的數(shù)據(jù)依賴。第14頁/共137頁4.2 規(guī)范化 規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。第15頁/共137頁函數(shù)依賴一、函數(shù)依賴二、平凡函數(shù)依賴與非平凡函數(shù)依賴三、完全函數(shù)依賴與部分函數(shù)依賴四、傳遞函數(shù)依賴第16頁/共137頁一、函數(shù)依賴定義5.1 設(shè)R(U)是一個(gè)屬性集U上的關(guān)系模式，X和Y是U的子集。 若對(duì)

7、于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等， 而在Y上的屬性值不等， 則稱 “X函數(shù)確定Y” 或 “Y函數(shù)依賴于X”，記作XY。 X稱為這個(gè)函數(shù)依賴的決定屬性集(Determinant)。 Y=f(x)第17頁/共137頁說明： 1. 函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿足的約束條件。2. 函數(shù)依賴是語義范疇的概念。只能根據(jù)數(shù)據(jù)的語義來確定函數(shù)依賴。 例如“姓名年齡”這個(gè)函數(shù)依賴只有在不允許有同名人的條件下成立3. 數(shù)據(jù)庫設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定。例如規(guī)定不允許同名人出現(xiàn)，函數(shù)依賴“姓名年齡”成立。所插

8、入的元組必須滿足規(guī)定的函數(shù)依賴，若發(fā)現(xiàn)有同名人存在， 則拒絕裝入該元組。第18頁/共137頁函數(shù)依賴（續(xù)）例: Student(Sno, Sname, Ssex, Sage, Sdept) 假設(shè)不允許重名，則有:Sno Ssex， Sno Sage , Sno Sdept， Sno Sname, Sname Ssex， Sname SageSname Sdept但Ssex Sage若XY，并且YX, 則記為XY。 若Y不函數(shù)依賴于X, 則記為XY。第19頁/共137頁二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果XY，但Y X，則稱XY是非平凡的函數(shù)依賴若XY，

9、但Y X, 則稱XY是平凡的函數(shù)依賴?yán)涸陉P(guān)系SC(Sno, Cno, Grade)中， 非平凡函數(shù)依賴： (Sno, Cno) Grade 平凡函數(shù)依賴： (Sno, Cno) Sno (Sno, Cno) Cno第20頁/共137頁平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)） 對(duì)于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反映新的語義，因此若不特別聲明， 我們總是討論非平凡函數(shù)依賴。第21頁/共137頁三、完全函數(shù)依賴與部分函數(shù)依賴定義5.2 在關(guān)系模式R(U)中，如果XY，并且對(duì)于X的任何一個(gè)真子集X，都有 X Y, 則稱Y完全函數(shù)依賴于X，記作X Y。 若XY，但Y不完全函數(shù)依賴于X，則稱Y

10、部分函數(shù)依賴于X，記作X P Y。 第22頁/共137頁完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）例: 在關(guān)系SC(Sno, Cno, Grade)中， 由于：Sno Grade，Cno Grade， 因此：(Sno, Cno) Grade 第23頁/共137頁四、傳遞函數(shù)依賴定義5.3 在關(guān)系模式R(U)中，如果XY，YZ，且Y X，YX，則稱Z傳遞函數(shù)依賴于X。注: 如果YX， 即XY，則Z直接依賴于X。例: 在關(guān)系Std(Sno, Sdept, Mname)中，有：Sno Sdept，Sdept Mname Mname傳遞函數(shù)依賴于Sno第24頁/共137頁碼定義5.4 設(shè)K為關(guān)系模式R中的屬性或

11、屬性組合。若K U，則K稱為R的一個(gè)侯選碼（Candidate Key）。若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼（Primary key）。 主屬性與非主屬性 ALL KEY第25頁/共137頁外部碼定義5.5 關(guān)系模式 R 中屬性或?qū)傩越MX 并非 R的碼，但 X 是另一個(gè)關(guān)系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼 主碼又和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。第26頁/共137頁范式 范式是符合某一種級(jí)別的關(guān)系模式的集合。 關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式。 范式的種類：第一范式(1NF)第二范式(2NF)第三范式(

12、3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF)第27頁/共137頁范式各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡(jiǎn)記為RnNF。NF5NF4BCNFNF3NF2NF1第28頁/共137頁 1NF的定義如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R1NF。 第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫。 但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式。第29頁/共137頁2NF例: 關(guān)系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方。 函數(shù)依

13、賴包括： (Sno, Cno) f Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc第30頁/共137頁 2NF SLC的碼為(Sno, Cno) SLC滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno)SnoCnoGradeSdeptSlocSLC第31頁/共137頁SLC不是一個(gè)好的關(guān)系模式(1) 插入異常假設(shè)Sno95102，SdeptIS，SlocN的學(xué)生還未選課，因課程號(hào)是主屬性，因此該學(xué)生的信息無法插入SLC。(2) 刪除異常 假定某個(gè)學(xué)生本來只選修了3號(hào)課

14、程這一門課?，F(xiàn)在因身體不適，他連3號(hào)課程也不選修了。因課程號(hào)是主屬性，此操作將導(dǎo)致該學(xué)生信息的整個(gè)元組都要?jiǎng)h除。 第32頁/共137頁SLC不是一個(gè)好的關(guān)系模式(3) 數(shù)據(jù)冗余度大 如果一個(gè)學(xué)生選修了10門課程，那么他的Sdept和Sloc值就要重復(fù)存儲(chǔ)了10次。(4) 修改復(fù)雜 例如學(xué)生轉(zhuǎn)系，在修改此學(xué)生元組的Sdept值的同時(shí)，還可能需要修改住處（Sloc）。如果這個(gè)學(xué)生選修了K門課，則必須無遺漏地修改K個(gè)元組中全部Sdept、Sloc信息。 第33頁/共137頁 2NF 原因 Sdept、 Sloc部分函數(shù)依賴于碼。 解決方法 SLC分解為兩個(gè)關(guān)系模式，以消除這些部分函數(shù)依賴 SC（Sn

15、o， Cno， Grade） SL（Sno， Sdept， Sloc）第34頁/共137頁 2NF SLC的碼為(Sno, Cno) SLC滿足第一范式。 非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno, Cno)SnoCnoGradeSdeptSlocSLC第35頁/共137頁2NF函數(shù)依賴圖：SnoCnoGradeSCSLSnoSdeptSloc第36頁/共137頁 2NF2NF的定義定義5.6 若關(guān)系模式R1NF，并且每一個(gè)非主屬性都完全函數(shù)依賴于R的碼，則R2NF。例：SLC(Sno, Sdept, Sloc, Cno, Grade) 1NF SLC(Sno, Sdept, Sl

16、oc, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF第37頁/共137頁 第二范式（續(xù)） 采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。第38頁/共137頁例：2NF關(guān)系模式SL(Sno, Sdept, Sloc)中函數(shù)依賴： SnoSdept SdeptSloc SnoSlocSloc傳遞函數(shù)依賴于Sno，即SL中存在非

17、主屬性對(duì)碼的傳遞函數(shù)依賴。第39頁/共137頁 3NF函數(shù)依賴圖：SLSnoSdeptSloc第40頁/共137頁 3NF 解決方法 采用投影分解法，把SL分解為兩個(gè)關(guān)系模式，以消除傳遞函數(shù)依賴： SD（Sno， Sdept） DL（Sdept， Sloc）SD的碼為Sno， DL的碼為Sdept。第41頁/共137頁 3NFSD的碼為Sno， DL的碼為Sdept。SnoSdeptSDSdeptSlocDL第42頁/共137頁 3NF 3NF的定義定義5.8 關(guān)系模式R 中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，Y X，YZ，成立，則稱R 3NF。例， SL(Sno,

18、 Sdept, Sloc) 2NF SL(Sno, Sdept, Sloc) 3NF SD（Sno， Sdept） 3NF DL（Sdept， Sloc） 3NF第43頁/共137頁 3NF 若R3NF，則R的每一個(gè)非主屬性既不部分函數(shù)依賴于候選碼也不傳遞函數(shù)依賴于候選碼。 如果R3NF，則R也是2NF。 采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。 將一個(gè)2NF關(guān)系分解為多個(gè)3NF的關(guān)系后，并不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。第44頁/共137頁范式（BCNF） 定義5.9 設(shè)

19、關(guān)系模式R1NF，如果對(duì)于R的每個(gè)函數(shù)依賴XY，若Y不屬于X，則X必含有候選碼，那么RBCNF。若RBCNF 每一個(gè)決定屬性集（因素）都包含（候選）碼 R中的所有屬性（主，非主屬性）都完全函數(shù)依賴于碼 R3NF（證明） 若R3NF 則 R不一定BCNF第45頁/共137頁 BCNF例：在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示課程。 每一教師只教一門課。每門課由若干教師教，某一學(xué)生選定某門課，就確定了一個(gè)固定的教師。某個(gè)學(xué)生選修某個(gè)教師的課就確定了所選課的名稱 ： (S，J)T，(S，T)J，TJ第46頁/共137頁 SJTSTJSTJ第47頁/共137頁BCNFSTJ3

20、NF (S，J)和(S，T)都可以作為候選碼 S、T、J都是主屬性STJBCNF TJ，T是決定屬性集，T不是候選碼第48頁/共137頁BCNF解決方法：將STJ分解為二個(gè)關(guān)系模式： SJ(S，J) BCNF， TJ(T，J) BCNF 沒有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴SJSTTJTJ第49頁/共137頁3NF與BCNF的關(guān)系 如果關(guān)系模式RBCNF， 必定有R3NF 如果R3NF，且R只有一個(gè)候選碼， 則R必屬于BCNF。第50頁/共137頁BCNF的關(guān)系模式所具有的性質(zhì) 所有非主屬性都完全函數(shù)依賴于每個(gè)候選碼 所有主屬性都完全函數(shù)依賴于每個(gè)不包含它的候選碼 沒有任何屬性完全函數(shù)

21、依賴于非碼的任何一組屬性第51頁/共137頁多值依賴與第四范式（4NF）例: 學(xué)校中某一門課程由多個(gè)教師講授，他們使用相同的一套參考書。關(guān)系模式Teaching(C, T, B) 課程C、教師T 和 參考書B第52頁/共137頁課 程 C教 員 T參 考 書 B 物理 數(shù)學(xué) 計(jì)算數(shù)學(xué)李 勇王 軍 李 勇張 平 張 平周 峰 普通物理學(xué)光學(xué)原理 物理習(xí)題集 數(shù)學(xué)分析微分方程高等代數(shù) 數(shù)學(xué)分析 表4.1第53頁/共137頁普通物理學(xué)光學(xué)原理物理習(xí)題集普通物理學(xué)光學(xué)原理物理習(xí)題集數(shù)學(xué)分析微分方程高等代數(shù)數(shù)學(xué)分析微分方程高等代數(shù)李 勇李 勇李 勇王 軍王 軍王 軍李 勇李 勇李 勇張 平張 平張 平

22、物 理物 理物 理物 理物 理物 理數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué) 參考書B教員T課程C用二維表表示Teaching 第54頁/共137頁多值依賴與第四范式（續(xù)） TeachingBCNF: Teach具有唯一候選碼(C，T，B)， 即全碼 Teaching模式中存在的問題 (1)數(shù)據(jù)冗余度大：有多少名任課教師，參考書就要存儲(chǔ)多少次 第55頁/共137頁多值依賴與第四范式（續(xù)） (2)插入操作復(fù)雜：當(dāng)某一課程增加一名任課教師時(shí)，該課程有多少本參照書，就必須插入多少個(gè)元組例如物理課增加一名教師劉關(guān)，需要插入兩個(gè)元組： （物理，劉關(guān)，普通物理學(xué)） （物理，劉關(guān)，光學(xué)原理）第56頁/共137頁

23、多值依賴與第四范式（續(xù)）(3) 刪除操作復(fù)雜：某一門課要去掉一本參考書，該課程有多少名教師，就必須刪除多少個(gè)元組(4) 修改操作復(fù)雜：某一門課要修改一本參考書，該課程有多少名教師，就必須修改多少個(gè)元組 產(chǎn)生原因存在多值依賴第57頁/共137頁一、多值依賴 定義5.10 設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式， X、 Y和Z是U的子集，并且ZUXY，多值依賴 XY成立當(dāng)且僅當(dāng)對(duì)R的任一關(guān)系r，r在（X，Z）上的每個(gè)值對(duì)應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無關(guān) 例 Teaching（C, T, B） 對(duì)于C的每一個(gè)值，T有一組值與之對(duì)應(yīng)，而不論B取何值第58頁/共137頁一、多值依賴 在R

24、（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。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2第59頁/共137頁多值依賴（續(xù)） 平凡多值依賴和非平凡的多值依賴若XY，而Z，則稱 XY為平凡的多值依賴否則稱XY為非平凡的多值依賴第60頁/共137頁多值依賴的性質(zhì)（1）多值依賴具有對(duì)稱性 若XY，則XZ，

25、其中ZUXY 多值依賴的對(duì)稱性可以用完全二分圖直觀地表示出來。（2）多值依賴具有傳遞性 若XY，YZ， 則XZ -Y第61頁/共137頁多值依賴的對(duì)稱性 XiZi 1 Zi 2 ZimYi 1 Yi 2 Yin第62頁/共137頁多值依賴的對(duì)稱性 物 理普通物理學(xué) 光學(xué)原理 物理習(xí)題集李勇 王軍第63頁/共137頁多值依賴（續(xù)）（3）函數(shù)依賴是多值依賴的特殊情況。 若XY，則XY。（4）若XY，XZ，則XY Z。（5）若XY，XZ，則XYZ。（6）若XY，XZ，則XY-Z，XZ -Y。第64頁/共137頁多值依賴與函數(shù)依賴的區(qū)別(1) 有效性 多值依賴的有效性與屬性集的范圍有關(guān)若XY在U上成立

26、，則在W（X Y W U）上一定成立；反之則不然，即XY在W（W U）上成立，在U上并不一定成立 多值依賴的定義中不僅涉及屬性組 X和 Y，而且涉及U中其余屬性Z。 一般地，在R（U）上若有XY在W（W U）上成立，則稱XY為R（U）的嵌入型多值依賴第65頁/共137頁多值依賴與函數(shù)依賴的區(qū)別 只要在R（U）的任何一個(gè)關(guān)系r中，元組在X和Y上的值滿足定義5.l（函數(shù)依賴）， 則函數(shù)依賴XY在任何屬性集W（X Y W U）上成立。第66頁/共137頁多值依賴（續(xù)）(2) 若函數(shù)依賴XY在R（U）上成立，則對(duì)于任何Y Y均有XY 成立 多值依賴XY若在R(U)上成立，不能斷言對(duì)于任何Y Y有XY

27、成立第67頁/共137頁二、第四范式（4NF） 定義4.10 關(guān)系模式R1NF，如果對(duì)于R的每個(gè)非平凡多值依賴XY（Y X），X都含有候選碼，則R4NF。 （XY） 如果R 4NF， 則R BCNF 不允許有非平凡且非函數(shù)依賴的多值依賴 允許的是函數(shù)依賴（是非平凡多值依賴）第68頁/共137頁第四范式（續(xù)）例： Teach(C,T,B) 4NF 存在非平凡的多值依賴CT，且C不是候選碼 用投影分解法把Teach分解為如下兩個(gè)關(guān)系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依賴 第69頁/共137頁4.2 規(guī)范化第一范式（1NF）第二范式（2NF）第三范式（

28、3NF）范式（BCNF）多值依賴與第四范式（4NF）規(guī)范化第70頁/共137頁規(guī)范化 關(guān)系數(shù)據(jù)庫的規(guī)范化理論是數(shù)據(jù)庫邏輯設(shè)計(jì)的工具。 一個(gè)關(guān)系只要其分量都是不可分的數(shù)據(jù)項(xiàng)，它就是規(guī)范化的關(guān)系，但這只是最基本的規(guī)范化。 規(guī)范化程度可以有多個(gè)不同的級(jí)別第71頁/共137頁規(guī)范化（續(xù)） 規(guī)范化程度過低的關(guān)系不一定能夠很好地描述現(xiàn)實(shí)世界，可能會(huì)存在插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題 一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合，這種過程就叫關(guān)系模式的規(guī)范化第72頁/共137頁規(guī)范化（續(xù)） 關(guān)系模式規(guī)范化的基本步驟 1NF 消除非主屬性對(duì)碼的部分函數(shù)依賴消除決

29、定屬性 2NF集非碼的非平 消除非主屬性對(duì)碼的傳遞函數(shù)依賴凡函數(shù)依賴 3NF 消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴 BCNF 消除非平凡且非函數(shù)依賴的多值依賴 4NF第73頁/共137頁規(guī)范化的基本思想 消除不合適的數(shù)據(jù)依賴 的各關(guān)系模式達(dá)到某種程度的“分離” 采用“一事一地”的模式設(shè)計(jì)原則 讓一個(gè)關(guān)系描述一個(gè)概念、一個(gè)實(shí)體或者實(shí)體間的一種聯(lián)系。若多于一個(gè)概念就把它“分離”出去 所謂規(guī)范化實(shí)質(zhì)上是概念的單一化第74頁/共137頁規(guī)范化（續(xù)） 不能說規(guī)范化程度越高的關(guān)系模式就越好 在設(shè)計(jì)數(shù)據(jù)庫模式結(jié)構(gòu)時(shí)，必須對(duì)現(xiàn)實(shí)世界的實(shí)際情況和用戶應(yīng)用需求作進(jìn)一步分析，確定一個(gè)合適的、能夠反映現(xiàn)實(shí)世界的模式 上

30、面的規(guī)范化步驟可以在其中任何一步終止第75頁/共137頁第四章 關(guān)系數(shù)據(jù)理論4.1 數(shù)據(jù)依賴4.2 規(guī)范化4.3 數(shù)據(jù)依賴的公理系統(tǒng)4.4 模式的分解第76頁/共137頁4.3 數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含定義5.11 對(duì)于滿足一組函數(shù)依賴 F 的關(guān)系模式R ，其任何一個(gè)關(guān)系r，若函數(shù)依賴XY都成立, 則稱 F邏輯蘊(yùn)含X Y第77頁/共137頁Armstrong公理系統(tǒng) 一套推理規(guī)則，是模式分解算法的理論基礎(chǔ) 用途 求給定關(guān)系模式的碼 從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴第78頁/共137頁1. Armstrong公理系統(tǒng) 關(guān)系模式R 來說有以下的推理規(guī)則： Al.自反律（Reflexivity）：

31、 若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)含。注意：由自反律所得到的函數(shù)依賴均是平凡的函數(shù)依賴，自反律的使用并不依賴于F第79頁/共137頁（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成立.自反律得證定理4.1 Armstrong推理規(guī)則是正確的第80頁/共137頁(2)增廣律: 若XY為F所蘊(yùn)含，且Z U，則XZY

32、Z 為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)含.增廣律得證。第81頁/共137頁(3) 傳遞律：若XY及YZ為F所蘊(yùn)含，則 XZ為 F所蘊(yùn)含。證：設(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)含.傳遞律得證。第82頁/共137頁2. 導(dǎo)出規(guī)則1.根據(jù)A1，A2，A3這三條推理規(guī)則可以得到下面三條推理規(guī)則： 合并規(guī)則：由XY，XZ，有

33、XYZ。 （A2， A3） 偽傳遞規(guī)則：由XY，WYZ，有XWZ。 （A2， A3） 分解規(guī)則：由XY及 ZY，有XZ。 （A1， A3）第83頁/共137頁導(dǎo)出規(guī)則2.根據(jù)合并規(guī)則和分解規(guī)則，可得引理5.1 引理5.l XA1 A2Ak成立的充分必要條件是XAi成立（i=l，2，k）。第84頁/共137頁3. 函數(shù)依賴閉包定義4.l2 在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體叫作 F的閉包，記為F+。定義4.13 設(shè)F為屬性集U上的一組函數(shù)依賴，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱為屬性集X關(guān)于函數(shù)依賴集F 的閉包第85頁/共137頁關(guān)于閉包的引

34、理 引理4.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+的子集的問題第86頁/共137頁求閉包的算法算法4.l 求屬性集X（X U）關(guān)于U上的函數(shù)依 賴集F 的閉包XF+ 輸入：X，F(xiàn)輸出：XF+步驟：（1）令X（0）=X，i=0（2）求B，這里B = A |( V)( W)(VWF V X（i）A W)；（3）X（i+1）=BX（i） 第87頁/共137頁算法4.l（4）判斷X（i+1）= X （i）嗎?（5）若相

35、等或X（i）=U , 則X（i）就是XF+ , 算法終止。（6）若否，則 i=i+l，返回第（2）步。對(duì)于算法5.l， 令ai =|X（i）|，ai 形成一個(gè)步長(zhǎng)大于1的嚴(yán)格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| - |X| 次循環(huán)就會(huì)終止。第88頁/共137頁 Define XF+ = closure of X = set of attributes functionally determined byX Basis: XF+ :=X Induction: If Y XF+, and Y A is a given FD, then add A to XF+ End wh

36、en XF+ cannot be changed.AlgorithmyX+New X+A第89頁/共137頁 U=A, B, C, D; F=A B, BC D; A+ = AB. C+ = C. (AC)+ = ABCD.ExampleACB第90頁/共137頁 ExampleACDBU=A, B, C, D; A B, BC D.(AC)+ = ABCD.第91頁/共137頁函數(shù)依賴閉包例1 已知關(guān)系模式R，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（AB）F+ 。解 設(shè)X（0）=AB；(1)計(jì)算X（1）: 逐一的掃描F集合中各個(gè)函數(shù)依賴， 找左部為A，B或AB

37、的函數(shù)依賴。得到兩個(gè)： ABC，BD。 于是X（1）=ABCD=ABCD。第92頁/共137頁函數(shù)依賴閉包(2)因?yàn)閄（0） X（1） ，所以再找出左部為ABCD子集的那些函數(shù)依賴，又得到ABC，BD， CE，ACB， 于是X（2）=X（1）BCDE=ABCDE。(3)因?yàn)閄（2）=U，算法終止所以（AB）F+ =ABCDE。第93頁/共137頁4. Armstrong公理系統(tǒng)的有效性與完備性 有效性：由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來的每一個(gè)函數(shù)依賴一定在F+中 /* Armstrong正確 完備性：F+中的每一個(gè)函數(shù)依賴，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來 /* A

38、rmstrong公理夠用，完全完備性：所有不能用Armstrong公理推導(dǎo)出來f, 都不為真 若 f 不能用Armstrong公理推導(dǎo)出來， f F+ 第94頁/共137頁有效性與完備性的證明證明：1. 有效性 可由定理5.l得證2. 完備性只需證明逆否命題: 若函數(shù)依賴XY不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含分三步證明：第95頁/共137頁有效性與完備性的證明(1)引理: 若VW成立，且V XF+，則W XF+ 證 因?yàn)?V XF+ ，所以有XV成立； 因?yàn)閄 V，VW，于是XW成立 所以W XF+ (2)/* 若 f 不能用Armstrong公理推導(dǎo)出來， f F+

39、 /* 若存在r， F+中的全部函數(shù)依賴在 r上成立。 /* 而不能用Armstrong公理推導(dǎo)出來的f , 在r上不成立。 構(gòu)造一張二維表r，它由下列兩個(gè)元組構(gòu)成，可以證明r必是R（U，F(xiàn)）的一個(gè)關(guān)系，即F+中的全部函數(shù)依賴在 r上成立。 第96頁/共137頁Armstrong公理系統(tǒng)的有效性與完備性(續(xù)) XF+ U-XF+ 11.1 00.0 11.1 11.1 若r不是R 的關(guān)系，則必由于F中有函數(shù)依賴VW在r上不成立所致。由r的構(gòu)成可知，V必定是XF+ 的子集，而W不是XF+ 的子集，可是由第（1）步，W XF+，矛盾。所以r必是R的一個(gè)關(guān)系。 第97頁/共137頁Armstrong

40、公理系統(tǒng)的有效性與完備性(續(xù))(3) )/* 若 f 不能用Armstrong公理推導(dǎo)出來， f F+ /* 而不能用Armstrong公理推導(dǎo)出來的 f , 在r上不成立。 若XY 不能由F從Armstrong公理導(dǎo)出，則Y 不是 XF+ 的子集。（引理5.2） 因此必有Y 的子集Y 滿足 Y U-XF+， 則XY在 r 中不成立，即XY必不為 R 蘊(yùn)含 /* 因?yàn)?F+中的全部函數(shù)依賴在 r上成立。第98頁/共137頁Armstrong公理系統(tǒng)的有效性與完備性(續(xù))Armstrong公理的完備性及有效性說明:“蘊(yùn)含” = “導(dǎo)出” 等價(jià)的概念 F+ =由F出發(fā)借助Armstrong公理導(dǎo)出

41、的函數(shù)依賴的集合第99頁/共137頁5. 函數(shù)依賴集等價(jià)定義4.14 如果G+=F+，就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。第100頁/共137頁函數(shù)依賴集等價(jià)的充要條件引理4.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+。第101頁/共137頁函數(shù)依賴集等價(jià) 要判定F G+，只須逐一對(duì)F中的函數(shù)依賴XY，考察 Y 是否屬于XG+ 就行了。

42、因此引理5.3 給出了判斷兩個(gè)函數(shù)依賴集等價(jià)的可行算法。 第102頁/共137頁6. 最小依賴集 定義4.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à)。 第103頁/共137頁最小依賴集例2 對(duì)于5.l節(jié)中的關(guān)系模式S，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G 設(shè)F=SNOS

43、DEPT，SNOMN， SDEPTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPTF是最小覆蓋，而F 不是。因?yàn)椋篎 -SNOMN與F 等價(jià) F -(SNO，SDEPT)SDEPT也與F 等價(jià) F -(SNO，SDEPT)SDEPT SNOSDEPT也與F 等價(jià)第104頁/共137頁7. 極小化過程定理4.3 每一個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小 函數(shù)依賴集Fm。此Fm稱為F的最小依賴集證:構(gòu)造性證明，依據(jù)定義分三步對(duì)F進(jìn)行“極小化處理”，找出F的一個(gè)最小依賴集。(1)逐一檢查F中各函數(shù)依賴FDi：XY， 若Y=A1A2 Ak，k 2， 則用 XAj |j=1，2， k 來取代

44、XY。 引理5.1保證了F變換前后的等價(jià)性。第105頁/共137頁極小化過程(2)逐一檢查F中各函數(shù)依賴FDi：XA， 令G=F-XA， 若AXG+， 則從F中去掉此函數(shù)依賴。 由于F與G =F-XA等價(jià)的充要條件是AXG+ 因此F變換前后是等價(jià)的。第106頁/共137頁極小化過程(3)逐一取出F中各函數(shù)依賴FDi：XA， 設(shè)X=B1B2Bm， 逐一考查Bi （i=l，2，m）， 若A （X-Bi ）F+ ， 則以X-Bi 取代X。 由于F與F-XAZA等價(jià)的充要條件是AZF+ ，其中Z=X-Bi 因此F變換前后是等價(jià)的。第107頁/共137頁極小化過程由定義，最后剩下的F就一定是極小依賴集。

45、 因?yàn)閷?duì)F的每一次“改造”都保證了改造前后的兩個(gè)函數(shù)依賴集等價(jià)，因此剩下的F與原來的F等價(jià)。 證畢 定理5.3的證明過程 也是求F極小依賴集的過程第108頁/共137頁極小化過程例3 F = AB，BA，BC， AC，CA Fm1、Fm2都是F的最小依賴集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依賴集Fm不一定是唯一的它與對(duì)各函數(shù)依賴FDi 及XA中X各屬性的處置順序有關(guān)第109頁/共137頁極小化過程 極小化過程( 定理4.3的證明 )也是檢驗(yàn)F是否為極小依賴集的一個(gè)算法 若改造后的F與原來的F相同，說明F本身就是一個(gè)最小依賴集第110頁/共137頁極小化過

46、程 在R中可以用與F等價(jià)的依賴集G來取代F 原因：兩個(gè)關(guān)系模式R1 ，R2，如果F與G等價(jià)，那么R1的關(guān)系一定是R2的關(guān)系。反過來，R2的關(guān)系也一定是R1的關(guān)系。 第111頁/共137頁第四章 關(guān)系數(shù)據(jù)理論4.1 數(shù)據(jù)依賴4.2 規(guī)范化4.3 數(shù)據(jù)依賴的公理系統(tǒng)4.4 模式的分解第112頁/共137頁4.4 模式的分解 把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義第113頁/共137頁關(guān)系模式分解的標(biāo)準(zhǔn)三種模式分解的等價(jià)定義 分解具有無損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無損連接性第11

47、4頁/共137頁模式的分解（續(xù)）定義定義4.16 關(guān)系模式R的一個(gè)分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影定義定義4.17 函數(shù)依賴集合XY | XY F+XY Ui 的一個(gè)覆蓋 Fi 叫作 F 在屬性 Ui 上的投影第115頁/共137頁模式的分解（續(xù)）例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題分解方法可以有多種 第116頁/共137頁模式的分解（續(xù)）SL SnoSdeptSloc 95001 CS A 950

48、02 IS B 95003 MA C 95004 IS B 95005 PH B 第117頁/共137頁模式的分解（續(xù)）1. SL分解為下面三個(gè)關(guān)系模式： SN(Sno) SD(Sdept) SO(Sloc)第118頁/共137頁分解后的關(guān)系為： SN SD SO S n o S d e p t Sloc 95001 CS A 95002 IS B 95003 MA C 9 5 0 0 4 P H 95005 第119頁/共137頁模式的分解（續(xù)）分解后的數(shù)據(jù)庫丟失了許多信息 例如無法查詢95001學(xué)生所在系或所在宿舍。 如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失

49、信息第120頁/共137頁模式的分解（續(xù)）2. SL分解為下面二個(gè)關(guān)系模式： NL(Sno, Sloc) DL(Sdept, Sloc)分解后的關(guān)系為： NL DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B 第121頁/共137頁模式的分解（續(xù)）NL DL Sno Sloc Sdept 95001 A CS 95002 B IS 95002 B PH 95003 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH 第122頁/共137頁模式的分解（續(xù)）NL DL比原來的SL關(guān)系多了3個(gè)元組 無法知道95002、95004、95005 究竟是哪個(gè)系的學(xué)生 元組增加了，信息丟失了第123頁/