模式的分解精品課件

1、模式的分解2022/9/211第1頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四數(shù)據(jù)庫(kù)原理第六章第四節(jié)模式的分解2022/9/212第2頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四定義6.16 模式分解在對(duì)函數(shù)依賴的基本性質(zhì)了解之后，可以具體地來(lái)討論模式的分解了。定義6.16：關(guān)系模式R（U，F(xiàn)）的一個(gè)分解是指：其中定義6.17： Fi是指函數(shù)依賴集合XY XYF+XY是Ui的子集的一個(gè)覆蓋。2022/9/213第3頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四6.4.1 模式分解的三個(gè)定義對(duì)于每一個(gè)分解是多種多樣的，但是分解后的模式應(yīng)該與原模式是等價(jià)的。那么怎

2、么衡量分解的等價(jià)呢？從不同的角度可以分為三種：分解要具有“無(wú)損連接性”分解要“保持函數(shù)依賴”分解既要“保持函數(shù)依賴”，又要具有“無(wú)損連接性”2022/9/214第4頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四本小節(jié)要討論的內(nèi)容“無(wú)損連接性”和“保持函數(shù)依賴”的含義；對(duì)于這三種角度的分解可以達(dá)到的分離程度，即可以達(dá)到第幾范式；對(duì)于這幾種分離的分解算法；下面用一個(gè)實(shí)際分解的例子來(lái)引出本小節(jié)的內(nèi)容。2022/9/215第5頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四一個(gè)分解實(shí)例例4：一個(gè)關(guān)系模式R，其中U=Sno，Sdept，Mn，F(xiàn)=SnoSdept，Sdept Mn。如果

3、我們把它分解成：我們可以對(duì)照課本表6.5和分解的辦法，我們可以把表6.5分解成了三個(gè)關(guān)系：r1=S1，S2，S3，S4r2=D1，D2，D3r3=張五，李四，王一2022/9/216第6頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四一個(gè)分解實(shí)例（續(xù)）我們從r1，r2和r3這三個(gè)關(guān)系中已經(jīng)不能回答“某個(gè)學(xué)生在哪個(gè)系學(xué)習(xí)”了，顯然這樣的分解是失敗的。這是由于失去了關(guān)系的“無(wú)損連接性”。 無(wú)損連接性是指：分解后的關(guān)系通過(guò)自然連接運(yùn)算還能恢復(fù)原來(lái)的關(guān)系。 而我們把r1，r2和r3做自然連接（它們的笛卡爾積）后，我們得到的是一個(gè)具有4*4*4=64行的沒(méi)有實(shí)際意義的關(guān)系表。不能恢復(fù)表5.3所示

4、的含義了。2022/9/217第7頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四一個(gè)分解實(shí)例（續(xù)2）分解2：這種分解通過(guò)自然連接后是可以恢復(fù)原來(lái)的關(guān)系的，但是我們發(fā)現(xiàn)在原來(lái)的關(guān)系模式的F中有函數(shù)依賴SdeptMn，而在分解后的關(guān)系模式中不存在了。因此，關(guān)系模式的分解就要求具有“保持函數(shù)依賴”的特性才好。2022/9/218第8頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四一個(gè)分解實(shí)例（續(xù)3）我們來(lái)看一個(gè)比較好的分解：我們按這種模式分解后的關(guān)系通過(guò)自然連接是可以恢復(fù)到原來(lái)的關(guān)系的，同時(shí)，我們可以顯然的發(fā)現(xiàn)在原關(guān)系模式中的函數(shù)依賴在新的關(guān)系模式中都存在，因此，這次分解既保證了“

5、無(wú)損連接特性”，又“保持了函數(shù)依賴”。下面我們用形式化的概念來(lái)描述“無(wú)損連接性”和“保持函數(shù)依賴性”。2022/9/219第9頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四6.4.2.1 分解的“無(wú)損連接性”我們先來(lái)定義幾個(gè)符號(hào)：分解：其中r是R的一個(gè)關(guān)系。再定義： = （r）也就是說(shuō) 是r在各個(gè)模式分解上的投影的連接。2022/9/2110第10頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四 與r以及ri的關(guān)系其中：r是R的一個(gè)關(guān)系；ri= （r）是Ri的一個(gè)關(guān)系；則有：2022/9/2111第11頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四無(wú)損連接的定義定義

6、6.18 是R的一個(gè)分解，若對(duì)R的任何一個(gè)關(guān)系r均有r= （r）成立，則稱這個(gè)分解具有無(wú)損連接性。也就是說(shuō)：把分解后的關(guān)系做自然連接后可以恢復(fù)成原來(lái)的關(guān)系就可以了。那么用什么樣的數(shù)學(xué)法子來(lái)判斷呢？2022/9/2112第12頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四判斷無(wú)損連接的算法算法6.2 判斷一個(gè)分解的無(wú)損連接性 是RU，F(xiàn)的一個(gè)分解，U=A1，A2，An，F(xiàn)=FD1，F(xiàn)D2，F(xiàn)Dm，這里我們?cè)O(shè)F是一個(gè)極小依賴集，記FDi為XiAli。（1）建立一張n列k行的表。一列對(duì)應(yīng)一個(gè)屬性，一行對(duì)應(yīng)一個(gè)分解后的模式；在i行j列中的空白處，若屬性Aj屬于Ui，則填上aj，否則填上bij

7、。2022/9/2113第13頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四判斷無(wú)損連接的算法（續(xù)）（2）對(duì)于每一個(gè)FDi做如下的操作：取F中的函數(shù)依賴XY，如果表格中有兩行在X分量上相等，在Y分量上不相等，那么修改Y分量上的值，使這兩行在Y分量上也相等，修改時(shí)分兩種情況：如果Y的分量上有一個(gè)是aj，那么另外一個(gè)也修改正aj。如果Y的分量上沒(méi)有aj，那么下標(biāo)i較小的那個(gè)bij替換其他的符號(hào)。2022/9/2114第14頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四判斷無(wú)損連接的算法（續(xù)2） 對(duì)F中的m個(gè)FD逐一進(jìn)行一次這樣的處置，稱為對(duì)F的一次掃描。 （3）比較掃描前后表的

8、變化，若有則轉(zhuǎn)到第（2）步，否則算法終止。 如果發(fā)生循環(huán)，那么前次掃描至少應(yīng)使該表減少一個(gè)符號(hào)，表中符號(hào)有限，因此循環(huán)必然終止。定理6.4：若修改結(jié)束后的表格中有一行全是a，即a1，a2，an，那么該模式分解是無(wú)損連接分解。 下面我們用兩個(gè)例子來(lái)解釋一下。2022/9/2115第15頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四判斷無(wú)損連接分解實(shí)例1例5：R，U=A，B，C，D，E，F(xiàn)=ABC，C D，D E，R的一個(gè)分解為R1（A，B，C），R2（C，D），R3（D，E）。解：我們來(lái)看算法的動(dòng)畫演示。2022/9/2116第16頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期

9、四例5 第（1）步構(gòu)造初始表ABCDEA,B,Ca1a2a3b14b15C,Db21b22a3a4b25D,Eb31b32b33a4a5UiAA,B,C因此此處填a1D不屬于A,B,C因此此處填b142022/9/2117第17頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四例5 第（2）步修改表ABCDEA,B,Ca1a2a3b14b15C,Db21b22a3a4b25D,Eb31b32b33a4a5對(duì)于ABC來(lái)說(shuō)，在AB屬性組上，在這三行中沒(méi)有任何兩行是相同的，因此不用修改C的值對(duì)于CD來(lái)說(shuō)，在C屬性組上，第1，2行的值相等（a3），因此要修改D的值，又因?yàn)樵贒屬性上存在a4，因此

10、把b14修改為a4a4對(duì)于DE來(lái)說(shuō)，在D屬性組上，第1，2，3行的值相等，因此要修改E的值，又因?yàn)樵贓屬性上存在a5，因此把b15，b25修改為a5a5a52022/9/2118第18頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四一個(gè)很有用的判定準(zhǔn)則(begin)當(dāng)關(guān)系模式R分解成兩個(gè)關(guān)系模式R1，R2時(shí)有下面的判定準(zhǔn)則。定理6.5 R的一個(gè)分解R1,R2具有無(wú)損連接性的充分必要條件是：U1U2U1-U2F+或U1U2U2-U1F+。也就是說(shuō)：分解后的兩個(gè)關(guān)系模式的公共屬性能函數(shù)確定U1或U2中的其他屬性，這樣的分解就是無(wú)損連接的。2022/9/2119第19頁(yè)，共33頁(yè)，2022年

11、，5月20日，6點(diǎn)25分，星期四6.4.2.2 保持函數(shù)依賴性保持函數(shù)依賴的判定相對(duì)簡(jiǎn)單。定義6.19 若 ，則R的分解保持函數(shù)依賴。也就是說(shuō)，各個(gè)分解后的模式中的函數(shù)依賴合并后可以與原模式的函數(shù)依賴等價(jià)。2022/9/2120第20頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四6.4.3 模式分解的算法在模式分解時(shí)：保持函數(shù)依賴時(shí)：模式分解一定可以達(dá)到3NF，不一定達(dá)到BCNF。既保持函數(shù)依賴，又保證無(wú)損連接：模式分解可以達(dá)到3NF，不一定達(dá)到BCNF。只要求保證無(wú)損連接性：模式分解一定可以達(dá)到4NF。2022/9/2121第21頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星

12、期四保持函數(shù)依賴轉(zhuǎn)換為3NF算法輸入：關(guān)系模式R輸出：R的一個(gè)分解 ，其中的每一個(gè)分解都是3NF的，且保持函數(shù)依賴。對(duì)R中的函數(shù)依賴做“極小化處理”，處理后的函數(shù)依賴集仍記為F，令 。找出不在F中的屬性，并把這些屬性構(gòu)成一個(gè)關(guān)系模式。把去掉這些屬性的剩余屬性仍記為U。若有XAF，并且XA=U，則 算法終止。否則，對(duì)F中的每個(gè)函數(shù)依賴都按具有相同左部的原則分組，即XY1， XY2， ，XYk，構(gòu)成關(guān)系模式R,且函數(shù)依賴集為XY1， XY2， ，XYk，并令 ，輸出 。2022/9/2122第22頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四既無(wú)損連接性又保持函數(shù)依賴的分解算法算法6.4

13、:（1） 設(shè)X是R的碼，R已由算法6.3分解為R1，R2，Rk，并令（2）若有某個(gè)Ui，X是Ui的子集，那就將R*從 中去掉。（3） 就是所求的分解。下面我們給出一個(gè)例子。2022/9/2123第23頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四模式分解的實(shí)例引例：設(shè)關(guān)系模式R，其中U=A，B，C，D，E，P，F(xiàn)=AB，AE P，CD A，CE D，BC D，此時(shí)F已經(jīng)是極小函數(shù)依賴集，我們先用算法6.3分解該模式：第一步：先作保持函數(shù)依賴的模式分解；（1）對(duì)F做極小化處理，可以省略。（2）去掉F中未出現(xiàn)的屬性，未找到。（3）在F中找X A，且XA=U，未發(fā)現(xiàn)。（4）對(duì)F中的函數(shù)依賴

14、按相同左部分組，并分解成一個(gè)模式合并到結(jié)果集中。2022/9/2124第24頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四模式分解的實(shí)例（續(xù)）我們?cè)贔中找不到相同的左部，因此對(duì)每個(gè)函數(shù)依賴進(jìn)行模式分解，如下所示。分解后的關(guān)系模式有： R1, R2, R3, R4, R52022/9/2125第25頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四模式分解的實(shí)例（續(xù)2）第二步：轉(zhuǎn)換為既保持函數(shù)依賴又具有無(wú)損連接的模式分解。（1）X=C，E是R的一個(gè)候選碼，此時(shí)Fx=CED，并令（2）我們?cè)谏弦徊降哪Ｊ椒纸庵邪l(fā)現(xiàn)U4= C,E,D,X是其子集，那么我們把 從 去掉。（3）顯然上一步

15、的分解也是這一步的解。 2022/9/2126第26頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四6.4.3.3 轉(zhuǎn)換為4NF的算法我們知道若一個(gè)關(guān)系模式中存在非平凡的非函數(shù)依賴的多值依賴，那么該關(guān)系的冗余是很大的，而且存在插入、修改和刪除異常。那么我們就需要轉(zhuǎn)換為4NF。我們不希望存在非平凡的非函數(shù)依賴的多值依賴，因此我們就要對(duì)存在這種多值依賴的屬性組進(jìn)行分解。這是通過(guò)定理6.6來(lái)實(shí)現(xiàn)的。2022/9/2127第27頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四定理6.6 多值依賴的分解定理6.6：關(guān)系模式R中，D為R中函數(shù)依賴FD和多值依賴MVD的集合。則X Y成立的充

16、要條件是R的分解具有無(wú)損連接性，其中Z=U-X-Y。2022/9/2128第28頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四達(dá)到4NF具有無(wú)損連接性分解算法分兩步：（1）先把原關(guān)系模式R按前述算法分解到BCNF。（2）對(duì)分解后的各個(gè)關(guān)系模式Ri（Ui，Di）若他不屬于4NF，那么按定理6.6分解。這是由于用定理6.6分解后的子模式只具有平凡的函數(shù)依賴了。2022/9/2129第29頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四本章小結(jié)關(guān)系模式的規(guī)范化，其基本思想： 2022/9/2130第30頁(yè)，共33頁(yè)，2022年，5月20日，6點(diǎn)25分，星期四小結(jié)(續(xù))若要求分解具有無(wú)損連接性，那么模式分解一定能夠達(dá)到4NF若要求分解保持函數(shù)依賴，那么模式分解一定能夠達(dá)到3NF，但不一定能夠達(dá)到BCNF若要求分解既具有無(wú)損連接性，又保