數(shù)據(jù)庫(kù)系統(tǒng)概論-第六章.ppt

數(shù)據(jù)庫(kù)系統(tǒng)概論 An Introduction to Database System 第六章 關(guān)系數(shù)據(jù)理論,第六章 關(guān)系數(shù)據(jù)理論,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng) *6.4 模式的分解 6.5 小結(jié),6.1關(guān)系模式設(shè)計(jì)的問(wèn)題,關(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ī)范化理論,概念回顧 關(guān)系：描述實(shí)體、屬性、實(shí)體間的聯(lián)系。 從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個(gè)子集。 關(guān)系模式：用來(lái)定義關(guān)系。 關(guān)系數(shù)據(jù)庫(kù)：基于關(guān)系模型的數(shù)據(jù)庫(kù)，利用關(guān)系來(lái)描述現(xiàn)實(shí)世界。 從形式上看，它由一組關(guān)系組成。 關(guān)系數(shù)據(jù)庫(kù)的模式：定義這組關(guān)系的關(guān)系模式的全體。,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,關(guān)系模式由五部分組成，即它是一個(gè)五元組： R(U, D, DOM, F) R： 關(guān)系名 U： 組成該關(guān)系的屬性名集合 D： 屬性組U中屬性所來(lái)自的域 DOM：屬性向域的映象集合 F： 屬性間數(shù)據(jù)的依賴(lài)關(guān)系集合 關(guān)系模式R（U, D, DOM, F）簡(jiǎn)化為一個(gè)三元組：R（U, F） 當(dāng)且僅當(dāng)U上的一個(gè)關(guān)系r 滿(mǎn)足F時(shí)，r稱(chēng)為關(guān)系模式 R（U, F）的一個(gè)關(guān)系 有時(shí)候，更簡(jiǎn)寫(xiě)成R(U)，即R(A1,A2,An)的形式,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,如何設(shè)計(jì)一個(gè)適合的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)，關(guān)鍵是關(guān)系數(shù)據(jù)庫(kù)模式的設(shè)計(jì)，一個(gè)好的關(guān)系數(shù)據(jù)庫(kù)模式應(yīng)該包括多少關(guān)系模式，而每一個(gè)關(guān)系模式又應(yīng)該包括哪些屬性，又如何將這些相互關(guān)聯(lián)的關(guān)系模式組建一個(gè)適合的關(guān)系模型，這些工作決定了到整個(gè)系統(tǒng)運(yùn)行的效率，也是系統(tǒng)成敗的關(guān)鍵所在，這屬于數(shù)據(jù)庫(kù)設(shè)計(jì)的問(wèn)題，確切地講是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的問(wèn)題(有關(guān)數(shù)據(jù)庫(kù)設(shè)計(jì)的全過(guò)程將在第7章詳細(xì)討論)。 本章講述關(guān)系數(shù)據(jù)庫(kù)規(guī)范化理論，這是數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的理論依據(jù)。,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,規(guī)范化理論主要包括三個(gè)方面的內(nèi)容： 函數(shù)依賴(lài) 范式（Normal Form） 模式設(shè)計(jì) 其中，函數(shù)依賴(lài)起著核心的作用，是模式分解和模式設(shè)計(jì)的基礎(chǔ)，范式是模式分解的標(biāo)準(zhǔn)。,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,關(guān)系模式的存儲(chǔ)異常問(wèn)題 數(shù)據(jù)庫(kù)的邏輯設(shè)計(jì)為什么要遵循一定的規(guī)范化理論？ 什么是好的關(guān)系模式？ 某些不好的關(guān)系模式可能導(dǎo)致哪些問(wèn)題？ 下面通過(guò)例子進(jìn)行分析:,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,描述教學(xué)管理數(shù)據(jù)庫(kù): 學(xué)號(hào)(sno),姓名(sname),年齡(age),所在系別(dept),所在系的系主任姓名(Mn),選修的課程號(hào)(cno),該課程的成績(jī)(score) 用一個(gè)單一的關(guān)系模式來(lái)表達(dá)： SCD(Sno,Sname,Age,Dept,Mn,Cno,Score) 語(yǔ)義定義如下: 一個(gè)系有若干個(gè)學(xué)生，但一個(gè)學(xué)生只屬于一個(gè)系； 一個(gè)系只有一名系主任； 一個(gè)學(xué)生可以選修多門(mén)功課，每門(mén)課程可有若干學(xué)生選修； 每個(gè)學(xué)生學(xué)習(xí)課程有一個(gè)成績(jī)。,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,教學(xué)管理數(shù)據(jù)庫(kù)的一個(gè)實(shí)例:,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,關(guān)系模式SCD存在的問(wèn)題: 1. 數(shù)據(jù)冗余 浪費(fèi)大量的存儲(chǔ)空間 例：每一個(gè)系主任的姓名重復(fù)出現(xiàn) 2. 更新異常（Update Anomalies） 數(shù)據(jù)冗余 ，更新數(shù)據(jù)時(shí)，維護(hù)數(shù)據(jù)完整性代價(jià)大。 例：某系更換系主任，或?qū)W生改名后,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,關(guān)系模式SCD存在的問(wèn)題(續(xù)): 3. 插入異常（Insertion Anomalies） 該插的數(shù)據(jù)插不進(jìn)去 例，如果一個(gè)系剛成立，尚無(wú)學(xué)生，我們就無(wú)法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫(kù)。又如，學(xué)生未選課，則學(xué)生信息無(wú)法輸入. (為什么？) 4. 刪除異常（Deletion Anomalies） 不該刪除的數(shù)據(jù)不得不刪 例，如果某個(gè)系的學(xué)生全部畢業(yè)了， 我們?cè)趧h除該系學(xué)生信息的同時(shí)，把這個(gè)系及其系主任的信息也丟掉了。,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,結(jié)論: 關(guān)系模式SCD不是一個(gè)好的模式。 “好”的模式應(yīng)該滿(mǎn)足： 不會(huì)發(fā)生插入異常、刪除異常、更新異常， 數(shù)據(jù)冗余應(yīng)盡可能少。 產(chǎn)生的原因：模式中的某些數(shù)據(jù)依賴(lài)引起的 解決方法：分解! 學(xué)生關(guān)系S(SNO,SN,AGE,DEPT) 選課關(guān)系SC(SNO,CNO,SCORE) 系關(guān)系D(DEPT,MN),6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,分解后: (左上：S； 左下：Dept; 右： SC),6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,分解后的關(guān)系模式是“好” 的。 不過(guò)，一個(gè)好的關(guān)系模式并不是在任何情況下都是最優(yōu)的。 如何按照一定的規(guī)范設(shè)計(jì)關(guān)系模式，將結(jié)構(gòu)復(fù)雜的關(guān)系分解成結(jié)構(gòu)簡(jiǎn)單的關(guān)系，從而把“不好”的關(guān)系數(shù)據(jù)庫(kù)模式轉(zhuǎn)變?yōu)椤昂谩钡年P(guān)系數(shù)據(jù)庫(kù)模式，這就是關(guān)系的規(guī)范化。 規(guī)范化又可以根據(jù)不同的要求而分成若干級(jí)別。 數(shù)據(jù)庫(kù)模式的好壞和關(guān)系中各屬性間的依賴(lài)關(guān)系有關(guān)，因此，我們先討論屬性間的依賴(lài)關(guān)系，然后再討論關(guān)系規(guī)范化理論。,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題,6.1 關(guān)系模式設(shè)計(jì)的問(wèn)題 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng) 6.4 關(guān)系模式的分解 6.5 小結(jié),第6章 關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)理論,函數(shù)依賴(lài) 平凡函數(shù)依賴(lài)與非平凡函數(shù)依賴(lài) 完全函數(shù)依賴(lài)與部分函數(shù)依賴(lài) 傳遞函數(shù)依賴(lài),6.2.1 函數(shù)依賴(lài),1. 函數(shù)依賴(lài) 定義6.1 設(shè)R(U)是一個(gè)屬性集U上的關(guān)系模式，X , Y U， r是R(U) 上的任意一個(gè)關(guān)系，如果成立 對(duì)t , s r，若tX = sX，則tY = sY 則稱(chēng) “X函數(shù)確定Y” 或 “Y函數(shù)依賴(lài)于X”，記作XY。(或不存在t,s, tX=sX而tYsY) X稱(chēng)為這個(gè)函數(shù)依賴(lài)的決定屬性集(Determinant)。 Y = f(x),6.2.1 函數(shù)依賴(lài),R(A,B,C,D,E):,tY,tX,sX,sY,S,t,只要sX = tX 就有 sY = tY: XY,函數(shù)依賴(lài),能找出哪些函數(shù)依賴(lài)關(guān)系?,學(xué)號(hào)姓名 學(xué)號(hào)年齡 學(xué)號(hào)系別 學(xué)號(hào)系主任 學(xué)號(hào) (姓名,年齡,系別,系主任) 系別系主任 (學(xué)號(hào),課程號(hào))成績(jī) 請(qǐng)思考： (學(xué)號(hào),姓名)年齡 ? (年齡,系別)系別 ? (平凡的函數(shù)依賴(lài)) (學(xué)號(hào),課程號(hào)) ?,函數(shù)依賴(lài),兩個(gè)記號(hào)： 若XY，并且YX, 則記為XY。 若Y不函數(shù)依賴(lài)于X, 則記為XY。 有關(guān)函數(shù)依賴(lài)的幾點(diǎn)說(shuō)明: 1) 函數(shù)依賴(lài)不是指關(guān)系模式R的某個(gè)或某些關(guān)系實(shí)例滿(mǎn)足的約束條件，而是指R的所有關(guān)系實(shí)例均要滿(mǎn)足的約束條件。 2) 函數(shù)依賴(lài)是語(yǔ)義范疇的概念。 只能根據(jù)語(yǔ)義來(lái)確定一個(gè)函數(shù)依賴(lài)。例如，對(duì)于前述關(guān)系模式，當(dāng)學(xué)生不存在重名的情況下，可以得到： 姓名年齡 姓名系別 3) 函數(shù)依賴(lài)關(guān)系的存在與時(shí)間無(wú)關(guān)。,函數(shù)依賴(lài),4) 函數(shù)依賴(lài)與屬性之間的聯(lián)系類(lèi)型有關(guān)。 在一個(gè)關(guān)系模式中，如果屬性X與Y有1:1聯(lián)系時(shí)，則存在函數(shù)依賴(lài)XY，YX，即XY。 如果屬性X與Y有m:1的聯(lián)系時(shí)，則只存在函數(shù)依賴(lài)XY。 例如，SNO與DEPT之間為m:1聯(lián)系，所以有SNODEPT。 如果屬性X與Y有m: n的聯(lián)系時(shí)，則X與Y之間不存在任何函數(shù)依賴(lài)關(guān)系。 例如，一個(gè)學(xué)生可以選修多門(mén)課程，一門(mén)課程又可以為多個(gè)學(xué)生選修，所以SNO與CNO之間不存在函數(shù)依賴(lài)關(guān)系。,函數(shù)依賴(lài),2.平凡函數(shù)依賴(lài)與非平凡函數(shù)依賴(lài) 定義6.2 在關(guān)系模式R(U)中，對(duì)于U的子集X和Y，如果XY，但Y X，則稱(chēng)XY是非平凡的函數(shù)依賴(lài)。若XY，但Y X, 則稱(chēng)XY是平凡的函數(shù)依賴(lài)。 非平凡的函數(shù)依賴(lài): (學(xué)號(hào),課程號(hào))成績(jī) 平凡的函數(shù)依賴(lài): (學(xué)號(hào),課程號(hào))學(xué)號(hào) (年齡,系別)系別 對(duì)于任何關(guān)系模式，平凡的函數(shù)依賴(lài)總是成立的，除非特別說(shuō)明，我們總是討論非平凡的函數(shù)依賴(lài)。,函數(shù)依賴(lài),3. 完全函數(shù)依賴(lài)與部分函數(shù)依賴(lài) 定義6.3 設(shè)關(guān)系模式R(U)，U是屬性全集，X和Y是U的子集: 如果XY，并且對(duì)于X的任何一個(gè)真子集X,都有XY，則稱(chēng)Y完全函數(shù)依賴(lài)于X，記作X f Y。 如果對(duì)X的某個(gè)真子集X，有XY，則稱(chēng)Y部分函數(shù)依賴(lài)于X，記作X p Y。 在SCD中，因?yàn)閷W(xué)號(hào) 成績(jī)，且課程號(hào) 成績(jī)，所以有：（學(xué)號(hào)，課程號(hào)） f 成績(jī) 。 而學(xué)號(hào)年齡，所以（學(xué)號(hào)，課程號(hào)） p 年齡。,函數(shù)依賴(lài),4. 傳遞函數(shù)依賴(lài) 定義6.4 在關(guān)系模式R(U)中，如果XY，YZ，且Y X，YX，則稱(chēng)Z傳遞函數(shù)依賴(lài)于X。 注: 如果YX， 即XY，則Z直接依賴(lài)于X。 在前述關(guān)系模式SCD中，有： 學(xué)號(hào) 系別，系別 系主任 系主任傳遞函數(shù)依賴(lài)于學(xué)號(hào),函數(shù)依賴(lài),碼 定義6.5 設(shè)K為關(guān)系模式R中的屬性或?qū)傩越M合。若K U，則K稱(chēng)為R的一個(gè)侯選碼Candidate Key）。若關(guān)系模式R有多個(gè)候選碼，則選定其中的一個(gè)做為主碼（Primary key）。 主屬性與非主屬性 全碼(ALL KEY),碼的定義,外碼 定義6.6 關(guān)系模式 R 中屬性或?qū)傩越MX 并非R的碼，但 X 是另一個(gè)關(guān)系模式的碼，則稱(chēng) X 是R 的外部碼（Foreign key）也稱(chēng)外碼 主碼和外部碼一起提供了表示關(guān)系間聯(lián)系的手段。,碼的定義,規(guī)范化理論正是用來(lái)改造關(guān)系模式，通過(guò)分解關(guān)系模式來(lái)消除其中不合適的數(shù)據(jù)依賴(lài)，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問(wèn)題。,6.2 關(guān)系模式的規(guī)范化,范式是符合某一種級(jí)別的關(guān)系模式的集合。 關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿(mǎn)足一定的要求。滿(mǎn)足不同程度要求的為不同范式。 通過(guò)模式分解將一個(gè)低級(jí)范式轉(zhuǎn)換為若干個(gè)高級(jí)范式的過(guò)程稱(chēng)作規(guī)范化。 范式的級(jí)別：,范式,策略 概念單一化：一個(gè)關(guān)系模式表示一個(gè)概念，一個(gè)實(shí)體，一個(gè)實(shí)體間聯(lián)系；多余部分分解出去。 目標(biāo) 較少冗余 避免修改麻煩 避免操作異常 某一關(guān)系模式R為第n范式，可簡(jiǎn)記為RnNF。,范式,1.定義 任給關(guān)系模式R(U,F)，若U中每個(gè)屬性及其值均為不可再分的基本數(shù)據(jù)元素（原子項(xiàng)），則R1NF。 2.說(shuō)明 關(guān)系DBS中,所有關(guān)系模式至少都必須是1NF。否則不能稱(chēng)為關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)。 例,1NF,3.轉(zhuǎn)換: 非1NF 1NF 去掉嵌套屬性的上層(保留最底層);重寫(xiě)行交叉處的值,1NF,4. 1NF 存在的問(wèn)題 SCD(Sno,Sname,Age,Dept,Mn,Cno,Score),1NF,1NF存在的問(wèn)題(續(xù)) 數(shù)據(jù)冗余;更新復(fù)雜;插入異常;刪除異常 5. 癥由: 非主屬性部分函數(shù)依賴(lài)于候選碼 候選碼: (Sno,Cno) U 注意到: Sno (sno,sname, age,dept,mn) 所以, 姓名、年齡、系別和系主任部分依賴(lài)于候選碼。 6. 解決方法：規(guī)范化(投影分解) 消除非主屬性對(duì)碼的部分依賴(lài)。 所有完全函數(shù)依賴(lài)于碼的屬性組成一個(gè)關(guān)系模式 所有部分FD于碼的屬性組成一個(gè)關(guān)系模式,1NF,分解后,1NF,SD,SC,分解后消除了哪些弊端？還保留了哪些弊端?,1.定義 定義6.12 若關(guān)系模式R1NF，并且每一個(gè)非主屬性都完全函數(shù)依賴(lài)于R的碼，則R2NF。 例6.10 SD(sno,sname,age,dept,mn), F=snosname, snoage, snodept, deptmn. 碼為sno, SD 2NF。 SC(sno,cno,score),F=(sno,cno)score. 碼為(sno,cno), SC 2NF。,2NF,推論: 若R1NF,且其候選碼為單個(gè)屬性,則R2NF (為什么?),2NF,2. 2NF存在的問(wèn)題 SD(sno,sname,age,dept,mn) 2NF 冗余仍存在:系主任信息冗余； 更新復(fù)雜:某系換系主任，需同時(shí)更改很多信息； 插入異常:某系無(wú)學(xué)生,則系及系統(tǒng)主任信息不能插入； 刪除異常:刪除某系全部學(xué)生,則將刪除系及主任信息。 3. 癥由 非主屬性對(duì)碼的傳遞依賴(lài):snodept, deptmn 4. 解決方法 投影分解,消去非主屬性對(duì)碼的傳遞依賴(lài)。,2NF,分解后,2NF,S,D,1.定義 定義6.13 關(guān)系模式R 中若不存在這樣的碼X、屬性組Y及非主屬性Z（Z Y）, 使得XY，Y X，YZ，成立，則稱(chēng)R 3NF。 若R 3NF,則每一非主屬性既不部分依賴(lài)于碼也不傳遞依賴(lài)于碼。 若R 3NF ,則必有R 2NF 。 采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。,3NF,推論1: 若R2NF，且至多存在一個(gè)非主屬性，則R3NF 推論2: 任何二元關(guān)系模式R(A,B)必為3NF。 2. 說(shuō)明 部分FD和傳遞FD是冗余及操作異常的重要根源。 3NF不存在非主屬性對(duì)候選碼的部分FD和傳遞FD。 3NF消去了大部分冗余及操作異常。 但并非所有的3NF都能完全消除冗余及操作異常。,3NF,例6.11 關(guān)系模式STJ(S,T,J)中,S表示學(xué)生,T表示教師,J表示課程。每一教師只教一門(mén)課,每門(mén)課有若干教師,某一學(xué)生選定某門(mén)課,就對(duì)應(yīng)一個(gè)固定的教師。即有: (S,J) T; (S,T) J; T J 顯然(S,J),(S,T)都是候選碼 STJ是3NF,3NF,3. 3NF仍可能存在冗余與更新異常 以STJ 3NF 為例 冗余:多個(gè)學(xué)生選同一老師的課時(shí),T,J重復(fù)。 修改麻煩:課程改名，需改多處。 插入異常: 學(xué)生未選課或教師開(kāi)課無(wú)人選時(shí) 刪除異常: 刪除學(xué)生信息時(shí),3NF,4. 癥由? 存在主屬性對(duì)候選碼的部分FD。 (S,T) J; T J 存在主屬性對(duì)候選碼的傳遞FD。 (S,J) T; T J 5. 解決方法 投影分解,消去主屬性對(duì)候選碼的部分FD ST(S,T), TJ(T,J),3NF,6. 分解后 冗余得到控制 插入異常得以避免 刪除異常得以避免 修改麻煩避免了,3NF,1.定義 定義6.14 設(shè)關(guān)系模式R1NF，如果對(duì)于R的每個(gè)函數(shù)依賴(lài)XY，若Y不屬于X，則X必含有候選碼，那么RBCNF。 2. BC范式的性質(zhì) 每一個(gè)函數(shù)依賴(lài)中的左部決定屬性集都包含有候選碼。 不存在非主屬性對(duì)候選碼的部分FD。 不存在非主屬性對(duì)候選碼的傳遞FD。 所有主屬性都完全FD于不包含它的候選碼。 沒(méi)有任何屬性完全函數(shù)依賴(lài)于非碼的任何一組屬性。,BCNF,3. 定理 如果RBCNF，則R3NF 證 反證法.設(shè)R是BC范式,但不是3NF.則必存在非主屬性對(duì)碼的傳遞FD.即存在非主屬性Z,通過(guò)屬性組Y，傳遞依賴(lài)于碼 X，亦即XY，YZ成立，這里Z Y , Y X. 根據(jù)BCNF的定義，Y必含有某個(gè)候選碼K。由候選碼的定義，有: Y X. 這與Y X矛盾，定理得證。,BCNF,例6.12 前述STJ(S,T,J)是3NF但不是BCNF，但分解后的ST(S,T)以及TJ(T,J)都是BCNF. 例6.13 前述S(sno,sname,age,dept)和D(dept,mn)以及SC(sno,cno,score)均為BCNF。 例6.14 關(guān)系模式SJP(S,J,P)中，S指學(xué)生,J表示課程,P表示名次。每個(gè)學(xué)生選修一門(mén)課獲得一定的名次，沒(méi)有并列名次。即: (S,J) P; (J,P) S (S,J)和(J,P)都可以作候選碼, SJP BCNF,BCNF,1.問(wèn)題的提出 設(shè)學(xué)校中某一門(mén)課程由多個(gè)教師講授，他們使用相同的一套參考書(shū)，每個(gè)教員可以講授多門(mén)課程,每種參考書(shū)可以供多門(mén)課程使用。考察關(guān)系模式： 關(guān)系模式Teaching(C, T, B) 課程C、教師T 和 參考書(shū)B(niǎo),多值依賴(lài),用非規(guī)范化的關(guān)系示意如下,多值依賴(lài),多值依賴(lài),規(guī)范化的二維表格,分析Teaching(C,T,B): 找出Teaching的非平凡函數(shù)依賴(lài) Teach具有唯一候選碼(C，T，B)， 即全碼 TeachingBCNF Teaching模式是否存在不良特性？ 數(shù)據(jù)冗余 插入異常 刪除異常 更新異常,多值依賴(lài),癥由: 多值依賴(lài): 給定的一對(duì)（X，Z）值有一組Y的值，這組值僅僅決定于X值而與Z值無(wú)關(guān)(Z = U-X-Y)。Y多值依賴(lài)于X。 考察(課程C,教員T)與(參考書(shū)B(niǎo)) 考察(課程C,參考書(shū)B(niǎo))與(教員T),多值依賴(lài),2. 定義: 定義6.15(描述型) 設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式， X、 Y和Z是U的子集，并且ZUXY，多值依賴(lài) XY成立當(dāng)且僅當(dāng)對(duì)R的任一關(guān)系r，r在（X，Z）上的每個(gè)值對(duì)應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無(wú)關(guān)。 例 Teaching（C, T, B）有 C T 和 C T,多值依賴(lài),定義6.15(形式化) 在R（U）的任一關(guān)系r中，如果存在元組s，t 使得sX=tX，那么就必然存在元組 v，w r，（v，w可以與s，t相同），使得: vX = wX = sX = tX vY = tY, wY = sY vZ = sZ，wZ = tZ （即交換s，t元組的Y值所得的兩個(gè)新元組必在r中），則Y多值依賴(lài)于X，記為XY。 這里，X，Y是U的子集，Z=U-X-Y。 或：r中若存在(x,y1,z1)和(x,y2,z2)，則必存在(x,y2,z1)和(x,y1,z2),多值依賴(lài),例6.15 找出關(guān)系上所滿(mǎn)足的多值依賴(lài):,多值依賴(lài),B C? 若使BC，需加入哪些元組？,AC AB CB CA 事實(shí)上AB, C B,加入后有沒(méi)有破壞前述依賴(lài)關(guān)系？,3. 平凡多值依賴(lài)與非平凡多值依賴(lài): 若XY，而Z，則稱(chēng) XY為平凡的多值依賴(lài) 否則稱(chēng)XY為非平凡的多值依賴(lài),多值依賴(lài),4. MVD性質(zhì): 多值依賴(lài)具有對(duì)稱(chēng)性 若XY，則XZ，其中ZUXY,多值依賴(lài),性質(zhì)(續(xù)): 函數(shù)依賴(lài)是多值依賴(lài)的特例，即 若XY，則XY 多值依賴(lài)具有傳遞性 若XY，YZ， 則X(Z Y) 并規(guī)則:若XY，XZ，則X(Y Z) 交規(guī)則:若XY，XZ，則X(YZ) 差規(guī)則: 若XY，XZ，則X(Y-Z)，X(Z Y) 偽傳遞規(guī)則: XY，WYZ， 則WX(Z W-Y),多值依賴(lài),5. 多值依賴(lài)與函數(shù)依賴(lài)的區(qū)別: 函數(shù)依賴(lài)規(guī)定某些元組不能出現(xiàn)在關(guān)系中 多值依賴(lài)要求某種形式的其它元組必須在關(guān)系中 有效性范圍不同 X Y的有效性?xún)H決定于X、Y屬性集上的值 X Y不僅涉及屬性組 X和 Y，而且涉及U中其余屬性Z 若XY在R(U)上成立，則對(duì)于任何Y Y，均有XY 成立; 多值依賴(lài)XY若在R(U)上成立，不能斷言對(duì)于任何Y Y有XY 成立 若XY在U上成立，則在W（X Y W U）上一定成立；反之則不然，即XY在W（W U）上成立，在U上并不一定成立(嵌入型MVD),多值依賴(lài),多值依賴(lài),AB在A(yíng)BC上成立，而在A(yíng)BCD上不成立,ABC 成立AB不成立,6. 不當(dāng)MVD的關(guān)系式引起的弊端及對(duì)策: Teaching(C,T,B) T(C,T) B(C,B),多值依賴(lài),1. 定義 定義6.16 關(guān)系模式R1NF，如果對(duì)于R的每個(gè)非平凡多值依賴(lài)XY（Y X），X都含有候選碼，則R4NF。 不允許有非平凡且非函數(shù)依賴(lài)的多值依賴(lài) 允許的是函數(shù)依賴(lài)（是非平凡多值依賴(lài)）,4NF,例6.16 關(guān)系模式: Teaching(C,T,B) 4NF 碼為(C, T, B) 存在MVD：CT,且C不是候選碼 分解成兩個(gè)關(guān)系模式： T(C, T) 4NF (碼:CT) B(C, B) 4NF (碼:CB) CT， CB是平凡多值依賴(lài),4NF,如果R 4NF， 則R BCNF 證 反證法。設(shè)R 4NF, 但R BCNF，但R中必存在某個(gè)非平凡FD : XY(當(dāng)然更有X Y)，且X不含R的碼。如果X Y=U，則X將成為碼，與假設(shè)矛盾; 而如果X Y U，則Z=U-X-Y , 從而X Y是一個(gè)非平凡的多值依賴(lài)，加之X不含R的碼，于是R 4NF, 這也與題設(shè)矛盾。,4NF,規(guī)范化小結(jié),2NF,4NF,1NF,3NF,消除非主屬性對(duì)碼的部分函數(shù)依賴(lài),消除非主屬性對(duì)碼的傳遞函數(shù)依賴(lài),消除主屬性對(duì)碼的部分和傳遞函數(shù)依賴(lài),消除非平凡的且非函數(shù)依賴(lài)的多值依賴(lài),BCNF,6. 關(guān)系模式的規(guī)范化,思考,任何一個(gè)二目關(guān)系模式R（A，B）一定屬于BCNF嗎？一定屬于4NF嗎？ 關(guān)系模式R（A，B，C），ABC一定成立嗎？ 一個(gè)全是主屬性的關(guān)系模式一定可以達(dá)到第幾范式？ 一個(gè)全碼的關(guān)系模式一定可以達(dá)到第幾范式？,第六章 關(guān)系數(shù)據(jù)理論,6.1 問(wèn)題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng) *6.4 模式的分解 6.5 小結(jié),6.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng),邏輯蘊(yùn)含 定義6.11 對(duì)于滿(mǎn)足一組函數(shù)依賴(lài) F 的關(guān)系模式R ，其任何一個(gè)關(guān)系r，若函數(shù)依賴(lài)XY都成立, （即r中任意兩元組t，s，若t X=s X，則t Y=s Y），則稱(chēng)F邏輯蘊(yùn)含X Y,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）自反律: 若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)含，增廣律得證。,定理 6.l Armstrong推理規(guī)則是正確的（續(xù)）,(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)含，傳遞 律得證。,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ù)Armstrong公理推導(dǎo)出來(lái)的每一個(gè)函數(shù)依賴(lài)一定在F+中； 完備性：F+中的每一個(gè)函數(shù)依賴(lài)，必定可以由F出發(fā)根據(jù)Armstrong公理推導(dǎo)出來(lái),3. 函數(shù)依賴(lài)閉包,定義6.l2 在關(guān)系模式R中為F所邏輯蘊(yùn)含的函數(shù)依賴(lài)的全體叫作 F的閉包，記為F+。 定義6.13 設(shè)F為屬性集U上的一組函數(shù)依賴(lài)，X U， XF+ = A|XA能由F 根據(jù)Armstrong公理導(dǎo)出，XF+稱(chēng)為屬性集X關(guān)于函數(shù)依賴(lài)集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, 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)于閉包的引理,引理6.2 設(shè)F為屬性集U上的一組函數(shù)依賴(lài)，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)題,求閉包的算法,算法6.1 求屬性集X（X U）關(guān)于U上的函數(shù)依賴(lài)集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）步。,算法6.1,對(duì)于算法6.1， 令ai =|X（i）|，ai 形成一個(gè)步長(zhǎng)大于1的嚴(yán)格遞增的序列，序列的上界是 | U |，因此該算法最多 |U| - |X| 次循環(huán)就 會(huì)終止。,函數(shù)依賴(lài)閉包,例1 已知關(guān)系模式R，其中 U=A，B，C，D，E； F=ABC，BD，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ù)依賴(lài)XY不能由F從Armstrong公理導(dǎo)出，那么它必然不為F所蘊(yùn)含,Armstrong公理系統(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ù)依賴(lài)在 r上成立。 XF+ U-XF+ 111 000 111 111 (3) 若XY 不能由F從Armstrong公理導(dǎo)出，則Y 不是XF+ 的子集。,5. 函數(shù)依賴(lài)集等價(jià),定義6.14 如果G+=F+，就說(shuō)函數(shù)依賴(lài)集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+。即F+ G+。 （3）同理可證G+ F+ ，所以F+ = G+。,6. 最小依賴(lài)集,定義6.15 如果函數(shù)依賴(lài)集F滿(mǎn)足下列條件，則稱(chēng)F為一個(gè)極小函數(shù)依賴(lài)集。亦稱(chēng)為最小依賴(lài)集或最小覆蓋。 (1) F中任一函數(shù)依賴(lài)的右部?jī)H含有一個(gè)屬性。 (2) F中不存在這樣的函數(shù)依賴(lài)XA，使得F與F-XA等價(jià)。 (3) F中不存在這樣的函數(shù)依賴(lài)XA， X有真子集Z使得F-XAZA與F等價(jià)。,最小依賴(lài)集,例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)椋篎 - SnoMname與F 等價(jià) F - (Sno，Sdept)Sdept也與F 等價(jià),7. 極小化過(guò)程,定理6.3 每一個(gè)函數(shù)依賴(lài)集F均等價(jià)于一個(gè)極小函數(shù)依賴(lài) 集Fm。此Fm稱(chēng)為F的最小依賴(lài)集。 證明: 構(gòu)造性證明，找出F的一個(gè)最小依賴(lài)集。,極小化過(guò)程（續(xù)）,(1)逐一檢查F中各函數(shù)依賴(lài)FDi：XY，若Y=A1A2 Ak，k 2， 則用 XAj |j=1，2， k 來(lái)取代XY。 (2)逐一檢查F中各函數(shù)依賴(lài)FDi：XA，令G=F-XA， 若AXG+， 則從F中去掉此函數(shù)依賴(lài)。 (3)逐一取出F中各函數(shù)依賴(lài)FDi：XA，設(shè)X=B1B2Bm， 逐一考查Bi （i=l，2，m），若A （X-Bi ）F+ ， 則以X-Bi 取代X。,極小化過(guò)程（續(xù)）,例3 F = AB，BA，BC，AC，CA Fm1、Fm2都是F的最小依賴(lài)集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依賴(lài)集Fm不唯一 極小化過(guò)程( 定理6.3的證明 )也是檢驗(yàn)F是否為極小依賴(lài)集的一個(gè)算法,第六章 關(guān)系數(shù)據(jù)理論,6.1 問(wèn)題的提出 6.2 規(guī)范化 6.3 數(shù)據(jù)依賴(lài)的公理系統(tǒng) *6.4 模式的分解 6.5 小結(jié),6.4.1 模式分解的定義 6.4.2 模式分解中的問(wèn)題 6.4.3 無(wú)損連接分解 6.4.4 保持函數(shù)依賴(lài)的分解 6.4.5 關(guān)系模式的分解算法 6.4.6 關(guān)系模式的設(shè)計(jì)原則,6.4 模式的分解,定義6.16 設(shè)有關(guān)系模式R, 稱(chēng)用= R1，R2，Rn 代替R的過(guò)程為R模式的分解， 稱(chēng)為R的一個(gè)分解，這里Ui和Fi必須同時(shí)滿(mǎn)足： U=U1U2Un Ui與Uj可以相交,但不允許Ui Uj或Uj Ui , ij, i,j=1,2,n Fi是F在Ui上的投影(也可記作Ri(F),6.4 模式的分解,定義6.17 函數(shù)依賴(lài)集合 XY | XY F+ XY Ui 的一個(gè)覆蓋 Fi 叫作 F 在屬性 Ui 上的投影 設(shè)有R,U=A,B,C,D, F=AB,CD (R最高為幾范式?) 1: R1(A,B,C), R2(C,D),F在R1,R2上的投影是什么? F1 = AB, F2=CD (R1最高為幾范式?R2呢?),6.4 模式的分解,設(shè)有R,U=A,B,C, F=AB,BC (R最高為幾范式?) 1: R1(A,B), R2(A,C),F在R1,R2上的投影是什么? F1 = AB, F2=AC (R1最高為幾范式?R2呢?),6.4 模式的分解,SCD(Sno,Sname,Age,Dept,Mn,Cno,Score) F=sno*, DeptMn,(sno,cno)score 分解1=SD,SC: SD(Sno,Sname,Age,Dept,Mn), F1=sno*,deptMn SC(Sno,Cno,Score), F2=(sno,cno) score 分解2=S,D,SC: S (Sno,Sname,Age,Dept),F1=sno(sname,age,dept) D(Dept,Mn),F2=deptMn SC(Sno, Cno,Score),F3=(sno,cno) score,6.4 模式的分解,6.4.1 模式分解的定義 6.4.2 模式分解中的問(wèn)題 6.4.3 無(wú)損連接分解 6.4.4 保持函數(shù)依賴(lài)的分解 6.4.5 關(guān)系模式的分解算法 6.4.6 關(guān)系模式的設(shè)計(jì)原則,6.4 模式的分解,把低一級(jí)的關(guān)系模式分解為若干個(gè)高一級(jí)的關(guān)系模式的方法并不是唯一的 只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價(jià)，分解方法才有意義 無(wú)損連接性 保持函數(shù)依賴(lài) 既保持函數(shù)依賴(lài)，又無(wú)損連接,6.4 模式的分解,6.4 模式的分解,A B, B C,(A,B): (學(xué)生,學(xué)院) (A,C): (學(xué)生,院長(zhǎng)),(A,C): (學(xué)生,院長(zhǎng)) (B,C): (學(xué)院,院長(zhǎng)),(A,B): (學(xué)生,學(xué)院) (B,C): (學(xué)院,院長(zhǎng)),6.4 模式的分解,A C,B C,=,多出違背事實(shí)的元組 有損連接的分解,A B, B C,6.4 模式的分解,A B,A C,=,插入,違反 B C: 不保持FD的分解,A B, B C,6.4 模式的分解,A B,B C,=,無(wú)損連接，且保持FD,A B, B C,6.4.1 模式分解的定義 6.4.2 模式分解中的問(wèn)題 6.4.3 無(wú)損連接分解 6.4.4 保持函數(shù)依賴(lài)的分解 6.4.5 關(guān)系模式的分解算法 6.4.6 關(guān)系模式的設(shè)計(jì)原則,6.4 模式的分解,定義6.18 關(guān)系模式R的一個(gè)分解 = R1，R2， ，Rn 若R與R1、R2、Rn自然連接的結(jié)果相等，則稱(chēng)關(guān)系模式R的這個(gè)分解具有無(wú)損連接性（Lossless join）。 具有無(wú)損連接性的分解保證不丟失信息 無(wú)損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問(wèn)題,6.4 模式的分解,算法6.2 判別一個(gè)分解是否具有無(wú)損連接性 U= A1, A2, , An = R1 , R2, , Rk 1.建立一個(gè)n列k行的矩陣 TB = Cij | 若Aj Ui , Cij = aj , 否則Cij = bij,6.4 模式的分解,算法6.2(續(xù)) 2. 對(duì)F中每一個(gè)函數(shù)依賴(lài)XY，若TB中存在元組 t1，t2，使得t1X=t2X，t1Yt2Y，則對(duì)每一個(gè)Ai Y： 若t1Ai,t2Ai中有一個(gè)等于aj,則另一個(gè)也改為aj ； 若不成立,則取t1Ai = t2Ai (t2的行號(hào)小于t1)。 (即Ai列上，只要其中有一個(gè)aj則全改為aj,否則全改為行號(hào)最小的即一列的值),6.4 模式的分解,算法6.2(續(xù)) 3. 反復(fù)執(zhí)行2, 直至： TB中出現(xiàn)一行為a1, a2 , , an 的一行。 TB不再發(fā)生變化, 且沒(méi)有一行為a1, , an。 在情況下， 為無(wú)損分解，否則為有損分解。 定理5.4 為無(wú)損連接的分解當(dāng)且僅當(dāng)是算法5.2終止時(shí),表中有一行為a1, , an。,6.4 模式的分解,例5 U=A,B,C,D,E, F=ABC, CD, DE, =(A, B, C), (C, D), (D, E)，判斷分解是否具有無(wú)損連接性。,6.4 模式的分解,ABC,CD,DE,別解 U=A,B,C,D,E, F=ABC, CD, DE, =(A, B, C), (C, D), (D, E)，判斷分解是否具有無(wú)損連接性。,ABC,CD,DE,6.4 模式的分解,例6 U=A,B,C,D,E, F=AC, BC, CD, DEC , CEA, =AD, AB, BE, CDE, AE, 判斷分解是否無(wú)損連接。,AC,BC,CD,DEC,CEA,b13,b13,a1,a1,a3,a4,a4,a4,b13,b13,a3,無(wú)損連接,6.4 模式的分解,定理6.5 R的一個(gè)分解無(wú)損連接 = R1, R2 具有無(wú)損連接性的充要條件是： U1 U2 U1-U2 F+ 或 U1 U2 U2-U1 F+,6.4 模式的分解,證明 借助算法6.2,將R的屬性分成三部分 ,(1) 充分性 如有U1 U2 U1-U2,則U2行(U1-U2)列全改為a,于是U2行全為a. 分解具有無(wú)損連接性; 同理, (2) 必要性 如是無(wú)損連接，則必有一行全a，,6.4 模式的分解,例7 R,U=A,B,C,F=A B的兩個(gè)分解： (1) 1 = R1(A,B),R2(A,C) (2) 2 = R1(A,B),R2(B,C) 問(wèn)兩分解具有無(wú)損連接性嗎? 解: (1) ABAC = A, AB-AC=B, A B F+ ,故分解 1具有無(wú)損連接性。 (2) ABBC = B, AB-BC=A, BC-AB=C. 無(wú)論B A，還是B C都不在F+ 中，所以分解 2不具有無(wú)損連接性。,6.4 模式的分解,例8 R,U=A,B,C,F=A B, C B 的分解： (1) 1 = AC,BC (2) 2 = AB,BC 問(wèn)兩分解具有無(wú)損連接性嗎? 解: (1) ACBC =C, AC-BC=A, BC-AC=B,C B F+ ,故分解 1具有無(wú)損連接性。 (2) ABBC = B, AB-BC=A, BC-AB=C. 無(wú)論B A，還是B C都不在F+ 中，所以分解 2不具有無(wú)損連接性。,6.4 模式的分解,例9 R,U=A,B,C,D,E,F,F=A B, C F, E A, CED 的分解： = ABE,CDEF 問(wèn)分解具有無(wú)損連接性嗎? 解: ABECDEF =E, ABE-CDEF=AB, E AB F+ (為什么?). 故分解具有無(wú)損連接性。 思考：R的候選碼是什么？它最高是幾范式？分解后的兩個(gè)關(guān)系模式又是幾范式?,6.4 模式的分解,6.4.1 模式分解的定義 6.4.2 模式分解中的問(wèn)題 6.4.3 無(wú)損連接分解 6.4.4 保持函數(shù)依賴(lài)的分解 6.4.5 關(guān)系模式的分解算法 6.4.6 關(guān)系模式的設(shè)計(jì)原則,6.4 模式的分解,定義6.19 關(guān)系模式R的一個(gè)= R1，R2， ，Rn 若 F 與 F1 F2 Fn等價(jià) 則稱(chēng)分解保持函數(shù)依賴(lài)。(Fi是F在Ui上的投影) 引理5.4 F+ = G+ F G+，G F+ 給出了判斷分解是否保持函數(shù)依賴(lài)的算法。,6.4 模式的分解,例10 R,U=A,B,C,F=A B, C B 的分解： (1) 1 = AC,BC (2) 2 = AB,BC 問(wèn)兩個(gè)分解是否為保持函數(shù)依賴(lài)的分解? 解: (1) F1=, F2=C B ; F1 F2=C B , 顯然與F=A B, C B 不等價(jià)。 分解不具保持函數(shù)依賴(lài)性。 (2) F1=A B, F2=C B ; F1 F2=A B ,C B = F. 分解是保持函數(shù)依賴(lài)的分解。,6.4 模式的分解,例11 R,U=A,B,C,D,E,F,F=A B, C F, E A, CED 的分解： = ABE,CDEF 問(wèn)分解具有保持函數(shù)依賴(lài)性嗎? 解: ABE(F)=E A, A B CDEF(F)=C F, CE D ABE(F) CDEF(F) = F 故分解具有保持函數(shù)依賴(lài)性。 前面已經(jīng)發(fā)現(xiàn)分解是無(wú)損連接的。問(wèn):該分解是否理想?,6.4 模式的分解,6.4 模式的分解,A B,A C,=,插入,違反 B C: 不保持FD的分解,A B, B C,例12 R,U=A,B,C,F=A B, B C 的分解： = AB,AC 保持函數(shù)依賴(lài)嗎? 解: F1=A B, F2=A C ; F1 F2=A B, A C , 與 F = A B, B C 并不等價(jià)。因?yàn)?(B C) (F1 F2) + ,但(B C) F + 。 所以，分解不具保持函數(shù)依賴(lài)性。,6.4 模式的分解,6.4.1 模式分解的定義 6.4.2 模式分解中的問(wèn)題 6.4.3 無(wú)損連接分解 6.4.4 保持函數(shù)依賴(lài)的分解 6.4.5 關(guān)系模式的分解算法 6.4.6 關(guān)系模式的設(shè)計(jì)原則,6.4 模式的分解,分解算法,算法6.2 判別一個(gè)分解的無(wú)損連接性 算法6.3（合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴(lài)的分解。 算法6.4 轉(zhuǎn)換為3NF既有無(wú)損連接性又保持函數(shù)依賴(lài)的分解 算法6.5 （分解法）轉(zhuǎn)換為BCNF的無(wú)損連接分解 算法6.6 達(dá)到4NF的具有無(wú)損連接性的分解,模式分解的幾個(gè)重要事實(shí)： 若僅要求分解具有無(wú)損連接性，則分解一定能達(dá)到4NF。 若僅要求分解保持FD，則分解一定能達(dá)到3NF，但不一定能達(dá)到BCNF。 若既要求分解具有無(wú)損連接性，又保持了FD，則分解一定能達(dá)到3NF，但不一定能達(dá)到BCNF。,6.4 模式的分解,算法6.3 達(dá)到3NF且保持函數(shù)依賴(lài)的分解算法。 輸入: 給定關(guān)系模式R 輸出: = R1, Rk, Ri 3NF, i = 1,2,k 步驟: 1. 求R的最小函數(shù)依賴(lài)集F; 2.若F中有XA ,且XA=U,則 = R,算法終止; 3.找出不在F中出現(xiàn)的屬性，將它們構(gòu)成一個(gè)關(guān)系模式，并從U中去掉它們(剩余屬性仍記為U); 4.對(duì)于F中的每個(gè)XA ,構(gòu)成一個(gè)關(guān)系模式XA.如果F中有XA1, XA2, ,XAn,則可以用XA1 A2 An代替n個(gè)模式XA1, XA2, XAn; 5.如發(fā)現(xiàn)某個(gè)Ui Uj,則應(yīng)將Ui去掉。,6.4 模式的分解,例13 R,U=S#,D,M,C#,G,F=S# D,S# M,D M,(S#,C#) G. 試將R分解3NF,并保持函數(shù)依賴(lài)。(比較例5.25的無(wú)損連接分解) 解: (1)最小依賴(lài)集F =S# D,D M,(S#,C#) G (2)分解 R1(S#，D)， S#D R2(D，M)， DM R3(S#，C#，G)， (S#,C#)G 這個(gè)分解是無(wú)損連接的分解嗎？,6.4 模式的分解,例14 R(C,T,H,R,S,G), 其中:C課程,T教師,H時(shí)間,R教室,S學(xué)生,G成績(jī). F： 1. CT(每門(mén)課僅一名教師上) 2. HRC(任一時(shí)間，一個(gè)教室只能上一門(mén)課) 3. HTR(一個(gè)時(shí)間，一個(gè)教師只能在一個(gè)教室上課) 4. CSG(一個(gè)學(xué)生，一門(mén)課只有一個(gè)成績(jī)) 5. HSR(一個(gè)時(shí)間，一個(gè)學(xué)生只能在一個(gè)教室上課)