第3章關(guān)系數(shù)據(jù)庫規(guī)范化理論1xt

1、1,數(shù)據(jù)庫技術(shù)及應(yīng)用,第三章　關(guān)系數(shù)據(jù)庫的規(guī)范化理論,2,3.1 關(guān)系模式的冗余和異常問題,范式（Normal Form）：是指規(guī)范化的關(guān)系模式。第一范式（1NF）：由滿足最基本規(guī)范化的關(guān)系模式。第一范式的關(guān)系模式再滿足另外一些約束條件就產(chǎn)生了第二范式、第三范式、BC范式等等。一個低一級的關(guān)系范式通過模式分解可以轉(zhuǎn)換成若干高一級范式的關(guān)系模式的集合，這種過程叫關(guān)系模式的規(guī)范化（ Normalization）。,3,二、 關(guān)系模

2、式規(guī)范化的必要性,關(guān)系模式應(yīng)滿足的基本要求1) 元組的每個分量必須是不可分的數(shù)據(jù)項。2) 數(shù)據(jù)庫中的數(shù)據(jù)冗余應(yīng)盡可能少?！　　?shù)據(jù)量巨增，系統(tǒng)負(fù)擔(dān)過重，浪費存儲空間，造成數(shù)據(jù)的不完整。3) 關(guān)系數(shù)據(jù)庫不能因為數(shù)據(jù)更新操作而引起數(shù)據(jù)不一致問題。（數(shù)據(jù)冗余） 4) 當(dāng)執(zhí)行數(shù)據(jù)插入操作時，數(shù)據(jù)庫中的數(shù)據(jù)不能產(chǎn)生插入異常現(xiàn)象。　　　數(shù)據(jù)庫中的數(shù)據(jù)因不能滿足某種完整性要求而不能正常地插入到數(shù)據(jù)庫中。5) 數(shù)據(jù)庫中的數(shù)據(jù)不

3、能在執(zhí)行刪除操作時產(chǎn)生刪除異常問題。刪除某種信息的同時，把其他信息也刪除了。多種信息捆綁在一起。,,4,關(guān)系中每一個分量都必須是不可分的數(shù)據(jù)項?！∨袛嗍欠駷殛P(guān)系的標(biāo)準(zhǔn)　關(guān)系的一切數(shù)學(xué)理論都是基于關(guān)系服從1NF。,修改后的數(shù)據(jù)結(jié)構(gòu)：,將大大增加關(guān)系操作的表達、優(yōu)化及執(zhí)行的復(fù)雜度。,5,6) 數(shù)據(jù)庫設(shè)計應(yīng)考慮查詢要求，數(shù)據(jù)組織應(yīng)合理。,在數(shù)據(jù)庫設(shè)計時，不僅要考慮到自身結(jié)構(gòu)的完整性，還要考慮到數(shù)據(jù)的使用要求?！　榱耸箶?shù)據(jù)查詢方便、數(shù)

4、據(jù)處理簡便，有必要通過視圖、索引和適當(dāng)增加數(shù)據(jù)冗余的方法。,6,2. 關(guān)系中異常和冗余問題,數(shù)據(jù)冗余大； 插入異常； 刪除異常； 更新異常。,7,3. 模式分解是關(guān)系規(guī)范化的主要方法,按“一事一地”的原則分解成“單位”、“物資”和“領(lǐng)料”三個關(guān)系，其關(guān)系模式為：,單位（單位編碼，單位名稱）物資（物資編碼，物資名稱，計量單位，價格）領(lǐng)料（單位編碼，物資編碼，領(lǐng)料時間，請領(lǐng)量，實發(fā)量）,關(guān)系模式: 物資領(lǐng)料（單位編碼，單位名稱，

5、物資編碼，物資名稱，領(lǐng)料時間，計量單位，價格，請領(lǐng)量，實發(fā)量）。,8,學(xué)生(學(xué)號，姓名，年齡，性別，系名稱)； 教學(xué)系(系名，系主任)； 選課(學(xué)號，課程名，成績).,,9,3.2 函數(shù)依賴,關(guān)系模式的簡化表示法關(guān)系模式的完整表示是一個五元組： R(U，D，Dom，F(xiàn)).其中：R為關(guān)系名；U為關(guān)系的屬性集合；D為屬性集U中屬性的數(shù)據(jù)域；Dom為屬性到域的映射；F為屬性集U的數(shù)據(jù)依賴集。關(guān)

6、系模式可以用三元組來為： R(U，F(xiàn)),10,2. 函數(shù)依賴的概念,設(shè)R（U）是屬性集U上的關(guān)系模式，X、Y是U的子集。若對于R（U）的任意一個可能的關(guān)系r，r中的任一元組在X中的屬性值確定后，則在Y中的屬性值也必確定。則稱X函數(shù)決定Y，或Y函數(shù)依賴于X，記作X→Y?！、?X→Y，但Y 　X，則稱X→Y是非平凡的函數(shù)依賴。　　若不特別聲明，總是討論非平凡的函數(shù)依賴?！、?X→Y，但Y?X，則稱X→Y是平凡的函數(shù)依賴。

7、　③ 若X→Y，則X叫做決定因素（Determinant），Y叫做依賴因素（Dependent）。?、?若X→Y，Y→X，則記作X?Y。?、?若Y不函數(shù)依賴于X，則記作X 　Y。,,,函數(shù)依賴是數(shù)據(jù)依賴的一種，實際上它描述的是同一關(guān)系中屬性間的聯(lián)系。,,11,例3，對于教學(xué)關(guān)系模式：教學(xué)（U，F(xiàn)）；U={學(xué)號，姓名，年齡，性別，系名，系主任，課程名，成績}；,例1：物資（物資編碼，物資名稱，計量單位，價格）　屬性“物資編碼”

8、和“物資名稱”間有函數(shù)依賴關(guān)系，物資編碼的值確定，物資名稱的值也惟一確定?！》Q “物資編碼”函數(shù)決定“物資名稱”或　　 “物資名稱”函數(shù)依賴于“物資編碼”。,例2：領(lǐng)料（單位編碼，物資編碼，領(lǐng)料時間，請領(lǐng)量，實發(fā)量）,F={學(xué)號→姓名，學(xué)號→年齡，學(xué)號→性別，學(xué)號→系名，系名→系主任，(學(xué)號，課程名)→成績}.,“物資編碼”與“請領(lǐng)量”間沒有函數(shù)依賴關(guān)系。但…,12,注意： 函數(shù)依賴是語義范疇的概念，我們只能根據(jù)數(shù)據(jù)的語義來

9、確定函數(shù)依賴。例如，“姓名→所在系”這個函數(shù)依賴只有在沒有同名人的條件下成立。如果有相同名字的人，則“所在系”就不再函數(shù)依賴于“姓名”了。,13,完全函數(shù)依賴、傳遞函數(shù)依賴,在R(U)中，如果X→Y，并且對于X的任何一個真子集X’，都有X’ Y，則稱Y對X完全函數(shù)依賴，記作：X→Y；若X→Y，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，記作： X→Y。 例:在教學(xué)關(guān)系模式：(學(xué)號，課程名)→成績，(學(xué)號，課程名)→姓名

10、.在R(U)中，如果X→Y，(Y X)，Y X，Y→Z，則稱Z對X傳遞函數(shù)依賴。傳遞函數(shù)依賴記作X → Z。例如，在教學(xué)模式中，因為：學(xué)號→系名，系名→系主任；所以：學(xué)號 → 系主任。,,P,f,f,P,傳遞,傳遞,14,碼定義： 設(shè)K為關(guān)系模式R(U)中的屬性或?qū)傩越M合，若K→U，則稱K為R的一個候選碼。若關(guān)系模式有多個候選碼，則選定其中的一個做為主碼（primary key）。主屬性：包含在任何一個關(guān)鍵字中的屬

11、性。非主屬性：不包含在任何候選碼中的屬性。 在最簡單的情況下，候選碼只包含一個屬性。在最極端的情況下，關(guān)系模式的所有屬性組是這個關(guān)系模式的候選碼，稱為全碼。,15,3.3 范式和規(guī)范化方法,數(shù)據(jù)依賴引起的主要問題是插入、刪除及更新異常等，解決的辦法是進行關(guān)系模式的合理分解，也就是對關(guān)系模式規(guī)范化?！》妒绞欠夏骋环N級別的關(guān)系模式的集合。滿足最低要求的叫第一范式，簡稱為1NF。在第一范式基礎(chǔ)上進一步滿足一些要求的為第二范式，簡

12、稱為2NF。其余以此類推。顯然各種范式之間存在　　　　　　　　　　　　　　　　　聯(lián)系。通常把某一關(guān)系模式R為第n范式簡記為R∈nNF。,,小知識：從1971年起，E。F。Codd相繼提出了第一范式、第二范式，第三范式， Codd與Boyce合作提出了Boyce －Codd范式，到目前為止，已提出了第五范式。,16,如果關(guān)系模式R，其所有的屬性均為簡單屬性，即每個屬性都是不可再分的，則稱R屬于第一范式，記作R?1NF。 　它不

13、允許屬性值為元組、數(shù)組或某種復(fù)合數(shù)據(jù)等。,一、 1NF的定義,僅滿足第一范式是不夠的，仍然存在異常和冗余問題，需對關(guān)系模式繼續(xù)規(guī)范，使之服從更高的范式，才能得到性能較高的關(guān)系模式。,17,二、 2NF,若關(guān)系模式R∈lNF，并且每一個非主屬性都完全函數(shù)依賴于R的碼，則R∈ 2NF。 2NF就是不允許關(guān)系模式的非主屬性對碼的部分依賴。即：X→Y，其中X是碼的真子集，Y是非主屬性。,顯然，碼只包含一個屬性的關(guān)系模式如果屬于1NF，那

14、么它一定屬于2NF。,18,例1：分析關(guān)系模式R（dwbm，wzbm，rq，dwmc，zgld，zgdz，qls，sfs）中的函數(shù)依賴：,19,如對關(guān)系模式R分解為兩個關(guān)系模式：R1（dwbm，wzbm，rq，qls，sfs）R2（dwbm， dwmc，zgld，zgdz）,關(guān)系分解實際上是把聯(lián)系不緊密的屬性盡量分開。,20,在教學(xué)模式中：,屬性集={學(xué)號，姓名，年齡，系名，系主任，課程名，成績}.　函數(shù)依賴集={學(xué)號→姓名，學(xué)號

15、→年齡，學(xué)號→性別，學(xué)號→系名， 系名→系主任，(學(xué)號，課程名)→成績}.主碼=(學(xué)號，課程名).  非主屬性=(姓名，年齡，系名，系主任，成績)。,{(學(xué)號，課程名)→姓名，(學(xué)號，課程名)→年齡，(學(xué)號，課程號)→性別 ，,(學(xué)號，課程名)→系名，(學(xué)號，課程名)→系主任；(學(xué)號，課程名)→成績}.顯然，教學(xué)模式不服從2NF，即：教學(xué)?2NF。,,P,P,P,P,P,非主屬性對碼的函數(shù)依

16、賴：,21,,根據(jù)2NF的定義，將教學(xué)關(guān)系模式分解：學(xué)生＿系（學(xué)號，姓名，性別，年齡，系名，系主任）。選課（學(xué)號，課程名，成績）,問題：滿足2NF的關(guān)系模式是否還存在異常和冗余問題？,22,三. 3NF,關(guān)系模式R〈U，F(xiàn)〉中若不存在這樣的碼X、屬性組Y及非主屬性Z(Z Y)使得X→Y、Y X、Y→Z成立，則稱R（U，F(xiàn)）?3NF?？梢宰C明，若R?3NF，則每一個非主屬性既不部分函數(shù)依賴于碼，也不傳遞函數(shù)依賴于碼。,,分析

17、下面關(guān)系模式的范式：R1（dwbm，wzbm，rq，qls，sfs）R2（dwbm， dwmc，zgld，zgdz）,R1 ?3NF ， R2∈ 3NF，對R2分解：R21（dwbm， dwmc，zgld）　　R22（zgld，zgdz）,23,例2：學(xué)生_系（學(xué)號，姓名，性別，年齡，系名，系主任）。,∵學(xué)號→系名，系名→系主任。則：,,如果分解為： 學(xué)生(學(xué)號，姓名，年齡，性別，系名)； 教學(xué)系(系名，系主任).顯

18、然分解后的各子模式均屬于3NF。,∴學(xué)生_系?3NF。,24,說明：,1、3NF范式是一個可用的關(guān)系模式應(yīng)滿足的最低范式。,2、把關(guān)系模式分解到第三范式，可以在相當(dāng)程度上減輕原關(guān)系中的異常和信息冗余，但也不能保證完全消除關(guān)系模式中的各種異常和信息冗余。要想使數(shù)據(jù)庫性能得到進一步的改善，就要把關(guān)系模式進一步規(guī)范化。,25,四. BCNF（Boyce Codd Normal Form）,關(guān)系模式R（U，F(xiàn)）?1NF。若X→Y（Y　X）時X必

19、含有碼，則R（U，F(xiàn)）?BCNF?！　〖矗宏P(guān)系模式R〈U，F(xiàn)〉中，若每一個決定因素都包含碼，則R〈U，F(xiàn)〉?BCNF。一個滿足BCNF的關(guān)系模式有：1) 所有非主屬性對每一個碼都是完全函數(shù)依賴?！?2) 所有的主屬性對每一個不包含它的碼，也是完全依賴。 3) 沒有任何屬性完全函數(shù)依賴于非碼的任何一組屬性。,26,例1：分析下面的關(guān)系是否滿足BC范式？S11(學(xué)號，姓名，所在系)S12(所在系，系主任姓名)S2(學(xué)號，

20、課程名，成績),答：均滿足BCNF范式,27,,例2：關(guān)系模式SPC(S，C，P)中，S是學(xué)生，C表示課程，P表示名次。語義：每一個學(xué)生選修每門課程的成績有一定的名次，每門課程中每一名次只有一個學(xué)生(即沒有并列名次)。由語義可得到下面的函數(shù)依賴：,（ S，C）→P；(C，P) →S候選碼：(S，C)與(C，P) 。SPC∈3NF，而且除(S，C)與(C，P)以外沒有其它決定因素，所以SPC∈BCNF,28,例3：關(guān)系模式STJ(S

21、，T，J)中，S表示學(xué)生，T表示教師，J表示課程?！　≌Z義為：每一教師只能講授一門課程，每門課程由若干教師講授；每個學(xué)生選修某門課程就對應(yīng)一個固定的教師?！　∮烧Z義可以得到STJ模式的函數(shù)依賴為： F={(S，J)→T，T→J}顯然：(S，J)和(T，S)都是關(guān)系的碼；　　　關(guān)系的主屬性集為{S，T，J}，非主屬性為?（空集）。P由于STJ模式中無非主屬性，所以它屬于3NF；但因為存在T→J，由于T不是碼，故STJ?B

22、CNF。,29,五、BCNF和3NF的比較,1) BCNF不僅強調(diào)非主屬性對碼的完全的直接的依賴，而且強調(diào)主屬性對碼的完全的直接的依賴，故R?BCNF，R一定屬于3NF。 2) 3NF只強調(diào)非主屬性對碼的完全直接依賴，這樣就可能出現(xiàn)主屬性對碼的部分依賴和傳遞依賴。,30,,,1NF,2NF,3NF,BCNF,,,,削除非主屬性對碼的部分函數(shù)依賴,削除非主屬性對碼的傳遞函數(shù)依賴,削除主屬性對碼的部分和傳遞函數(shù)依賴,圖1　各種范式規(guī)范化

23、過程,31,規(guī)范化小結(jié)：1、在關(guān)系數(shù)據(jù)庫中，對關(guān)系模式的基本要求是滿足第一范式。這樣的關(guān)系模式就是合法的、允許的。但是，人們發(fā)現(xiàn)有些關(guān)系模式存在插入、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等毛病。人們尋求解決問題的方法，這就是規(guī)范化的目的。2、規(guī)范化的基本思想是逐步消除數(shù)據(jù)依賴中不合適的部分，使模式中的各關(guān)系模式達到某種程度的“分離”，即“一事一地”的模式設(shè)計原則。讓一個關(guān)系描述一個概念、一個實體或者實體間的一種聯(lián)系。若多于一個概念就把它“分

24、離”出去。因此所謂規(guī)范化實質(zhì)上是概念的單一化。,32,3、實際上，在對模式進行分解時，除考慮數(shù)據(jù)等價和依賴等價以外，還要考慮效率。　　當(dāng)我們對數(shù)據(jù)庫的操作主要是查詢而更新較少時，為了提高查詢效率，可能寧愿保留適當(dāng)?shù)臄?shù)據(jù)冗余，讓關(guān)系模式中的屬性多些，而不愿把模式分解得太小，否則為了查詢一些數(shù)據(jù)，常常要做大量的連接運算，把多個關(guān)系模式連在一起才能從中找到相關(guān)的數(shù)據(jù)。,在實際應(yīng)用中，對模式分解的要求并不一定要達到BC范式或更高的范式，有時達

25、到第三范式就足夠了。,33,關(guān)系規(guī)范化理論研究：,函數(shù)依賴?yán)碚摰难芯俊。?）關(guān)系模式上的所有依賴通過一些公理系統(tǒng)（ Armstrong ）而獲得關(guān)系模式上的所有依賴?；镜挠烧Z義獲取，其他部分由公理系統(tǒng)推出?！?（2）最小函數(shù)依賴集:等價的函數(shù)依賴集中最小者?！∧Ｊ椒纸獾难芯俊。?）無損連接（反映了模式分解的數(shù)據(jù)等價原則。 ）　　當(dāng)對關(guān)系模式R進行分解時，R的元組將分別在相應(yīng)屬性集進行投影而產(chǎn)生新的關(guān)系?！　∪绻麑π碌年P(guān)系進

26、行自然連接得到的元組的集合與原關(guān)系完全一致，則稱為無損連接 ?！。?）保持依賴　　當(dāng)對關(guān)系模式R進行分解時，R的函數(shù)依賴集也將按相應(yīng)的模式進行分解。如果分解后總的函數(shù)依賴集與原函數(shù)依賴集保持一致，則稱為保持依賴。,,34,F1={A→B，B → C，A →C}與F2={A→B，B → C， A→BC}F3={A→B，B → C}是否等價？,,35,3.4 關(guān)系模式的分解算法 一、關(guān)系模式分解的算法基礎(chǔ),函數(shù)依賴的邏輯蘊含

27、 設(shè)F是模式R〈U〉的函數(shù)依賴集，X和Y是屬性集U的子集。如果從F中的函數(shù)依賴能推出X→Y，則稱F邏輯蘊含X→Y，或稱X→Y是F的邏輯蘊含。如：F＝｛A→B，B → C｝，問A →C是否成立？　　這就需要函數(shù)依賴的邏輯隱含知識，用函數(shù)依賴的公理系統(tǒng)推出。,36,2. Armstrong公理系統(tǒng)(1) Armstrong公理系統(tǒng)設(shè)U為屬性集，F(xiàn)是U上的函數(shù)依賴集，于是有關(guān)系模式R〈U，F(xiàn)〉。對R（U，F(xiàn)）來說，有以下的推

28、理規(guī)則：1) 自反律：若Y?X?U，則X→Y為F所蘊含。2) 增廣律：若X→Y為F所蘊含，且Z?U，則XZ→YZ為F所蘊含。3) 傳遞律：若X→Y及Y→Z為F所蘊含，則X→Z為F所蘊含。(2) Armstrong公理的三個推理1) 合并規(guī)則：由X→Y，X→Z，有X→YZ。2) 偽傳遞規(guī)則：由X→Y，WY→Z，有XW→Z。3) 分解規(guī)則：由X→Y及Z?Y，有X→Z。,由合并規(guī)則和分解規(guī)則，容易知：X →A1A2…Ak成立的充

29、分必要條件為X →Ai成立。（i=1,2, …k ）,37,,2、指出下列關(guān)系屬于第幾范式？并說明理由　。,（1）R(X,Y,Z) F={XY→Z}解：　　∵R的候選碼為XY，而R中決定因素只有XY ，決定因素包含了碼。　　∴ R∈BCNF。,（2）R(X,Y,Z) F={Y→Z，XZ→Y}　解：∵R的候選碼為XY或XZ，不存在非主屬性對碼的部分或傳遞函數(shù)依賴　　∴ R∈3NF。,38,（3）R(X,Y,Z) F=

30、{Y→Z，Y→X，X→YZ，}解：∵R的候選碼為X和Y（單個屬性）， X→YZ等價于： X→Y， X→Z，故X　Y，不存在非主屬性Z對碼的傳遞函數(shù)依賴。又決定因素都是碼，　　∴ R∈BCNF。,（4）R(X,Y,Z) F={X→Y，X→Z }解：∵R的候選碼為X（單個屬性）， 又每一個函數(shù)依賴的左部都是碼，　　∴ R∈BCNF。,,39,（5）R(X,Y,Z) F={XY→Z}解：∵R的候選碼為XY， 又每一個函數(shù)依賴

31、的左部都是碼，　　∴ R∈BCNF。,（6）R(W，X,Y,Z) F={X→Z，WX→Y}解：∵R的候選碼為WX， 存在非主屬性對碼的部分函數(shù)依賴。　　∴ R∈1NF。,40,3. 函數(shù)依賴集閉包F+和屬性集閉包XF+,(1) 函數(shù)依賴集閉包F+和屬性集閉包XF+的定義 在關(guān)系模式R（U，F(xiàn)）中，為F所邏輯蘊含的函數(shù)依賴的全體叫做F的閉包，記作F+?！≡O(shè)有關(guān)系模式R（U，F(xiàn)），X是U的子集，稱所有從F推出的函數(shù)依賴集X

32、→Ai中Ai的屬性集為X的屬性閉包，記作XF+。即： XF+={ Ai | Ai∈U，X→Ai∈F+}(2) 屬性集閉包XF+的求法　1) 選X作為閉包XF+的初值XF(0)。2) XF(i+1)是由XF(i)并上集合A所組成，其中A為F中存在的函數(shù)依賴Y→Z，而A?Z，Y?XF(i)。3) 重復(fù)步驟2)。一旦發(fā)現(xiàn)XF(i)= XF(i+1)，則XF(i)為所求XF+。,41,【例1】已知關(guān)系R〈U，F(xiàn)〉，其中U={A，B，C，

33、D，E}，F(xiàn)={AB→C，B→D，C→E，EC→B，AC→B}，求(AB)F+。設(shè)X=AB∵ XF(0)=AB 　　：AB為閉包初值,為本身。 XF(1)=ABCD ?。河葾B→C，B → D可得CD在閉包中。由 XF(2)=ABCDE ：由C → E，知E在閉包中。 XF(3)= XF(2)=ABCDE ∴ (AB)F+=ABCDE={A，B，C，D，E},42,4. 函數(shù)依賴集的最

34、小化,最小函數(shù)依賴集的定義　　如果函數(shù)依賴集F滿足下列條件，則稱F為一個極小函數(shù)依賴集。亦稱為最小依賴集或最小覆蓋。1) F中任一函數(shù)依賴的右部僅含有一個屬性。2) F中不存在這樣的函數(shù)依賴X→A，使得F與F－{X→A}等價。(不含冗余函數(shù)依賴。) 3) F中不存在這樣的函數(shù)依賴X→A，X有真子集Z使得F-{X→A}∪{Z-A}與F等價。(決定因素不含冗余屬性。)如F={A→B，B → C，A →C}不是最小函數(shù)依

35、賴集。,43,(2) 最小函數(shù)依賴集的求法　1) 逐一檢查F中各函數(shù)依賴X→Y，若Y=A1A2…Ak，k≥2，則用{X→Aj|j=1，2，…k}來取代X→Y。(右邊的屬性單值化)　2) 逐一檢查F中各函數(shù)依賴X→A，令G=F－{X→A}，若A∈XG+，則從F中去掉此函數(shù)依賴。(去掉冗余函數(shù)依賴)　3) 逐一取出F中各函數(shù)依賴X→A，設(shè)X=B1B2…Bm，逐一檢查Bi（i=1，2，…，m），如果A∈(X-Bi)F+，則以X－Bi取代

36、X。(左邊的屬性單值化),44,【例4-2】設(shè)F={A→BC，B→AC，C→A}，對F進行極小化處理。,解：1) 根據(jù)分解規(guī)則把F中的函數(shù)依賴轉(zhuǎn)換成右部都是單屬性的函數(shù)依賴集合，分解后的函數(shù)依賴集仍用F表示。 F={A→B，A→C，B→A，B→C，C→A}2) 去掉F中冗余的函數(shù)依賴。判斷A→B。設(shè)：G1={ A→C，B→A，B→C，C→A}，得：AG1+=AC ∵ B?AG1+ ∴ A→B不冗余判斷A→C。設(shè)：G2

37、={ A→B，B→A，B→C，C→A}，得：AG2+=ABC ∵ C?AG2+ ∴ A→C冗余判斷B→A。設(shè)：G3={ A→B，B→C，C→A}，（去掉A→C冗余后）得：BG3+=BCA ∵ A?BG3+ ∴ B→A冗余判斷B→C。設(shè)：G4={ A→B，C→A}，得：BG4+=B ∵ C?BG4+ ∴ B→C不冗余判斷C→A。設(shè)：G5={ A→B，B→C }， 得：CG5+=C ∵ A?CG5+ ∴ C→A不

38、冗余 Fm={ A→B，B→C，C→A},45,【例4-3】求F={AB→C，A→B，B→A}的最小函數(shù)依賴集Fm。,解：(1)去掉F中冗余的函數(shù)依賴。判斷AB→C是否冗余。設(shè)：G1={ A→B，B→A}，得：(AB)G1+=AB ∵ C? (AB)G1+ ∴ AB→C不冗余判斷A→B是否冗余。設(shè)：G2={ AB→C，B→A}，得：AG2+=A ∵ B?ABG2+ ∴ A→B不冗余判斷B→A是否冗余。設(shè)：G

39、3={ AB→C，A→B }，得：BG3+=B ∵ A?BG3+ ∴B→A不冗余經(jīng)過檢驗后的函數(shù)依賴集仍然為F={AB→C，A→B，B→A}。(2) 去掉各函數(shù)依賴左部冗余的屬性。本題只需考慮AB→C的情況。方法1：在決定因素中去掉B，若C?AF+，則以A→C代替AB→C。求得：AF+=ABC ∵ C?AF+ ∴ 以A→C代替AB→C故：Fm={A→C，A→B，B→A}方法2：在決定因素中去掉A，若C?BF

40、+，則以B→C代替AB→C。求得：BF+=ABC ∵ C?BF+ ∴ 以B→C代替AB→C故：Fm={B→C，A→B，B→A},46,3.4.2 判定分解服從規(guī)范的方法,1. 關(guān)系分解的無損連接性 　 設(shè)關(guān)系模式R，如果把它分解為兩個（或多個）子模式R1和R2，相應(yīng)一個R關(guān)系中的數(shù)據(jù)就要被分成R1 、R2兩個（或多個）子表?！　　〖偃鐚⑦@些子表自然連接，即進行R1∞R2操作，得到的結(jié)果與原來關(guān)系中的數(shù)據(jù)一致，

41、信息并沒有丟失，則稱該分解具有無損連接性，否則如果R≠R1 ∞ R2，則稱該分解不具有無損連接性。2. 判斷分解成兩個關(guān)系具有無損連接性的方法定理：R〈U，F(xiàn)〉的一個分解?={ R1(U1，F(xiàn)1)，R2(U2，F(xiàn)2)}具有無損連接性的充分必要條件是： (U1∩U2)→(U1-U2∈F+). 或 U1∩U2→U2-U1∈F+.3. 判斷分解保持函數(shù)依賴的方法設(shè)Ｒ〈U，F(xiàn)〉的分解?={R1〈U1，F(xiàn)1〉，R1〈U2，F(xiàn)2〉

42、，…Rk〈UK，F(xiàn)K〉}，若F+=(∪Fi)+，則稱分解?保持函數(shù)依賴。,47,【例３-5】關(guān)系模式R={CITY，ST，ZIP}，其中CITY為城市，ST為街道，ZIP為郵政編碼，F(xiàn)={(CITY，ST)→ZIP，ZIP→CITY}。如果將R分解成R1和R2，R1={ST，ZIP}，R2={CITY，ZIP}，檢查分解是否具有無損連接和保持函數(shù)依賴。解：1) 檢查無損連接性。求得：R1∩R2={ZIP}；R2-R1={CITY}.

43、∵ (ZIP→CITY)∈F+. ∴ 分解具有無損連接性　　　2) 檢查分解是否保持函數(shù)依賴　求得：πR1(F)=Ф；πR2(F)={ ZIP→CITY}.∵ πR1(F)∪πR2(F)={ ZIP→CITY}≠F+. 　　∴ 該分解不保持函數(shù)依賴。,48,3.4.3 關(guān)系模式的分解方法,1) 對R（U，F(xiàn)）中的F進行極小化處理。處理后的函數(shù)依賴集仍用F表示。2) 找出不再在F中出現(xiàn)的屬性（極小化后），這樣的屬性構(gòu)成一

44、個關(guān)系模式，并把這些屬性從U中去掉。3) 如果F中有一個函數(shù)依賴涉及R的全部屬性，則R不能再分解。4) 如果F中含有X→A，則分解應(yīng)包含模式XA，如果X→A1，X→A2，…X→An均屬于F，則分解應(yīng)包含模式XA1A2…An?！纠?-6】設(shè)關(guān)系模式R〈U，F(xiàn)〉，U={C，T，H，R，S，G，X，Y，Z}，F(xiàn)={C→T，CS→G，HR→C，HS→R，TH→R，C→X}，將R分解為3NF，且保持函數(shù)依賴。解：設(shè)該函數(shù)依賴集已經(jīng)是最小化

45、的，則分解?為： ?={YZ，CTX，CSG，HRC，HSR，THR}.,一、將關(guān)系模式轉(zhuǎn)化為3NF的保持函數(shù)依賴的分解,49,2. 將關(guān)系轉(zhuǎn)化為3NF、且既具有無損連接性又能保持函數(shù)依賴的分解,分解算法為：1) 設(shè)X是R（U，F(xiàn)）的碼，R〈U，F(xiàn)〉先進行保持函數(shù)依賴的分解，結(jié)果為?={ R1（U1，F(xiàn)1），R2〈U2，F(xiàn)2〉，…，Rk〈Uk，F(xiàn)k〉}，令τ=?∪{R*（X，F(xiàn)x）}。2) 若有某個Ui，X? Ui，將R*〈

46、X，F(xiàn)x〉從τ中去掉，τ就是所求的分解?！纠?-7】有關(guān)系模式R〈U，F(xiàn)〉，U={C，T，H，R，S，G}，F(xiàn)={C→T，CS→G，HR→C，HS→R，TH→R}，將R分解為3NF，且既具有無損連接性又能保持函數(shù)依賴。解：求得關(guān)系模式R的碼為HS，它的一個保持函數(shù)依賴的3NF為： ?={CT，CSG，HRC，HSR，THR}.∵ HS?HSR∴ τ=?={ CT，CSG，HRC，HSR，THR}為滿足要求的分解。,5