關系模式分解

第3講關系模式的分解第5章關系數(shù)據(jù)庫模式設計1主要內(nèi)容模式分解無損聯(lián)接分解保持函數(shù)依賴集2ρR(U,F)U=U1∪U2∪…∪Uk對于任意的i,j(1≤i,j≤k)，不成立Ui

UjFi是F在Ui上的投影={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)}R(U,F)的一個分解也稱數(shù)據(jù)庫模式一、模式分解1、分解定義3

設有關系模式R(U,F)，F(xiàn)是R的函數(shù)依賴集，Z是U的子集，則把F＋中所有滿足XY

Z的函數(shù)依賴X→Y組成的集合，稱為依賴集F在屬性集Z上的投影，記為πZ(F)：

πZ(F)＝{X→Y|X→Y∈F＋且XY

Z}2、F在Ui上的投影4兩個問題：思考：？R(U)R1(U1),R2(U2),…,Rk(Uk)FF1,F2,…,Fk？數(shù)據(jù)等價依賴（語義）等價無損聯(lián)接保持依賴5二、無損聯(lián)接分解6二、無損聯(lián)接分解1、定義設有關系模式R(U,F)，ρ=（R1,R2…,Rk）是R的一個分解。如果對于R的任一滿足F的關系r，把r在ρ上的投影的聯(lián)接表達式記為：

m

(r)＝πR1(r)∞πR2(r)∞…∞πRk(r)如果r＝m

(r)成立，則稱這個分解ρ是滿足依賴集F的無損聯(lián)接分解。7輸入：關系模式R(A1,…,An)，函數(shù)依賴集F，R的一個分解ρ＝(R1,…,Rk)。輸出：ρ是否為無損聯(lián)接的判斷。方法:2、算法5.2判斷一個分解的無損聯(lián)接性8s[i,j]Aj在Ri中,ajAj不在Ri中,bij（1）構造一個k行n列表S，其中：2、算法5.2判斷一個分解的無損聯(lián)接性（續(xù)1）9（2）依據(jù)函數(shù)依賴集F進行修正：X→Y若Y值中有

aj，其它也改為aj若Y值中無aj，其它改為bij（下標?。〧D的選擇順序可隨意2、算法5.2判斷一個分解的無損聯(lián)接性（續(xù)2）10a1ana2……分解ρ具有無損聯(lián)接性（3）判斷條件：2、算法5.2判斷一個分解的無損聯(lián)接性（續(xù)3）11第一步：構造表S例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。12第二步：修正①A→C例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。13第二步：修正①A→C例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。14第二步：修正②B→C例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。15第二步：修正②B→C例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。16第二步：修正③C→D例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。17第二步：修正③C→D例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。18第二步：修正④DE→C例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。19第二步：修正④DE→C例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。20第二步：修正⑤CE→A例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。21第二步：修正⑤CE→A例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。22第三步：判斷分解ρ具有無損聯(lián)接性例5.7設R(ABCDE)，F(xiàn)={A→C，B→C，C→D，DE→C，CE→A}，ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}，檢驗分解ρ是否具有無損聯(lián)接性。23設有關系模式R(U,F)，F(xiàn)是R的屬性集U上的函數(shù)依賴集，ρ=（R1,R2）是R的一個分解，當且僅當

（R1∩R2）→（R1-R2）或（R1∩R2）→（R2-R1）時，ρ具有無損聯(lián)接性。3、判斷定理24證：充分性

(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立aa…aaa…aaa…aaa…abb…bbb…b∈F3、判斷定理（續(xù)1）25證：充分性

(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立aa…aaa…aaa…aaa…abb…b∈Faa…a3、判斷定理（續(xù)2）26證：充分性

(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立aa…aaa…aaa…aaa…abb…bbb…b∈F+3、判斷定理（續(xù)3）27證：充分性

(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)成立aa…aaa…aaa…aaa…abb…b∈F+aa…aρ具有無損聯(lián)接性3、判斷定理（續(xù)4）28（R1∩R2）→（R1-R2）證：必要性3、判斷定理（續(xù)5）29（R1∩R2）→（R2-R1）證：必要性3、判斷定理（續(xù)6）30分解ρ不具有無損聯(lián)接性舉例：

例5.8設有關系模式R(A,B,C)，函數(shù)依賴集F={A→B，C→B}，分解ρ={R1,R2}，其中R1=AB，R2=BC。檢驗分解ρ是否具有無損聯(lián)接性。31三、保持函數(shù)依賴集321、定義設有關系模式R(U,F)，F(xiàn)是R的函數(shù)依賴集，ρ＝{R1,R2,…,Rk}是R上的一個分解。如果所有函數(shù)依賴集πRi(F)（i=1，2，…,k）的并集邏輯蘊含F(xiàn)中的每一個函數(shù)依賴，則稱分解ρ具有依賴保持性，也即分解ρ保持依賴集F。即33對F中每個X→Y,計算XG+YXG+?保持依賴Y不保持依賴N令G=，驗證G

=F?2、保持依賴的判斷方法34例：設有關系模式R(A,B,C,D,E,P)，R的函數(shù)依賴集F={C→P,EC→D,E→A,A→B}。當將R分解成{R1(CP),R2(AE),R3(CDE),R4(BCE)}時，判斷該分解是否保持依賴性？

πR1