Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/725
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | VANDEURZEN, Luc | - |
dc.contributor.author | GYSSENS, Marc | - |
dc.contributor.author | Van Gucht, Dirk | - |
dc.date.accessioned | 2005-04-14T15:21:11Z | - |
dc.date.available | 2005-04-14T15:21:11Z | - |
dc.date.issued | 1998 | - |
dc.identifier.citation | Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, Pag. 109-118 | - |
dc.identifier.isbn | 0-89791-996-3 | - |
dc.identifier.uri | http://hdl.handle.net/1942/725 | - |
dc.description.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. | - |
dc.format.extent | 260405 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | Association for Computing Machinery | - |
dc.title | An Expressive Language for Linear Spatial Database Queries | - |
dc.type | Proceedings Paper | - |
local.type.specified | Proceedings Paper | - |
dc.bibliographicCitation.oldjcat | - | |
dc.identifier.url | http://doi.acm.org/10.1145/275487.275500 | - |
item.accessRights | Open Access | - |
item.fullcitation | VANDEURZEN, Luc; GYSSENS, Marc & Van Gucht, Dirk (1998) An Expressive Language for Linear Spatial Database Queries. In: Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, Pag. 109-118. | - |
item.contributor | VANDEURZEN, Luc | - |
item.contributor | GYSSENS, Marc | - |
item.contributor | Van Gucht, Dirk | - |
item.fulltext | With Fulltext | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
expressive.pdf | 254.3 kB | Adobe PDF | View/Open |
Page view(s)
130
checked on Nov 7, 2023
Download(s)
312
checked on Nov 7, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.