Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/946
Title: Linearization and completeness results for terminating transitive closure queries on spatial databases
Authors: GEERTS, Floris 
KUIJPERS, Bart 
VAN DEN BUSSCHE, Jan 
Issue Date: 2006
Publisher: SIAM
Source: Siam Journal on Computing, 35(6). p. 1386-1439
Abstract: We study queries to spatial databases, where spatial data are modelled as semialgebraic sets, using the relational calculus with polynomial inequalities as a basic query language. We work with the extension of the relational calculus with terminating transitive closures. The main result is that this language can express the linearization of semi-algebraic databases. We also show that the sublanguage with linear inequalities only can express all computable queries on semi-linear databases. As a consequence of these results, we obtain a completeness result for topological queries on semi-algebraic databases.
Document URI: http://hdl.handle.net/1942/946
ISSN: 0097-5397
e-ISSN: 1095-7111
DOI: 10.1137/S0097539702410065
ISI #: 000237145600006
Category: A1
Type: Journal Contribution
Validations: ecoom 2007
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
linearization.pdf535.86 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

2
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

4
checked on May 13, 2022

Page view(s)

50
checked on May 18, 2022

Download(s)

154
checked on May 18, 2022

Google ScholarTM

Check

Altmetric


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