第16講模式分解

1、6.4 模式的分解模式分解的定義無損連接分解保持函數(shù)依賴的分解模式分解的算法1關(guān)系模式R的一個(gè)分解是指 =R1, R2, Rn 其中U= U1U2Un ，并且沒有Ui Uj, ij ， Fi是F在Ui上的投影。F在Ui上的投影（記作Ui F）是指 函數(shù)依賴集合XY| XYF+XYUi的一個(gè)覆蓋Fi。例1:已知R,UA,B,C,D, F=A-BD, D-C, 如果將R分解為R1(U1, F1)和R2(U2, F2), 其中U1=A,B,D, U2=A,C, 則F1,F2分別是？一、關(guān)系模式分解的定義2 一個(gè)模式的分解是多種多樣的，但是分解后產(chǎn)生的模式應(yīng)與原模式等價(jià)。 對(duì)“等價(jià)”的三種定義： 分解

2、具有“無損連接性”； 分解要“保持函數(shù)依賴”； 分解既具有“無損連接性”，又“保持函數(shù)依賴”。3例2：已知關(guān)系模式R,其中 USno,Sdept,Sloc,F=Sno-Sdept,Sdept-Sloc. 分析R屬于？NF，并分析R的各種模式分解方法。 Sno Sdept Sloc 99001 計(jì)算機(jī) D1 99002電信 D2 99003自控 D3 99004電信 D2 99005管理 D2 表1：R的一個(gè)關(guān)系r1.分解1：R1、R2、R3分解后的DB無法恢復(fù)到原來的情況。42.分解2： R1 R2Sno Sdept Sloc 99001 計(jì)算機(jī) D1 99002電信 D2 99003自控 D

3、3 99004電信 D2 99005管理 D2 表1：R的一個(gè)關(guān)系r分解后可以恢復(fù)，但仍然存在插入和刪除異常。53.分解3： R1 R2Sno Sdept Sloc 99001 計(jì)算機(jī) D1 99002電信 D2 99003自控 D3 99004電信 D2 99005管理 D2 表1：R的一個(gè)關(guān)系r分解可恢復(fù)，并且解決了異常。6二、無損連接的分解引入一個(gè)記號(hào)：設(shè)=R1, R2, Rk 是R的一個(gè)分解，r是R的一個(gè)關(guān)系。定義m(r)= 即m(r)是r在中各關(guān)系模式上投影的自然連接。定義：=R1,Rk是R的一個(gè)分解.若對(duì)R的任一關(guān)系r都有r=m(r)，則稱具有無損連接性。簡(jiǎn)稱為無損分解。ki=1R

4、i(r)7判斷一個(gè)分解是否具有無損連接性方法一： 定理：已知R的一個(gè)分解=R1,R2, 具有無損連接性的充要條件是 (U1U2)(U1-U2)F+ 或(U1U2)(U2-U1)F+ 證明從略。例3: 已知R, U=A,B,C, F=AB, CB。 分解1=AB, BC、分解2=AC, BC是否具備無損連接性？例4：已知R,U=ABCDEF , F=AB,CF,EA,CED =R1(ABE),R2(CDEF)是否具備無損連接性？ 8 =R1,RK是R的一個(gè)分解，U=A1,An, F=FD1,FDm，并設(shè)F是一極小依賴集， 記FDi為 XiAli1）建立一個(gè)n列k行的表。每列對(duì)應(yīng)一個(gè)屬性Aj ，每

5、行對(duì)應(yīng)一個(gè)子關(guān)系模式的屬性集Ui 。若Aj屬于Ui，則在第i行j列交叉處填上aj，否則填上bij；2）對(duì)每個(gè)FDi做如下操作：找到Xi所對(duì)應(yīng)的列中具有相同符號(hào)的那些行，考察這些行中l(wèi)i列的元素，若其中有ali則全部改為ali，否則全部改為bmli；m是這些行的行號(hào)最小值（若某個(gè)btli被更動(dòng) ，那么該表的li列中凡是btli的符號(hào)均作相應(yīng)更改）。 若有一行成為a1，an。則算法終止，分解具備無損連接性。 對(duì)F中個(gè)FD逐一進(jìn)行上述處理，稱為對(duì)F的一次掃描。3）比較掃描前后，若表有變化，則返回2）；若表無變化，則算法終止，分解不具備無損連接性。判斷一個(gè)分解是否具有無損連接性方法二：9例5：已知R,

6、U=A,B,C,D,E,F=AB-C,C-D, D-E,R的一個(gè)分解為R1(A,B,C),R2(C,D),R3(D,E)。 判斷此分解是否具備無損連接性。例6：設(shè)有關(guān)系模式R, U=E,G,H,I,J, F=E-I, J-I, I-G, GH-I, IH-E, 判斷= EG, EJ, JH, IGH, EH 是否為無損連接分解。10三、保持函數(shù)依賴的分解定義:設(shè)=R1, Rk是R的一 個(gè)分解，若 , 則保持函數(shù)依賴。 其中FiUi F.例7: 已知R,U=A,B,C,F=AB，CB 判斷1=AC,AB是否具有依賴保持性？ 例8: 已知R,U=ABCDEF, F=AB,EA,CF, CED，判斷

7、2=ABE,CDEF是否具有依賴保持性？11四、模式分解的算法算法1（合成法)： 將R分解為3NF并保持函數(shù)依賴的算法對(duì)R中的函數(shù)依賴集F進(jìn)行極小化處理（處理后的結(jié)果仍記為F）；找出不在F中出現(xiàn)的屬性，把它們構(gòu)成一個(gè)關(guān)系模式。并把這些屬性從U中去掉（剩余的屬性仍記為U）；若XAF且XA=U,則=R，算法終止； 否則，對(duì)F按具有相同左部的原則分組，每組函數(shù)依賴Fi所涉及的全部屬性形成一個(gè)屬性集Ui；若 Ui包含于Uj就去掉Ui。停止，是3NF且具有依賴保持性。 12例9：已知R, U=C, T, H, I, S, G， 最小集F=CT, CSG, HTI, HI C, HSI， 將R分解為3NF

8、且具有函數(shù)依賴保持性。 13設(shè)X是R的碼。R由算法1分解為=R1, R2, Rn，令 R* 若有某個(gè)Ui, X Ui,將R*從中去掉。即為所求。算法2：分解為3NF，既具有無損連接性又保持函數(shù)依賴四、模式分解的算法14四、模式分解的算法算法3（分解法）：分解為BCNF,且具有無損連接性。步驟：令=R檢查：若中所有關(guān)系模式均屬于BCNF，則算法終止。若中Ri不屬于BCNF,則必有XAFi+,且X不是Ri的碼，顯然AX是Ui的真子集。對(duì)Ri進(jìn)行分解:Ri1,Ri2,其中Ui1=XA, Ui2=Ui-A,用分解Ri1, Ri2代替Ri,轉(zhuǎn)15例10：已知R, U=C, T, H, I, S, G，

9、最小集F=CT, CSG, HTI, HIC, HSI， 將R分解為BCNF且為無損分解。 16作業(yè)：1.對(duì)給定的關(guān)系模式R,U=A,B,C,D,E,P,F=A-B, C-P, E-A, CE-D,有如下分解：=R1(ABE), R2(CDEP)1)求R的候選碼，并判斷是否無損2）R1,R2分別屬于第幾范式2. 關(guān)系R(ABCDE)滿足下列函數(shù)依賴：F=A-C, C-D, B-C, DE-C, CE-A1)求R的候選碼2)判斷=AD, AB, BC, CDE, AE是否無損連接分解3)分解R為BCNF，并具有無損連接性173.設(shè)有關(guān)系模式R。U=E,G,H,I,J, F=E-I, J-I, I

10、-G, GH-I, IH-E1)求R的候選碼2)判斷=EG, EJ, JH, IGH, EH是否為無損連接分解3)分解R為3NF，要求具有無損連接性并保持函數(shù)依賴18小結(jié)關(guān)系模式設(shè)計(jì)最低要求為1NF范式級(jí)別并非越高越好： 大多分解到3NF即可滿足要求； 依用戶效率、空間、訪問特征確定；19一、函數(shù)依賴1.FD定義：若r中任意兩個(gè)元組t，s，如果tx=sx導(dǎo)致ty=sy ,則xy。2.FD的邏輯蘊(yùn)涵，F(xiàn)+ =XY| XY是從F用推理系統(tǒng)推出3.Armstrong推理系統(tǒng) 自反，若Y X, 則XY 增廣，若XY 則XZYZ 傳遞，若XY,YZ, 則XZ 推論： 合并，若XY ,XZ, 則XYZ 分解，若XYZ,