递归查询(数据库)

时间：2022-12-17 02:30:02 | 来源：信息时代

时间：2022-12-17 02:30:02 来源：信息时代

    递归查询 : 一种用递归的逻辑程序定义的查询或涉及递归规则求值的查询。演绎数据库不仅需要处理非递归查询,而且必须处理由逻辑规则表示的递归查询。因此,递归查询和查询优化处理一直是演绎数据库的重要特性和主要研究课题。传统数据库及关系查询语言通常并不支持递归查询,而且在问题求解系统中会生成无限的一阶语言,使执行效率降低。由于低效一直是制约递归查询得以广泛应用的关键因素,也是影响数据库效率的重要原因,因此近年来人们对递归查询算法的研究十分关注,其研究集中在递归查询的表达方式和寻求复杂度较低的查询优化算法方面。
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为非线性递归。
设逻辑程序P₁包含如下规则:
r₁:path(X,Y):-arc(X,Y)。
r₂:path(X,Y):-arc(X,Z),path(Z,Y)。
谓词path是递归谓词,而谓词arc是非递归谓词。规则r₁是非递归规则,而规则r₂是递归规则,并且是线性的。这样,逻辑程序P₁是一个递归,并且线性递归。
如果又设逻辑程序P₂包含如下规则:
r₁:path(X,Y):-arc(X,Y)。
r₃: path(X,Y):-path(X,Z),path(Z,Y)。
这里,规则r₃是一个非线性递归规则,而逻辑程序P₂是一个非线性递归。
3.线性递归中的特殊子类
线性递归中有一些比较实用的特殊子类——右线性递归、左线性递归和混合线性递归。这些递归的定义都只涉及一个递归谓词,且该递归谓词与特定的约束模式相关联。
如果一个递归逻辑程序只包含单个IDB谓词p,并且它的所有规则或者是基本规则,或者是关于约束模式α左线性的,则称该逻辑程序是关于约束模式α左线性的,简称左线性递归。类似地,如果一个递归逻辑程序只包含单个IDB谓词p,并且它的所有规则或者是基本规则,或者是关于约束模式α右线性的,则称该逻辑程序是关于约束模式α右线性的,简称右线性递归。混合线性递归是既包含左线性规则,又包含右线性规则的递归。
对于一个线性递归规则,不能简单地根据递归子目标出现在规则体的左部还是右部来判断它是左线性的还是右线性的,还必须考虑约束模式。
对前述递归规则r₂,如果给定的约束模式为bf,即规则r₂头部的第一个变元是被约束的,而第二个变元是自由的。这时,确实r₂是右线性的,从而,逻辑程序P₁关于约束模式bf是右线性递归。但是,如果给定的约束模式为fb,则在给定的子目标次序下,r₂的递归子目标path(Z,Y)约束模式为bb。因此,关于约束模式fb,r₂不是右线性的。然而,如果将r₂的递归子目标移到规则体的左部,得到:r′₂:path(X,Y):-path(Z,Y),arc(X,Z),则r′₂关于约束模式fb是左线性的。而逻辑程序P₁关于约束模式fb则是右线性递归。