Title
First-order languages expressing constructible spatial database queries First-order languages expressing constructible spatial database queries
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Philadelphia, Pa ,
Subject
Mathematics
Computer. Automation
Source (journal)
SIAM JOURNAL ON COMPUTING
SIAM journal on computing. - Philadelphia, Pa, 1972, currens
Volume/pages
36(2007) :6 , p. 1570-1599
ISSN
0097-5397
ISI
000246299400003
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000246299400003&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000246299400003&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle