Please use this identifier to cite or link to this item:
Title: First Order Languages Expressing Constructible Spatial Database Queries
Authors: KUIJPERS, Bart 
KUPER, Gabriel
Issue Date: 2007
Publisher: SIAM
Source: SIAM JOURNAL ON COMPUTING, 36(6). p. 1570-1599
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.
Keywords: constraint databases, real algebraic geometry, first-order logic, query languages,
Document URI:
ISSN: 0097-5397
e-ISSN: 1095-7111
DOI: 10.1137/S0097539702407199
ISI #: 000246299400003
Category: A1
Type: Journal Contribution
Validations: ecoom 2008
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
07-SIAM-EuQL.pdf283.93 kBAdobe PDFView/Open
Show full item record

Google ScholarTM



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