第六章 關(guān)系數(shù)據(jù)理論-new

第六章關(guān)系數(shù)據(jù)理論問題的提出規(guī)范化數(shù)據(jù)依賴的公理系統(tǒng)關(guān)系模式的分解本章主要內(nèi)容本章討論的核心問題如何判斷一個(gè)關(guān)系模式是否存在問題如何構(gòu)造一個(gè)好的數(shù)據(jù)庫模式6.1問題的提出一個(gè)關(guān)系模式應(yīng)當(dāng)是一個(gè)五元組。R(U,D,DOM,F)這里：(1)關(guān)系名R，它是符號(hào)化的元組語義；(2)一組屬性U;(3)屬性組U中屬性所來自的域D;(4)屬性到域的映射DOM;(5)屬性組U上的一組數(shù)據(jù)依賴F。由于(3),(4)對(duì)模式設(shè)計(jì)關(guān)系不大，因此在本章中把關(guān)系模式看作是一個(gè)三元組：R<U,F>6.1問題的提出數(shù)據(jù)依賴是一個(gè)關(guān)系內(nèi)部屬性與屬性之間的一種約束關(guān)系。這種約束關(guān)系是通過屬性間值的相等與否體現(xiàn)出來的數(shù)據(jù)間相關(guān)聯(lián)系。它是現(xiàn)實(shí)世界屬性間相互聯(lián)系的抽象，是數(shù)據(jù)內(nèi)在的性質(zhì)，是語義的體現(xiàn)。例子:描述學(xué)校教務(wù)的數(shù)據(jù)庫，該數(shù)據(jù)庫涉及的對(duì)象包括學(xué)生的學(xué)號(hào)(Sno)、所在系(Sdept)、系主任名(Mname)、課程號(hào)(Cno)和成績(Grade)。假設(shè)用一個(gè)單一的關(guān)系模式Student來表示，則該關(guān)系模式的屬性集合為U={Sno,Sdept,Mname,Cno,Grade}其中:一個(gè)系有若干學(xué)生,但一個(gè)學(xué)生只屬于一個(gè)系一個(gè)系只有一名(正職)負(fù)責(zé)人一個(gè)學(xué)生可以選修多門課程,每門課可有若干學(xué)生選修每個(gè)學(xué)生學(xué)習(xí)每一門課程有一個(gè)成績于是得到屬性組U上的一組函數(shù)依賴FF={Sno→Sdept,Sdept→Mname,(Sno,Cno)→Grade}6.1問題的提出6.1問題的提出某一時(shí)刻關(guān)系模式Student的一個(gè)實(shí)例，即數(shù)據(jù)表。S1CS李洪C190S2CS李洪C1 90S3CS李洪C190S4CS李洪C190S5MA張力C190S5MA張力C190存在的問題冗余太大：每一個(gè)系的系主任姓名重復(fù)出現(xiàn)，重復(fù)次數(shù)與該系所有學(xué)生的所有課程成績出現(xiàn)次數(shù)相同，這將浪費(fèi)大量存儲(chǔ)空間。刪除異常:刪除某系學(xué)生的選課將刪除系信息插入異常:系剛成立,無學(xué)生，就無法把這個(gè)系及其系主任的信息存入數(shù)據(jù)庫。更新異常：某系更換系主任后，必須修改與該系學(xué)生有關(guān)的每一個(gè)元組。6.1問題的提出結(jié)論:關(guān)系模式Student(Sno,Sdept,Mname,Cno,Grade)不是好的關(guān)系模式,好的關(guān)系模式不會(huì)發(fā)生插入異常、刪除異常并且冗余盡可能少。 為什么會(huì)發(fā)生這些問題？這是因?yàn)檫@個(gè)模式中的函數(shù)依賴存在某些不好的性質(zhì)。假如把這個(gè)單一的模式改造一下，分成3個(gè)關(guān)系模式：S(Sno,Sdept,Sno→Sdept)SC(Sno,Cno,Grade,(Sno,Cno)→Grade)DEPT(Sdept,Mname,Sdept→Mname)這3個(gè)模式都不會(huì)發(fā)生插入異常、刪除異常的毛病，數(shù)據(jù)的冗余也得到了控制。一個(gè)模式的數(shù)據(jù)依賴會(huì)有哪些不好的性質(zhì)，如何改造一個(gè)不好的模式，這就是下一節(jié)規(guī)范化理論討論的內(nèi)容。6.2規(guī)范化根據(jù)屬性間依賴情況來判定關(guān)系是否具有某些不合適的性質(zhì)。通常按屬性間依賴情況來區(qū)分關(guān)系規(guī)范化的程度分為第一范式、第二范式、第三范式和第四范式等。6.2規(guī)范化定義6.1函數(shù)依賴:設(shè)R<U>是屬性集U上的關(guān)系模式,X,Y是U的子集,若對(duì)于R<U>的任意一個(gè)可能的關(guān)系r,r中不可能存在兩個(gè)元組在X上的屬性值相等,而在Y上的屬性值不等,則稱“X函數(shù)確定Y”或“Y函數(shù)依賴于X”,記作XY。函數(shù)依賴和別的數(shù)據(jù)依賴一樣是語義范疇的概念。函數(shù)依賴不是指關(guān)系模式R的某個(gè)或某些關(guān)系滿足的約束條件，而是指R的一切關(guān)系均要滿足的約束條件。

6.2規(guī)范化一些記號(hào)和術(shù)語:若XY,但YX則稱X→Y是非平凡的函數(shù)依賴。若XY,但ＹＸ則稱Ｘ→Ｙ是平凡的函數(shù)依賴。對(duì)于任一關(guān)系模式，平凡函數(shù)依賴都是必然成立的，它不反應(yīng)新的語義。若不特別聲明，總是討論非平凡的函數(shù)依賴。若X→Y，則X稱為這個(gè)函數(shù)依賴的決定屬性組，也稱為決定因素。若X→Y，Y→X，則記作X←→Y。若Y不函數(shù)依賴于X，則記作XY6.2規(guī)范化定義6.2完全函數(shù)依賴:在R<U>中,如果XY,并且對(duì)于X的任何真子集X’

,都有X’Y,則稱Y對(duì)X完全函數(shù)依賴,記作XY部分函數(shù)依賴:如果XY,但Y不完全函數(shù)依賴于X,則稱Y對(duì)X部分函數(shù)依賴,記作XY定義6.3函數(shù)傳遞依賴:在R<U>中,如果XY,(YX),

YX,YZ,則稱Z對(duì)X傳遞函數(shù)依賴。記為X→Z。fp傳遞6.2規(guī)范化6.2.2碼定義6.4候選碼:設(shè)K為R<U,F>中的屬性或?qū)傩越M,若KU,則K為R的候選碼。若候選碼多于一個(gè)，則選定其中的一個(gè)為主碼。包含在任何一個(gè)候選碼中的屬性，稱為主屬性。不包含在任何碼中的屬性稱為非主屬性或非碼屬性。最簡單的情況，單個(gè)屬性是碼。最極端的情況，整個(gè)屬性組是碼，稱為全碼。定義6.5關(guān)系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(guān)系模式的碼，則稱X是R的外部碼，也稱外碼。f6.2規(guī)范化6.2.3范式關(guān)系數(shù)據(jù)庫中的關(guān)系是要滿足一定要求的，滿足不同程度要求的為不同范式。滿足最低要求的叫第一范式，簡稱1NF。在第一范式中滿足進(jìn)一步要求的為第二范式，其余依次類推。范式就是符合某一種級(jí)別的關(guān)系模式的集合，則R為第幾范式就可以寫成R∈xNF。對(duì)于各種范式之間的聯(lián)系有1NF2NF3NFBCNF4NF5NF一個(gè)低一級(jí)范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式集合，這種過程就叫規(guī)范化。一范式(1NF)：如果一個(gè)關(guān)系中的所有屬性值均是原子的，則稱該關(guān)系滿足1NF。關(guān)系模型中的關(guān)系必須滿足1NF6.2規(guī)范化定義6.6二范式(2NF):若R1NF,且每一個(gè)非主屬性完全函數(shù)依賴于碼,則稱R2NF例子:關(guān)系模式S-L-G(S#,SD,SL,C#,G),其中一個(gè)系的學(xué)生只住一個(gè)地方SL,碼為(S#,C#),函數(shù)依賴有:(S#,C#)G因?yàn)镾#SD,所以(S#,C#)SD因?yàn)镾#SL,所以(S#,C#)SLS-L-G2NF

fpp6.2規(guī)范化問題:關(guān)系模式S-L-G(S#,SD,SL,C#,G)不屬于2NF,將出現(xiàn)插入異常:如果學(xué)生95001沒選課,不能插入刪除異常:如果一個(gè)學(xué)生只選修了一門課,如刪除這門課，會(huì)導(dǎo)致數(shù)據(jù)庫中沒有該學(xué)生的其他信息，如S#,SD,SL。修改復(fù)雜:學(xué)生轉(zhuǎn)系,不僅修改所在系,還修改住處6.2規(guī)范化規(guī)范化:解決辦法是用投影分解所以關(guān)系模式S-L-C被分解為S-C(S#,C#,G)S-L(S#,SD,SL)定義6.7三范式(3NF):關(guān)系模式R<U,F>中若不存在這樣的碼X,屬性組Y以及非主屬性組Z(ZY),使得XY，YZ和YX成立，則稱R<U,F>3NF 如果關(guān)系模式R<U,F>2NF，且每一個(gè)非主屬性不傳遞依賴于任一候選關(guān)鍵字，則稱R<U,F>3NF可以證明如果R<U,F>3NF,則每一個(gè)非主屬性既不部分依賴于碼,也不傳遞依賴于碼6.2規(guī)范化例子:關(guān)系模式S-L(S#,SD,SL)中有S#SD,SDS#,SDSL則S#SL所以S-L3NF問題:關(guān)系模式S-L不屬于3NF,將出現(xiàn)插入異常:一個(gè)系剛成立,無學(xué)生刪除異常:某個(gè)系的學(xué)生全畢業(yè)了修改復(fù)雜:學(xué)生轉(zhuǎn)系,不僅修改SD,也要修改SL規(guī)范化:解決方法是投影分解,將S-L分解為不好:S-D(S#,SD)好:S-D(S#,SD)S-L(S#,SL)D-L(SD,SL)傳遞?6.2規(guī)范化關(guān)系模式S-L-G(S#,SD,SL,C#,G)分解為S-G(S#,C#,G)S-D(S#,SD)

D-L(SD,SL)BCNF(BoyceCoddNormalForm):關(guān)系模式R<U,F>1NF,若XY且YX時(shí),X必含有碼,則RBCNF6.2規(guī)范化討論RBCNF,則R3NF若R3NF,則R未必屬于BCNF例如:關(guān)系模式STJ(S,T,J),其中每位教師只教授一門課,每門課由若干教師擔(dān)任,某一學(xué)生S選定一門課J,就對(duì)應(yīng)一位固定的教師T,因此對(duì)應(yīng)函數(shù)依賴可表示TJ

(S,J)T(S,T)J,候選碼為(S,J)和(S,T)結(jié)論:STJ3NF,但STJBCNF6.3數(shù)據(jù)依賴的公理系統(tǒng)數(shù)據(jù)依賴的公理系統(tǒng)是模式分解算法的理論基礎(chǔ)Armstrong公理系統(tǒng):函數(shù)依賴的一個(gè)有效而完備的公理系統(tǒng)定義6.11邏輯蘊(yùn)含:對(duì)于滿足一組函數(shù)依賴F的關(guān)系模式R<U,F>,其中任何一個(gè)關(guān)系r,若函數(shù)依賴XY都成立(即r中任意兩元組t,s，若t[X]=s[X],則t[Y]=s[Y]),則稱F邏輯蘊(yùn)含XY一套推理規(guī)則(Armstrong公理系統(tǒng)):可以求得給定關(guān)系模式的碼,可以從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴，例如已知函數(shù)依賴集F，要問X→Y是否為F所蘊(yùn)含。6.3數(shù)據(jù)依賴的公理系統(tǒng)Armstrong公理系統(tǒng):設(shè)U為屬性集總體,F是U上的一組函數(shù)依賴,于是有關(guān)系模式R<U,F>,對(duì)R<U,F>來說有以下的推理規(guī)則：A1自反律:若YXU,則XY為F所蘊(yùn)含A2增廣律:若XY為F所蘊(yùn)含,且ZU,則XZYZ為F所蘊(yùn)含A3傳遞律:若XY及YZ為F所蘊(yùn)含,則XZ為F所蘊(yùn)含定理6.1Amstrong推理規(guī)則是正確的。6.3數(shù)據(jù)依賴的公理系統(tǒng)證明1:設(shè)YXU對(duì)R<U,F>的任一關(guān)系r中的任意兩個(gè)元組t,s若t[X]=s[X],由YX可得t[Y]=s[Y]所以XY成立證明2:設(shè)XY為F所蘊(yùn)含,且ZU對(duì)R<U,F>的任一關(guān)系r中的任意兩個(gè)元組t,s若t[XZ]=s[XZ],則有t[X]=s[X]和t[Z]=s[Z]又XY成立,則有t[Y]=s[Y]所以t[YZ]=s[YZ],所以XZYZ為F所蘊(yùn)含6.3數(shù)據(jù)依賴的公理系統(tǒng)證明3:設(shè)XY及YZ為F所蘊(yùn)含對(duì)R<U,F>的任一關(guān)系r中的任意兩個(gè)元組t,s若t[X]=s[X],由XY可得t[Y]=s[Y]又YZ成立,則有t[Z]=s[Z]所以XZ為F所蘊(yùn)含根據(jù)上述推理規(guī)則得到另外的推理規(guī)則1合并規(guī)則:若XY，XZ,則有XYZ2偽傳遞規(guī)則:若XY，WYZ,則有XWZ3分解規(guī)則:若XY及ZY,則有XZ6.3數(shù)據(jù)依賴的公理系統(tǒng)引理6.1:XA1A2...

Ak成立的充分必要條件是X

Ai成立(由合并規(guī)則和分解規(guī)則可以證明)定義6.12:F的閉包在關(guān)系模式R<U,F>中為F所邏輯蘊(yùn)含的函數(shù)依賴的全體,記作F+Armstrong公理系統(tǒng)是有效的、完備的有效的:指由F出發(fā),根據(jù)Armstrong公理導(dǎo)出的每個(gè)函數(shù)依賴一定在F+中完備的:指F+中的每個(gè)函數(shù)依賴必定可由F出發(fā),根據(jù)Armstrong公理推導(dǎo)出來6.3數(shù)據(jù)依賴的公理系統(tǒng)證明完備性，要解決如何判定一個(gè)函數(shù)依賴是否屬于由F根據(jù)Armstrong公理推導(dǎo)出來的函數(shù)依賴的集合。理論上是可以求得F+的,如果有F+,判斷XY是否屬于F+是非常容易的,但實(shí)際上由F求F+有時(shí)幾乎是不可能做到的,例如從F={XA1,XA2,…,XAn}出發(fā)至少可以推導(dǎo)出2n個(gè)不同的函數(shù)依賴。為此引入了下面的概念：定義6.13:設(shè)F為屬性集U上的一組函數(shù)依賴,XU,XF+={A|XA能由F根據(jù)Armstrong公理導(dǎo)出},XF+稱為屬性集X關(guān)于函數(shù)依賴集F的閉包引理6.2:設(shè)F為屬性集U上的一組函數(shù)依賴,X,YU,XY能由F根據(jù)Armstrong公理導(dǎo)出的充分必要條件是YXF+6.3數(shù)據(jù)依賴的公理系統(tǒng)判斷XY是否能由F根據(jù)Armstrong公里推導(dǎo)出來的問題,轉(zhuǎn)化為求XF+,判斷Y是否為XF+的子集問題。這個(gè)問題由算法6.1解決。算法6.1求XF+算法(輸入X,F,輸出XF+)(1)令X(0)=X,i=0(2)求B,B={A|(v)(w)(vwFvX(i)Aw)}(3)X(i+1)=BX(i)(4)判斷X(i+1)=X(i)?(5)若相等或X(i)=U,XF+=X(i),結(jié)束(6)若不等,i=i+1,返回(2)找到左部為X子集的函數(shù)依賴6.3數(shù)據(jù)依賴的公理系統(tǒng)例子:已知關(guān)系模式R<U,F>,U={A,B,C,D,E},F={ABC,BD,CE,ECB,ACB}求(AB)F+(1)X(0)=AB,i=0(2)求B,B={CD}(3)X(1)=BX(0)={ABCD}(4)因?yàn)閄(1)X(0),所以再找出左部為ABCD子集的那些函數(shù)依賴(5)B={CDBE}(6)X(2)=BX(1)={ABCDE}(AB)F+={ABCDE}找到左部為X子集的函數(shù)依賴6.3數(shù)據(jù)依賴的公理系統(tǒng)定理6.2Amstrong公理系統(tǒng)是有效的、完備的。Amstrong公理的完備性及有效性說明了“導(dǎo)出”與“蘊(yùn)含”是兩個(gè)完全等價(jià)的概念。于是F+也可以說成是由F出發(fā)借助Armstrong公理導(dǎo)出的函數(shù)依賴的集合。從蘊(yùn)含(或?qū)С?的概念出發(fā)，又引出了兩個(gè)函數(shù)依賴等價(jià)和最小依賴集的概念。6.3數(shù)據(jù)依賴的公理系統(tǒng)定義6.14

如果G+=F+,就說函數(shù)依賴集F覆蓋G（F是G的覆蓋，或G是F的覆蓋），或F與G等價(jià)。引理6.3:F+=G+的充分必要條件是FG+和GF+證:必要性F+=G+F+G+G+F+

所以F

G+G

F+充分性F

G+則F+(G+)+,但(G+)+=G+故F+G+同理可證G+F+

所以F+=G+6.3數(shù)據(jù)依賴的公理系統(tǒng)定義6.15:如果函數(shù)依賴集F滿足下列條件,則稱F為一個(gè)極小的函數(shù)依賴集,也稱最小覆蓋(1)F中的每個(gè)函數(shù)依賴的右部為單屬性(2)F中不存在這樣的函數(shù)依賴XA,使得F-{XA}與F等價(jià)

(3)F中不存在這樣的函數(shù)依賴XA,使得F-{XA}{ZA}與F等價(jià)(ZX)6.3數(shù)據(jù)依賴的公理系統(tǒng)定理6.3:每個(gè)函數(shù)依賴集F均等價(jià)于一個(gè)極小的函數(shù)依賴集Fm,Fm稱為F的最小覆蓋證明:只要能構(gòu)造一個(gè)滿足定義6.15中3個(gè)條件的覆蓋Fm,定理得證(1)逐一檢查F中的函數(shù)依賴XY,如Y=A1A2...An,則用{XAi|i=1,2...,K}取代XY(2)逐一檢查XAi令G=F-{XAi},若AiXG+則從F中去掉該函數(shù)依賴,對(duì)所有的XAi檢查并處理后的覆蓋G’,G’滿足定義6.15中的(1)(2)6.3數(shù)據(jù)依賴的公理系統(tǒng)(3)檢查G‘中每個(gè)函數(shù)依賴XA,設(shè)X=B1B2...Bm,對(duì)Bi逐一做下列檢查和處理G’與G’-{XA}{(X-Bi)A}是否等價(jià)如等價(jià),則以X-Bi取代X,如不等價(jià),則X不變所有的Bi檢查完后,令最后的X為Z并以G’-{XA}{(ZA)代替G’G’中每個(gè)XA做如此檢查后,求得函數(shù)依賴集G’’顯然G’’滿足定義5中的3項(xiàng),故令G’’為Fm,即Fm是可構(gòu)造的6.3數(shù)據(jù)依賴的公理系統(tǒng)求候選關(guān)鍵字的經(jīng)驗(yàn)方法若屬性A僅出現(xiàn)在所有函數(shù)依賴的右部，則它一定不包含在任何候選關(guān)鍵字中；若屬性A僅出現(xiàn)在所有函數(shù)依賴的左部，則它一定包含在某個(gè)候選關(guān)鍵字中；若屬性A既出現(xiàn)在函數(shù)依賴的右部，又出現(xiàn)在左部，則它可能包含在候選關(guān)鍵字中；若屬性A既不出現(xiàn)在函數(shù)依賴的左部，又不出現(xiàn)在函數(shù)依賴的右部。在上述基礎(chǔ)上求屬性集閉包。6.3數(shù)據(jù)依賴的公理系統(tǒng)給定關(guān)系模式R,求候選碼例子:對(duì)于R(ABCDE),F={AB,BCE,EDA}求出R的所有候選關(guān)鍵字如果K是關(guān)鍵字,則有KU,所以只要判斷KF+=U且K’F+U(K’K)(CD)F+={CD}(CDE)F+={CDEAB}(CDA)F+={ABCDE}(CDB)F+={CDBEA}R的候選關(guān)鍵字為CDA，CDB，CDE。f6.4模式分解定義6.16關(guān)系模式R<U,F>的一個(gè)分解是指={R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn>},其中

,并且沒有UiUj,1i,jn,Fi是F在Ui上的投影。Fi是F在Ui上的投影的定義是：定義6.17函數(shù)依賴集合的一個(gè)覆蓋Fi叫做F在屬性Ui上的投影。6.4模式分解6.4.1模式分解的3個(gè)定義對(duì)于一個(gè)模式的分解是多種多樣的，分解后產(chǎn)生的模式應(yīng)與原模式等價(jià)。對(duì)“等價(jià)”的概念形成了三種不同的定義。分解具有“無損連接性”分解要“保持函數(shù)依賴”分解既要“保持函數(shù)依賴”，又要具有“無損連接性”6.4模式分解例子:已知R<U,F>,其中U={Sno,Sdept,Mname}F={SnoSdept,SdeptMname},R<U,F>的元組語義是學(xué)生Sno正在Sdept系學(xué)習(xí)，其系主任是Mname。并且一個(gè)學(xué)生(Sno)只在一個(gè)系學(xué)習(xí)，一個(gè)系只有一名系主任。R的一個(gè)關(guān)系如下表。S4畢業(yè)，則D3的系主任是王一的信息也丟掉了。一個(gè)系D5尚無在校學(xué)生，那么這個(gè)系的系主任是趙某的信息也無法輸入。SnoSdept

Mname

S1D1張五S2D1張五S3D2李四S4D3王一6.4模式分解分解1={R1<S#,>,R2<SD,>,R3<MN,>}分解后Ri的關(guān)系ri是R的關(guān)系r在Ui上的投影r1={S1,S2,S3,S4}r2={D1,D2,D3}r3={張五,李四,王一}如果回答“S1在哪個(gè)系學(xué)習(xí)”也不可能了。6.4模式分解分解2={R1<{Sno,Sdpet},{SnoSdept}>,R2<{Sno,Mname},{SnoMname}>}SnoSdeptMnamer1={{S1,D1},{S2,D1},S1D1張五{S3,D2},{S4,,D3}}S2D1張五r2={{S1,張五},{S2,張五},S3D2李四{S3,李四},{S4,王一}}S4D3王一2對(duì)R的分解是可恢復(fù)的，但是前面提到的插入和刪除異常仍然沒有解決，原因就在于原來在R中存在的函數(shù)依賴SdeptMname，現(xiàn)在在R1和R2中都不再存在了。因此要求分解具有“保持函數(shù)依賴”的特性。6.4模式分解分解3={R1<{Sno,Sdept},{SnoSdept}>,R2<{Sno,Mname},{SdeptMname}>}SnoSdeptMnamer1={{S1,D1},{S2,D1},S1D1張五{S3,D2},{S4,,D3}}S2D1張五r2={{D1,張五},{S3,李四},S3D2李四{S4,王一}}S4D3王一通過自然連接,可以恢復(fù)r3既具有無損連接性，又保持函數(shù)依賴。它解決了更新異常，又沒有丟失原數(shù)據(jù)庫的信息，這是所希望的分解。6.4模式分解結(jié)論:對(duì)一個(gè)模式的分解是多種多樣的分解具有“無損連接性”分解要保持函數(shù)依賴分解既要保持函數(shù)依賴又要具有無損連接性

定義3:設(shè)={R1,R2,…,Rn}是R的一個(gè)分解,r是R的任意一個(gè)值,如果滿足條件r=r1r2,…,rn,其中ri=Ui(r),稱分解具有無損連接性或簡稱無損分解6.4模式分解定義4:設(shè)={R1,R2,…,Rn}是R的一個(gè)分解,如果

邏輯蘊(yùn)含F(xiàn),稱分解保持函數(shù)依賴

關(guān)系模式分解的兩種準(zhǔn)則

只滿足無損分解:最基本的要求,發(fā)同樣的查詢得到查詢結(jié)果相等即滿足無損分解又滿足保持函數(shù)依賴6.4模式分解算法6.2無損分解測試算法:檢測一個(gè)分解是否無損分解輸入:關(guān)系模式R(A1,A2,...,An)R上的函數(shù)依賴集FR上的分解={R1,R2,...,Rk}輸出:是無損分解步驟:6.4模式分解(1)建立n列,k行的矩陣M屬性的K個(gè)關(guān)系模式A1A2...Aj...AnR1R2Ri...M[i,j]Rk.........M[i,j]=aj若AiUi

bij若AiUi6.4模式分解(2)對(duì)F中的每個(gè)函數(shù)依賴XY反復(fù)進(jìn)行下面的檢查和處理,直到M無變化為止檢查X中的屬性所對(duì)應(yīng)的列,找出X相等的那些行,如果找到X相等的兩行(或多行),把相應(yīng)的Y屬性對(duì)應(yīng)的符號(hào)改為一致,即如果其中之一為aj,則其他也改成aj,如果這兩個(gè)符號(hào)為bij和blj,將它們統(tǒng)一成bij或blj(3)當(dāng)M無變化時(shí),如果M中有一行變成了a1,a2...,an,則是無損分解,否則不是6.4模式分解例子:關(guān)系模式R(ABCDE)={R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)}是R的一個(gè)分解,在R上有下列函數(shù)依賴F={AC,BC,CD,DEC,CEA},判別是否是無損分解解:(1)建M(2)對(duì)AC檢查b13,b23,b53b13對(duì)BC檢查b13,b33b13ABCDER1R2R3R4R56.4模式分解ABCDER1a1b12b13a4b15R2a1a2b23b24b25R3b31a2b33b34a5R4b41b42a3a4a5R5a1b52b53b54a5ABCDER1a1b12b13a4b15R2a1a2

b13b24b25R3b31a2b33b34a5R4b41b42a3a4a5R5a1b52b13b54a5={R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)}對(duì)AC檢查對(duì)BC檢查6.4模式分解對(duì)CD檢查對(duì)DEC檢查ABCDER1a1b12b13a4b15