Polynomial-time program transformations in deductive databases

ABSTRACT

We investigate the complexity of various optimization techniques for logic 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 NP-hardness. To this end, we define the k-containment problem on conjunctive queries, and show that while the 2-containment problem is in P, the 3-containment problem is NP-complete. These results provide a complete description of the complexity of conjunctive query containment. We also extend these results to provide a natural characterization of certain optimization problems in logic databases, such as the detection of sequencability and commutativity among pairs of Linear rules, the detection of 1-boundedness in sirups, and the detection of ZYT-linearizability in simple nonlinear recursions.

REFERENCES

• 1: Aho, A. V., Y. Sagiv and :I. D. Ulllational expressions," SIAM J. Comp. 8, pp. 218-246.
• 2: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 3: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• 4: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• 5: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 6: Ioannidis, Y.E. {1989a}. "Towards an algebraic theory of recursion," TR-801, Dept. of C.S., University of Wisconsin. ._
• 7: ioannidis, Y.E. {19895}. "C0mmutativity and its role in the processing of linear recursion," TR-804, Dept. of C.S., University of Wisconsin.
• 8: Johnson, D. S. and A. Klug {1983}. "Optimizing conjunctive queries that contain untyped variables," SIAM J. Comp. 12, pp. 616-640.
• 9: P. C. Kanellakis, Logic programming and parallel complexity, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 10: Jeffrey F. Naughton, Compiling separable recursions, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.312-319, June 01-03, 1988, Chicago, Illinois, United States
• 11: R. Ramakrishnan , Y. Sagiv , J. D. Ullman , M. Y Vardi, Proof-tree transformation theorems and their applications, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.172-181, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73739]
• 12: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 13: Domenico Saccà , Carlo Zaniolo, On the implementation of a simple class of logic queries for databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.16-23, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.6013]
• 14: Y. P. Saraiya, Linearising nonlinear recursions in polynomial time, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.182-189, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73740]
• 15: Unman, J. D. {1989}. Principles of Database and Knowledgebase Systems, V01. II, Computer Science Press, Rockville, Md.
• 16: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 17: Zhang, W., C.T. Yu and D. Troy, "A necessary and sufficient condition to linearize doubly recursive programs in logic databases," unpublished manuscript, Dept. of EECS, University of Illinois at Chicago.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Algorithms, Design, Management, Performance, Theory, Verification