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

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

例：設有關系模式R(A,B,C,D,E,F),F={A→D,E→D,D→B,BC→D,DC→A}，求R的所有候選碼。推論2：對于給定的關系模式R及其函數依賴集F，若X(X∈R)是N類和L類屬性組成的屬性集，且X＋包含了R的全部屬性，則X必為R的惟一候選碼。.第五章關系數據理論6.1數據依賴6.2規范化6.3數據依賴的公理系統6.4模式的分解.6.4模式的分解關系模式的規范化過程是通過對關系模式的分解來實現的把低一級的關系模式分解為若干個高一級的關系模式的方法并不是唯一的只有能夠保證分解后的關系模式與原關系模式等價，分解方法才有意義.模式的分解（續）定義6.16關系模式R<U,F>的一個分解：ρ={R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}

（其中U=U1∪U2∪…∪Un，且不存在Ui

Uj，Fi為F在Ui上的投影），意味著相應地將存儲在一個二維表中的數據分散到若干個二維表中去。.模式的分解（續）例:SL（Sno，Sdept，Sloc）

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

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

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

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

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

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

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

無法知道95002、95004、95005

究竟是哪個系的學生

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

將SL分解為下面二個關系模式：

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

分解后的關系為：

.模式的分解（續）ND────────────NL──────────SnoSdeptSnoSloc

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

───────────────────────.模式的分解（續）NDNL──────────────SnoSdeptSloc──────────────

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

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

.保持函數依賴的模式分解設關系模式R<U,F>被分解為若干個關系模式R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>（其中U=U1∪U2∪…∪Un，且不存在UiUj，Fi為F在Ui上的投影），若F所邏輯蘊含的函數依賴一定也由分解得到的某個關系模式中的函數依賴Fi所邏輯蘊含，則稱關系模式R的這個分解是保持函數依賴的（Preservedependency）。.第四種分解方法

將SL分解為下面二個關系模式：

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

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