ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

An Expressive Language for Linear Spatial Database Queries.

Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: An Expressive Language for Linear Spatial Database Queries. PODS 1998: 109-118
@inproceedings{DBLP:conf/pods/VandeurzenGG98,
  author    = {Luc Vandeurzen and
               Marc Gyssens and
               Dirk Van Gucht},
  title     = {An Expressive Language for Linear Spatial Database Queries},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {109-118},
  ee        = {http://doi.acm.org/10.1145/275487.275500, db/conf/pods/VandeurzenGG98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We exhibit a coordinate-based language, called PFOL, which is sound for the linear queries computable in first-order logic over the reals and extends the latter's restriction to linear arithmetic. To evaluate its expressive power, we first consider PFOL-fin, the PFOL queries that compute finite outputs upon finite inputs. In order to study this fragment of PFOL, we also define a syntactical language, called SPFOL, which is safe with respect to queries from finite inputs to finite outputs. We show that SPFOL has the same expressive power as SafeEuQl [15], whence all ruler-and-compass constructions in the plane on finite sets of points can be expressed in SPFOL. This result gives a geometrical justification of SPFOL, and highlights the richness of PFOL-fin. Then, we define finite representations for arbitrary semi-linear sets and show that there are PFOL programs for both the encoding and the decoding. This result is used (i) to identify a broad, natural class of linear queries expressible in PFOL, highlighting the richness of general PFOL, and (ii) to establish a general theorem about lifting query languages on finite databases to query languages on arbitrary linear databases. This theorem is applied to a recent result of Benedikt and Libkin [5] from finite to arbitrary semi-linear sets, yielding the existence of a natural, syntactically definable fragment of FO+poly sound and complete for all FO+poly-expressible linear queries.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington. ACM Press 1998, ISBN 0-89791-996-3
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1407 KB]

References

[1]
Foto N. Afrati, Theodore Andronikos, Theodore G. Kavalieros: On the Expressiveness of Query Languages with Linear Constraints; Capturing Desirable Spatial Properties. CDB 1997: 105-115 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]
Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16 BibTeX
[4]
Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98 BibTeX
[5]
Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108 BibTeX
[6]
...
[7]
...
[8]
Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48 BibTeX
[9]
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 BibTeX
[10]
...
[11]
Stéphane Grumbach, Jianwen Su, Christophe Tollu: Linear Constraint Query Languages: Expressive Power and Complexity. LCC 1994: 426-446 BibTeX
[12]
...
[13]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX
[14]
Jürg Nievergelt, Michael Freeston: Special Issue Editorial: Other Objects, or: What is unique about Spatial Data? Comput. J. 37(1): 1-2(1994) BibTeX
[15]
...
[16]
Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288 BibTeX
[17]
Niki Pissinou, Richard T. Snodgrass, Ramez Elmasri, Inderpal Singh Mumick, M. Tamer Özsu, Barbara Pernici, Arie Segev, Babis Theodoulidis, Umeshwar Dayal: Towards an Infrastructure for Temporal Databases: Report of an Invitational ARPA/NSF Workshop. SIGMOD Record 23(1): 35-51(1994) BibTeX
[18]
Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: On the Desirability and Limitations of Linear Spatial Database Models. SSD 1995: 14-28 BibTeX
[19]
Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: On Query Languages for Linear Queries Definable with Polynomial Constraints. CP 1996: 468-481 BibTeX

Referenced by

  1. Stephan Kreutzer: Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls. ICDT 2001: 248-262
  2. David Gross, Michel de Rougemont: Uniform Generation in Spatial Constraint Databases and Applications. PODS 2000: 254-259
  3. Floris Geerts, Bart Kuijpers: Linear Approximation of Planar Spatial Databases Using Transitive-Closure Logic. PODS 2000: 126-135
  4. Evgeny Dantsin, Andrei Voronkov: Expressive Power and Data Complexity of Query Languages for Trees and Lists. PODS 2000: 157-165
  5. Michael Benedikt, Leonid Libkin: Exact and Approximate Aggregation in Constraint Query. PODS 1999: 102-113
  6. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:19 2009