On the Complexity of Single-Rule Datalog Queries | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the Complexity of Single-Rule Datalog Queries

  • Conference paper
Logic for Programming and Automated Reasoning (LPAR 1999)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 1705))

Abstract

Datalog is a well-known database query language based on the logic programming paradigm. A general datalog program consists of a number of rules and facts. Programs containing a unique rule and possibly some facts are called single rule programs (sirups). We study both the combined and the program complexity of sirups, ie., the complexity of evaluating sirups over variable and fixed databases, respectively. Moreover, we study the descriptive complexity of sirups, i.e., their expressive power. In all cases it turns out that even very restricted classes of sirups have the same complexity and essentially the same expressive power as general datalog programs. We show that the evaluation of single clause programs is EXPTIME complete (combined complexity), and, if restricted to linear recursive rules, PSPACE complete. Moreover, sirups with one recursive rule and one additional fact capture PTIME on ordered structures, if a certain data representation is assumed and certain predefined relations are provided. Our results are obtained by a uniform product construction which maps a datalog program into a single rule by essentially maintaining its semantics. We also prove that the datalog clause implication problem, i.e., deciding whether a datalog clause implies another one, is EXPTIME complete.

This work was done while this author was on leave from the Institut für Informationssysteme, TU Wien, Austria. Gottlob’s work was supported by the Austrian Science Fund Project Z29-INF and by a McKay Lectureship of UC Berkeley.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S. Aanderaa. On the Decision Problem for Formulas in which all Disjunctions are binary. Proc. of the 2nd Scandinavian Logic Symposium, pp. 1–18, North Holland Publishing Company, 1971.

    Google Scholar 

  2. S. Abiteboul. Boundedness is undecidable for datalog programs with a single recursive rule. Information Processing Letters, 32(6):281–289, 1989.

    Article  MATH  MathSciNet  Google Scholar 

  3. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.

    Google Scholar 

  4. F. Afrati and C. H. Papadimitriou. The parallel complexity of simple logic programs. Journal of the Association for Computing Machinery, 40(4):891–916, 1993.

    MATH  MathSciNet  Google Scholar 

  5. E. Börger Reduktionstypen in Krom-und Hornformeln. Ph.D. Dissertation, Minister, Germany, 1971.

    Google Scholar 

  6. E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer, Berlin Heidelberg, 1997.

    MATH  Google Scholar 

  7. S. Ceri, G. Gottlob, and L. Tanca. Logic Programming and Databases. Surveys in Computer Science. Springer Verlag, 1990.

    Google Scholar 

  8. A. K. Chandra, H. Lewis, and J. Makowsky. Embedded implicational dependencies and their inference problem. In ACM Symposium on Theory of Computing (STOC), pages 342–354, 1981.

    Google Scholar 

  9. A. Chandra and P. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proc. Ninth ACM Symposium on the Theory of Computing, pages 77–90, 1977.

    Google Scholar 

  10. E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. In Proceedings Twelfth Annual IEEE Conference on Computational Complexity, pages 82–101, Ulm, Germany, June 1997. Full version available from the authors.

    Google Scholar 

  11. P. Devienne, P. Lebègue, and J.-C. Routier. Halting problem of one binary Horn clause is undecidable. In P. Enjalbert, A. Finkel, and K. Wagner, editors, Proceedings Tenth Symposium on Theoretical Aspects of Computing (STACS-93), number 665 in LNCS, pages 48–57, Würzburg, February 1993. Springer.

    Google Scholar 

  12. H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Perspectives in Mathematical Logic. Springer, 1995.

    Google Scholar 

  13. M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proc. 5th International Conference and Symposium on Logic Programming, pages 1070–1080. The MIT Press, 1988.

    Google Scholar 

  14. G. Gottlob. Subsumption and implication. Information Processing Letters, 24(2):109–111, 1987.

    Article  MATH  MathSciNet  Google Scholar 

  15. E. Grädel. The Expressive Power of Second-Order Horn Logic. In Proceedings STACS-91, LNCS 480, pages 466–477, 1991.

    Chapter  Google Scholar 

  16. E. Grädel. Capturing Complexity Classes with Fragments of Second Order Logic. Theoretical Computer Science, 101:35–57, 1992.

    Article  MATH  MathSciNet  Google Scholar 

  17. Y. Gurevich. Logic and the Challenge of Computer Science. In E. Börger, editor, Trends in Theoretical Computer Science, chapter 1. Computer Science Press, 1988.

    Google Scholar 

  18. P. Hanschke and J. Würtz. Satisfiability of the smallest binary program. Information Processing Utters, 45(5):237–241, 1993.

    Article  MATH  Google Scholar 

  19. G. G. Hillebrand, P. C. Kanellakis, H. G. Mairson, and M. Y. Vardi. Undecidable boundedness problems for datalog programs. Journal of Logic Programming, 25(2):163–190, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  20. N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86–104, 1986.

    Article  MATH  MathSciNet  Google Scholar 

  21. N. Immerman. Descriptive Complexity Theory. Springer, 1998 (to appear).

    Google Scholar 

  22. P. Kanellakis. Logic programming and parallel complexity. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 547–586. Morgan Kaufmann, 1988.

    Google Scholar 

  23. J. U. Kietz, S. Dzeroski. Inductive Logic Programming and Learnability. SIGART Bulletin 5(1), pp. 22–32,1994.

    Article  Google Scholar 

  24. H. Lewis. Krom Formulas with One Dyadic Predicate Letter. Journal of Symbolic Logic, 46(2):341–362, 1976.

    Google Scholar 

  25. J. Marcinkowski. The 3 frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG programs. In ACM Symposium on Theory of Computing (STOC), volume 1046 of Lecture Notes in Computer Science, pages 427–438. Springer Verlag, 1996.

    Google Scholar 

  26. J. Marcinkowski. DATALOG SIRUPs uniform boundedness is undecidable. In Proc. IEEE Conference on Logic in Computer Science (LICS), pages 13–24. IEEE Computer Society Press, 1996.

    Google Scholar 

  27. J. Marcinkowski and L. Pacholski. Undecidability of the Horn-clause implication problem. In Proc. IEEE International Conference of Foundations of Computer Science (FOCS), pages 354–362. IEEE Computer Society Press, 1992.

    Google Scholar 

  28. L. J. Stockmeyer. The Polynomial-Time Hierarchy. Theoretical Computer Science, 3:1–22, 1977.

    Article  MATH  MathSciNet  Google Scholar 

  29. J. D. Ullman and A. van Gelder. Parallel complexity of logical query programs. Algorithmica, 3:5–42, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  30. J. Ullman. Database and Knowledge-Base Systems, volume I. Computer Science Press, 1988.

    Google Scholar 

  31. J. Ullman. Database and Knowledge-Base Systems, volume II. Computer Science Press, 1989.

    Google Scholar 

  32. M. Vardi. Complexity of Relational Query Languages. In Proceedings 14th STOC, pages 137–146, San Francisco, 1982.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Division, Dept of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA, 94720

    Georg Gottlob & Christos Papadimitriou

Authors
  1. Georg Gottlob
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christos Papadimitriou
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Max-Planck-Institut für Informatik, Im Stadtwald, D-66123, Saarbrücken, Germany

    Harald Ganzinger

  2. AT&T Labs Research, 180 Park Ave, Florham Park, NJ, 07932-0971, USA

    David McAllester

  3. Department of Computer Science, University of Manchester, Oxford Road, M13 9PL, Manchester, UK

    Andrei Voronkov

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gottlob, G., Papadimitriou, C. (1999). On the Complexity of Single-Rule Datalog Queries. In: Ganzinger, H., McAllester, D., Voronkov, A. (eds) Logic for Programming and Automated Reasoning. LPAR 1999. Lecture Notes in Computer Science(), vol 1705. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48242-3_13

Download citation

  • DOI: https://doi.org/10.1007/3-540-48242-3_13

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-66492-5

  • Online ISBN: 978-3-540-48242-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics