ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Topological Queries in Spatial Databases.

Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92
@inproceedings{DBLP:conf/pods/PapadimitriouSV96,
  author    = {Christos H. Papadimitriou and
               Dan Suciu and
               Victor Vianu},
  title     = {Topological Queries in Spatial Databases},
  booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 3-5, 1996, Montreal,
               Canada},
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {81-92},
  ee        = {http://doi.acm.org/10.1145/237661.237683, db/conf/pods/PapadimitriouSV96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We study query language for topological properties of two-dimensional spatial databases, starting from the topological relationships between pairs of planar regions introduced by Egenhofer and Franzosa. We show that the closure of these relationships under appropriate logical operators yields languages which are complete for topological properties. This provides a theoretical a posteriori justification for the choice of these particular relationships. Unlike the point-based languages studied in previous work on constraint databases, our languages are region based - quantifiers range over regions in the plane. This yields a family of languages, whose complexity ranges from NC to undecidable. Another type of completeness result shows that the region-based language of complexity NC expresses precisely the same topological properties as well-known point-based languages. Finally we show that each set of semi-algebraic regions is characterized up to homeomorphism by an invariant representable as a finite structure, computable in NC. This allows to answer all topological queries on semi-algebraic regions by queries on the invariant whose complexity is polynomially related to the original. Also, we show that for the purpose of answering topological queries, semi-algebraic regions can always be represented simply as polynomial regions.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, 1996, Montreal, Canada. ACM Press 1996, ISBN 0-89791-781-2
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1327 KB]

References

[AVV95]
Serge Abiteboul, Moshe Y. Vardi, Victor Vianu: Computing with Infinitary Logic. ICDT 1992: 113-123 BibTeX
[BDLW95]
Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16 BibTeX
[Ba77]
...
[BF85]
...
[BKR84]
Michael Ben-Or, Dexter Kozen, John H. Reif: The Complexity of Elementary Algebra and Geometry (Preliminary Abstract). STOC 1984: 457-464 BibTeX
[Cla85]
...
[CRC94]
...
[Cor79]
...
[EgFra]
...
[EET76]
...
[GPP95]
...
[GS94]
Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300 BibTeX
[GS95]
Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77 BibTeX
[GST94]
Stéphane Grumbach, Jianwen Su, Christophe Tollu: Linear Constraint Query Languages: Expressive Power and Complexity. LCC 1994: 426-446 BibTeX
[KG94]
...
[KKR90]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX
[KY85]
Dexter Kozen, Chee-Keng Yap: Algebraic Cell Decomposition in NC (Preliminary Version). FOCS 1985: 515-521 BibTeX
[Kra91]
...
[KM94]
...
[KPV95]
Bart Kuijpers, Jan Paredaens, Jan Van den Bussche: Lossless Representation of Topological Spatial Data. SSD 1995: 1-13 BibTeX
[LT92]
...
[Moi]
...
[Par+94]
Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288 BibTeX
[Par95]
Jan Paredaens: Spatial Databases, The Final Frontier. ICDT 1995: 14-32 BibTeX
[Par+95]
Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: First-order Queries on Finite Structures over the Reals. LICS 1995: 79-87 BibTeX
[RC89]
David A. Randell, Anthony G. Cohn: Modelling Topological and Metrical Properties in Physical Processes. KR 1989: 357-368 BibTeX
[Rog]
...
[SW94]
...
[St]
...
[Tar51]
...

Referenced by

  1. Michael Benedikt, Martin Grohe, Leonid Libkin, Luc Segoufin: Reachability and Connectivity Queries in Constraint Databases. PODS 2000: 104-115
  2. Michael Benedikt, Leonid Libkin: Exact and Approximate Aggregation in Constraint Query. PODS 1999: 102-113
  3. Bart Kuijpers, Jan Van den Bussche: On Capturing First-Order Topological Properties of Planar Spatial Databases. ICDT 1999: 187-198
  4. Luc Segoufin, Victor Vianu: Querying Spatial Databases via Topological Invariants. PODS 1998: 89-98
  5. Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht: Complete Geometrical Query Languages. PODS 1997: 62-67
  6. Bart Kuijpers, Jan Paredaens, Jan Van den Bussche: On Topological Elementary Equivalence of Spatial Databases. ICDT 1997: 432-446
  7. Stéphane Grumbach, Philippe Rigaux, Michel Scholl, Luc Segoufin: DEDALE, A Spatial Constraint Database. DBPL 1997: 38-59
  8. Catriel Beeri, Tova Milo, Paula Ta-Shma: Towards a Language for the Fully Generic Queries. DBPL 1997: 239-259
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:14 2009