Optimizing datalog programs
Optimizing datalog programs
复制标题
优化数据记录程序
DOI：
10.1145/28659.28696
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
Y. Sagiv
中科院分区：
文献类型：
--
作者：
Y. Sagiv
数据记录程序，即没有函数符号的PROLOG程序，被认为是假设出现在规则头部的变量也必须出现在规则正文中。程序的输入是一组基本原子(除了程序规则之外还给出了这些原子)，因此可以被视为与程序的一些谓词之间的关系赋值。如果两个程序为所有可能的关系分配产生相同的结果，则两个程序是等价的。如果两个程序对所有谓词(即，外延的和有意的)初始关系的所有可能赋值产生相同的结果，则两个程序一致等价。众所周知，Datalog程序的等价性问题是不可判定的。证明了一致等价是可判定的，并给出了在一致等价条件下最小化Datalog规划的一个算法。开发了一种删除程序中在等价(但不是一致等价)下冗余的部分的技术。在数据库满足一定约束的情况下，给出了一致等价性的判定方法。
Datalog programs, i.e., Prolog programs without function symbols, are considered It is assumed that a variable appearing in the head of a rule must also appear in the body of the rule. The input of a program is a set of ground atoms (which are given in addition to the program's rules) and, therefore, can be viewed as an assignment of relations to some of the program's predicates. Two programs are equivalent if they produce the same result for all possible assignments of relations to the extensional predicates (i.e., the predicates that do not appear as heads of rules). Two programs are uniformly equivalent if they produce the same result for all possible assignments of initial relations to all the predicates (i.e., both extensional and intentional). The equivalence problem for Datalog programs is known to be undecidable. It is shown that uniform equivalence is decidable, and an algorithm is given for minimizing a Datalog program under uniform equivalence. A technique for removing parts of a program that are redundant under equivalence (but not under uniform equivalence) is developed. A procedure for testing uniform equivalence is also developed for the case in which the database satisfies some constraints.