模式分解精品課件

1、模式分解第1頁，共67頁，2022年，5月20日，6點25分，星期四最小依賴集第2頁，共67頁，2022年，5月20日，6點25分，星期四1）考查AB，去掉它，計算A+=AC，不包含B，不能去掉2）考查 B A，去掉它，計算BB C A，包含A，可去掉它3）考查 B C，去掉它，計算BB，不包含C，不能去掉4）考查A C，去掉它，計算AA B C，包含C，可去掉它5）考查 C A，去掉它，計算CC，不包含A，不能去掉1 2 3 4 5第3頁，共67頁，2022年，5月20日，6點25分，星期四求解關(guān)系模式的候選碼屬性分類L類：只出現(xiàn)在函數(shù)依賴的左邊的屬性R類：只出現(xiàn)在函數(shù)依賴的右邊的屬性N類：

2、在函數(shù)依賴的兩邊均未出現(xiàn)的屬性LR類：出現(xiàn)在函數(shù)依賴的兩邊的屬性第4頁，共67頁，2022年，5月20日，6點25分，星期四求解關(guān)系模式的候選碼對于給定的關(guān)系模式R及其函數(shù)依賴集F如果X是L或N類屬性，則X必為R的任一候選碼的成員如果X是R類屬性，則X必不在任何候選碼中如果X是L和N類組成的屬性組，且X+包含了全部屬性，則X是R的唯一候選碼第5頁，共67頁，2022年，5月20日，6點25分，星期四前例例：關(guān)系模式CTHRSG, 若最小依賴集為F=C T, HR C,CS G,HS R,HT R, 候選關(guān)鍵字為HS？解： L、N類屬性為HS，LR屬性為CTR HS+=HS RCTG，包含全部屬

3、性，所以為唯一候選碼第6頁，共67頁，2022年，5月20日，6點25分，星期四函數(shù)依賴圖FDG用有向圖表示的函數(shù)依賴，如XY即X Y第7頁，共67頁，2022年，5月20日，6點25分，星期四L或N類屬性有E和C, LR類屬性ADB，令X=EC,(EC)+=U,EC為R的唯一候選碼。對左邊為單屬性的函數(shù)依賴集求所有候選碼(1) 求F的最小依賴集F(2) 作出函數(shù)依賴圖FDG(3) 從FDG圖中找出無入邊的屬性集X(4) 察看FDG圖中有無回路，若無，則輸出X并結(jié) 束,否則進(jìn)行下一步(5) 從各獨立回路中各取一個結(jié)點的屬性與X組成一個候選碼，重復(fù)取得所有可能的組合，即R的全部候選碼第8頁，共6

4、7頁，2022年，5月20日，6點25分，星期四IBOQSD第9頁，共67頁，2022年，5月20日，6點25分，星期四ZWYXSDIBOQ第10頁，共67頁，2022年，5月20日，6點25分，星期四算法：對左邊為多屬性的函數(shù)依賴集求所有候選碼 (1) 將R所有屬性分為L,R,N,LR四類，并令X代表L,N兩類，令Y代表LR類。(2) 求X+，若X+包含R全部屬性，則X即為R的唯一候選碼，結(jié)束，否則轉(zhuǎn)下一步。(3) 在Y中取一屬性A，求(XA)+,若它包含R的全部屬性，則轉(zhuǎn)下一步，否則換一個屬性重試，直至試完所有Y中的屬性。(4) 若已找出所有候選碼，則結(jié)束，否則在Y中依次取兩個、三個、，求

5、它們的屬性閉包，直至其閉包包含R的全部屬性。屬于N-P完全問題 (一類直觀上難解可又找不出方法來證明它們的確難解的計算問題)多屬性下求解候選碼的充分條件第11頁，共67頁，2022年，5月20日，6點25分，星期四第六章 關(guān)系數(shù)據(jù)理論6.1 數(shù)據(jù)依賴6.2 規(guī)范化6.3 數(shù)據(jù)依賴的公理系統(tǒng)6.4 模式的分解第12頁，共67頁，2022年，5月20日，6點25分，星期四6.4 模式的分解把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的。只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義。第13頁，共67頁，2022年，5月20日，6點25分，星期四關(guān)系模式分解的標(biāo)準(zhǔn)三

6、種模式分解的等價定義 分解具有無損連接性 分解要保持函數(shù)依賴 分解既要保持函數(shù)依賴，又要具有無損連接性第14頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）定義6.16 關(guān)系模式R的一個分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影。定義6.17 函數(shù)依賴集合XY | XY F+XY Ui 的一個覆蓋 Fi 叫作 F 在屬性 Ui 上的投影第15頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）定義6.16 關(guān)系模式R的一個分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F(xiàn)i

7、為 F在 Ui 上的投影。定義6.17 函數(shù)依賴集合XY | XY F+XY Ui 的一個覆蓋 Fi 叫作 F 在屬性 Ui 上的投影第16頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）例: SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc SL2NF 存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題分解方法可以有多種 。第17頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）SL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS

8、B 95005 PH B 第18頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）1. SL分解為下面三個關(guān)系模式： SN(Sno) SD(Sdept) SO(Sloc)第19頁，共67頁，2022年，5月20日，6點25分，星期四分解后的關(guān)系為： SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 PH 95005 第20頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）分解后的數(shù)據(jù)庫丟失了許多信息 例如無法查詢95001學(xué)生所在系或所在宿舍。 如果分解后的關(guān)系可以通過自然連

9、接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息第21頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）2. SL分解為下面二個關(guān)系模式： NL(Sno, Sloc) DL(Sdept, Sloc)分解后的關(guān)系為： NL DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B 第22頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）NL DL Sno Sloc Sdept 95001 A CS 95002 B IS 95002 B PH 950

10、03 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH 第23頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）NLDL比原來的SL關(guān)系多了3個元組 無法知道95002、95004、95005 究竟是哪個系的學(xué)生元組增加了，信息丟失了第24頁，共67頁，2022年，5月20日，6點25分，星期四第三種分解方法3. 將SL分解為下面二個關(guān)系模式： ND(Sno, Sdept) NL(Sno, Sloc) 分解后的關(guān)系為： 第25頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）ND NL Sno Sdep

11、t Sno Sloc 95001 CS 95001 A 95002 IS 95002 B 95003 MA 95003 C 95004 IS 95004 B 95005 PH 95005 B 第26頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)） ND NL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 與SL關(guān)系一樣，因此沒有丟失信息。第27頁，共67頁，2022年，5月20日，6點25分，星期四具有無損連接性的模式分解關(guān)系模式R的一個分解 = R1，R2， ，Rn,若R與R

12、1、R2、Rn自然連接的結(jié)果相等，則稱關(guān)系,模式R的這個分解具有無損連接性（Lossless join）具有無損連接性的分解保證不丟失信息無損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題第28頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)） 第三種分解方法具有無損連接性 問題: 這種分解方法沒有保持原關(guān)系中的函數(shù)依賴 SL中的函數(shù)依賴SdeptSloc， 沒有投影到關(guān)系模式ND、NL上 第29頁，共67頁，2022年，5月20日，6點25分，星期四保持函數(shù)依賴的模式分解設(shè)關(guān)系模式R被分解為若干個關(guān)系模式 R1，R2，Rn （其中U=U1U2Un，且不存

13、在Ui Uj，F(xiàn)i為F在Ui上的投影），若F所邏輯蘊含的函數(shù)依賴一定也由分解得到的某個關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊含，則稱關(guān)系模式R的這個分解是保持函數(shù)依賴的（Preserve dependency）。第30頁，共67頁，2022年，5月20日，6點25分，星期四保持函數(shù)依賴的模式分解第31頁，共67頁，2022年，5月20日，6點25分，星期四例 子R(A,B,C), F=AB, C B分解1=(A,B,AB), (A,C)分解2=(A,B, AB), (B,C, C B)計算分解1,2中3個模式的閉包FAB：A+=AB,B+=B,AB+=AB, 則對AB的分解有函數(shù)依賴ABAC：A+=

14、A,C+=C,AC+=AC, 則對AC的分解沒有函數(shù)依賴BC：B+=B,C+=CB,BC+=BC, 則對BC的分解只有函數(shù)依賴CB分解1：只有AB，顯然，分解1不具有依賴保持性分解2：保留了所有函數(shù)依賴，具有依賴保持性分析兩種分解的依賴保持性？第32頁，共67頁，2022年，5月20日，6點25分，星期四第四種分解方法SL（Sno， Sdept， Sloc） F= SnoSdept,SdeptSloc,SnoSloc將SL分解為下面二個關(guān)系模式： ND(Sno, Sdept) DL(Sdept, Sloc) 這種分解方法就保持了函數(shù)依賴。 第33頁，共67頁，2022年，5月20日，6點25分

15、，星期四模式的分解（續(xù)）如果一個分解具有無損連接性，則它能夠保證不丟失信息。如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨立的標(biāo)準(zhǔn)。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。第34頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）第一種分解方法既不具有無損連接性，也未保持函 數(shù)依賴，它不是原關(guān)系模式的一個等價分解 SN(Sno)， SD(Sdept)， SO(Sloc)第二種分解方法保持了函數(shù)依賴，但不具有無損連 接性。 NL(Sno, Sloc)， DL(Sd

16、ept, Sloc)SL（Sno， Sdept， Sloc）F= SnoSdept,SdeptSloc,SnoSloc第35頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）第三種分解方法具有無損連接性，但未持函數(shù)依賴 ND(Sno, Sdept)， NL(Sno, Sloc)第四種分解方法既具有無損連接性，又保持了函數(shù)依賴 ND(Sno, Sdept)， DL(Sdept, Sloc)SL（Sno， Sdept， Sloc）F= SnoSdept,SdeptSloc,SnoSloc第36頁，共67頁，2022年，5月20日，6點25分，星期四分解算法算法6.2 判別一個

17、分解的無損連接性算法6.3 （合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解。算法6.4 轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解算法6.5 轉(zhuǎn)換為BCNF的無損連接分解（分解法）算法6.6 達(dá)到4NF的具有無損連接性的分解P196 圖5 .11第37頁，共67頁，2022年，5月20日，6點25分，星期四判別一個分解的無損連接性算法6.2(1)構(gòu)造初始表：構(gòu)造一個k行n列的初始表，其中每列對應(yīng)于R的一個屬性，每行用于表示分解后的一個模式組成。 如果屬性Aj屬于關(guān)系模式Ri, 則在表的第一i行第j列置符號aj，否則置符號bij 。(2)根據(jù)F中的函數(shù)依賴修改表內(nèi)容： 考察F中的每個函數(shù)依賴XY

18、,在屬性組X所在的那些列上尋找具有相同符號的行，如果找到這樣的兩行或更多的行， 則修改這些行，則使這些行上屬性組Y所在的列上元素相同。 修改規(guī)則是：如果y所在的要修改的行中有一個為aj， 則這些元素均變成aj；否則改動為bmj（其中m為這些行的最小行號）。第38頁，共67頁，2022年，5月20日，6點25分，星期四判別一個分解的無損連接性注意：若某個bij被改動，則該列中凡是與bij相同的符號均做相同的改動。 循環(huán)地對F中的函數(shù)依賴進(jìn)行逐個處理，直到發(fā)現(xiàn)表中有一行 變?yōu)閍1,a2,an或不能再被修改為止。 (3)判斷分解是否為無損聯(lián)接： 如果通過修改，發(fā)現(xiàn)表中有一行變a1,a2, an, 則

19、分解是無損聯(lián)接的，否則分解不具有無損聯(lián)接性。第39頁，共67頁，2022年，5月20日，6點25分，星期四ABCDEa1a2a3b14b15b21b22a3a4b25b31b32b33a4a5ABCDEa1a2a3a4a5b21b22a3a4a5b31b32b33a4a5初始表：最后結(jié)果：R1R2R3R1R2R3122例子：判斷無損連接性第40頁，共67頁，2022年，5月20日，6點25分，星期四ABCDEa1a2a3a3a4a4a5ABCDEa1a2a3a4a5a3a4a5a4a5初始表：最后結(jié)果：R1R2R3R1R2R3122簡易方法：只畫關(guān)注數(shù)據(jù)第41頁，共67頁，2022年，5月20

20、日，6點25分，星期四判別一個分解的無損連接性已知關(guān)系模式R(ABCDE)及函數(shù)依賴集F=AC,BC,CD,DEC,CEA 驗證分解=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)是否為無損聯(lián)接。 第42頁，共67頁，2022年，5月20日，6點25分，星期四通過修改發(fā)現(xiàn)表中第三行元素變?yōu)閍1,a2,an,分解是無損聯(lián)接。 第43頁，共67頁，2022年，5月20日，6點25分，星期四判別一個分解的無損連接性定理：如果R的分解為r =R1，R2，F(xiàn)為R所滿足的函數(shù)依賴集合，分解r具有無損聯(lián)接性的充要條件是：R1 R2 （R1R2）F+或R1 R2 （R2R1） F+ 第

21、44頁，共67頁，2022年，5月20日，6點25分，星期四模式的分解（續(xù)）定義6.16 關(guān)系模式R的一個分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，F(xiàn)i 為 F在 Ui 上的投影。定義6.17 函數(shù)依賴集合XY | XY F+XY Ui 的一個覆蓋 Fi 叫作 F 在屬性 Ui 上的投影第45頁，共67頁，2022年，5月20日，6點25分，星期四判別一個分解的無損連接性關(guān)系模式R(A,B,C,D) 函數(shù)依賴集F=AB,CD,=R1(AB)，R2(CD)， 求R1,R2 ,并檢驗分解的無損聯(lián)接性和分解的函數(shù)依賴保持性。 解：F1=R1(F)=AB, F2=R2(F)=

22、CD，分解為 R1(AB,AB),R2(CD,CD) U1U2=ABCD=, U1-U2=AB, U2-U1=CD, AB F+, CD F+, 所以不是無損分解。 第46頁，共67頁，2022年，5月20日，6點25分，星期四判別一個分解的無損連接性例：設(shè)R=ABC，F(xiàn)=AB，則1=R1(AB)， R2(AC)和 2=R1(AB)， R3(BC)是否具有無損聯(lián)接性 。第47頁，共67頁，2022年，5月20日，6點25分，星期四判別一個分解的無損連接性例 將R=(ABCD,AB,BC,BD,CA)分解為關(guān)于U1=AB，U2=ACD兩個關(guān)系，求R1、R2， 并檢驗分解的無損聯(lián)接性和分解的函數(shù)依

23、賴保持性。 解：F1=R1(F)=AB,BA, F2=R2(F)=AC,CA,AD R1=(AB,AB,BA)R2=(ACD,AC,CA,AD) U1U2=ABACD=A,U1-U2=AB-ACD=B,ABF+,所以是無損連接分解； 第48頁，共67頁，2022年，5月20日，6點25分，星期四（F1UF2)+=AB,BA,AC,CA,AD +AB,BC,BD,CA +=F+, 所以是函數(shù)依賴保持性。第49頁，共67頁，2022年，5月20日，6點25分，星期四練習(xí)：已知關(guān)系模式R(CITY,ST,ZIP), F=(CITY,ST)ZIP,ZIPCITY， 以及R上的一個分解=R1, R2,

24、R1 =ST,ZIP, R2 =CITY,ZIP， 求R1,R2 ,并檢驗分解的無損聯(lián)接性和分解的函數(shù)依賴保持性。 答案 R1=(ST,ZIP,) R2=(CITY,ZIP,ZIPCITY)， 是無損分解,但不具有函數(shù)依賴保持性。 第50頁，共67頁，2022年，5月20日，6點25分，星期四(1)極小化處理F(2)如果R中的某些屬性在F的所有依賴的左邊和右邊都不出現(xiàn)，那么這些屬性可以從R中分出去，單獨構(gòu)成一個關(guān)系模式。 (3)如果F中有一個依賴XA有XA=R，則=R，轉(zhuǎn)(4) (4)對于F中每一個XA，構(gòu)成一個關(guān)系模式XA，如果F有有XA1，XA2.XAn,則可以用模式XA1A2.An代替n

25、個模式XA1,XA2.XAn; (5)分解結(jié)束。 算法6.3分解成3NF模式集（合成法）保持函數(shù)依賴一般情況下，只要用F中所有函數(shù)依賴左右兩邊的屬性組成各個關(guān)系子模式，函數(shù)依賴中不涉及的屬性組成一個關(guān)系。第51頁，共67頁，2022年，5月20日，6點25分，星期四具有依賴保持性的3NF分解例子例1：SL(Sno, Sdept, Sloc)F= SnoSdept, SdeptSloc, SnoSlocF=SnoSdept, SdeptSloc，因為去掉SnoSloc，Sno+=Sno Sdept Sloc, 包含Sloc, 則可去掉具有依賴保持性的3NF分解為Sno ，Sdept和Sdept

26、，Sloc例2：關(guān)系模式CTHRSG, 若最小依賴集為F=C T, HR C,CS G,HS R,HT R具有依賴保持性的3NF分解為CT,CHR,CSG,HSR,HTR第52頁，共67頁，2022年，5月20日，6點25分，星期四分解成3NF模式（保持函數(shù)依賴又無損連接）使用合成法將RU,F分解為= 設(shè)X是R的碼，令=R*X,FX 如有某個Ui，使得：X Ui，則從中去掉R*X,FX 即所求 第53頁，共67頁，2022年，5月20日，6點25分，星期四例 子例：關(guān)系模式CTHRSG, 若最小依賴集為F=C T, HR C,CS G,HS R,HT R, 候選關(guān)鍵字為HS如前例，具有依賴保持

27、性的3NF分解為CT,CHR,CSG,HSR,HTR則具有無損連接和依賴保持性的3NF分解為CT,CHR,CSG,HSR,HTR, HSHS和HSR重復(fù)，則為CT,CHR,CSG,HSR,HTR 第54頁，共67頁，2022年，5月20日，6點25分，星期四1、設(shè)U=A，B，C，D，E，F(xiàn) F=ABCDE,DEABC,ABD,EC,DEF 求最小依賴集，并使用算法分解到3NF解： F=ABCD，ABCE，DEA，DEB，DEC， ABD，EC，DEF ABD， ABCD 去掉ABCD 又 EC， DEC 去掉DEC Fm=ABCE,ABD,EC,DEA,DEB,DEF 其碼：ABC，ABE，D

28、E 按算法1得到： =R1ABCE，ABCE，R2（ABD，ABD）， R3，R4例 題第55頁，共67頁，2022年，5月20日，6點25分，星期四例 題其中，(1)R3的屬性包含在R1關(guān)系的屬性中，去掉R3 R2的屬性包含在R4關(guān)系的屬性中，去掉R2；=R1ABCE，ABCE，R2（ABD，ABD）， R3，R4 (2)由于R*ABC，F(xiàn)ABC，R*DE，F(xiàn)DE， R*ABE，F(xiàn)ABE皆是中的某個Ui的子集，因此全部去掉。最終的分解為：=R1ABCE，ABCE，EC，R2故上面的分解既保持函數(shù)依賴又無損連接。 第56頁，共67頁，2022年，5月20日，6點25分，星期四分解成BCNF模式

29、集的算法無損聯(lián)接分解成BCNF模式集的算法： (1)置初值=R; (2)如果中所有關(guān)系模式都是BCNF，則轉(zhuǎn)(4); (3)如果中有一個關(guān)系模式S不是BCNF，則S中必能找到一個函數(shù)依賴集XA有X不是S的鍵，且A不屬于X，設(shè)S1=XA，S2=S-A，用分解S1,S2代替S，轉(zhuǎn)(2)； (4)分解結(jié)束。輸出。Notice:重點在于(3)步，判斷哪個關(guān)系不是BCNF，并找到X和A。第57頁，共67頁，2022年，5月20日，6點25分，星期四分成BCNF設(shè)關(guān)系模式R，R的函數(shù)依賴關(guān)系F=AD，ED，DB，BCD，DCA請將該關(guān)系分解到BCNF。 解：找到候選鍵： ED ECDC .(1)DCA E

30、CA .(2)DB DCBCB ECB .(3) 由(1)(2)(3) 得ECABD EC為鍵，這里關(guān)系鍵僅有一個(在右邊有E和C未出現(xiàn)鍵中必包含EC為鍵) 主屬性EC, 非主屬性A,B,D 。第58頁，共67頁，2022年，5月20日，6點25分，星期四分成BCNF（無損） 直接分解到BCNF AD，A BCE R1(AD)，R2(ABCE) 在R2中 EB 分解：R21(EB)，R22(EAC) R分解為R1(AD)，R2(EB)，R3(EAC) 分解不是唯一的。第59頁，共67頁，2022年，5月20日，6點25分，星期四分解算法解P196 圖5 .11若要求分解具有無損連接性，那么模式分解一定能夠達(dá)到4NF。若要求分解保持函數(shù)依賴，那么模式分解一定能夠達(dá)到3NF，但不一定能夠達(dá)到BCNF。若要求分解既具有無損連接性，又保持函數(shù)依賴，則模式分解一定能夠達(dá)到3NF，但不一定能夠達(dá)到BCNF。第60頁，共67頁，2022年，5月20日，6點25分，星期四泛關(guān)系假設(shè) “假設(shè)已知一個模式S，它僅由單個關(guān)系模式組成，問題是要設(shè)計一個模式SD，它與S等價，但在某些方面更好一些”。從一個關(guān)系模式出發(fā)，而不是從一組關(guān)系模式出發(fā)實行分解?！暗葍r”的定義也是一組關(guān)系模式與一個關(guān)系模式的“等價”。第61頁，共67頁，2022年，5月20日，6點25分，星期四小結(jié)(續(xù)