數(shù)據(jù)庫原理第17講

數(shù)據(jù)庫系統(tǒng)概論AnIntroductiontoDatabaseSystem第六章關(guān)系數(shù)據(jù)理論.候選碼的求解理論和算法對于給定的關(guān)系R（A1，A2，…，An）和函數(shù)依賴集F，可將其屬性分為四類：L類：僅出現(xiàn)在F的函數(shù)依賴左部的屬性。R類：僅出現(xiàn)在F的函數(shù)依賴右部的屬性。N類：在F的函數(shù)依賴左右兩邊均未出現(xiàn)的屬性。LR類：在F的函數(shù)依賴左右兩邊均出現(xiàn)的屬性。.快速求解候選碼定理1:對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是L類屬性，則X必為R的任一候選碼的成員。 例：設(shè)有關(guān)系模式R(A,B,C,D),F={D→B,B→D,AD→B,AC→D}，求R的所有候選碼。推論1：對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是L類屬性，且X＋包含了R的全部屬性，則X必為R的惟一候選碼。.快速求解候選碼（續(xù)）定理2:對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是R類屬性，則X不在任何候選碼中。

定理3：對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是N類屬性，則X必包含在R的任一候選碼中。.快速求解候選碼

例：設(shè)有關(guān)系模式R(A,B,C,D,E,F),F={A→D,E→D,D→B,BC→D,DC→A}，求R的所有候選碼。推論2：對于給定的關(guān)系模式R及其函數(shù)依賴集F，若X(X∈R)是N類和L類屬性組成的屬性集，且X＋包含了R的全部屬性，則X必為R的惟一候選碼。.第五章關(guān)系數(shù)據(jù)理論6.1數(shù)據(jù)依賴6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)6.4模式的分解.6.4模式的分解關(guān)系模式的規(guī)范化過程是通過對關(guān)系模式的分解來實現(xiàn)的把低一級的關(guān)系模式分解為若干個高一級的關(guān)系模式的方法并不是唯一的只有能夠保證分解后的關(guān)系模式與原關(guān)系模式等價，分解方法才有意義.模式的分解（續(xù)）定義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上的投影），意味著相應(yīng)地將存儲在一個二維表中的數(shù)據(jù)分散到若干個二維表中去。.模式的分解（續(xù)）例:SL（Sno，Sdept，Sloc）

F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}SL∈2NF存在插入異常、刪除異常、冗余度大和修改復(fù)雜等問題因此需要分解該關(guān)系模式，使成為更高范式的關(guān)系模式。分解方法可以有多種：.模式的分解（續(xù)）SL──────────────────Sno Sdept Sloc──────────────────95001CSA95002ISB95003MAC95004ISB95005 PH B──────────────────.模式的分解（續(xù)）第一種分解方法：將SL分解為下面三個關(guān)系模式：

SN(Sno)SD(Sdept)SO(Sloc).分解后的關(guān)系為：

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

──────────────────95001CSA95002ISB95003MAC95004PH─────95005────────────.模式的分解（續(xù)） SN、SD和SO都是規(guī)范化程度很高的關(guān)系模式（5NF）。但分解后的數(shù)據(jù)庫丟失了許多信息例如無法查詢95001學(xué)生所在系或所在宿舍。因此這種分解方法是不可取的。如果分解后的關(guān)系可以通過自然連接恢復(fù)為原來的關(guān)系，那么這種分解就沒有丟失信息.模式的分解（續(xù)）第二種分解方法： 將SL分解為下面二個關(guān)系模式：

NL(Sno,Sloc)DL(Sdept,Sloc)分解后的關(guān)系為：

NL────────────DL────────────SnoSlocSdeptSloc

────────────────────────95001A CSA95002B ISB95003C MAC95004B PHB95005B──────────────────────.模式的分解（續(xù)）NLDL─────────────SnoSlocSdept─────────────95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH.模式的分解（續(xù)） NLDL比原來的SL關(guān)系多了3個元組

無法知道95002、95004、95005

究竟是哪個系的學(xué)生

元組增加了，信息丟失了.第三種分解方法第三種分解方法：

將SL分解為下面二個關(guān)系模式：

ND(Sno,Sdept)NL(Sno,Sloc)

分解后的關(guān)系為：

.模式的分解（續(xù)）ND────────────NL──────────SnoSdeptSnoSloc

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

───────────────────────.模式的分解（續(xù)）NDNL──────────────SnoSdeptSloc──────────────

95001CSA95002ISB95003MAC95004CSA95005PHB──────────────與SL關(guān)系一樣，因此沒有丟失信息.具有無損連接性的模式分解關(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ù)冗余等問題.模式的分解（續(xù)）

第三種分解方法具有無損連接性，保證了不丟失原關(guān)系中的信息，但它并沒有解決更新異常和數(shù)據(jù)冗余問題。例如95001學(xué)生由CS系轉(zhuǎn)到IS系，ND關(guān)系的（95001，CS）元組和NL關(guān)系的（95001，A）元組必須同時修改，否則會破壞數(shù)據(jù)庫的一致性。之所以出現(xiàn)上述問題，是因為這種分解得到的關(guān)系模式不是互相獨立的，分解沒有保持原關(guān)系中的函數(shù)依賴。SL中的函數(shù)依賴Sdept→Sloc沒有投影到關(guān)系模式ND、NL上

.保持函數(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所邏輯蘊含的函數(shù)依賴一定也由分解得到的某個關(guān)系模式中的函數(shù)依賴Fi所邏輯蘊含，則稱關(guān)系模式R的這個分解是保持函數(shù)依賴的（Preservedependency）。.第四種分解方法

將SL分解為下面二個關(guān)系模式：

ND(Sno,Sdept)DL(Sdept,Sloc)

這種分解方法就保持了函數(shù)依賴。.關(guān)系模式分解的標(biāo)準(zhǔn)判斷對關(guān)系模式的一個分解是否與原關(guān)系模式等價的標(biāo)準(zhǔn)⒈分解具有無損連接性⒉分解要保持函數(shù)依賴⒊分解既要保持函數(shù)依賴，又要具有無損連接性.模式的分解（續(xù)）如果一個分解具有無損連接性，則它能夠保證不丟失信息。如果一個分解保持了函數(shù)依賴，則它可以減輕或解決各種異常情況。分解具有無損連接性和分解保持函數(shù)依賴是兩個互相獨立的標(biāo)準(zhǔn)。具有無損連接性的分解不一定能夠保持函數(shù)依賴。同樣，保持函數(shù)依