Ralf Hartmut Güting
Michael H. Böhlen
Martin Erwig
Christian S. Jensen
Abstract
Spatio-temporal databases deal with geometries changing over time. The goal of our work is to provide a DBMS data model and query language capable of handling such time-dependent geometries, including those changing continuously that describe moving objects. Two fundamental abstractions are moving point and moving region, describing objects for which only the time-dependent position, or position and extent, respectively, are of interest. We propose to present such time-dependent geometries as attribute data types with suitable operations, that is, to provide an abstract data type extension to a DBMS data model and query language. This paper presents a design of such a system of abstract data types. It turns out that besides the main types of interest, moving point and moving region, a relatively large number of auxiliary data types are needed. For example, one needs a line type to represent the projection of a moving point into the plane, or a “moving real” to represent the time-dependent distance of two points. It then becomes crucial to achieve (i) orthogonality in the design of the system, i.e., type constructors can be applied unifomly; (ii) genericity and consistency of operations, i.e., operations range over as many types as possible and behave consistently; and (iii) closure and consistency between structure and operations of nontemporal and related temporal types. Satisfying these goal leads to a simple and expressive system of abstract data types that may be integrated into a query language to yield a powerful language for querying spatio-temporal data, including moving objects. The paper formally defines the types and operations, offers detailed insight into the considerations that went into the design, and exemplifies the use of the abstract data types using SQL. The paper offers a precise and conceptually clean foundation for implementing a spatio-temporal DBMS extension.
- B HLEN, M. H., JENSEN, C. S., AND SKJELLAUG, B. 1998. Spatio-temporal database support for legacy applications. In Proceedings of the 1998 ACM Symposium on Applied Computing (Atlanta, GA, Feb.), 226-234. Google Scholar
- CHENG, T. S., AND GADIA, S. K., 1994. A pattern matching language for spatio-temporal databases. In Proceedings of the 3rd ACM International Conference on Information and Knowledge Management (CIKM '94, Gaithersburg, MD, Nov. 28-Dec. 2). ACM Press, New York, NY, 288-295. Google Scholar
- CHOMICKI, J. AND REVESZ, P. 1997. Constraint-based interoperability of spatio-temporal databases. In Proceedings of the 5th International Symposium on Large Spatial Databases (Berlin, Germany), 142-161. Google Scholar
- CLIFFORD, J. 1982. A model for historical databases. In Proceedings of the Workshop on Logical Bases for Data Bases (Dec.),Google Scholar
- CLIFFORD, J. AND CROKER, A. 1987. The historical relational data model (HRDM) and algebra based on lifespans. In Proceedings of the Third IEEE International Conference on Data Engineering, IEEE Computer Society Press, Los Alamitos, CA, 528-537. Google Scholar
- DAVIS, J. R. 1998. IBM's DB2 spatial extender: managing geo-spatial information within the DBMS. Tech. Rep. Research Division, IBM, New York, NY.Google Scholar
- DYRESON, C. E. AND SNODGRASS, R. T. 1994. Efficient timestamp input and output. Softw. Pract. Exper. 24, 1 (Jan. 1994), 89-109. Google Scholar
- EGENHOFER, M. J. 1994. Spatial SQL: A query and presentation language. IEEE Trans. Knowl. Data Eng. 6, 1 (Feb.), 86-95. Google Scholar
- ERWIG, M., G WING, R. H., SCHNEIDER, M., AND VAZIRGIANNIS, M. 1999. Spatio-temporal data types: an approach to modeling and querying moving objects in databases. GeoInfo. 3, 3, 269 -296. Google Scholar
- FORLIZZI, L., G WING, R. H., NARDELLI, E., AND SCHNEIDER, M. 1999. A data model and data structures for moving objects databases. In Proceedings of the ACM SIGMOD Conference on Management of Data (Dallas, TX, May), 319-330. Google Scholar
- GAAL, S. 1964. Point Set Topology. Academic Press, Inc., Duluth, MN.Google Scholar
- GADIA, S. K. 1988. A homogeneous relational model and query languages for temporal databases. ACM Trans. Database Syst. 13, 4 (Dec. 1988), 418-448. Google Scholar
- GARGANO, M., NARDELLI, E., AND TALAMO, M. 1991. Abstract data types for the logical modeling of complex objects. Inf. Syst. 16, 5.Google Scholar
- GRUMBACH, S., RIGAUX, P., AND SEGOUFIN, L. 1998. The DEDALE system for complex spatial queries. SIGMOD Rec. 27, 2, 213-224. Google Scholar
- G WING, R. H. 1988. Geo-relational algebra: A model and query language for geometric database systems. In Advances in Database Technology: EDBT '88, J. W. Schmidt, S. Ceri, and M. Missikoff, Eds., 506-527. Google Scholar
- G WING, R. H. 1989. Gral: an extensible relational database system for geometric applications. In Proceedings of the 15th International Conference on Very Large Data Bases (VLDB '89, Amsterdam, The Netherlands, Aug 22-25), P. G. Apers and G. Wiederhold, Eds. Morgan Kaufmann Publishers Inc., San Francisco, CA, 33-44. Google Scholar
- G TING, R. H. 1993. Second-order signature: A tool for specifying data models, query processing, and optimization. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD '93, Washington, DC, May 26-28), P. Buneman and S. Jajodia, Eds. ACM Press, New York, NY, 277-286. Google Scholar
- G TING, R. H. 1994. An introduction to spatial database systems. VLDB J. 3 (Oct.), 357-399. Google Scholar
- G TING, R. H. AND SCHNEIDER, M. 1995. Realm-based spatial data types: The ROSE algebra. VLDB J. 4, 2, 100-143. Google Scholar
- G TING, R. H., B HLEN, M., ERWIG, M., JENSEN, C., LORENTZOS, N., SCHNEIDER, M., AND VAZIRGIANNIS, M. 1998. A foundation for representing and querying moving objects. Tech. Rep. Informatik 238, FernUniversitat, Hagen. http://www.fernuni-hagen.de inf/pi4/papers/ Foundation.ps.gzGoogle Scholar
- INFORMIX PRESS. 1997a. Extending Informix Universal Server: Data Types. Informix Software, Inc.Google Scholar
- INFORMIX PRESS. 1997b. Informix Geodetic DataBlade Module: User's Guide. Informix Software, Inc.Google Scholar
- KLOPPROGGE, M. R. AND LOCKEMANN, P. C. 1983. Modelling information preserving databases: Consequences of the concept of time. In Proceedings of the 1983 Conference on Very Large Data Bases, 399-416. Google Scholar
- K MPKE, T. 1994. Storing and retrieving changes in a sequence of polygons. Int. J. Geograph. Inf. Syst. 8, 6, 493-513.Google Scholar
- LOECKX, J., EHRICH, H.-D., AND WOLF, M. 1997. Specification of Abstract Data Types. Wiley/Teubner computing series. John Wiley and Sons, Inc., New York, NY. Google Scholar
- LORENTZOS, N. A. AND MITSOPOULOS, Y. G. 1997. SQL extension for interval data. IEEE Trans. Knowl. Data Eng. 9, 3 (May/June), 480-499. Google Scholar
- MCKENZIE, L. E. AND SNODGRASS, R. T. 1991. Evaluation of relational algebras incorporating the time dimension in databases. ACM Comput. Surv. 23, 4 (Dec. 1991), 501-543. Google Scholar
- MELTON, J. AND SIMON, A. R. 1993. Understanding the New SQL: A Complete Guide. Morgan Kaufmann series in data management systems. Morgan Kaufmann Publishers Inc., San Francisco, CA. Google Scholar
- ORACLE CORP. 1997. Oracle8: Spatial Cartridge. Oracle Corp., Redwood City, CA. ZSOYOGLU, G. AND SNODGRASS, R. 1995. Temporal and real-time databases: A survey. IEEE Trans. Knowl. Data Eng. 7, 4 (Aug.), 513-532. Google Scholar
- RAAFAT, H., YANG, Z., AND GAUTHIER, D. 1994. Relational spatial topologies for historical geographic information. Int. J. Geograph. Inf. Syst. 8, 2, 163-173.Google Scholar
- ROUSSOPOULOS, N., FALOUTSOS, C., AND SELLIS, T. 1988. An efficient pictorial database system for PSQL. IEEE Trans. Softw. Eng. 14, 5 (May), 639-650. Google Scholar
- SCHOLL, M. AND VOISARD, A. 1989. Thematic map modeling. In Proceedings of the First Symposium on Design and Implementation of Large Spatial Databases (SSD '89, Santa Barbara, CA, July 17 and 18), A. P. Buchmann, O. G nther, T. R. Smith, and Y.-F. Wang, Eds. Springer Lecture Notes in Computer Science, vol. 409. Springer-Verlag, New York, NY, 167-190. Google Scholar
- SISTLA, A. P., WOLFSON, O., CHAMBERLAIN, S., AND DAO, S. 1997. Modeling and querying moving objects. In Proceedings of the 1997 International Conference on Data Engineering, 422-432. Google Scholar
- SNODGRASS, R. T. 1995. The TSQL2 Temporal Query Language. Kluwer Academic Publishers, Hingham, MA. Google Scholar
- TANSEL, A. U., CLIFFORD, J., GADIA, S., JAJODIA, S., SEGEV, A., AND SNODGRASS, R., Eds. 1993. Temporal Databases: Theory, Design, and Implementation. Benjamin-Cummings Publ. Co., Inc., Redwood City, CA. Google Scholar
- TILOVE, R. B. 1980. Set membership classification: A unified approach to geometric intersection problems. IEEE Trans. Comput. C-29, 874-883.Google Scholar
- VAZIRGIANNIS, M., THEODORIDIS, Y., AND SELLIS, T. 1998. Spatio-temporal composition and indexing for large multimedia applications. Multimedia Syst. 6, 4, 284-298. Google Scholar
- WORBOYS, F. 1994. A unified model for spatial and temporal information. Comput. J. 37, 1, 25-34.Google Scholar
Index Terms
- A foundation for representing and querying moving objects
Recommendations
Implementation of spatio-temporal data types with Java generics
AIKED'11: Proceedings of the 10th WSEAS international conference on Artificial intelligence, knowledge engineering and data basesSpatio-temporal database is a new type of database that manages spatio-temporal objects and supports corresponding query languages. If position and/or extent of an objects changes continuously, we talk about moving object database. A moving objects ...
Moving GeoPQL: a pictorial language towards spatio-temporal queries
Nowadays, two of the main challenges involving spatio-temporal databases concern the integration of their spatial and temporal features to store and query spatial objects changing over time, and the development of a simple and friendly language to query ...
Spatio-Temporal Data Types: An Approach to Modeling and Querying Moving Objects in Databases
Spatio-temporal databases deal with geometries changing over time. In general, geometries cannot only change in discrete steps, but continuously, and we are talking about moving objects. If only the position in space of an object is relevant, then ...
Comments