關系模式的分解
將一個關系模式分解為多個關系模式之後
原模式所滿足的特性在新的模式中是否被保持
為了保持原來模式所滿足的特性
要求分解處理具有無損聯接性和保持函數依賴性
模式分解中存在的問題
設有關系模式R
R
R
R
…
Rk都是R的子集
R=R
∪ R
∪ … ∪ Rk
關系模式R
R
R
…
Rk的集合用r 表示
r ={R
R
R
…
Rk}
用r代替R的過程稱為關系模式的分解
例
設關系模式R（ABC）
F={A →B
B →C}
r是R的滿足F的當前值
將其按下列方式分解
會存在哪些問題
將R分解為r
={R
(A)
R
(B)
R
(C)}
將R分解為r
={R
(AB)
R
(AC)}
將R分解為r
={R
(AB)
R
(BC)}
將R分解為r
={R
(AC)
R
(BC)}
分解的衡量標准
分解具有無損聯接
分解要保持函數依賴
分解既要保持依賴
又要具有無損聯接
無損聯接性
無損聯接性是指當關系模式分解時
原關系模式下的任一合法的關系實例在分解之後能通過自然聯接恢復起來
定義
設r ={R
R
R
…
Rk}是關系模式R(U
F)的一個分解
如果對於R的任一滿足F的關系r都有
r=∏R
(r)︱×︱ ∏R
(r)︱×︱… ︱×︱ ∏Rk(r)
則稱這個分解滿足依賴集F的無損聯接
算法
檢驗無損聯接性
輸入
關系模式R {A
A
A
…
An}
函數依賴集F以及分解r ={R
R
R
…
Rk}
輸出
確定r是否具有無損聯接性
方法
構造一個k行n列的表
第i行對應於關系模式Ri
第j列對應於屬性Aj
如果Aj ∈ Ri
則在第i行第j列上放符號aj
否則放符號bjj
逐個檢查F中的每個函數依賴
並修改表中的元素
其方法如下
取F中的一個函數依賴X→Y
在X的分量中尋找相同的行
然後將這些行中的Y的分量改為相同的符號
如果其中有aj
則將bjj改為 aj
若其中無aj
則改為bjj
反復進行
如果發現某一行變成a
a
…
ak
則分解r具有無損聯接性
如果F中所有函數依賴都不能再修改表中的內容
且沒有發現這樣的行
則分解r不具有無損聯接性
例
設有關系模式R(U
F)
U=(A
B
C)
F={A→B
C→B}
判斷一個分解r={AC
BC}是否具有無損聯接性
例
設R=ABCDE
R
=AD
R
=AB
R
=BE
R
=CDE
R
=AE
設函數依賴是A→C
B→C
C→D
DE→C
CE→A
判斷r ={R
R
R
R
R
}是否具有無損聯接性
定理
如果R的分解為r ={R
R
}
F為R所滿足的函數依賴集合
分解r具有無損聯接性的充要條件是
R
∩ R
→（R
—R
）
或R
∩ R
→（R
—R
）
例
設R=ABC
F={A→B}
則r
={R
(AB)
R
(AC)}和r
={R
(AB)
R
(BC)}是否具有無損聯接性
保持函數依賴的分解
定義
設有關系模式R
F是R的函數依賴集
Z是R的一個屬性集合
則稱Z所涉及到的F+中所有函數依賴為F在Z上的投影
記為∏Z(F)
有
∏Z(F)={X→Y| X→Y ∈ F+且XYÍ Z}
定義
設關系模式R的一個分解r ={R
R
……
Rk}
F是R的依賴集
如果F等價於∏R
(F) ∪ ∏R
(F) ∪ … ∪ ∏Rk(F)
則稱分解r具有依賴保持性
注意
一個無損聯接分解不一定具有依賴保持性
同樣
一個依賴保持性分解不一定具有無損聯接性
例
設關系模式R=（CITY
ST
ZIP）
滿足下列函數依賴
(CITY
ST) →ZIP
ZIP →CITY
將R分解為r ={R
R
}
R
={ST
ZIP}
R
={CITY
ZIP}
檢查是否保持無損聯接性和函數依賴性
作業
設關系模式R（A
B
C
D
E
G）
F={AB →C
C →A
BC →D
ACD →B
D →EG
BE →C
CG →BD
CE →AG}
求屬性集閉包(BD) +
求函數依賴集F={AB →CE
A →C
GP →B
EP →A
CDE →P
HB →P
D →HG
ABC →PG} 最小函數依賴集Fmin
設關系模式R（U
V
W
X
Y
Z）
F={U →V
W →Z
Y →U
WY →X}
={WZ
VY
WXY
UV}是否具有無損聯接性
From:http://tw.wingwit.com/Article/os/xtgl/201311/8787.html
