廣義依賴(數(shù)據(jù)庫)

時間：2022-12-25 08:30:01 | 來源：信息時代

時間：2022-12-25 08:30:01 來源：信息時代

    廣義依賴 : 函數(shù)依賴、多值依賴、嵌入的多值依賴、連接依賴、子集依賴等多種數(shù)據(jù)依賴的共同推廣,它可揭示各種依賴的很多共同性質(zhì),給出各種依賴都可使用的很多統(tǒng)一方法。
廣義依賴的概念是由Beeri、Vardi、Paredaens、Ullman等人于1980～1981年分別獨立地提出的。廣義依賴又分為等值產(chǎn)生依賴及元組產(chǎn)生依賴。廣義依賴的出現(xiàn)使數(shù)據(jù)庫的很多理論(例如追趕算法、蘊涵判定等)有了統(tǒng)一、一致的形式。廣義依賴是現(xiàn)在通用的名稱,實際上在 1980年,Fagin及Yannakakis等還提出過蘊涵依賴及代數(shù)依賴等,也都是為了解決各種依賴的統(tǒng)一及推廣問題。以上這些研究的成功使得關系數(shù)據(jù)庫理論的覆蓋面更加擴大了。
用表示所有變量的集合, 表示所有常數(shù)的集合,R={A₁, …,A_m}是一個關系模式, R到上的映射v,稱為R上的變量元組,這個元組也可用記號〈v[A₁],…,v[A_m]〉來表示。設v₁,…,v_n是關系模式R上的n個變量元組,且對任何1≤i₁,i₂≤n及1≤j₁,j₂≤m,只要j₁≠j₂,就有v_i1[A_j1]≠v_i2[A_j2],即對每個A_i∈R,v[A_i]不與T中A_i以外屬性上的變量相同,則稱v₁,…,v_n為R上的一個造型表。若等式x=y中的x,y都是在v₁,…,v_n中出現(xiàn)的變量,則稱記號:v₁,…,v_n/x=y是一個等值產(chǎn)生依賴。我們把所有變量及所有常數(shù),即∪中的元素統(tǒng)稱為“符號”。設V是v₁,…,v_n中所有變量的集合, Ψ是從V到符號集合∪的映射, 稱Ψ為符號映射。如果v_i＝〈x₁,…,x_m〉,則記Ψ(v_i)=〈Ψ(x₁₎,…,Ψ(x_m)〉。
R是一個關系模式,v₁,…,v_n/x=y是R上的一個等值產(chǎn)生依賴,r是R上的一個關系(關系請參看關系數(shù)據(jù)庫條目),記T=v₁,…,v_n,若Ψ能使Ψ(v₁₎∈r,…,Ψ(v_n)∈r,則稱Ψ是從T到r的同態(tài)映射,若用記號Ψ(T)來表示{Ψ(v₁₎,…,Ψ(v_n)},則符號映射Ψ是從T到r的同態(tài)映射的充要條件就是Ψ(T)>r。如果對每一個從T到r的同態(tài)映射Ψ都有Ψ(x)=Ψ(y)成立,則稱r適合等值產(chǎn)生依賴T/x=y。
設T=v₁,…,v_n是關系模式R上一個造型表。設v是R上的一個變量元組,滿足對每個A∈R,v[A]不與T中A以外屬性上的變量相同,則稱記號v₁,…,v_n/v,或T/v,為R上的元組產(chǎn)生依賴。稱只出現(xiàn)在v中而不出現(xiàn)在T中的變量為獨立變量。v中沒有獨立變量的元組產(chǎn)生依賴稱為“完全元組產(chǎn)生依賴”,有獨立變量的稱為“嵌入的元組產(chǎn)生依賴”。R是一個關系模式,T/v是R上的一個元組產(chǎn)生依賴,r是R上的一個關系,v中非獨立變量所對應的屬性集合是V₀＝{A₁,…,A_m},若對應每個T到r的同態(tài)映射y,都有一個u∈r存在,使得Ψ(A₁₎＝u[A₁],…,Ψ(A_m)＝u[A_m],則稱關系r適合元組產(chǎn)生依賴T/v。
設R是一個關系模式,R上的等值產(chǎn)生依賴及元組產(chǎn)生依賴統(tǒng)稱R上的廣義依賴。若∑是一個R上廣義依賴的集合,則稱二元組(R,∑)為一個廣義依賴模式。若r是R上的一個關系,且r適合∑中的所有廣義依賴,則稱r是(R,∑)的一個實例。設(R,∑)是一個廣義依賴模式,T/x=y(或T/v)是R上的一個廣義依賴,若R上的每個適合∑的關系r,也都適合T/x=y(或T/v),則稱∑蘊涵T/x=y(或T/v),記作∑⊧T/x=y(或∑⊧T/v)。 為了給出在廣義依賴模式中判定蘊涵的方法(這個方法顯然將是判定蘊涵的最普遍的方法),先定義“依賴應用于造型表”的概念:設R是一個關系模式,T是R上的一個造型表。T₀/x=y是R上的一個等值產(chǎn)生依賴,將T看作是R上的一個關系(也可稱為變量關系),Ψ是從T₀到關系T的一個同態(tài)映射。稱“將T中的Ψ(y)全換成Ψ(x)而得到一個新的造型表T”這件事為: “應用廣義依賴T₀/x=y到T”并稱T是應用T₀/x=y于T的結(jié)果。
設R是一個關系模式,T是R上的一個造型表,T₀/v是R上的一個元組產(chǎn)生依賴,將T看作是R上的一個關系,Ψ使從T₀到關系T的一個同態(tài)映射,若v中的獨立變量是x₁,…,x_m,將Ψ擴展到這些獨立變量上,且滿足Ψ(x₁₎,…,Ψ(x_m)不與T中任何一個變量相同,而且它們彼此也互不相同,令T`=T∪{Ψ(v)},此過程稱為“應用廣義依賴T<sub>0</sub>/v到T上”,并稱T`為應用T₀/v到T上的結(jié)果。顯然這時T`仍是R上的一個造型表。
按照這些定義,給出廣義依賴集合蘊涵一個等值產(chǎn)生依賴的判定算法及廣義依賴集合蘊涵一個元組產(chǎn)生依賴的判定方法如下。這些方法被統(tǒng)稱為廣義追趕算法,是判定蘊涵的最一般的方法。
判定關系模式R上一個廣義依賴集合∑是否蘊涵一個等值產(chǎn)生依賴T/x=y的方法是:
(1)令T₁＝T及i=1。
(2)對T_i進行檢查,查看是否所有x,y位置上的符號都已換成了相同的符號,若是,則∑蘊涵T/x=y,并稱此時為成功的追趕; 否則執(zhí)行步驟3。
(3)應用∑中的各個依賴于T_i,若應用某一個不能使T_i有改變,則再應用下一個,直到有一個∑中的依賴應用于T_i后能使T_i有改變?yōu)橹?并將此應用的結(jié)果記為T_i+1,令i=i+1,轉(zhuǎn)步驟2。若所有∑中的依賴應用于T_i后,都不能使T_i有改變,則∑不蘊涵T/x=y。
判定關系模式R上一個廣義依賴集合∑是否蘊涵一個元組產(chǎn)生依賴T/v的方法是:
(1)令T₁＝T及i=1。
(2)對T_i進行檢查,查看是否存在一行,這一行的非獨立變量與v的非獨立變量完全相同,若有,∑蘊涵T/v,并稱此時為成功的追趕,稱該行為目標行; 若沒有,則執(zhí)行步驟(3)。
(3)依次應用∑中的各個依賴于T_i,若應用某一個依賴不能使T_i有改變,則再應用下一個。若所有∑中的依賴應用于T_i后,都不能使T_i有改變,則∑不蘊涵T/v。若能有一個依賴應用后能使T_i有改變,則將此應用的結(jié)果記為T_i+1,并令i=i+1,轉(zhuǎn)步驟2。
廣義追趕算法,當∑|≠σ且≠∑中含有嵌入的依賴時,有可能無限執(zhí)行下去,不會結(jié)束。不過對于這種不會結(jié)束的情況,嚴格地說已不能成為一種算法,只能作為∑σ的一種特殊形式的指示。 廣義依賴的有向無回路圖等其他內(nèi)容詳見參考文獻[1]。