Experience with SAND-Tcl: a scripting tool for spatial databases

ABSTRACT

The use of scripting makes it possible to overcome many important difficulties in the development of database applications. By extending a general-purpose scripting language with constructs derived both from the database kernel and from the intended application domain, issues such as query processing and user interfacing can be approached in an economical and flexible way. This is illustrated by describing our experience with SAND-Tcl, a scripting tool developed by us for building spatial database applications. SAND-Tcl is an extension of the Tcl embedded scripting language with the constructs of the SAND environment for developing applications involving both spatial and non-spatial data. SAND-Tcl acts as a "glue" to hold together all the subsystems of SAND. In fact, query evaluation plans are SAND-Tcl programs (or scripts) which are written on-the-fly by SAND in response to a query defined by the user. This permits the rapid prototyping of algorithms and makes SAND a useful tool both for applications and research. The focus is on data storage, retrieval operations, and spatial indexing. Implementations of operations such as spatial selection, ranking, and spatial join are given. In addition, tools are described to make possible the construction of graphical user interfaces to a spatial database as well as providing users the ability to view and interact with spatial objects in a graphical manner. This is achieved through the use of SAND-Tcl scripts and the Tk graphical user interface toolkit which is tightly coupled to Tcl.

REFERENCES

• 1: D. J. Abel. SIRO-DBMS: A database tool-kit for geographical information systems. International Journal of Geographical Information Systems, 3(2):103--116, April-June 1989.
• 2: Apple Computer Inc., MacIntosh Human Interface Guidelines, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 3: L. Becker and R. H. Güting. Rule-based optimization and query processing in an extensible geometric database system. Technical Report 312, Dortmund University, Dortmund, West Germany, August 1989.
• 4: 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
• 5: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 6: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 7: W. Clinger and J. Rees (Editors). Revised(4) report on the algorithmic language Scheme. http://www-swiss.ai.mit.edu/ftpdir/scheme-reports/r4rs.ps.
• 8: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 9: Max J. Egenhofer , Andrew U. Frank , Jeffrey P. Jackson, A Topological Data Model for Spatial Databases, Proceedings of the First Symposium on Design and Implementation of Large Spatial Databases, p.271-286, July 17-18, 1989
• 10: C. Esperança. Orthogonal objects and their application in spatial databases. PhD thesis, University of Maryland, December 1995. (Also available as Technical Report TR-3566, University of Maryland, College Park, MD).
• 11: G. Graefe, Volcano— An Extensible and Parallel Query Evaluation System, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.120-135, February 1994 [doi>10.1109/69.273032]
• 12: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• 13: 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
• 14: 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
• 15: Ralf Hartmut Güting , Thomas de Ridder , Markus Schneider, Implementation of the ROSE Algebra: Efficient Algorithms for Realm-Based Spatial Data Types, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.216-239, August 06-09, 1995
• 16: 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
• 17: Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995
• 18: Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.237-248, June 01-04, 1998, Seattle, Washington, United States
• 19: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 20: Erik G. Hoel , Hanan Samet, Benchmarking Spatial Join Operations with Spatial Output, Proceedings of the 21th International Conference on Very Large Data Bases, p.606-618, September 11-15, 1995
• 21: N. Kabra and D. DeWitt. OPT++ - an object-oriented implementation for extensible database query optimization. See also http://www.cs.wisc.edu/~navin/research/apg.html, 1996.
• 22: Henry F. Korth , Abraham Silberschatz, Database System Concepts, McGraw-Hill, Inc., New York, NY, 1990
• 23: Mark Lutz, Programming python, O'Reilly & Associates, Inc., Sebastopol, CA, 1996
• 24: Aaron Marcus , Nick Smilonich , Lynne Thompson, The cross-GUI handbook for multiplatform user interface design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 25: CORPORATE Microsoft Corp., The Windows interface: an application design guide, Microsoft Press, Redmond, WA, 1992
• 26: S. Morehouse. The architecture of Arc/Info. Auto-Carto, 9:266--277, 1989.
• 27: 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]
• 28: Open Systems Foundation. OSF/Motif Style Guide. P T R Prentice Hall, Englewood Cliffs, NJ, 1993.
• 29: 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]
• 30: John K. Ousterhout, Tcl and the Tk toolkit, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 31: 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
• 32: Sunil Prabhakar , Divyakant Agrawal , Amr El Abbadi , Ambuj Singh , Terrence Smith, Browsing and placement of multiresolution images on parallel disks, Proceedings of the fifth workshop on I/O in parallel and distributed systems, p.102-113, November 17-17, 1997, San Jose, California, United States [doi>10.1145/266220.266230]
• 33: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 34: M. Stonebraker. Limitations of spatial simulators for relational DBMSs. Technical report, INFORMIX Software, Inc., 1997. (see http://www.informix.com/informix/corpinfo/zines/whitpprs/wpsplsim.pdf).
• 35: M. Stonebraker, T. Sellis, and E. Hanson. An analysis of rule indexing implementations in data base systems. In Proceedings of the First International Conference on Expert Database Systems, pages 353--364, Charleston, SC, April 1986.
• 36: T. Vijlbrief and P. van Oosterom. The GEO++ system: An extensible GIS. In Proceedings of the 5th International Symposium on Spatial Data Handling, pages 40--50, Charleston, SC, August 1992.
• 37: Agnès Voisard, Towards a Toolbox for Geographic User Interfaces, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.75-97, August 28-30, 1991