网络百科 知识 递归查询是什么意思

递归查询是什么意思

递归查询 : 一种用递归的逻辑程序定义的查询或涉及递归 规则求值的查询。演绎数据库不仅需要处理非递归 查询,而且必须处理由逻辑规则表示的递归查询。 因此,递归查询和查询优化处理一直是演绎数据库 的重要特性和主要研究课题。传统数据库及关系查 询语言通常并不支持递归查询,而且在问题求解系 统中会生成无限的一阶语言,使执行效率降低。由 于低效一直是制约递归查询得以广泛应用的关键因 素,也是影响数据库效率的重要原因,因此近年来 人们对递归查询算法的研究十分关注,其研究集中 在递归查询的表达方式和寻求复杂度较低的查询优 化算法方面。
1.递归查询算法
递归(recursion)是将一个较大的问题归约到一 个或多个子问题的求解过程,这些子问题在结构上 与原问题相同,但子问题的求解比原问题简单。递 归算法用于演绎数据库的查询优化被称为递归查 询。常用的递归查询算法有:
(1)线性递归查询(linear recursive query): 递归 查询中的一个子类,它通过线性递归规则来实现查 询。该规则是指规则递归谓词在规则体中出现且仅 出现一次的规则。线性递归系统都是由所谓的独立 规则组成的。
(2)传递闭包查询(transitive closure query): 一 种基于传递闭包算法的递归查询方法。传递闭包查 询可定义为: 在一组规则中,若谓词p出现在规则 头为谓词q的规则的规则体中,则称p导出q,记 作p→q。这里,“→”是一种传递关系,则记→* 为→的传递闭包。传递闭包查询被认为是新一代数 据库系统应具备的重要操作,可应用于求解“最短 路径”等数学难题。常用的传递闭包算法有: ①迭 代算法(iterative algorithm): 包括半纯真、对数等传 递闭包算法,其特点是重复地计算某一关系代数表 达式,直至没有新的结果产生为止; ②直接算法 (direct algorithm): 包括基于矩阵和基于图的算法。 前者将传递闭包的计算转化为矩阵的表示与操作; 后者则将闭包的计算变为图的遍历求解问题。直接 算法的特点是对每一个元素(例如一个结点或一条 边)只计算一次;③混合型算法:综合各种传递闭包 算法而形成的一种传递闭包算法,用于递归查询, 如可以将基于矩阵和基于图的算法综合成一种混合 型的传递闭包算法。
(3) Datalog递归查询: 采用纯Horn子句的 Datalog语言实现的递归查询方法,包括: 可分 离(separable)、右线性(right linear)、可变换 (commutable)、可分解(factorable)等各种递归查询的 优化算法。
(4) 自底向上的递归优化(bottom-up recursive optimization):一种递归查询算法,又称为前向链接 (forward chaining)或不动点(fixpoint)算法。其作法 是: 从已知事实出发,不断地应用规则进行搜索, 直至获得查询结果。该算法一般都采用“一次一个 集合”的方法,它与Prolog所采用的“一次一个记 录”的方式正好对应。多数自底向上的递归算法是 魔集、半纯真算法的扩展。后来,J.F.Naughton等 人相继提出了“滑动式窗口制表”和“利用规则顺 序”等优化算法,前者用于克服存储空间开销大和 效率低的问题;而后者用来优化逻辑程序的不动点 求值问题。
2.递归查询的实现
递归查询的实现是通过构造递归谓词、递归规 则和递归逻辑程序来实现的。
(1)递归谓词: 指直接或间接地由自身定义的 谓词。如果存在一个规则r,其头部谓词为q,并且 谓词p出现在r的规则体中,则称谓词p导出谓词 q,记作p→q。令→+表示→的非自反的传递闭包, 即如果p→q,则p→+q; 如果存在谓词s使得p→s 且s→+q,则p→+q。如果p→+p,则称谓词p为递 归谓词; 否则,称p为非递归谓词。如果p→+q, 并且q→+p,则称p和q是相互递归的。
(2)递归规则: 指规则体中包含递归子目标的 规则。设规则r的头部谓词为q。如果与q相互递 归的谓词p出现在r的规则体中,则称规则r为递 归规则; 否则,称r为基本规则。如果r的规则体 中仅出现一个与q相互递归的谓词p,并且p仅在r 的规则体中出现一次,则称r为线性递归规则; 其 他递归规则称为非线性递归规则。
(3)递归逻辑程序: 简称递归(recursion)。如果 逻辑程序P包含递归规则,则称P是递归的逻辑程 序,简称递归。如果逻辑程序P包含递归规则,并 且所有递归规则都是线性的,则称P为线性递归程 序,简称线性递归。如果逻辑程序P包含非线性的 递归规则,则称P为非线性递归。
设逻辑程序P1包含如下规则:
r1:path(X,Y):-arc(X,Y)。
r2:path(X,Y):-arc(X,Z),path(Z,Y)。
谓词path是递归谓词,而谓词arc是非递归谓 词。规则r1是非递归规则,而规则r2是递归规则, 并且是线性的。这样,逻辑程序P1是一个递归,并 且线性递归。
如果又设逻辑程序P2包含如下规则:
r1:path(X,Y):-arc(X,Y)。
r3: path(X,Y):-path(X,Z),path(Z,Y)。
这里,规则r3是一个非线性递归规则,而逻辑 程序P2是一个非线性递归。
3.线性递归中的特殊子类
线性递归中有一些比较实用的特殊子类——右 线性递归、左线性递归和混合线性递归。这些递归 的定义都只涉及一个递归谓词,且该递归谓词与特 定的约束模式相关联。
如果一个递归逻辑程序只包含单个IDB谓词 p,并且它的所有规则或者是基本规则,或者是关于 约束模式α左线性的,则称该逻辑程序是关于约束 模式α左线性的,简称左线性递归。类似地,如果 一个递归逻辑程序只包含单个IDB谓词p,并且它 的所有规则或者是基本规则,或者是关于约束模式 α右线性的,则称该逻辑程序是关于约束模式α右线 性的,简称右线性递归。混合线性递归是既包含左 线性规则,又包含右线性规则的递归。
对于一个线性递归规则,不能简单地根据递归 子目标出现在规则体的左部还是右部来判断它是左 线性的还是右线性的,还必须考虑约束模式。
对前述递归规则r2,如果给定的约束模式为bf, 即规则r2头部的第一个变元是被约束的,而第二个 变元是自由的。这时,确实r2是右线性的,从而, 逻辑程序P1关于约束模式bf是右线性递归。但是, 如果给定的约束模式为fb,则在给定的子目标次序 下,r2的递归子目标path(Z,Y)约束模式为bb。因此, 关于约束模式fb,r2不是右线性的。然而,如果将 r2的递归子目标移到规则体的左部,得到:r′2:path(X, Y):-path(Z,Y),arc(X,Z),则r′2关于约束模式fb是 左线性的。而逻辑程序P1关于约束模式fb则是右 线性递归。

返回顶部