时间：2022-12-03 02:30:02 | 来源：信息时代
时间：2022-12-03 02:30:02 来源：信息时代
演绎数据库查询 : 演绎数据库中采用关系代数或传递闭包算法实现演绎推理的一种智能查询算法,包括非递归查询与递归查询。非递归查询(nonrecursive query)指可以直接用关系代数操作来表示和实现的查询,其含义是: 如果定义查询谓词的规则集不含递归规则,则查询谓词对应的关系可以用EDB关系的关系代数表达式来表示,从而可以用关系代数操作来实现该查询。如果定义查询谓词的规则集中含有递归规则,则称该查询为递归查询(recursive query),除非引入诸如传递闭包操作等新的运算,否则递归查询不能用关系代数表示。
1. 查询的表示形式
在演绎数据库中,查询用一组逻辑规则和一个形如p(…)的表达式表示,其中p为查询谓词,它的某些变元可能是被约束的,而另一些是变量。如果查询谓词p是EDB谓词,其对应的关系存储在数据库中,该查询可以简单地用关系代数操作实现。如果查询谓词p是IDB谓词,并且定义p的逻辑程序是递归的(即包含递归规则),则称该查询为递归查询,否则称它为非递归查询。例如,要查询ancestor(‘张华’,Y)?求“张华”的祖先Y,其中查询谓词ancestor可由以下规则定义:
ancestor(X,Y):-parent(X,Y)。
ancestor(X,Y):-parent(X,Z),ancestor(Z,Y)。
其中parent是EDB谓词,其对应的关系为PARENT。由于谓词ancestor是递归定义的,因此这是一个递归查询,需要通过计算不动点得到查询的回答。而如要查询grandfather(‘张华’,Y)?求“张华”的祖父Y,其中查询谓词grandfather由规则:grandfather(X,Y):-father(X,Z),father(Z,Y).来定义。其中father是EDB谓词,其对应关系为FATHER。该查询是非递归查询,因为定义查询谓词grandfather的规则是非递归的。
2.关系代数的基本操作
关系代数只能表示非递归查询。每个关系代数表达式表示的查询都可以用非递归的逻辑程序表示。设关系代数表达式可以用并、差、笛卡儿积、投影和选择五种基本操作表示。对于一个给定的关系代数表达式E,可以使用如下方法将其用逻辑规则来表示:
(1) E=E1∪E2,其中E1和E2都是n元关系。设谓词e、e1和e2对应的关系分别为E、E1和E2,则表达式E有如下规则:
e(X1,X2,…,Xn):-e1(X1,X2,…,Xn)。
e(X1,X2,…,Xn):-e2(X1,X2,…,Xn)。
(2) E=E1-E2,其中E1和E2都是n元关系。设谓词e、e1和e2对应的关系分别为E、E1和E2,则表达式E有如下规则:e(X1,X2,…,Xn):-e1(X1,X2,…,Xn),～e2(X1,X2,…,Xn)。
(3) E=E1×E2,其中E1是n元关系,而E2是m元关系。设谓词e、e1和e2对应的关系分别为E、E1和E2,则表达式E有如下规则:e(X1,X2,…,Xn,Xn+1,Xn+2,…,Xn+m):-e1(X1,X2,…,Xn),～e2(Xn+1,Xn+2,…,Xn+m)。
(4) E=πil,…,ik(E1),其中E1是n元关系。设谓词e和e1对应的关系分别为E和E1,则表达式E有如下规则:e(Xi1,…,Xik):-e1(X1,X2,…,Xn)。
(5) E=σF(E1),其中E1是n元关系,F是一个简单选择。如果F为＄iθ＄j(θ为算术比较运算符),表示E的第i个分量与第j个分量进行θ比较,则表达式E有如下规则:e(X1,X2,…,Xn):-e1(X1,X2,…,Xn),XiθXj。
类似地,如果F为＄iθc或cθ＄j(c为常量),则表达式E有如下规则:e(X1,X2,…,Xn):-e1(X1,X2,…,Xn),Xiθc.或e(X1,X2,…,Xn):-e1(X1,X2,…,Xn),cθXj。
如果E1和E2还包含关系运算,可以使用以上方法对它们继续处理。最终得到一组定义谓词e的规则,谓词e对应的关系就是关系代数表达式E表示关系。
在线咨询
