- Abstract:
-
We study queries to spatial databases, where spatial data are modeled as semi-algebraic 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 semialgebraic databases. We also show that the sublanguage with linear inequalities only can express all computable queries on semilinear databases. As a consequence of these results, we obtain a completeness result for topological queries on semialgebraic databases.
- Links To Paper
- 1st Link
- Bibtex format
- @Article{EDI-INF-RR-0804,
- author = {
Floris Geerts
and Bart Kuijpers
and Jan Van den Bussche
},
- title = {Linearization and completeness results for terminating transitive closure queries on spatial databases},
- journal = {SIAM Journal on Computing},
- publisher = {SIAM},
- year = 2006,
- month = {Apr},
- volume = {35(6)},
- pages = {1386-1439},
- doi = {10.1137/S0097539702410065},
- url = {http://epubs.siam.org/fulltext/SICOMP/volume-35/41006.pdf},
- }
|
