第六章關(guān)系數(shù)據(jù)理論2022優(yōu)秀文檔

6.3數(shù)據(jù)依賴的公理系統(tǒng)邏輯蘊(yùn)含 定義6.11對于滿足一組函數(shù)依賴F的關(guān)系模式R<U，F(xiàn)>，其任何一個關(guān)系r，若函數(shù)依賴X→Y都成立,則稱

F邏輯蘊(yùn)含X→Y1Armstrong公理系統(tǒng)一套推理規(guī)則，是模式分解算法的理論基礎(chǔ)用途求給定關(guān)系模式的碼從一組函數(shù)依賴求得蘊(yùn)含的函數(shù)依賴21.Armstrong公理系統(tǒng)對關(guān)系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：Al.自反律（Reflexivity）：若Y

X

U，則X→Y為F所蘊(yùn)含。A2.增廣律（Augmentation）：若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。A3.傳遞律（Transitivity）：若X→Y及Y→Z為F所蘊(yùn)含，則X→Z為F所蘊(yùn)含。3（l）自反律:若Y

X

U，則X→Y為F所蘊(yùn)含證:設(shè)Y

X

U

對R<U，F(xiàn)>的任一關(guān)系r中的任意兩個元組t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得證4(2)增廣律:若X→Y為F所蘊(yùn)含，且Z

U，則XZ→YZ為F所蘊(yùn)含。證：設(shè)X→Y為F所蘊(yùn)含，且Z

U。設(shè)R<U，F(xiàn)>的任一關(guān)系r中任意的兩個元組t，s；若t[XZ]=s[XZ]，則有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ為F所蘊(yùn)含.增廣律得證。5例:SL（Sno，Sdept，Sloc）────────────────────────────────若t[X]=s[X]，由于YX，有t[y]=s[y]，被決定因素列沒有a，則全改為b;分解三：ND(Sno,Sdept)，NL(Sno,Sloc)95001CSA判斷方法：第一步：造記錄表；關(guān)于模式分解無損連接性的判斷算法第三種分解方法具有無損連接性具有無損連接性的分解保證不丟失信息第二步：改記錄表并判斷。第三種分解方法具有無損連接性⒊分解既要保持函數(shù)依賴，又要具有無損連接性(2)增廣律:若X→Y為F所蘊(yùn)含，且ZU，則XZ→YZ為F所蘊(yùn)含。(3)傳遞律：若X→Y及Y→Z為F所蘊(yùn)含，則

X→Z為F所蘊(yùn)含。證：設(shè)X→Y及Y→Z為F所蘊(yùn)含。對R<U，F(xiàn)>的任一關(guān)系r中的任意兩個元組t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z為F所蘊(yùn)含.傳遞律得證。6第六章關(guān)系數(shù)據(jù)理論6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解76.4模式的分解把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義8關(guān)系模式分解的標(biāo)準(zhǔn)什么是“等價”？三種模式分解“等價”的定義⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性96.4模式的分解定義6.16關(guān)系模式R<U,F>的一個分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}U=U1∪U2∪…∪Un，且不存在Ui

Uj，F(xiàn)i為F在Ui上的投影106.4模式的分解例:SL（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題分解方法可以有多種115.4模式的分解SL──────────────────Sno Sdept Sloc──────────────────95001CSA95002ISB95003MAC95004ISB95005 PH B──────────────────125.4模式的分解1.SL分解為下面三個關(guān)系模式：SN(Sno)SD(Sdept)SO(Sloc)13分解后的關(guān)系為：

SN──────SD──────SO──────SnoSdeptSloc

──────────────────95001CSA95002ISB95003MAC95004PH─────95005────────────146.4模式的分解 分解后的數(shù)據(jù)庫丟失了許多信息例如無法查詢95001學(xué)生所在系或所在宿舍。

如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息．156.4模式的分解2.SL分解為下面二個關(guān)系模式：NL(Sno,Sloc)DL(Sdept,Sloc)分解后的關(guān)系為：NL────────────DL────────────SnoSlocSdeptSloc────────────────────────95001A CSA95002B ISB95003C MAC95004B PHB95005B──────────────────────166.4模式的分解NLDL─────────────SnoSlocSdept─────────────95001ACS

95002BIS95002BPH

95003CMA

95004BIS95004BPH

95005BIS95005BPH

NLDL比原來的SL關(guān)系多了3個元組無法知道95002、95004、95005究竟是哪個系的學(xué)生

元組增加了，信息丟失了176.4模式的分解3.將SL分解為下面二個關(guān)系模式：ND(Sno,Sdept)NL(Sno,Sloc)分解后的關(guān)系為：

186.4模式的分解ND────────────NL──────────SnoSdeptSnoSloc

──────────────────────95001CS95001A95002IS95002B95003MA95003C95004IS95004B95005PH95005B

───────────────────────196.4模式的分解NDNL──────────────SnoSdeptSloc──────────────

95001CSA95002ISB95003MAC95004CSA95005PHB──────────────與SL關(guān)系一樣，因此沒有丟失信息20具有無損連接性的模式分解關(guān)系模式R<U,F>的一個分解ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}若R與R1、R2、…、Rn自然連接的結(jié)果相等，則稱關(guān)系模式R的這個分解ρ具有無損連接性（Losslessjoin）具有無損連接性的分解保證不丟失信息無損連接性不一定能解決插入異常、刪除異常、修改復(fù)雜、數(shù)據(jù)冗余等問題216.4模式的分解

第三種分解方法具有無損連接性

問題:這種分解方法沒有保持原關(guān)系中的函數(shù)依賴SL中的函數(shù)依賴Sdept→Sloc沒有投影到關(guān)系模式ND、NL上

22保持函數(shù)依賴的模式分解設(shè)關(guān)系模式R<U,F>被分解為若干個關(guān)系模式R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>（其中U=U1∪U2∪…∪Un，且不存在UiUj，F(xiàn)i為F在Ui上的投影），若F所邏輯蘊(yùn)含的函數(shù)依賴一定也由分解得到的某個關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊(yùn)含，則稱關(guān)系模式R的這個分解是保持函數(shù)依賴的（Preservedependency）。23第四種分解方法將SL分解為下面二個關(guān)系模式：ND(Sno,Sdept)DL(Sdept,Sloc)這種分解方法就保持了函數(shù)依賴。246.4模式的分解如果一個分解具有無損連接性，則它能夠保證不丟失信息。如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨(dú)立的標(biāo)準(zhǔn)。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依賴的分解也不一定具有無損連接性。256.4模式的分解第一種分解方法既不具有無損連接性，也未保持函數(shù)依賴，它不是原關(guān)系模式的一個等價分解.

第三種分解方法具有無損連接性，但未持函數(shù)依賴.

第四種分解方法既具有無損連接性，又保持了函數(shù)依賴.26分解算法算法6.2判別一個分解的無損連接性算法6.3（合成法）轉(zhuǎn)換為3NF的保持函數(shù)依賴的分解。算法6.4轉(zhuǎn)換為3NF既有無損連接性又保持函數(shù)依賴的分解算法6.5轉(zhuǎn)換為BCNF的無損連接分解（分解法）算法6.6達(dá)到4NF的具有無損連接性的分解27設(shè)關(guān)系模式R=A1,…,An，R上成立的FD集F，R的一個分解p={R1,…,Rk}。無損連接分解的判斷步驟如下：(1)構(gòu)造一張k行n列的表格，每列對應(yīng)一個屬性Aj(1≤j≤n)，每行對應(yīng)一個模式Ri(1≤i≤k)。如果Aj在Ri中，那么在表格的第i行第j列處填上符號aj，否則填上符號bij。

關(guān)于模式分解無損連接性的判斷算法28

(2)把表格看成模式R的一個關(guān)系，反復(fù)檢查F中每個FD在表格中是否成立，若不成立，則修改表格中的元素。修改方法如下：對于F中一個FD：X→Y，如果表格中有兩行在X分量上相等，在Y分量上不相等，那么把這兩行在Y分量上改成相等。如果Y的分量中有一個是aj，那么另一個也改成aj;如果沒有aj，那么用其中的一個bij替換另一個(盡量把ij改成較小的數(shù)，亦即取i值較小的那個)。

關(guān)于模式分解無損連接性的判斷算法29(3)若在修改的過程中，發(fā)現(xiàn)表格中有一行全是a，即a1,a2,…,an，那么可立即斷定p相對于F是無損連接分解，此時不必再繼續(xù)修改。若經(jīng)過多次修改直到表格不能修改之后，發(fā)現(xiàn)表格中不存在有一行全是a的情況，那么分解就是有損的。注意，這里有個循環(huán)反復(fù)修改的過程，因?yàn)橐淮涡薷目赡軐?dǎo)致表格能繼續(xù)修改。關(guān)于模式分解無損連接性的判斷算法30關(guān)于模式分解無損連接性的判斷算法判斷方法：第一步：造記錄表；第二步：改記錄表并判斷。

例:SL（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}分解一：SN(Sno)，SD(Sdept)，SO(Sloc)分解二：NL(Sno,Sloc)，DL(Sdept,Sloc)分解三：ND(Sno,Sdept)，NL(Sno,Sloc)分解四：ND(Sno,Sdept)，DL(Sdept,Sloc)31關(guān)于模式分解無損連接性的判斷算法例:SL（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SnoSdeptSlocNDa1a2b13NLa1b22a3第一步：造記錄表行表示原始表的各屬性；列表示分解后的表若在分解后的表中該屬性存在，即為a,否則記為ba的下角標(biāo)為列數(shù)，b的下角標(biāo)包括行和列（前為行，后為列）分解三：ND(Sno,Sdept)，NL(Sno,Sloc)32關(guān)于模式分解無損連接性的判斷算法例:SL（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SnoSdeptSlocNDa1a2b13NLa1b22a3第二步：改記錄表立足原始表中存在的函數(shù)依賴，找到記錄表的對應(yīng)列進(jìn)行修改；

若決定因素列相同，被決定因素列存在a，則將該列均改為a,

被決定因素列沒有a，則全改為b;a2a3若某一行全變?yōu)閍,則這種分解方式保持無損連接（在任意一步可中止）33關(guān)于模式分解無損連接性的判斷算法例:SL（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SnoSdeptSlocNLa1b12a3DLb21a2a3分解二：NL(Sno,Sloc)，DL(Sdept,Sloc)沒有某一行全變?yōu)閍,這種分解方式不能保持無損連接34F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}對關(guān)系模式R<U，F(xiàn)>來說有以下的推理規(guī)則：95003MAC2判別一個分解的無損連接性──────────────────────（其中U=U1∪U2∪…∪Un，且不存在UiUj，F(xiàn)i為F在