Knowledge compilation = query rewriting + view synthesis

ABSTRACT

In Knowledge Compilation (KC) an intractable deduction problem KB ⊨ f is split into two phases: 1) KB is preprocessed, thus obtaining a data structure DKB; 2) the problem is efficiently solved using DKB and f. Our goal is to study KC in the context of relational databases: Both KB and f are represented as databases, and '⊨' is represented as a query Q in second-order logic. DKB is a database, to be synthesized from KB by means of an appropriate view. Q is rewritten, thus obtaining Qr. We show syntactic restrictions on Q implying that a polynomial-size DKB and a first-order Qr exist, which imply that phase 2 can be done in polynomial time. We also present classes of queries (in some sense complementary to the former ones) for which either no polynomial-size DKB or no first-order Qr exist (unless the PH collapses). Compilation to other complexity classes is also addressed.

REFERENCES

• 1: Rachel Ben-Eliyahu , Rina Dechter, Default reasoning using classical logic, Artificial Intelligence, v.84 n.1-2, p.113-150, July 1996 [doi>10.1016/0004-3702(95)00095-X]
• 2: Marco Cadoli , Francesco M. Donini, A survey on knowledge compilation, AI Communications, v.10 n.3-4, p.137-150, Dec. 1997
• 3: M. Cadoli, F. M. Donini, P. Liberatore, and M. Schaerf. Preprocessing of intractable problems. Technical Report DIS 24-97, Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza", November 1997. To appear in Information and Computation.
• 4: Marco Cadoli , Francesco M. Donini , Marco Schaerf, Is intractability of nonmonotonic reasoning a real drawback?, Artificial Intelligence, v.88 n.1-2, p.215-251, Dec. 1996 [doi>10.1016/S0004-3702(96)00009-4]
• 5: A. K. Chandra and G. Markowsky. On the number of prime implicants. Discrete Mathematics, 24:7-11, 1978.
• 6: A. Darwiche and P. Marquis. A perspective on knowledge compilation. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI 2001), pages 470-475, 2001.
• 7: Thomas Eiter , Georg Gottlob, Propositional circumscription and extended closed-world reasoning are &Pgr;p2-complete, Theoretical Computer Science, v.114 n.2, p.231-245, June 21, 1993 [doi>10.1016/0304-3975(93)90073-3]
• 8: R. Fagin. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. In R. M. Karp, editor, Complexity of Computation, pages 43-74. AMS, 1974.
• 9: G. Gogic, H. A. Kautz, C. Papadimitriou, and B. Selman. The comparative linguistics of knowledge representation. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI'95), pages 862-869, 1995.
• 10: G. Gottlob , P. G. Kolaitis , T. Schwentick, Existential second-order logic over graphs: charting the tractability frontier, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.664, November 12-14, 2000
• 11: Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804678]
• 12: H. A. Kautz and B. Selman. Forming concepts for fast inference. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI'92), pages 786-793, 1992.
• 13: Phokion G. Kolaitis , Madhukar N. Thakur, Logical definability of NP optimization problems, Information and Computation, v.115 n.2, p.321-353, Dec. 1994 [doi>10.1006/inco.1994.1100]
• 14: V. Lifschitz. Computing circumscription. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI'85), pages 121-127, 1985.
• 15: Jack Minker, On Indefinite Databases and the Closed World Assumption, Proceedings of the 6th Conference on Automated Deduction, p.292-308, June 07-09, 1982
• 16: Yoram Moses , Moshe Tennenholtz, Off-line reasoning for on-line efficiency: knowledge bases, Artificial Intelligence, v.83 n.2, p.229-239, June 1996 [doi>10.1016/0004-3702(95)00015-1]
• 17: Anil Nerode , Raymond T. Ng , V. S. Subrahmanian, Computing circumscriptive databases, I: theory and algorithms, Information and Computation, v.116 n.1, p.58-80, Jan. 1995 [doi>10.1006/inco.1995.1005]
• 18: Bart Selman , Henry Kautz, Knowledge compilation and theory approximation, Journal of the ACM (JACM), v.43 n.2, p.193-224, March 1996 [doi>10.1145/226643.226644]
• 19: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 20: Marianne Winslett, Updating logical databases, Cambridge University Press, New York, NY, 1991

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Languages, Theory

Keywords:
complexity, deductive databases., logic in databases