Querying Spatial Databases via Topological Invariants
Luc Segoufin, Victor Vianu
Full Paper (PDF)

Abstract
The paper investigates the use of topological annotations (called topological invariants) to answer topological queries in spatial databases. The focus is on the translation of topological queries against the spatial database into queries against the topological invariant. The languages considered are first-order on the spatial database side, and fixpoint and first-order on the topological invariant side. In particular, it is shown that fixpoint expresses precisely the ptime queries on topological invariants.

References

References, where available, link to the DBLP on the World Wide Web.

[AHV95]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents
[AV91]
Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. JCSS 43(1): 62-124(1991)
[AV95]
Serge Abiteboul, Victor Vianu: Computing with First-Order Logic. JCSS 50(2): 309-335(1995)
[BDLW96]
Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16
[CFI92]
...
[Cor79]
...
[Cro63]
...
[DLW95]
Anuj Dawar, Steven Lindell, Scott Weinstein: Infinitary Logic and Inductive Definability over Finite Structures. Information and Computation 119(2): 160-175(1995)
[FSV95]
Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi: On Monadic NP vs. Monadic co-NP. Information and Computation 120(1): 78-92(1995)
[Gro97]
Martin Grohe: Large Finite Structures with Few Lk-Types. LICS 1997: 216-227
[GO93]
Erich Grädel, Martin Otto: Inductive Definability with Counting on Finite Structures. CSL 1992: 231-247
[GK97]
Stéphane Grumbach, Gabriel M. Kuper: Tractable Recursion over Geometric Data. CP 1997: 450-462
[GS97]
Stéphane Grumbach, Jianwen Su: Queries with Arithmetical Constraints. TCS 173(1): 151-181(1997)
[GS98]
...
[GST94]
Stéphane Grumbach, Jianwen Su, Christophe Tollu: Linear Constraint Query Languages: Expressive Power and Complexity. LCC 1994: 426-446
[Gur84]
...
[IGN]
...
[I86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986)
[I87]
...
[KKR90]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313
[KY85]
Dexter Kozen, Chee-Keng Yap: Algebraic Cell Decomposition in NC (Preliminary Version). FOCS 1985: 515-521
[KPV95]
Bart Kuijpers, Jan Paredaens, Jan Van den Bussche: Lossless Representation of Topological Spatial Data. SSD 1995: 1-13
[KPV97]
Bart Kuijpers, Jan Paredaens, Jan Van den Bussche: On Topological Elementary Equivalence of Spatial Databases. ICDT 1997: 432-446
[M85]
...
[M89]
...
[Mar58]
...
[PSV96]
Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92
[Par+94]
Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288
[Par95]
Jan Paredaens: Spatial Databases, The Final Frontier. ICDT 1995: 14-32
[Par+95]
Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: First-order Queries on Finite Structures over the Reals. LICS 1995: 79-87
[Seg]
...
[Seq]
Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11
[Tar51]
...
[V82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146
BIBTEX

@inproceedings{DBLP:conf/pods/SegoufinV98,
author = {Luc Segoufin and
Victor Vianu},
title = {Querying Spatial Databases via Topological Invariants},
booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-966-3},
pages = {89-98},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).