演绎数据库语言(数据库)

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

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

    演绎数据库语言 : 演绎数据库提供给用户的一种实现演绎推理和智能查询的计算机语言,该语言一般是基于一阶谓词逻辑的。通常,这样的语言系统是由一个合式公式集、一个演绎推理系统和一个解释机制组成的。
1. 演绎数据库语言
常用的演绎数据库语言有:
(1) Prolog语言:是由马赛大学的A.Colmereaer和P.Roussel创立的。Prolog语言是一种逻辑程序语言,Prolog中客观世界的描述可表达为对象之间所有可能的关系,关系可以复合。逻辑语言的逻辑基础是一阶谓词逻辑,其操作语义是归结。Prolog程序是由Horn子句形式的规则和事实子句的集合。Prolog语言采用的控制策略是自顶向下、从左到右,带回溯的、深度优先搜索,其基本操作是匹配合一,可直接用于推理。
(2) OPS(official production system):是由卡内基-梅隆大学提出的一种基于规则的产生式知识处理系统。在演绎推理中,表示“如果A则B”的因果关系或推理关系的规则称为产生式规则。OPS逻辑语言家族已有OPS 1,…,OPS5、OPS5+、OPS83等多种版本,这种演绎数据库语言采用的是自底向上的控制策略。
(3) Datalog:是一种特殊形式的Horn子句所构成的演绎数据库语言,目前它已作为一种较好的逻辑知识表示语言,在演绎数据库、知识库和人工智能中广泛应用,并被称为Horn子句在这些领域中的专门Datalog版本。作为一种数据库语言,Datalog采用了类似于Prolog的记法,但与Prolog不同的是:①Datalog中的项仅由个体常量或个体变量组成而不允许使用函数作为变元;②Datalog程序的含义遵循模型论的解释,并且作为数据库语言或数据模型,它们还遵循证明论的解释;③Datalog是一种非过程语言,其规则或规则中子目标的书写次序并不决定它们的处理次序;④Datalog必须满足安全性规则。因为演绎数据库中,数据必须是有限的,必须对变量作量的限制,这就是Datalog安全性规则。以下重点介绍Datalog语言的特点与Datalog模型。
2. Datalog语言及其特点
Datalog是一个杜撰的词,意为“数据逻辑”,它既是一种数据库语言,又是一种逻辑程序设计语言。通常,可以将Datalog视为适合数据库操作的某种逻辑程序设计语言(如Prolog)的专门版本。Datalog语言的语法及重要特性如下:
(1) Datalog的基础数据模型是关系模型。在Datalog中,每个谓词都代表一个关系。通常谓词用以小写英文字母开始的字符串表示,而其对应的关系用大写英文字母开始的字符串表示。Datalog不对变元命名,谓词p的第i个变元对应于其对应关系P的第i列。如果一个谓词的对应关系存储在数据库中,则将该谓词称为外延数据库(EDB)谓词,其对应的关系为EDB关系。由规则定义的谓词称作内涵数据库(IDB)谓词,其对应的关系为IDB关系。
(2)原子公式是Datalog程序的基本单位。原子公式是一个带变元列表的谓词符号,如p(A₁,A₂,…,A_n),其中p是谓词符号,A₁,A₂,…,A_n是变元。在Datalog中,变元只能是变量或常量。通常,变元和常量分别用以大写或小写的英文字母开始的字符串表示。每个原子公式都对应一个关系,该关系是谓词对应关系的受限形式: ①如果原子公式中出现常量,则在常量出现的分量上做相等选择;②如果同一个变量出现多次,则在具有相同变量的分量上做相等选择。例如,原子公式emps(‘李明’,Salary,Dept)对应于关系σ_{＄1=‘李明’}(EMPS),其中,EMPS是谓词emps的对应关系。Datalog也使用算术比较运算符构造原子公式。算术比较运算符称作内部谓词(用中缀表示),其他谓词称作一般谓词。
(3) Datalog中的规则是一种Horn子句,并采用类似Prolog的记法,如,H:-B₁,B₂,…,B_n。其中,H为规则的头部,B₁,B₂,…,B_n为规则体,而B_i(1≤i≤n)为规则体中的子目标,它们是原子公式(正的子目标)或负的原子公式(负的子目标)。如果子目标B_i是内部谓词,则称B_i为内部子目标,否则B_i为一般子目标。该规则表示“如果B₁,B₂,…,B_n均为真,则H为真”。事实也可以看作规则,其规则体为空。
(4) Datalog程序由一组规则组成。如果Datalog程序定义了递归谓词,则它是递归的,否则是非递归的。如果p_i是IDB谓词,定义它的规则都是调整后的规则,则IDB谓词p_i对应的关系可以用一个关系代数表达式E_i表示。其基本方法是: 对每个以p_i为头部谓词的规则,将它的规则体关系投影到头部变量上,然后取它们的并。如果一个非递归的Datalog程序定义了m个IDB谓词,则可对这些IDB谓词确定一个次序p₁,p₂,…,p_m,使得当i<j时,p_i对应的关系p_i不在p_j的关系代数表达式E_i中出现。这样,可以依次计算p₁,p₂,…,p_m对应的关系p₁,p₂,…,p_m。如果Datalog程序是递归的,则IDB谓词对应的关系必须通过求不动点得到。
(5) Datalog是高度非过程化的语言,其规则的书写次序和规则体中子目标的书写次序都不决定它们的实际执行次序,并且不含诸如cut和fail等与逻辑不协调的操作。此外,对于递归查询,采用自顶向下还是自底向上处理,由系统自动进行选择。而其他逻辑语言,只支持自顶向下(如Prolog)或自底向上(如OPS5)的求值。
(6)提高Datalog表达能力。其能力一是体现在允许在规则中出现否定子目标; 二是能处理集合值变量。但是,如果不限制否定词的使用,会导致不动点不存在。处理否定的方法有:①采用分层否定:一个逻辑程序是分层的,如果它的所有谓词都可以赋予一个非负整数秩,使得任何谓词都不否定地依赖具有相等或较高秩的其他谓词。对于分层的逻辑程序,可以逐层处理,得到它的一个极小不动点,并用它定义规则的计算含义。引入分层否定后,Datalog的表达能力比关系代数强。②用局部分层处理否定: 局部分层把对谓词的限制进一步扩充到函数词和常量: ③用膨胀不动点处理否定: 在计算不动点时,一个事实一旦导出就不再丢弃。膨胀不动点比分层否定具有更强的处理否定的能力,但是当逻辑程序是分层的时,分层否定是更自然的选择。通常,提高Datalog表达能力还可采用限制集合值变量、使用嵌套关系、允许变元中出现函数词等措施。
3. Datalog数据模型
智能数据库和管理信息系统用于决策支持的需求,使人们将演绎数据库、知识库的研究转向了提高数据库中“逻辑规则”的表达能力和查询优化方面。为适应在知识库中表示知识,要对Horn子句作一些必要的限制,在逻辑规则方面,就出现了基于逻辑的Datalog数据模型。这种演绎数据模型提供了递归定义能力,具有比关系数据模型更强的表达能力,包括定义复杂的数据模型,更强的数据操纵能力,支持更完善的完整性约束条件,并最终提供一个具有数据操纵与宿主语言功能的统一的说明性语言。
Datalog数据模型是用一系列关系代数操作实现的。与Prolog不同的是:Datalog程序的含义应遵循模型论的观点; 或者,当它们等价时,也遵循证明论的观点。然而,Prolog所具有的计算性含义在某些情况下可能既偏离模型论,又偏离了证明论。
本质上,Datalog数据模型的数学基础与关系模型是相同的。在Datalog中,谓词符号表示关系。然而,如同关系代数的形式定义一样,通常未用属性对这些关系的列命名。它们是列表集合意义下的关系,分量以固定的顺序出现,对列的访问仅通过给定谓词符号的自变元中的位置来进行。例如,若p是一个三元谓词符号,可以用p(X,Y,Z)表示它,而变量X指示谓词p的对应关系中的某个元组的第一分量。
对Datalog数据模型,涉及对datalog不动点的语义、半朴素求解、带有否定的逻辑、分层规则和魔集技术的研究,其中尤以魔集重写技术、魔谓词、魔集变换、魔集规则约简、广义魔集等研究成果较突出。而在逻辑规则及知识表示和查询优化研究方面也取得较大进展。如Solomon证明查询优化问题是不可判定的,M.J.Maher和Y.Sagiv在逻辑程序的合取查询方面,提出了逻辑程序的等价、判定方法和包含问题; A.Klug给出了内部谓词中有不等式时的合取查询包含问题等成果。此外,在线性递归优化方面,也有右线性递归、混合线性递归、传递闭包和闭半回路中的传递闭包,以及将非线性转化为线性递归的方法。