Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/7902
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | KUIJPERS, Bart | - |
dc.contributor.author | PAREDAENS, Jan | - |
dc.contributor.author | KUPER, Gabriel | - |
dc.contributor.author | VANDEURZEN, Luc | - |
dc.date.accessioned | 2008-02-21T13:04:10Z | - |
dc.date.available | 2008-02-21T13:04:10Z | - |
dc.date.issued | 2007 | - |
dc.identifier.citation | SIAM JOURNAL ON COMPUTING, 36(6). p. 1570-1599 | - |
dc.identifier.issn | 0097-5397 | - |
dc.identifier.uri | http://hdl.handle.net/1942/7902 | - |
dc.description.abstract | The research presented in this paper is situated in the framework of constraint databases introduced by Kanellakis, Kuper, and Revesz in their seminal paper of 1990, specifically, the language with real polynomial constraints (FO + poly). For reasons of efficiency, this model is implemented with only linear polynomial constraints, but this limitation to linear polynomial constraints has severe implications on the expressive power of the query language. In particular, when used for modeling spatial data, important queries that involve Euclidean distance are not expressible. The aim of this paper is to identify a class of two-dimensional constraint databases and a query language within the constraint model that go beyond the linear model and allow the expression of queries concerning distance. We seek inspiration in the Euclidean constructions, i.e., constructions by ruler and compass. We first present a programming language that captures exactly the first-order ruler-and-compass constructions that are expressible in a first-order language with real polynomial constraints. If this language is extended with a while operator, we obtain a language that is complete for all ruler-and-compass constructions in the plane. We then transform this language in a natural way into a query language on finite point databases, but this language turns out to have the same expressive power as FO + poly and is therefore too powerful for our purposes. We then consider a safe fragment of this language and use this to construct a query language that allows the expression of Euclidean distance without having the full power of FO + poly. | - |
dc.language.iso | en | - |
dc.publisher | SIAM | - |
dc.subject.other | constraint databases, real algebraic geometry, first-order logic, query languages, | - |
dc.title | First Order Languages Expressing Constructible Spatial Database Queries | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 1599 | - |
dc.identifier.issue | 6 | - |
dc.identifier.spage | 1570 | - |
dc.identifier.volume | 36 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1137/S0097539702407199 | - |
dc.identifier.isi | 000246299400003 | - |
item.fullcitation | KUIJPERS, Bart; PAREDAENS, Jan; KUPER, Gabriel & VANDEURZEN, Luc (2007) First Order Languages Expressing Constructible Spatial Database Queries. In: SIAM JOURNAL ON COMPUTING, 36(6). p. 1570-1599. | - |
item.fulltext | With Fulltext | - |
item.validation | ecoom 2008 | - |
item.contributor | KUIJPERS, Bart | - |
item.contributor | PAREDAENS, Jan | - |
item.contributor | KUPER, Gabriel | - |
item.contributor | VANDEURZEN, Luc | - |
item.accessRights | Open Access | - |
crisitem.journal.issn | 0097-5397 | - |
crisitem.journal.eissn | 1095-7111 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
07-SIAM-EuQL.pdf | 283.93 kB | Adobe PDF | View/Open |
Page view(s)
66
checked on Jun 14, 2023
Download(s)
142
checked on Jun 14, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.