無(wú)回路數(shù)據(jù)庫(kù)(數(shù)據(jù)庫(kù))

時(shí)間：2022-11-29 14:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-11-29 14:30:01 來(lái)源：信息時(shí)代

    無(wú)回路數(shù)據(jù)庫(kù) : 一大類具有很多良好性質(zhì)的數(shù)據(jù)庫(kù)的總稱,由于這一大類數(shù)據(jù)庫(kù)的數(shù)據(jù)庫(kù)模式用超圖表示時(shí),超圖沒(méi)有回路,因此特稱為無(wú)回路數(shù)據(jù)庫(kù)。
這一大類數(shù)據(jù)庫(kù)又分為α無(wú)回路、β無(wú)回路及γ無(wú)回路3個(gè)子類。最初是為了研究泛關(guān)系查詢沒(méi)有二義性而被提出的,但研究發(fā)現(xiàn)它們還有許多其他良好性質(zhì)。即人們研究了α無(wú)回路超圖、閉無(wú)回路超圖、有弦共形特性、Graham算法、兩兩一致與整體一致、完全約簡(jiǎn)、連接樹、運(yùn)行相交特性、單調(diào)連接表達(dá)式、單調(diào)順序連接表達(dá)式、β無(wú)回路超圖、弱β回路超圖、既約邊集、無(wú)關(guān)節(jié)集、Graham回路超圖、γ無(wú)回路超圖、弱γ回路超圖、不可比較的相交邊集、純回路超圖等理論,并證明了直到γ無(wú)回路時(shí)泛關(guān)系查詢才能沒(méi)有二義性。
1982年Fagin,Mendelzon,Ullman等首先提出了無(wú)回路數(shù)據(jù)庫(kù)的概念。1983年他們又明確地把無(wú)回路的數(shù)據(jù)庫(kù)超圖分為了α無(wú)回路、β無(wú)回路及γ無(wú)回路。γ無(wú)回路時(shí)泛關(guān)系查詢才能沒(méi)有二義性的證明也是他們給出的。在研究過(guò)程中人們發(fā)現(xiàn)這類數(shù)據(jù)庫(kù)還有許多良好的性質(zhì)。1986年,A.D’Atri及Moscarini還研究了α,β,γ各種無(wú)回路數(shù)據(jù)庫(kù)的識(shí)別方法及設(shè)計(jì)算法,使無(wú)回路數(shù)據(jù)庫(kù)的理論研究更臻完整。
設(shè)Ω={R,…,R_n}是一個(gè)數(shù)據(jù)庫(kù)模式,U是所有屬性的集合,則稱以U中的屬性為點(diǎn),以Ω中的關(guān)系模式R_i(i=1,…,n)為超邊的超圖H=(U,∑)為數(shù)據(jù)庫(kù)的超圖。
α無(wú)回路超圖是這樣一種超圖它的所有塊都是平凡的。這里平凡的是指一個(gè)集合只包含一個(gè)元素,而塊是指連通的無(wú)關(guān)節(jié)集的部分邊集。
部分邊集及關(guān)節(jié)集的定義如下:
設(shè)(N,E)是一個(gè)超圖,MN,在集合{e∩E|e∈E}中刪去是其他元素子集的那些元素后得到的結(jié)果記為F,則F就是“由M產(chǎn)生的部分邊集”,簡(jiǎn)稱“部分邊集”,若存在e₁,e₂∈F,f=e₁∩e₂,而{e-f|e∈F}的連通分量比F的連通分量多,則稱f為F的關(guān)節(jié)集。
α無(wú)回路與以下11個(gè)性質(zhì)等價(jià):
(1) H是閉α無(wú)回路超圖。
(2) H是有弦共形圖。
(3) H應(yīng)用Graham算法成功。
(4)連接依賴⋈Ω等價(jià)于一個(gè)多值依賴集合。
(5)連接依賴⋈Ω等價(jià)于一個(gè)無(wú)沖突的多值依賴集合。
(6)Ω上的兩兩一致數(shù)據(jù)庫(kù)一定是整體一致數(shù)據(jù)庫(kù)。
(7)Ω上的每個(gè)數(shù)據(jù)庫(kù)都有一個(gè)完全約簡(jiǎn)。
(8)Ω有連接樹。
(9)Ω有運(yùn)行相交特性。
(10)Ω有單調(diào)連接表達(dá)式。
(11)Ω有單調(diào)順序連接表達(dá)式。
在一個(gè)超圖中若它的每個(gè)子超圖都是α無(wú)回路的,則稱它為β無(wú)回路的,若有一個(gè)子圖不是α無(wú)回路的,則稱它為β回路的。超圖中的一個(gè)超邊序列R₁,…,R_m,R_m+1,其中R₁＝R_m+1,若記X=R₁,…,R_m,R′_i＝R_i-X(i=1,…,m+1),而R₁′,…,R′_m,R′_m+1是一個(gè)純回路,則稱這個(gè)超邊序列是一個(gè)β回路。這里純回路是指R′₁,…,R′_m互不相同,R′_m＝R′_m+1,且對(duì)所有1≤i≤m都有R′_i＝R′_i+1≠。
β回路超圖的以下5個(gè)性質(zhì)等價(jià):
(1) H是β回路的,當(dāng)它有一個(gè)β回路。
(2) H是β回路的,當(dāng)它有一個(gè)子圖不是α無(wú)回路的。
(3) H是β回路的,當(dāng)它有某個(gè)非平凡連通的既約邊集沒(méi)有關(guān)節(jié)集。
(4) H是β回路的,當(dāng)它有一個(gè)弱β回路。
(5) H是β回路的,當(dāng)它有一個(gè)Graham回路。
γ回路是超圖H中的一個(gè)交替序列S₁,x₁,S₂,x₂,…,S_m,x_m,S_m+1,其中x₁,…,x_m是H中互不相同的點(diǎn),S₁,…,S_m是H中互不相同的邊,S₁＝S_m+1,x_i∈S_i∩S_i+1(i=1,…,m)而且x_i不屬于S_i及S_i+1以外的S_j(i=1,…,m-1)。
γ回路的以下四個(gè)性質(zhì)等價(jià):
(1) H是γ回路的,當(dāng)H有一條γ回路。
(2) H是γ回路的,當(dāng)H有一條弱γ回路。
(3) H是γ回路的,當(dāng)H有一條長(zhǎng)度為3的γ回路或有一條純回路。
(4) H是γ回路的,當(dāng)H有一對(duì)相交但不可比較的邊E及F,并可推知若H=(U,∑)不是γ回路的(即γ無(wú)回路的),則Ω上的連通的順序連接表達(dá)式都是單調(diào)順序連接表達(dá)式。
以上這些性質(zhì)的嚴(yán)格定義及它們彼此等價(jià)的完整證明,γ無(wú)回路時(shí)泛關(guān)系查詢一定沒(méi)有二義性的證明。均請(qǐng)見文獻(xiàn)[1] 。
對(duì)于一個(gè)給定的超圖H=(N,E),可用一種遞歸方法來(lái)識(shí)別它是否是θ無(wú)回路的(這里θ∈{α,β,γ})。該方法詳見參考文獻(xiàn)[1]。
由于各種無(wú)回路超圖與眾多的性質(zhì)等價(jià),致使它的應(yīng)用已經(jīng)超出了解決泛關(guān)系查詢沒(méi)有二義性的范疇,所以經(jīng)常需要設(shè)計(jì)出指定類型的無(wú)回路超圖。θ無(wú)回路超圖的合理的、完全的和獨(dú)立的設(shè)計(jì)方法:(這里θ∈{α,β,γ})及合理性、完全性和獨(dú)立性的嚴(yán)格定義詳見參考文獻(xiàn)[1]。