Subtree-Elimination Algorithms in Deductive Databases

摘要

A deductive database consists of a set of stored facts, and a set of logicalrules (typically, recursive Horn clauses) that are used to manipulate these facts. A number of optimizations in such databases involve the transformation of sets of logical rules (programs) to simpler, more efficiently evaluable programs. The authors consider a class of optimizations in which the transformation is a simple syntactic restriction on the form of the original program, and in which the correctness of the transformation indicates the existence of a normal form for the proof trees generated by the program. For example, the existence of basis-linearizability in a nonlinear program indicates that the program is inherently linear, and permits the use of special-purpose query evaluators for linear recursions. The canonical example of a basis-linearizable program is the program that computes the transitive closure of a binary relation; the corresponding normal form for the proof trees is that of right-linearity. Similarly, if a program is sequencable, then it is conducive to a pipelined evaluation. In addition, the existence of k-boundedness in a program permits the elimination of recursion overhead in evaluating the program. The authors investigate the complexity of detecting such optimization opportunities, and provide correct (but not always complete) algorithms for this purpose. The techniques used in the authors' analysis provide a complete description of the complexity of deciding the equivalence of conjunctive queries (single-rule, nonrecursive programs), and tight undecidability results for the detection of program equivalence.