Querying Spatial Databases via Topological Invariants.
Luc Segoufin, Victor Vianu:
Querying Spatial Databases via Topological Invariants.
PODS 1998: 89-98@inproceedings{DBLP:conf/pods/SegoufinV98,
author = {Luc Segoufin and
Victor Vianu},
editor = {Alberto O. Mendelzon and
Jan Paredaens},
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,
USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-996-3},
pages = {89-98},
ee = {http://doi.acm.org/10.1145/275487.275498, db/conf/pods/SegoufinV98.html},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
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.
Copyright © 1998 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
Alberto O. Mendelzon, Jan Paredaens (Eds.):
Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, USA.
ACM Press 1998, ISBN 0-89791-996-3
Contents 
[Index Terms]
[Full Text in PDF Format, 1411 KB]
References
- [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.
J. Comput. Syst. Sci. 43(1): 62-124(1991)
- [AV95]
- Serge Abiteboul, Victor Vianu:
Computing with First-Order Logic.
J. Comput. Syst. Sci. 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.
Inf. Comput. 119(2): 160-175(1995)
- [FSV95]
- Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi:
On Monadic NP vs. Monadic co-NP.
Inf. Comput. 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.
Theor. Comput. Sci. 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
Last update Thu May 24 04:40:33 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
