规则的计算含义(数据库)

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

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

    规则的计算含义 : 提供一种“计算”规则的方法,以告之一个潜在的事实是真还是假。Prolog就是以这种方法定义规则的含义的。在演绎数据库中,一个规则被转换为一个左部为关系,右部为关系代数表达式的方程。对于非递归规则,其对应方程的关系代数表达式可以直接求值,求值结果就是该规则的计算含义。对于递归规则,则需要通过不动点计算,对这些方程求解来得到规则的计算含义。这里,规则的计算含义就称为不动点计算规则含义。在演绎数据库中,规则的计算含义遵循规则的模型论解释,用规则的导出方程的不动点定义。
1. 规则的导出方程
给定一组Datalog规则(逻辑程序),每个规则转换成一个Datalog方程,称为该规则的导出方程。方程的左部是规则头部谓词对应的关系,方程的右部是由规则体导出的关系代数表达式。在Datalog方程中,EDB关系被看作关系常量,而IDB关系被看作关系变量。如,对于规则:p(X,Y):-q(X,Z),p(Z,Y)。其中p为IDB谓词,q为EDB谓词,其对应的关系分别为P和Q。由该规则导出的Datalog方程为: P(X,Y)=π_X,Y(Q(X,Z)⋈P(Z,Y))。
2.用不动点定义规则的计算含义
不动点的思想源于数学领域。1976年,M.H.Van Emden和R.A.Kowalski将不动点引入逻辑程序设计。1982年,A.K.Chandra和D.Harel将不动点的思想引入演绎数据库。以下为引入不动点概念定义算逻辑程序中规则的计算含义。
给定一组Datalog方程和这组方程涉及的EDB关系R₁,…,R_k。设该方程组涉及的IDB关系为P₁,…,P_m。该Datalog方程组关于R₁,…,R_k的不动点就是使得这些方程都成立的IDB关系P₁,…,P_m的一个解。设S₁＝{P₁⁽¹⁾,…,P_m⁽¹⁾} 和S₂＝{P₁⁽²⁾,…,P_m⁽²⁾}是该方程组的两个不动点。如果对于1≤i≤m,关系P_i⁽¹⁾都是关系P_i⁽²⁾的子集,则称S₁小于S₂,记作S₁<S₂。如果S₀是Datalog方程组的一个不动点,并且不存在其他不动点使得SS₀,则称是该Datalog方程组的一个极小不动点。Datalog方程组的最小不动点是满足如下条件的不动点:如果S是Datalog方程组的不动点,则SS₀。
对于不含否定词的Datalog规则,其导出方程的最小不动点是唯一存在的,它是可以使用规则由EDB关系导出(证明)的事实集。因此,不含否定词的Datalog规则的计算含义用最小不动点定义。
极小不动点可以迭代地求解。设P_i＝1_i(R₁,…,R_k,P₁,…,P_m)(1≤i≤m)是由一组Datalog规则导出的Datalog方程组,其中P₁,…,P_m是IDB谓词对应的关系,R₁,…,R_k是EDB谓词对应的关系,_i(R₁,…,R_k,P₁,…,P_m)定义在EDB关系R₁,…,R_k和IDB关系P₁,…,P_m上的关系表达式。该Datalog方程组的极小不动点可以用如下迭代过程计算: ①令P_i⁰＝{}(1≤i≤m);②对于j=0,1,…,反复地计算P_i^j+1＝_i(R₁,…,R_k,P₁^j,…,P_m^j) (1≤i≤m),直到对于所有的1≤i≤m,P_i^j+1＝P_i^j。{P₁^j,…,P_m^j}即为该Datalog方程组的极小不动点。当Datalog规则中不含否定词时,极小不动点是唯一的,{P₁^j,…,P_m^j}就是最小不动点。
用最小不动点定义Datalog规则的计算含义的方法可以推广到包含否定词的Datalog规则中。然而,如果不限制否定词的使用,则包含否定词的Datalog规则的不动点可能不存在。一种限制否定词使用的方法是要求包含否定词的Datalog规则必须是可分层的。一组规则是可分层的,如果规则中的谓词可以分成若干层,其中层是满足如下条件谓词的最大集合: ①如果谓词定义谓词p的规则含有非否定的子目标q(…),则p所在的层不低于q所在的层: ②如果谓词定义谓词p的规则含有否定的子目标q(…), 则p所在的层高于q所在的层。 对于可分层的包含否定词的Datalog规则,在求不动点时,可以由低层到高层,逐层对IDB谓词进行处理。在处理第i层时,低于第i层的IDB谓词被视为EDB谓词。这将产生规则的一个极小不动点——完美不动点(perfect fixed point),并用它定义规则的计算含义。
另一种处理否定的方法是用膨胀不动点(inflationary fixed point)定义规则的计算含义。膨胀不动点也可以迭代地计算,但是与计算极小不动点不同,一个事实一经导出就不再丢弃。即用P_i^j+1＝P_i^j∪_i(R₁,…,R_k,P₁^j,…,P_m^j) , 而 不 是 用P_i^j+1＝_i(R₁,…,R_k,P₁^j,…,P_m^j)迭代地计算P_i^j+1(1≤i≤m)。当规则中不含否定词时,关系代数表达式_i(1≤i≤m)都是单调的,
_i(R₁,…,R_k,P₁^j,…,P_m^j)=P_i^j∪_i(R₁,…,R_k,P₁^j,…,P_m^j)膨胀不动点就是最小不动点。然而,在一般情况下,膨胀不动点不一定是最小不动点,但它是极小的。膨胀不动点比分层否定具有更强的表达能力,但是当规则是可分层的时,用完美不动点定义规则的计算含义是更好的选择。
用不动点计算规则含义的方法还可以推广到谓词变元包含函数词的规则。然而,允许函数作为谓词的变元时,规则所定义的谓词可能是一个无限关系。这时,不可能通过有限次迭代计算逻辑程序的不动点。尽管如此,不动点很好地定义了逻辑程序的语义,并且无限关系中的任何元组都可以在不动点计算的有限步迭代得到。