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

Towards a Theory of Spatial Database Queries.

Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288
@inproceedings{DBLP:conf/pods/ParedaensBG94,
  author    = {Jan Paredaens and
               Jan Van den Bussche and
               Dirk Van Gucht},
  title     = {Towards a Theory of Spatial Database Queries},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {279-288},
  ee        = {http://doi.acm.org/10.1145/182591.182640, db/conf/pods/pods94-279.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A general model for spatial databases is considered, which extends the relational model by allowing as tuple components not only atomic values but also geometrical figures. The model, which is inspired by the work of Kanellakis, Kuper and Revesz on constraint query languages, includes a calculus and an algebra which are equivalent. Given this framework, the concept of spatial database query is investigated. Thereto, Chandra and Harel's well-known consistency criterion for classical relational queries is adapted. Various adaptations are proposed, depending on the kinds of geometry in which the spatial information in the database is to be interpreted. The consistency problem for calculus queries is studied. Expressiveness issues are examined. The main purpose of the paper is to open up new grounds for theoretical research in the area of spatial database systems. Consequently, many open problems are indicated.

Copyright © 1994 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 Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 909 KB]

References

[AO93]
...
[Arn88]
Dennis S. Arnon: Geometric Reasoning with Logic and Algebra. Artif. Intell. 37(1-3): 37-60(1988) BibTeX
[ASU79]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[BCR87]
...
[Buc89]
...
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[Col75]
...
[EF91]
...
[Eng93]
...
[GS]
Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300 BibTeX
[GS91]
...
[HRR91]
...
[HY84]
Richard Hull, Chee-Keng Yap: The Format Model: A Theory of database Organization. J. ACM 31(3): 518-544(1984) BibTeX
[KKR90]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX
[Ren92]
James Renegar: On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals. J. Symb. Comput. 13(3): 255-300(1992) BibTeX
[Ren92a]
James Renegar: On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part II: The General Decision Problem. Preliminaries for Quantifier Elimination. J. Symb. Comput. 13(3): 301-328(1992) BibTeX
[Ren92b]
James Renegar: On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part III: Quantifier Elimination. J. Symb. Comput. 13(3): 329-352(1992) BibTeX
[Sch79]
...
[T+93]
Abdullah Uz Tansel, James Clifford, Shashi K. Gadia, Sushil Jajodia, Arie Segev, Richard T. Snodgrass (Eds.): Temporal Databases: Theory, Design, and Implementation. Benjamin/Cummings 1993, ISBN 0-8053-2413-5
Contents BibTeX
[Tar51]
...
[Tar86]
...

Referenced by

  1. Jan Van den Bussche: Constraint databases: A tutorial introduction. SIGMOD Record 29(3): 44-51(2000)
  2. Theodore Johnson, Laks V. S. Lakshmanan, Raymond T. Ng: The 3W Model and Algebra for Unified Data Mining. VLDB 2000: 21-32
  3. David Gross, Michel de Rougemont: Uniform Generation in Spatial Constraint Databases and Applications. PODS 2000: 254-259
  4. Ouri Wolfson, Liqin Jiang, A. Prasad Sistla, Sam Chamberlain, Naphtali Rishe, Minglin Deng: Databases for Tracking Mobile Units in Real Time. ICDT 1999: 169-186
  5. Stéphane Grumbach, Philippe Rigaux, Luc Segoufin: On the Orthographic Dimension of Constraint Databases. ICDT 1999: 199-216
  6. Peter Z. Revesz: Safe Query Languages for Constraint Databases. ACM Trans. Database Syst. 23(1): 58-99(1998)
  7. Alberto Belussi, Elisa Bertino, Barbara Catania: An Extended Algebra for Constraint Databases. IEEE Trans. Knowl. Data Eng. 10(5): 686-705(1998)
  8. Stéphane Grumbach, Philippe Rigaux, Luc Segoufin: The DEDALE System for Complex Spatial Queries. SIGMOD Conference 1998: 213-224
  9. Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: An Expressive Language for Linear Spatial Database Queries. PODS 1998: 109-118
  10. Luc Segoufin, Victor Vianu: Querying Spatial Databases via Topological Invariants. PODS 1998: 89-98
  11. Frank Neven, Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen: Typed Query Languages for Databases Containing Queries. PODS 1998: 189-196
  12. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
  13. Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht: Complete Geometrical Query Languages. PODS 1997: 62-67
  14. Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht: On the Decidability of Semi-Linearity of Semi-Algebraic Sets and Its Implications for Spatial Databases. PODS 1997: 68-77
  15. Bart Kuijpers, Jan Paredaens, Jan Van den Bussche: On Topological Elementary Equivalence of Spatial Databases. ICDT 1997: 432-446
  16. A. Prasad Sistla, Ouri Wolfson, Sam Chamberlain, Son Dao: Modeling and Querying Moving Objects. ICDE 1997: 422-432
  17. Jan Paredaens, Bart Kuijpers, Gabriel M. Kuper, Luc Vandeurzen: Eucil, Tarski, and Engler Encompassed (Preliminary Report). DBPL 1997: 1-24
  18. Bart Kuijpers: Degrees of Monotonicity of Spatial Transformations. DBPL 1997: 60-77
  19. Stéphane Grumbach, Philippe Rigaux, Michel Scholl, Luc Segoufin: DEDALE, A Spatial Constraint Database. DBPL 1997: 38-59
  20. Catriel Beeri, Tova Milo, Paula Ta-Shma: Towards a Language for the Fully Generic Queries. DBPL 1997: 239-259
  21. Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92
  22. Stéphane Grumbach, Jianwen Su: Towards Practical Constraint Databases. PODS 1996: 28-39
  23. Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48
  24. Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16
  25. Catriel Beeri, Tova Milo, Paula Ta-Shma: On Genericity and Parametricity. PODS 1996: 104-116
  26. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  27. Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77
  28. Jan Chomicki, Gabriel M. Kuper: Measuring Infinite Relations. PODS 1995: 78-85
  29. Peter Z. Revesz: Datalog Queries of Set Constraint Databases. ICDT 1995: 425-438
  30. Jan Paredaens: Spatial Databases, The Final Frontier. ICDT 1995: 14-32
  31. Stéphane Grumbach, Zoé Lacroix: Computing Queries on Linear Constraint Databases. DBPL 1995: 11
  32. Jean-Pierre Cheiney, Vincent Oria: Spatial Database Querying with Logic Languages. DASFAA 1995: 342-349
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:11 2009