On the Efficiency of Transforming Database Logic Programs

摘要

We investigate the complexity of various optimization techniques for deductive databases. In particular, we provide polynomial-time algorithms for restricted versions of common program transformations, and show that a minor relaxation of these restrictions leads to N P-hardness. To this end, we define the k-containment problem on conjunctive queries and show that while the two-containment problem is in P (and in NLOGSPACE for function-free queries), the three-containment problem is N P-complete. These results provide a complete description of the complexity of conjunctive query containment. We extend this description to provide a natural characterization of certain optimization problems in deductive databases, such as the detection of serializability and commutativity among pairs of linear rules, the detection of one-boundedness in sirups, and the detection of basis-linearizability in simple nonlinear recursions.