An Expressive Language for Linear Spatial Database Queries
Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht
Full Paper (PDF)

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.

References

References, where available, link to the DBLP on the World Wide Web.

[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
[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
[3]
Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16
[4]
Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98
[5]
Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
[6]
...
[7]
...
[8]
Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48
[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
[10]
...
[11]
Stéphane Grumbach, Jianwen Su, Christophe Tollu: Linear Constraint Query Languages: Expressive Power and Complexity. LCC 1994: 426-446
[12]
...
[13]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. JCSS 51(1): 26-52(1995)
[14]
Jürg Nievergelt, Michael Freeston: Special Issue Editorial: Other Objects, or: What is unique about Spatial Data? The Computer Journal 37(1): 1-2(1994)
[15]
...
[16]
Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288
[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)
[18]
Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: On the Desirability and Limitations of Linear Spatial Database Models. SSD 1995: 14-28
[19]
Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: On Query Languages for Linear Queries Definable with Polynomial Constraints. CP 1996: 468-481 Referenced By:
  1. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
BIBTEX

@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-966-3},
pages = {109-118},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).