Expressive Power and Data Complexity of Query Languages for Trees and Lists.

@inproceedings{DBLP:conf/pods/DantsinV00,
  author    = {Evgeny Dantsin and
               Andrei Voronkov},
  title     = {Expressive Power and Data Complexity of Query Languages for Trees
               and Lists},
  booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium
               on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,
               USA},
  publisher = {ACM},
  year      = {2000},
  isbn      = {1-58113-214-X},
  pages     = {157-165},
  ee        = {http://doi.acm.org/10.1145/335168.335218, db/conf/pods/DantsinV00.html},
  crossref  = {DBLP:conf/pods/00},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 2000 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[2]

Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX

[3]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[4]

Krzysztof R. Apt: Logic Programming. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990: 493-574 BibTeX

[5]

Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98 BibTeX

[6]

Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108 BibTeX

[7]

Leonard Berman: The Complexitiy of Logical Theories. Theor. Comput. Sci. 11: 71-77(1980) BibTeX

[8]

Howard A. Blair, V. Wiktor Marek, John S. Schlipf: The Expressiveness of Locally Stratified Programs. Ann. Math. Artif. Intell. 15(2): 209-229(1995) BibTeX

[9]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[10]

Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht: A Query Language for List-Based Complex Objects. PODS 1994: 179-189 BibTeX

[11]

Kevin J. Compton, C. Ward Henson: A Uniform Method for Proving Lower Bounds on the Computational Complexity of Logical Theories. Ann. Pure Appl. Logic 48(1): 1-79(1990) BibTeX

[12]

Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov: Complexity and Expressive Power of Logic Programming. IEEE Conference on Computational Complexity 1997: 82-101 BibTeX

[13]

...

[14]

...

[15]

...

[16]

...

[17]

Richard Hull, Jianwen Su: Algebraic and Calculus Query Languages for Recursively Typed Complex Objects. J. Comput. Syst. Sci. 47(1): 121-156(1993) BibTeX

[18]

Richard Hull, Jianwen Su: Domain Independence and the Relational Calculus. Acta Inf. 31(6): 513-524(1994) BibTeX

[19]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[20]

Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX

[21]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX

[22]

Gabriel M. Kuper, Moshe Y. Vardi: The Logical Data Model. ACM Trans. Database Syst. 18(3): 379-413(1993) BibTeX

[23]

Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model. Theor. Comput. Sci. 116(1&2): 33-57(1993) BibTeX

[24]

Michael J. Maher: Complete Axiomatizations of the Algebras of Finite, Rational and Infinite Trees. LICS 1988: 348-357 BibTeX

[25]

...

[26]

Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: First-order Queries on Finite Structures over the Reals. LICS 1995: 79-87 BibTeX

[27]

...

[28-1]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[28-2]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[29]

Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: An Expressive Language for Linear Spatial Database Queries. PODS 1998: 109-118 BibTeX

[30]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[31]

...

[32]

Hugo Volger: Turing Machines with Linear Alternation, Theories of Bounded Concatenation and the Decision Problem of First Order Theories. Theor. Comput. Sci. 23: 333-337(1983) BibTeX

[33]

Sergei G. Vorobyov: An Improved Lower Bound for the Elementary Theories of Trees. CADE 1996: 275-287 BibTeX

[34]

Sergei G. Vorobyov, Andrei Voronkov: Complexity of Nonrecursive Logic Programs with Complex Values. PODS 1998: 244-253 BibTeX

Referenced by

1. Jan Van den Bussche: Constraint databases: A tutorial introduction. SIGMOD Record 29(3): 44-51(2000)