Relational Expressive Power of Constraint Query Languages.

@inproceedings{DBLP:conf/pods/BenediktDLW96,
  author    = {Michael Benedikt and
               Guozhu Dong and
               Leonid Libkin and
               Limsoon Wong},
  title     = {Relational Expressive Power of Constraint Query Languages},
  booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 3-5, 1996, Montreal,
               Canada},
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {5-16},
  ee        = {http://doi.acm.org/10.1145/237661.237667, db/conf/pods/BenediktDLW96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The expressive power of first-order query languages with several classes of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augmented with polynomial inequality constraints over the reals. Furthermore, noting that relational queries exhibit several forms of genericity, we establish a number of collapse results of the following form: The class of generic boolean queries expressible in the relational calculus augmented with a given class of constraints coincides (with or without an order relation). We prove such results for both the natural and active-domain semantics. As a consequence, the relational calculus augmented with polynomial inequalities expresses the same classes of generic boolean queries under both the natural and active-domain semantics.

In the course of proving these results for the active-domain semantics, we establish Ramsey-type theorems saying that any query involving certain kinds of constraints coincides with a constraint-free query on databases whose elements come from a certain infinite subset of the domain. To prove the collapse results for the natural semantics, we make use of techniques from nonstandard analysis and from the model theory of ordered structures.

Copyright © 1996 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.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

Journal Version

References

[1]

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

[2]

Foto N. Afrati, Stavros S. Cosmadakis, Stéphane Grumbach, Gabriel M. Kuper: Linear vs Polynomial Constraints in Database Query Languages. PPCP 1994: 181-192 BibTeX

[3]

Foto N. Afrati, Theodoros Andronikos, Theodoros G. Kavalieros: On the Expressiveness of First-Order Constraint Languages. CDB 1995: 22-39 BibTeX

[4]

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

[5]

...

[6]

Michael Benedikt, Leonid Libkin: On the Structure of Queries in Constraint Query Languages. LICS 1996: 25-34 BibTeX

[7]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX

[8]

...

[9]

...

[10]

...

[11]

...

[12]

...

[13]

Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300 BibTeX

[14]

Stéphane Grumbach, Jianwen Su: First-order Definability over Constraint Databases. CP 1995: 121-136 BibTeX

[15]

Stéphane Grumbach, Jianwen Su, Christophe Tollu: Linear Constraint Query Languages: Expressive Power and Complexity. LCC 1994: 426-446 BibTeX

[16]

...

[17]

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

[18]

Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53 BibTeX

[19]

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

[20]

Gabriel M. Kuper: On The Expressive Power of the Relational Calculus with Arithmetic Constraints. ICDT 1990: 202-211 BibTeX

[21]

Leonid Libkin, Limsoon Wong: Conservativity of Nested Relational Calculi with Internal Generic Functions. Inf. Process. Lett. 49(6): 273-280(1994) BibTeX

[22]

Leonid Libkin, Limsoon Wong: Query Languages for Bags and Aggregate Functions. J. Comput. Syst. Sci. 55(2): 241-272(1997) BibTeX

[23]

...

[24]

...

[25]

Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288 BibTeX

[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]

...

[29]

...

[30]

Alexei P. Stolboushkin, Michael A. Taitslin: Linear vs. Order Contstrained Queries Over Rational Databases. PODS 1996: 17-27 BibTeX

[31]

...

[32]

...

[33]

...

[34]

Limsoon Wong: Normal Forms and Conservative Properties for Query Languages over Collection Types. PODS 1993: 26-36 BibTeX

Referenced by

1. David Gross, Michel de Rougemont: Uniform Generation in Spatial Constraint Databases and Applications. PODS 2000: 254-259
2. Peter Z. Revesz: Safe Query Languages for Constraint Databases. ACM Trans. Database Syst. 23(1): 58-99(1998)
3. Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: An Expressive Language for Linear Spatial Database Queries. PODS 1998: 109-118
4. Luc Segoufin, Victor Vianu: Querying Spatial Databases via Topological Invariants. PODS 1998: 89-98
5. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
6. Oscar H. Ibarra, Jianwen Su: On the Containment and Equivalence of Database Queries with Linear Constraints. PODS 1997: 32-43
7. Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht: On the Decidability of Semi-Linearity of Semi-Algebraic Sets and Its Implications for Spatial Databases. PODS 1997: 68-77
8. Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98
9. Bart Kuijpers, Jan Paredaens, Jan Van den Bussche: On Topological Elementary Equivalence of Spatial Databases. ICDT 1997: 432-446
10. Michael Benedikt, H. Jerome Keisler: Expressive Power of Unary Counters. ICDT 1997: 291-305
11. Bart Kuijpers: Degrees of Monotonicity of Spatial Transformations. DBPL 1997: 60-77
12. Serge Abiteboul, Gabriel M. Kuper, Harry G. Mairson, Alexander A. Shvartsman, Moshe Y. Vardi: In Memoriam Paris C. Kanellakis. ACM Comput. Surv. 28(1): 3-15(1996)
13. Alexei P. Stolboushkin, Michael A. Taitslin: Linear vs. Order Contstrained Queries Over Rational Databases. PODS 1996: 17-27
14. Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92
15. Michael Benedikt, Timothy Griffin, Leonid Libkin: Verifiable Properties of Database Transactions. PODS 1996: 117-127