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

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