Subtree-Elimination Algorithms in Deductive Databases.

A deductive database consists of a set of stored facts, and a set of logical rules 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. We 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. We investigate the complexity of detecting such optimization opportunities, and provide correct but not always complete algorithms for this purpose. Each of the problems that are mentioned above may be described in terms of the subtree-elimination problem, which we define and analyze. We relate the detection of basis-linearizability, sequencability and 1-boundedness to the complexity classes NC, P and NP, and show that the first two of these problems are, in general, undecidable. The techniques used in our analysis provide a complete description of the complexity of deciding the equivalence of conjunctive queries single-rule, non recursive programs.