邏輯程序等價(jià)性(數(shù)據(jù)庫(kù))

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

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

    邏輯程序等價(jià)性 : 判定兩個(gè)邏輯程序是否等價(jià)(或有界)是一種優(yōu)化邏輯程序的求值方法。等價(jià)、一致等價(jià)、查詢等價(jià)和有界等價(jià)。
1.等價(jià)
設(shè)兩個(gè)邏輯程序P和P′涉及相同謂詞,即P和P′中出現(xiàn)相同的EDB謂詞,并定義了相同的IDB謂詞。如果對(duì)于任意給定的EDB作為輸入,邏輯程序P和P′將產(chǎn)生相同的IDB作為輸出,則稱邏輯程序P和P′是等價(jià)的,記作P≡P′。
邏輯程序的等價(jià)性是不可判定的。然而,有些邏輯程序的等價(jià)性可以使用它們實(shí)際語(yǔ)義判斷。如果邏輯程序P和P′是等價(jià)的,并且P更容易處理,則在查詢處理時(shí)可以使用P,這將使得查詢處理更加有效。下例用于說(shuō)明邏輯程序P₁(r₁和r₂₎和P₂(r₁和r₃₎是否等價(jià):
P₁: r₁:ancestor(X,Y):-parent(X,Y).
r₂:ancestor(X,Y):-parent(X,Z),ancestor(Z,Y).
P₂:r₁:ancestor(X,Y):-parent(X,Y).
r₃:ancestor(X,Y):-ancestor(X,Z),ancestor(Z,Y).
規(guī)則r₁表明如果Y是X的父母,則Y是X的祖先; 規(guī)則r₂表明如果存在Z使得Z是X的父母,并且Y是Z的祖先,則Y是X的祖先; 規(guī)則r₃表明:如果存在Z使得Z是X的祖先,并且Y是Z的祖先,則Y是X的祖先。顯然,P₁和P₂是等價(jià)的。
2. 一致等價(jià)
設(shè)兩個(gè)邏輯程序P和P′涉及相同謂詞。如果對(duì)于任意給定的EDB和IDB的初值作為輸入,P和P′將產(chǎn)生相同的IDB作為輸出,則稱邏輯程序P和P′是一致等價(jià)的。如果邏輯程序P和P′是一致等價(jià)的,則它們一定是等價(jià)的,但是其逆不真。一致等價(jià)性概念是Y.Sagiv提出的,旨在進(jìn)一步優(yōu)化邏輯程序的求值。它還證明了對(duì)于Datalog,一致等價(jià)性是可判定的。
如前例的邏輯程序P₁和P₂是等價(jià)的,但它們并不一致等價(jià)。然而,如果邏輯程序P₃包含如下兩個(gè)規(guī)則:
r₁:ancestor(X,Y):-parent(X,Y).
r₄:ancestor(X,Y):-ancestor(X,Z),parent(Z,Y).
其中,規(guī)則r₄表明:如果存在Z使得Z是X的祖先,并且Y是Z的父母,則Y是X的祖先。這時(shí),邏輯程序P₁和P₃是一致等價(jià)的,因此也是等價(jià)的。
3. 查詢等價(jià)
給定一個(gè)查詢q和用于計(jì)算該查詢的兩個(gè)邏輯程序P和P′。若以任意給定的EDB作為輸入,邏輯程序P和P′總是產(chǎn)生給定查詢q的相同回答,則稱邏輯程序P和P′是關(guān)于查詢q等價(jià)的,簡(jiǎn)稱查詢等價(jià)。如果兩個(gè)邏輯程序是等價(jià)的,則對(duì)于任意查詢它們必然產(chǎn)生相同的回答,因而必然是查詢等價(jià)的。然而,關(guān)于給定查詢q等價(jià)的兩個(gè)邏輯程序并不一般等價(jià)。如前例中的邏輯程序P₁給定的查詢是“ancestor(‘李明’,Y)?”,即可找出李明的祖先。對(duì)于給定的查詢,邏輯程序P₁是右線性的。使用右線性遞歸變換,即可得到如下一組規(guī)則:
m_ancestor(‘李明’).
m_ancestor(Z):-m_ancestor(X),parent(X,Z).
a_ancestor(Y):-m_ancestor(X),parent(X,Y).
ancestor(‘李明’,Y):-a_ancestor(Y).
把以上規(guī)則記作邏輯程序P₄。對(duì)于任意給定EDB關(guān)系PARENT,邏輯程序P₄將正確地回答查詢“ancestor(‘李明’,Y)? ”。因此,P₄與邏輯程序P₁是關(guān)于“ancestor(‘李明’,Y)?”查詢等價(jià)的。
邏輯程序的查詢等價(jià)比等價(jià)或一致等價(jià)更有實(shí)際意義,因?yàn)閷?duì)于演繹數(shù)據(jù)庫(kù),有效地計(jì)算查詢的回答是至關(guān)重要的。通常,給定一個(gè)邏輯程序P,很難找到一個(gè)與P等價(jià)的邏輯程序P′,對(duì)于回答任意查詢,P′都比P更有效。然而,對(duì)于給定的查詢q和計(jì)算該查詢的邏輯程序P,常?？梢哉业揭粋€(gè)邏輯程序P′,P′和P關(guān)于q查詢等價(jià),并且P′能夠更有效地計(jì)算給定的查詢。目前,用各種變換(魔集變換、右線性遞歸變換、左線性遞歸變換、混合線性遞歸變換和計(jì)數(shù)線性遞歸變換)產(chǎn)生查詢等價(jià)的邏輯程序遠(yuǎn)比原來(lái)的邏輯程序能更加有效地計(jì)算查詢的回答。
4. 有界等價(jià)
有界等價(jià)是指一個(gè)遞歸邏輯程序等價(jià)于一個(gè)非遞歸的邏輯程序,又稱邏輯程序的有界性。邏輯程序的有界性(boundedness of logic program)的含義是: 對(duì)于一個(gè)給定的邏輯程序P,如果存在一個(gè)非遞歸的邏輯程序P′與之等價(jià),則稱邏輯程序P是有界的。顯然,非遞歸的邏輯程序是有界的。對(duì)于遞歸的邏輯程序,其有界性是不可判定的,但是對(duì)于Datalog程序的某些遞歸子類,如對(duì)于二元、線性的Datalog程序,其有界性是可以判定的。如果一個(gè)邏輯程序是有界的,則可以消除遞歸,化遞歸查詢?yōu)榉沁f歸查詢,從而可以利用關(guān)系代數(shù)的查詢優(yōu)化技術(shù)來(lái)進(jìn)行處理。