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},
editor = {Richard Hull},
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}
}
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 ...
Printed Edition
Richard Hull (Ed.):
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 
[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
- [BDLW95]
- Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong:
Relational Expressive Power of Constraint Query Languages.
PODS 1996: 5-16
- [Ba77]
- ...
- [BF85]
- ...
- [BKR84]
- Michael Ben-Or, Dexter Kozen, John H. Reif:
The Complexity of Elementary Algebra and Geometry (Preliminary Abstract).
STOC 1984: 457-464
- [Cla85]
- ...
- [CRC94]
- ...
- [Cor79]
- ...
- [EgFra]
- ...
- [EET76]
- ...
- [GPP95]
- ...
- [GS94]
- Stéphane Grumbach, Jianwen Su:
Finitely Representable Databases.
PODS 1994: 289-300
- [GS95]
- Stéphane Grumbach, Jianwen Su:
Dense-Order Constraint Databases.
PODS 1995: 66-77
- [GST94]
- Stéphane Grumbach, Jianwen Su, Christophe Tollu:
Linear Constraint Query Languages: Expressive Power and Complexity.
LCC 1994: 426-446
- [KG94]
- ...
- [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
- [Kra91]
- ...
- [KM94]
- ...
- [KPV95]
- Bart Kuijpers, Jan Paredaens, Jan Van den Bussche:
Lossless Representation of Topological Spatial Data.
SSD 1995: 1-13
- [LT92]
- ...
- [Moi]
- ...
- [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
- [RC89]
- David A. Randell, Anthony G. Cohn:
Modelling Topological and Metrical Properties in Physical Processes.
KR 1989: 357-368
- [Rog]
- ...
- [SW94]
- ...
- [St]
- ...
- [Tar51]
- ...
Referenced by
- Michael Benedikt, Martin Grohe, Leonid Libkin, Luc Segoufin:
Reachability and Connectivity Queries in Constraint Databases.
PODS 2000: 104-115
- Michael Benedikt, Leonid Libkin:
Exact and Approximate Aggregation in Constraint Query.
PODS 1999: 102-113
- Bart Kuijpers, Jan Van den Bussche:
On Capturing First-Order Topological Properties of Planar Spatial Databases.
ICDT 1999: 187-198
- Luc Segoufin, Victor Vianu:
Querying Spatial Databases via Topological Invariants.
PODS 1998: 89-98
- Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht:
Complete Geometrical Query Languages.
PODS 1997: 62-67
- Bart Kuijpers, Jan Paredaens, Jan Van den Bussche:
On Topological Elementary Equivalence of Spatial Databases.
ICDT 1997: 432-446
- Stéphane Grumbach, Philippe Rigaux, Michel Scholl, Luc Segoufin:
DEDALE, A Spatial Constraint Database.
DBPL 1997: 38-59
- Catriel Beeri, Tova Milo, Paula Ta-Shma:
Towards a Language for the Fully Generic Queries.
DBPL 1997: 239-259
Last update Fri May 25 08:32:50 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
