Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/597
Title: | On the expressiveness of linear-constraint query languages for spatial databases | Authors: | GYSSENS, Marc VANDEURZEN, Luc Van Gucht, Dirk |
Issue Date: | 2001 | Publisher: | Elsevier - Science Direct | Source: | THEORETICAL COMPUTER SCIENCE, 254(1-2). p. 423-463 | 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-finite, the PFOL programs that compute finite outputs upon finite inputs. In order to study this fragment of PFOL, we also define an equivalent syntactical language, called SPFOL. We show that SPFOL has the same expressive power as SafeEuql (S. Cluet, R. Hull (Eds.), Proceedings of the Sixth International Workshop on Database Programming Languages, Lecture Notes in Computer Science, Vol. 1369, Springer, Berlin, 1997, pp. 1-24), 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, hence, also of PFOL-finite. 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 FO + poly-expressible linear queries of which we show equivalence with the class of PFOL-expressible queries, 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 (SIAM J. Comput. 29 (2000) 1652-1682) 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. (C) 2004 Elsevier Inc. All rights reserved. | Document URI: | http://hdl.handle.net/1942/597 | ISSN: | 0304-3975 | e-ISSN: | 1879-2294 | DOI: | 10.1016/S0304-3975(99)00316-3 | ISI #: | 000167791900015 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2002 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
journal.pdf | 295 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
7
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
3
checked on Oct 13, 2024
Page view(s)
68
checked on Jul 31, 2023
Download(s)
162
checked on Jul 31, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.