Title
Linearization and completeness results for terminating transitive closure queries on spatial databases Linearization and completeness results for terminating transitive closure queries on spatial databases
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Philadelphia, Pa ,
Subject
Computer. Automation
Source (journal)
SIAM journal on computing. - Philadelphia, Pa, 1972, currens
Volume/pages
35(2006) :6 , p. 1386-1439
ISSN
0097-5397
ISI
000237145600006
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Abstract
We study queries to spatial databases, where spatial data are modeled 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 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.
E-info
https://repository.uantwerpen.be/docman/iruaauth/731148/50349788956.pdf
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000237145600006&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000237145600006&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000237145600006&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848