Complexity of query answering in logic databases with complex values | SpringerLink
Skip to main content
Springer Nature Link
Log in

Complexity of query answering in logic databases with complex values

  • Conference paper
  • First Online:
Logical Foundations of Computer Science (LFCS 1997)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1234))

Included in the following conference series:

Abstract

This paper studies the complexity of the query answering problem in logic databases with complex values. Logic databases are represented as Horn clause logic programs; complex values are described in a data model based on equational theories. As examples of complex values, we consider trees, bags and finite sets. We give a natural sufficient condition under which the query answering problem for non-recursive programs with complex values is in NEXP. In particular, logic programs with trees, bags and finite sets satisfy this condition. We also show that the query answering problem for non-recursive range restricted logic programs is NEXP-hard. Thereby, the query answering problem for logic databases with trees, bags and sets turns out to be NEXP-complete.

Supported by grants from the Swedish Royal Academy of Sciences, the Swedish Institute and RFBR/INTAS.

Supported by a TFR grant.

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. Abiteboul and S. Grumbach. A rule-based language with functions and sets. ACM Transactions on Database Systems, 16(1):1–30, 1991.

    Google Scholar 

  2. S. Abiteboul and C. Beeri. The power of languages for the manipulation of complex values. VLDB Journal, 4:727–794, 1995.

    Google Scholar 

  3. K.R. Apt. Logic programming. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B: Formal Methods and Semantics, chapter 10, pages 493–574. Elsevier Science, Amsterdam, 1990.

    Google Scholar 

  4. C. Beeri, S. Naqvi, O. Schmueli, and S. Tsur. Set constructors in a logic database language. Journal of Logic Programming, 10:181–232, 1991.

    Google Scholar 

  5. B. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer Verlag, 1997.

    Google Scholar 

  6. E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. In CCC'97, 1997. To appear.

    Google Scholar 

  7. E. Dantsin and A. Voronkov. Complexity of query answering in logic databases with complex values. UPMAIL technical report, Uppsala University, Computing Science Department, 1997. http://www.csd.uu.se/papers/reports.html

    Google Scholar 

  8. A. Dovier, E.G. Omodeo, E. Pontelli, and G. Rossi. {log}: A language for programming in logic with finite sets. Journal of Logic Programming, 28(1):1–44, 1996.

    Google Scholar 

  9. M. Gabbrielli, G.M. Dore, and G. Levi. Observable semantics for constraint logic programs. Journal of Logic and Computation, 5(2):133–171, 1995.

    Google Scholar 

  10. J.H. Gallier and S. Raatz. Extending SLD-resolution to equational Horn clauses using E-unification. Journal of Logic Programming, 6(3):3–44, 1989.

    Google Scholar 

  11. J. Jaffar and M. Maher. Constraint logic programming: a survey. Journal of Logic Programming, 19,20:503–581, 1994.

    Google Scholar 

  12. B. Jayaraman and D.A. Plaisted. Programming with equations, subsets and relations. In Proc. NACLP'89, Cleveland, 1989. MIT Press.

    Google Scholar 

  13. D. Kapur and P. Narendran. NP-completeness of the set unification and matching problems. In J. Siekmann, editor, Proc. 8th CADE, volume 230 of Lecture Notes in Computer Science, 1986.

    Google Scholar 

  14. G.M. Kuper. Logic programming with sets. Journal of Computer and System Sciences, 41:44–64, 1990.

    Google Scholar 

  15. G.M. Kuper and M.Y. Vardi. The logical data model. ACM Transactions on Database Systems, 18(3):379–413, 1993.

    Google Scholar 

  16. J.W. Lloyd. Foundations of Logic Programming (2nd edition). Springer Verlag, 1987.

    Google Scholar 

  17. M.J. Maher. A CLP view of logic programming. In Proc. Conf. on Algebraic and Logic Programming, volume 632 of Lecture Notes in Computer Science, pages 364–383, October 1992.

    Google Scholar 

  18. T. Munakata. Notes on implementing sets in Prolog. Communications of the ACM, 35(3):112–120, 1992.

    Google Scholar 

  19. C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

    Google Scholar 

  20. O. Shmueli, S. Tsur, and C. Zaniolo. Compilation of set terms in the logic data language (LDL). Journal of Logic Programming, 12(1):89–119, 1992.

    Google Scholar 

  21. G. Smolka and R. Treinen. Records for logic programming. Journal of Logic Programming, 18:229–258, 1994.

    Google Scholar 

  22. M. Vardi. The complexity of relational query languages. In Proc. 14th ACM STOC, 1982.

    Google Scholar 

  23. A. Voronkov. Logic programming with bounded quantifiers revisited. UPMAIL Technical Report, Uppsala University, Computing Science Department, 1997, to appear.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Steklov Institute of Mathematics at St.Petersburg, Fontanka 27, 191011, St.Petersburg, Russia

    Evgeny Dantsin

  2. Computing Science Department, Uppsala University, Box 311, S-751 05, Uppsala, Sweden

    Andrei Voronkov

Authors
  1. Evgeny Dantsin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrei Voronkov
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Sergei Adian Anil Nerode

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dantsin, E., Voronkov, A. (1997). Complexity of query answering in logic databases with complex values. In: Adian, S., Nerode, A. (eds) Logical Foundations of Computer Science. LFCS 1997. Lecture Notes in Computer Science, vol 1234. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63045-7_7

Download citation

  • DOI: https://doi.org/10.1007/3-540-63045-7_7

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63045-6

  • Online ISBN: 978-3-540-69065-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation