Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/725

Title: An Expressive Language for Linear Spatial Database Queries
Authors: VANDEURZEN, Luc
Van Gucht, Dirk
Issue Date: 1998
Publisher: Association for Computing Machinery
Citation: Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, Pag. 109-118
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.
URI: http://hdl.handle.net/1942/725
Link to publication: http://doi.acm.org/10.1145/275487.275500
ISBN: 0-89791-996-3
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A254.3 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.