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 | Size | Format | |
---|---|---|---|---|
linearization.pdf | 535.86 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.