無損分解和保持依賴的判斷
大部分是對一個關系模式分解成兩個模式的考察,分解為三個以上模式時無損分解和保持依賴的判斷比較復雜,考的可能性不大,因此我們只對“一個關系模式分解成兩個模式”這種類型的題的相關判斷做一個總結。以下的論述都基于這樣一個前提:
R是具有函數依賴集F的關系模式,(R1 ,R2)是R的一個分解。
首先我們給出一個看似無關卻非常重要的概念:屬性集的閉包。
令α為一屬性集。我們稱在函數依賴集F下由α函數確定的所有屬性的集合為F下α的閉包,記為α+ 。
下面給出一個計算α+的算法,該算法的輸入是函數依賴集F和屬性集α,輸出存儲在變量result中。
算法一:
result:=α;
while(result發生變化)do
for each 函數依賴β→γ in F do
begin
if β∈result then result:=result∪γ;
end
屬性集閉包的計算有以下兩個常用用途:
·判斷α是否為超碼,通過計算α+(α在F下的閉包),看α+ 是否包含了R中的所有屬性。若是,則α為R的超碼。
·通過檢驗是否β∈α+,來驗證函數依賴是否成立。也就是說,用屬性閉包計算α+,看它是否包含β。
(請原諒我用∈符號來表示兩個集合之間的包含關系,那個表示包含的符號我找不到,大家知道是什么意思就行了。)
看一個例子吧,2005年11月系分上午37題:
● 給定關系R(A1,A2,A3,A4)上的函數依賴集F={A1→A2,A3→A2,A2→A3,A2→A4},R的候選關鍵字為________。
(37)A. A1 B. A1A3 C. A1A3A4 D. A1A2A3
首先我們按照上面的算法計算A1+ 。
result=A1,
由于A1→A2,A1∈result,所以result=result∪A2=A1A2
由于A2→A3,A2∈result,所以result=result∪A3=A1A2A3
由于A2→A4,A2∈result,所以result=result∪A3=A1A2A3A4
由于A3→A2,A3∈result,所以result=result∪A2=A1A2A3A4
通過計算我們看到,A1+ =result={A1A2A3A4},所以A1是R的超碼,理所當然是R的候選關鍵字。此題選A 。
好了,有了前面的鋪墊,我們進入正題。
如果R1∩R2是R1或R2的超碼,則R上的分解(R1,R2)是無損分解。這是一個充分條件,當所有的約束都是函數依賴時它才是必要條件(例如多值依賴就是一種非函數依賴的約束),不過這已經足夠了。
保持依賴的判斷。
如果F上的每一個函數依賴都在其分解后的某一個關系上成立,則這個分解是保持依賴的(這是一個充分條件)。
如果上述判斷失敗,并不能斷言分解不是保持依賴的,還要使用下面的通用方法來做進一步判斷。
該方法的表述如下:
算法二:
對F上的每一個α→β使用下面的過程:
result:=α;
while(result發生變化)do
for each 分解后的Ri
t=(result∩Ri)+ ∩Ri
result=result∪t
這里的屬性閉包是在函數依賴集F下計算出來的。如果result中包含了β的所有屬性,則函數依賴α→β。分解是保持依賴的當且僅當上述過程中F的所有依賴都被保持。
●設關系模式R<U, F>,其中U={A, B, C, D, E},F={A→BC,C→D,BC→E,E→A},則分解ρ={R1(ABCE),R2(CD)}滿足 (43) 。
(43) A.具有無損連接性、保持函數依賴
B.不具有無損連接性、保持函數依賴
C.具有無損連接性、不保持函數依賴
D.不具有無損連接性、不保持函數依賴
由于C→D,C∈result,所以result=result∪D=CD
可見C是R2的超碼,該分解是一個無損分解。
再做保持依賴的判斷。
A→BC,BC→E, E→A都在R1上成立(也就是說每一個函數依賴左右兩邊的屬性都在R1中),C→D在R2上成立,因此給分解是保持依賴的。
選A。
再看一個復雜點的例題。2007年5月數工40-41題。
●給定關系模式R<U, F>,U={A, B, C, D, E},F={B→A,D→A,A→E,AC→B},其候選關鍵字為
(40) ,則分解ρ={R1(ABCE),R2(CD)}滿足 (41) 。
(40) A.ABD
B.ABE
C.ACD
D.CD
(41) A.具有無損連接性、保持函數依賴
B.不具有無損連接性、保持函數依賴
C.具有無損連接性、不保持函數依賴
D.不具有無損連接性、不保持函數依賴
看見了吧,和前面一題多么的相像!
對于第一問,分別計算ABCD四個選項的閉包,
(ABD)+ = { ABDE }
(ABE)+ = { ABE }
(ACD)+ = { ABCDE }
(CD)+ = { ABCDE }
選D。
先做無損鏈接的判斷。R1∩R2={C},計算C+。
因此C既不是R1也不是R2的超碼,該分解不具有無損分解性。
再做保持依賴的判斷。
B→A,A→E,AC→B在R1上成立,D→A在R1和R2上都不成立,因此需做進一步判斷。
由于B→A,A→E,AC→B都是被保持的(因為它們的元素都在R1中),因此我們要判斷的是D→A是不是也被保持。
對于D→A應用算法二:
result=D
對R1,result∩R1=ф(空集,找不到空集的符號,就用這個表示吧),t=ф,result=D
再對R2,result∩R2=D,D+ =ADE ,t=D+ ∩R2=D,result=D
一個循環后result未發生變化,因此最后result=D,并未包含A,所以D→A未被保持,該分解不是保持依賴的。