The DEDALE system for complex spatial queries

ABSTRACT

This paper presents DEDALE, a spatial database system intended to overcome some limitations of current systems by providing an abstract and non-specialized data model and query language for the representation and manipulation of spatial objects. DEDALE relies on a logical model based on linear constraints, which generalizes the constraint database model of [KKR90]. While in the classical constraint model, spatial data is always decomposed into its convex components, in DEDALE holes are allowed to fit the need of practical applications. The logical representation of spatial data although slightly more costly in memory, has the advantage of simplifying the algorithms. DEDALE relies on nested relations, in which all sorts of data (thematic, spatial, etc.) are stored in a uniform fashion. This new data model supports declarative query languages, which allow an intuitive and efficient manipulation of spatial objects. Their formal foundation constitutes a basis for practical query optimization. We describe several evaluation rules tailored for geometric data and give the specification of an optimizer module for spatial queries. Except for the latter module, the system has been fully implemented upon the O2 DBMS, thus proving the effectiveness of a constraint-based approach for the design of spatial database systems.

REFERENCES

• AS83: l). Abel and J.L. Smith. A Data Structure and Algorithm Based on a Linear Key for a Rectangle Retrieval Problem. Computer Vision, Graphics and Image Processing, 24:1-t3, 1983.
• BBC97: Alberto Belussi , Elisa Bertino , Barbara Catania, Manipulating Spatial Data in Constraint Databases, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.115-141, July 15-18, 1997
• BCD89: François Bancilhon , Sophie Cluet , C. Delobel, A query language for the O2 object-oriented databases, Proceedings of the second international workshop on Database programming languages, p.122-138, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• BDK92: François Bancilhon , Claude Delobel , Paris Kanellakis, Building an object-oriented database system: the story of 02, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• BKSS90: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• Cod70: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• DGVG97: Freddy Dumortier , Marc Gyssens , Luc Vandeurzen , Dirk Van Gucht, On the decidability of semi-linearity for semi-algebraic sets and its implications for spatial databases (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.68-77, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263670]
• Fre87: Johann Christoph Freytag, A rule-based view of query optimization, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.173-180, May 27-29, 1987, San Francisco, California, United States
• Gae95: Volker Gaede, Optimal Redundancy in Spatial Database Systems, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.96-116, August 06-09, 1995
• GK97: S. (}rumbach and G. Kuper. Tractable recursion over geometric data. In International Conference on Con- .straint Programming, 1997.
• Gra93: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• GRS98: S. Grumbach, P. Rigaux, and L. Segoufin. The dedale system for complex spatial queries. Technical Report 131, INR,IA-VERSO, 1998. ftp://ftp, inria, fr/IN RIA /Projects / verso/Versol{epo r t- 131.ps.gz.
• GRSS97: Stéphane Grumbach , Philippe Rigaux , Michel Scholl , Luc Segoufin, DEDALE, A Spatial Constraint Database, Proceedings of the 6th International Workshop on Database Programming Languages, p.38-59, August 18-20, 1997
• GS95: Ralf Hartmut Güting , Markus Schneider, Realm-based spatial data types: the ROSE algebra, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.2, p.243-286, April 1995 [doi>10.1007/BF01237921]
• GS97: Stéphane Grumbach , Jianwen Su, Queries with arithmetical constraints, Theoretical Computer Science, v.173 n.1, p.151-181, Feb. 1997 [doi>10.1016/S0304-3975(96)00194-6]
• GST94: Stéphane Grumbach , Jianwen Su , Christophe Tollu, Linear Constraint Query Languages: Expressive Power and Complexity, Selected Papers from the International Workshop on Logical and Computational Complexity, p.426-446, October 13-16, 1994
• Gut84: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• Güt89: R. H. Güting, Gral: an extensible relational database system for geometric applications, Proceedings of the 15th international conference on Very large data bases, p.33-44, July 1989, Amsterdam, The Netherlands
• Güt94: Ralf Hartmut Güting, An introduction to spatial database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• Her96: J. Herring, The ORACLE 7 Spatial Data ()ption. Technical report, ORACLE Corp., 1996.
• Ja97: Jignesh Patel , JieBing Yu , Navin Kabra , Kristin Tufte , Biswadeep Nag , Josef Burger , Nancy Hall , Karthikeyan Ramasamy , Roger Lueder , Curt Ellmann , Jim Kupsch , Shelly Guo , Johan Larson , David De Witt , Jeffrey Naughton, Building a scaleable geo-spatial DBMS: technology, implementation, and evaluation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.336-347, May 11-15, 1997, Tucson, Arizona, United States
• KG94: Paris C. Kanellakis , Dina Q Goldin, Constraint Programming and Database Query Languages, Brown University, Providence, RI, 1994
• KKR90: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• KPV95: Bart Kuijpers , Jan Paredaens , Jan Van den Bussche, Lossless Representation of Topological Spatial Data, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.1-13, August 06-09, 1995
• Mor89: S. Morehouse. The Architecture of ARC/INFO. In Proc. Intl. Syrup. on Computer-Assisted Cartograph.y (Auto-Carto 9), pages 266-277, 1989.
• NHS84: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• OM88: J. A. Orenstein , F. A. Manola, PROBE Spatial Data Modeling and Query Processing in an Image Database Application, IEEE Transactions on Software Engineering, v.14 n.5, p.611-629, May 1988 [doi>10.1109/32.6139]
• PS85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• PVV94: Jan Paredaens , Jan Van den Bussche , Dirk Van Gucht, Towards a theory of spatial database queries (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.279-288, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182640]
• RFS88: N. Roussopoulos , C. Faloutsos , T. Sellis, An Efficient Pictorial Database System for PSQL, IEEE Transactions on Software Engineering, v.14 n.5, p.639-650, May 1988 [doi>10.1109/32.6141]
• Sam90: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Sch86: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• SFGM93: Michael Stonebraker , Jim Frew , Kenn Gardels , Jeff Meredith, The SEQUOIA 2000 storage benchmark, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.2-11, May 25-28, 1993, Washington, D.C., United States
• SGR96: M. Schotl, G. Grangeret, and X. Rehse. Point and window queries with linear spatial indices: An evaluation with 02. Technical Report RRC-96- 09, Cedric Lab, CNAM, Paris, 1996. Available at ht t p: //si k kim. cnam .fr.
• SRF87: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• SV89: M. Scholl , A. Voisard, Thematic map modeling, Proceedings of the first symposium on Design and implementation of large spatial databases, p.167-190, February 1990, Santa Barbara, California, United States
• Tom90: C.D. Tomlin. Geographic information Systems and Cartographic Modeling. Prentice-Hall, 1990.
• Ube94: Michael Ubell, The Montage extensible DataBlade architecture, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.482, May 24-27, 1994, Minneapolis, Minnesota, United States
• Ull88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Languages