演绎数据库系统(数据库)

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

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

    演绎数据库系统 : 一种具有逻辑运算和演绎推理能力的数据库系统。按照J.D.Ullman的观点,一个演绎数据库应是这样的程序系统: ①有一种说明式语言,即多种可能形式之一的逻辑,用作宿主语言和查询语言; ②具有DBMS的主要功能,能有效存取大量数据、实现数据共享和对数据的并行存取与故障恢复等功能。多年来,演绎数据库一直沿着这个研究方向在努力,并相继产生了一些试验性的系统。
1. NAIL! 系统
NAIL!是斯坦福大学的J.D.Ullman及其学生开发的一个试验性演绎数据库系统。该项目的主要目标是研究逻辑查询优化。图1为NAIL! 系统的结构。NAIL!的源代码采用类似Prolog符号书写,规则必须是安全的,并采用分层否定。源程序经预处理后被编译成内部表,并将谓词划分成强连通成分(SCC)。一个SCC可以是单个非递归谓词(IDB或EDB),或者是相互递归的谓词的最小集。
一旦规则被编译,系统将接受查询。查询是一个谓词,其中变元可以是常量或变量。SCC将决定如何处理一组逻辑规则。对于被修饰的目标Pa,NAIL!系统将为计算p关系的相关部分选择一个策略。给定被修饰的目标Pa,策略选择算法开始为p的SCC构造一个规则/目标图,所有不在p的SCC中的谓词都作为EDB子目标处理。如果成功地构造了一个规则/目标图,就考察所有外部的被修饰目标——其谓词在p的SCC之外的那些目标。再通过策略选择算法,为每一个外部目标选择一种策略。由于外部目标处在低于p的层次,因此必将最终到达某一点,在那里只有被修饰的EDB目标和内部算术目标要处理。这些目标是平凡的,或者成功,或者失败。失败时需回溯,并导致重新构造规则/目标图。

图1 NAIL!的结构

查询时要确定一个被修饰目标,并由捕获规则决定采用什么策略。每个捕获规则对应于一个计算逻辑规则的算法,如“左线性递归”、“魔集”。捕获规则由检测算法和执行算法两部分代码组成,最后由执行算法产生内部中间代码(ICODE)来计算与该目标匹配的元组。查询中捕获规则的测试部分将依次被测试,直到成功。例如,线性递归的Datalog类可能依次含有左线性、右线性、左右混合线性、计数线性和魔集等策略的捕获规则。当NAIL!为一个给定的被修饰目标发现一个策略时,它将决定放入策略数据库。下次遇到同样的被修饰目标,即使约束关系不同,也不必重新选择,而是在该数据库中查找适当的策略。为了避免重复漫无目标的搜索,策略数据库中也存放否定的事实,指出找不到可用于处理某特定被修饰目标Pa的捕获规则。查询是否成功的策略通过一个称作ICODE的语言程序来实现和回答。该语言由一些关系代数操作(选择、投影、积、并、差和各种连接)语句组成。除并和差之外,其余都能以Prolog规则形式的ICODE语句实现。ICODE还具有控制流的特点。
NAIL!系统以SQL数据库为基础,用于实现传统的DBMS功能,并将实际数据存于SQL数据库中,此外还在NAIL!系统的后端加入了一种过程式语言Glue作为控制结构,将其与NAIL!混合使用,以提高系统性能。
2. LDL(logic data language)系统
LDL系统是由美国Texas州奥斯汀的MCC开发,其系统结构和目标类似于NAIL!。它不仅是一个逻辑处理系统,也是一个完整的DBMS。在LDL中,规则被译成一种叫做谓词连接图的内部形式(规则中允许函数符号,而否定必须是分层的),经过广泛的查询优化处理后,规则被译成一种称为FAD的中间代码。这种语言类似于NAIL! 的ICODE,基本上是关系代数的扩充,使之具有处理函数符号和控制流的能力。
LDL的查询优化程序在响应含有被约束变元和自由变元的查询时,要回答该查询所需的所有谓词的约束模式,而不需要重新确定子目标的次序。但在执行规则的半朴质计算时,LDL也同NAIL! 一样,需要考虑对应于子目标的关系连接次序。LDL确定了约束模式后,将为查询改写规则。这时,可采用魔集、左线性或右线性规则等变换来实现。实用中可优先选择左线性或右线性变换,且计数变换优先于魔集。同时在变换之后,应采用半朴质方法自底向上地计算结果规则。LDL还提供了一种“推进投影变换”规则改写技术,能在自底向上的查询计算中,尽早地去掉最终将被投影掉的谓词分量。
对于变换后的规则,LDL采用了魔集规则化简的方法对规则进行化简,结果导致规则体增长。由于规则体的计算涉及子目标间关系的连接,因此重新确定子目标的次序对于提高规则的求值效率十分重要。为此,LDL采用了一种在无环超图上实现的穷举搜索算法。
3.其他的演绎数据库试验系统
如下为一些有名的试验性演绎数据库:
(1) 由Y.Dahl采用Prolog语言实现的一种SOLARS16,系统具有DBMS的诸多功能和提供一种交会式语言,而在演绎推理、智能检索方面也独具特色。
(2)俄亥俄州州立大学开发的医学演绎数据库系统MEDICAL IDABLE,该系统包括一个解剖学模型,可回答用户的各种提问。
(3)美国加州大学伯克利分校研制的POSTQUEL系统:是对Ingres的查询语言QUEL的扩充,可用关键字retrieve^*标明一个检索的重复执行,并模拟Datalog规则的递归查询。
(4)问题回答系统(question answering system):系统能用自然语言进行问答,具有较高智能。系统中的演绎系统,能理解自然语言并将其转换成形式语言(如谓词演算等),也能将形式语言转换成自然语言。同时系统有完善的信息检索系统,能对存储在数据库中的各种事实进行逻辑演绎推理,以得到所需要的具体答案。
(5) 由马里兰大学J.Minker等采用谓词演算方法实现的马里兰反演证明过程系统(MRPPS)(见图2)。

图2 马里兰反演证明过程系统(MRPPS)

综上所述,作为智能数据库初级阶段的演绎数据库迄今还一直停留在试验和原型化阶段,还没有商品化的演绎数据库系统问世。就其原因,主要是基于逻辑数据模型的演绎数据库采用的递归查询算法的计算效率很低。因此,提高演绎数据库的查询效率,实现查询优化与智能检索和完善演绎数据库的各种算法等,多年来一直是演绎数据库研究领域面临的主要问题。此外,基于Horn逻辑的语言如何有效实现、演绎数据库的计算传递闭包算法能否用更加简便的递归查询计算来代替等问题,也都需要进行更加深入的研究。而且,演绎数据库至今并未能流行起来,还与演绎数据库缺乏应用需求的强力推动有着密切的关系。随着人工智能、计算智能(神经网络、遗传算法、模糊逻辑)、数据挖掘与知识发现、Web数据库和Agent等技术的飞速发展,人们期盼演绎数据库、知识库等智能数据库技术取得突破性进展。