逻辑程序等价性(数据库)

时间：2022-11-01 12:30:01 | 来源：信息时代

时间：2022-11-01 12:30:01 来源：信息时代

    逻辑程序等价性 : 判定两个逻辑程序是否等价(或有界)是一种优化逻辑程序的求值方法。等价、一致等价、查询等价和有界等价。
1.等价
设两个逻辑程序P和P′涉及相同谓词,即P和P′中出现相同的EDB谓词,并定义了相同的IDB谓词。如果对于任意给定的EDB作为输入,逻辑程序P和P′将产生相同的IDB作为输出,则称逻辑程序P和P′是等价的,记作P≡P′。
逻辑程序的等价性是不可判定的。然而,有些逻辑程序的等价性可以使用它们实际语义判断。如果逻辑程序P和P′是等价的,并且P更容易处理,则在查询处理时可以使用P,这将使得查询处理更加有效。下例用于说明逻辑程序P₁(r₁和r₂₎和P₂(r₁和r₃₎是否等价:
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).
规则r₁表明如果Y是X的父母,则Y是X的祖先; 规则r₂表明如果存在Z使得Z是X的父母,并且Y是Z的祖先,则Y是X的祖先; 规则r₃表明:如果存在Z使得Z是X的祖先,并且Y是Z的祖先,则Y是X的祖先。显然,P₁和P₂是等价的。
2. 一致等价
设两个逻辑程序P和P′涉及相同谓词。如果对于任意给定的EDB和IDB的初值作为输入,P和P′将产生相同的IDB作为输出,则称逻辑程序P和P′是一致等价的。如果逻辑程序P和P′是一致等价的,则它们一定是等价的,但是其逆不真。一致等价性概念是Y.Sagiv提出的,旨在进一步优化逻辑程序的求值。它还证明了对于Datalog,一致等价性是可判定的。
如前例的逻辑程序P₁和P₂是等价的,但它们并不一致等价。然而,如果逻辑程序P₃包含如下两个规则:
r₁:ancestor(X,Y):-parent(X,Y).
r₄:ancestor(X,Y):-ancestor(X,Z),parent(Z,Y).
其中,规则r₄表明:如果存在Z使得Z是X的祖先,并且Y是Z的父母,则Y是X的祖先。这时,逻辑程序P₁和P₃是一致等价的,因此也是等价的。
3. 查询等价
给定一个查询q和用于计算该查询的两个逻辑程序P和P′。若以任意给定的EDB作为输入,逻辑程序P和P′总是产生给定查询q的相同回答,则称逻辑程序P和P′是关于查询q等价的,简称查询等价。如果两个逻辑程序是等价的,则对于任意查询它们必然产生相同的回答,因而必然是查询等价的。然而,关于给定查询q等价的两个逻辑程序并不一般等价。如前例中的逻辑程序P₁给定的查询是“ancestor(‘李明’,Y)?”,即可找出李明的祖先。对于给定的查询,逻辑程序P₁是右线性的。使用右线性递归变换,即可得到如下一组规则:
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).
把以上规则记作逻辑程序P₄。对于任意给定EDB关系PARENT,逻辑程序P₄将正确地回答查询“ancestor(‘李明’,Y)? ”。因此,P₄与逻辑程序P₁是关于“ancestor(‘李明’,Y)?”查询等价的。
逻辑程序的查询等价比等价或一致等价更有实际意义,因为对于演绎数据库,有效地计算查询的回答是至关重要的。通常,给定一个逻辑程序P,很难找到一个与P等价的逻辑程序P′,对于回答任意查询,P′都比P更有效。然而,对于给定的查询q和计算该查询的逻辑程序P,常常可以找到一个逻辑程序P′,P′和P关于q查询等价,并且P′能够更有效地计算给定的查询。目前,用各种变换(魔集变换、右线性递归变换、左线性递归变换、混合线性递归变换和计数线性递归变换)产生查询等价的逻辑程序远比原来的逻辑程序能更加有效地计算查询的回答。
4. 有界等价
有界等价是指一个递归逻辑程序等价于一个非递归的逻辑程序,又称逻辑程序的有界性。逻辑程序的有界性(boundedness of logic program)的含义是: 对于一个给定的逻辑程序P,如果存在一个非递归的逻辑程序P′与之等价,则称逻辑程序P是有界的。显然,非递归的逻辑程序是有界的。对于递归的逻辑程序,其有界性是不可判定的,但是对于Datalog程序的某些递归子类,如对于二元、线性的Datalog程序,其有界性是可以判定的。如果一个逻辑程序是有界的,则可以消除递归,化递归查询为非递归查询,从而可以利用关系代数的查询优化技术来进行处理。