Languages for Relational Databases over Interpreted Structures.

@inproceedings{DBLP:conf/pods/BenediktL97,
  author    = {Michael Benedikt and
               Leonid Libkin},
  title     = {Languages for Relational Databases over Interpreted Structures},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {87-98},
  ee        = {http://doi.acm.org/10.1145/263661.263672, db/conf/pods/BenediktL97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We rework parts of the classical relational theory when the underlying domain is a structure with some interpreted operations that can be used in queries. We identify parts of the classical theory that go through 'as before' when interpreted structure is present, parts that go through only for classes of nicely-behaved structures, and parts that only arise in the interpreted case. The first category includes a number of results on equivalence of query languages, as well as expressive power characterizations for the active-domain semantics for a variety of logics. The second category includes most of our results on the natural semantics, including results on cases where the natural semantics collapses to the active semantics. While these collapse results have been proved by nonconstructive means for first-order logic in previous work, we here give a set of algorithms for eliminating unbounded quantifications in favor of bounded ones. Furthermore, we show these results for a new class of higher-order logics that mix unbounded and bounded quantification. We give a set of normal forms for these logics, under special conditions on the interpreted structures.

As a by-product, we obtain an elementary proof of the fact that parity test is not definable in the relational calculus with polynomial inequality constraints.

Copyright © 1997 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

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]

...

[4]

David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306(1990) BibTeX

[5]

Catriel Beeri, Tova Milo: Functional and Predicative Programming in OODB's. PODS 1992: 176-190 BibTeX

[6]

Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16 BibTeX

[7]

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

[8]

...

[9]

Michael Ben-Or, Dexter Kozen, John H. Reif: The Complexity of Elementary Algebra and Geometry. J. Comput. Syst. Sci. 32(2): 251-264(1986) BibTeX

[10]

...

[11]

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

[12]

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

[13]

...

[14]

Anuj Dawar, Steven Lindell, Scott Weinstein: First Order Logic, Fixed Point Logic and Linear Order. CSL 1995: 161-177 BibTeX

[15]

...

[16]

Martha Escobar-Molano, Richard Hull, Dean Jacobs: Safety and Translation of Calculus Queries with Scalar Functions. PODS 1993: 253-264 BibTeX

[17]

Kousha Etessami: Counting Quantifiers, Successor Relations, and Logarithmic Space. J. Comput. Syst. Sci. 54(3): 400-411(1997) BibTeX

[18]

Erich Grädel, Yuri Gurevich: Metafinite Model Theory. LCC 1994: 313-366 BibTeX

[19]

...

[20]

...

[21]

...

[22]

Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX

[23]

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

[24]

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

[25]

Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60 BibTeX

[26]

Phokion G. Kolaitis, Moshe Y. Vardi: 0-1 Laws and Decision Problems for Fragments of Second-Order Logic. Inf. Comput. 87(1/2): 301-337(1990) BibTeX

[27]

Phokion G. Kolaitis, Moshe Y. Vardi: Infinitary Logics and 0-1 Laws. Inf. Comput. 98(2): 258-294(1992) BibTeX

[28]

Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122 BibTeX

[29]

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

[30]

...

[31]

Martin Otto, Jan Van den Bussche: First-Order Queries on Databases Embedded in an Infinite Structure. Inf. Process. Lett. 60(1): 37-41(1996) BibTeX

[32]

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

[33]

...

[34]

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

[35]

...

[36]

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

[37]

Moshe Y. Vardi: On the Complexity of Bounded-Variable Queries. PODS 1995: 266-276 BibTeX

Referenced by

1. David Gross, Michel de Rougemont: Uniform Generation in Spatial Constraint Databases and Applications. PODS 2000: 254-259
2. Evgeny Dantsin, Andrei Voronkov: Expressive Power and Data Complexity of Query Languages for Trees and Lists. PODS 2000: 157-165
3. Michael Benedikt, Martin Grohe, Leonid Libkin, Luc Segoufin: Reachability and Connectivity Queries in Constraint Databases. PODS 2000: 104-115
4. Michael Benedikt, Leonid Libkin: Exact and Approximate Aggregation in Constraint Query. PODS 1999: 102-113
5. Luca Cabibbo, Riccardo Torlone: A Framework for the Investigation of Aggregate Functions in Database Queries. ICDT 1999: 383-397
6. Sergei G. Vorobyov, Andrei Voronkov: Complexity of Nonrecursive Logic Programs with Complex Values. PODS 1998: 244-253
7. Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: An Expressive Language for Linear Spatial Database Queries. PODS 1998: 109-118
8. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
9. Bart Kuijpers: Degrees of Monotonicity of Spatial Transformations. DBPL 1997: 60-77