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

Abstract

References

[1]

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

[2]

Serge Abiteboul , Victor Vianu : Datalog Extensions for Database Queries and Updates. JCSS 43(1) : 62-124(1991)

[3]

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

[4]

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

[5]

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

[6]

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

[7]

Leonard Berman : The Complexitiy of Logical Theories. TCS 11 : 71-77(1980)

[8]

Howard A. Blair , V. Wiktor Marek , John S. Schlipf : The Expressiveness of Locally Stratified Programs. Annals of Mathematics and Artificial Intelligence 15(2) : 209-229(1995)

[9]

Ashok K. Chandra , David Harel : Structure and Complexity of Relational Queries. JCSS 25(1) : 99-128(1982)

[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

[11]

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

[12]

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

[13]

...

[14]

...

[15]

...

[16]

...

[17]

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

[18]

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

[19]

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

[20]

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

[21]

Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz : Constraint Query Languages. JCSS 51(1) : 26-52(1995)

[22]

Gabriel M. Kuper , Moshe Y. Vardi : The Logical Data Model. TODS 18(3) : 379-413(1993)

[23]

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

[24]

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

[25]

...

[26]

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

[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

[28-2]

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

[29]

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

[30]

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

[31]

...

[32]

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

[33]

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

[34]

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

Referenced by

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

BIBTEX