A foundation for representing and querying moving objects

ACM Transactions on Database Systems - Tập 25 Số 1 - Trang 1-42 - 2000
Ralf Hartmut Güting1, Michael H. Böhlen2, Martin Erwig1, Christian S. Jensen2, Nikos A. Lorentzos3, Markus Schneider1, Michalis Vazirgiannis4
1FernUniv. Hagen#TAB#
2Aalborg University
3Agricultural University of Athens
4Athens Univ. of Economics and Business#TAB#

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

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 . 10.1145/330560.330675 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. 10.1145/330560.330675

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 . 10.1145/191246.191296 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. 10.1145/191246.191296

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 . 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.

CLIFFORD , J. 1982 . A model for historical databases . In Proceedings of the Workshop on Logical Bases for Data Bases (Dec.) , CLIFFORD, J. 1982. A model for historical databases. In Proceedings of the Workshop on Logical Bases for Data Bases (Dec.),

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 . 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.

10.1002/spe.4380240106

10.1109/69.273029

10.1023/A:1009805532638

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 . 10.1145/342009.335426 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. 10.1145/342009.335426

GAAL , S. 1964. Point Set Topology . Academic Press, Inc. , Duluth, MN . GAAL, S. 1964. Point Set Topology. Academic Press, Inc., Duluth, MN.

10.1145/49346.50065

GARGANO , M. , NARDELLI , E. , AND TALAMO , M. 1991 . Abstract data types for the logical modeling of complex objects . Inf. Syst. 16 , 5 . GARGANO, M., NARDELLI, E., AND TALAMO, M. 1991. Abstract data types for the logical modeling of complex objects. Inf. Syst. 16, 5.

10.1145/276305.276324

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 . 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.

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 . 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.

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 . 10.1145/170035.170079 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. 10.1145/170035.170079

G TING , R. H. 1994 . An introduction to spatial database systems . VLDB J. 3 ( Oct. ), 357 - 399 . G TING, R. H. 1994. An introduction to spatial database systems. VLDB J. 3 (Oct.), 357-399.

10.1007/BF01237921

INFORMIX PRESS . 1997a. Extending Informix Universal Server: Data Types. Informix Software , Inc . INFORMIX PRESS. 1997a. Extending Informix Universal Server: Data Types. Informix Software, Inc.

INFORMIX PRESS . 1997b. Informix Geodetic DataBlade Module: User's Guide. Informix Software , Inc . INFORMIX PRESS. 1997b. Informix Geodetic DataBlade Module: User's Guide. Informix Software, Inc.

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 . 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.

K MPKE , T. 1994 . Storing and retrieving changes in a sequence of polygons . Int. J. Geograph. Inf. Syst. 8 , 6 , 493 - 513 . K MPKE, T. 1994. Storing and retrieving changes in a sequence of polygons. Int. J. Geograph. Inf. Syst. 8, 6, 493-513.

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. 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.

10.1109/69.599935

10.1145/125137.125166

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. 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.

10.1109/69.404027

RAAFAT , H. , YANG , Z. , AND GAUTHIER , D. 1994 . Relational spatial topologies for historical geographic information . Int. J. Geograph. Inf. Syst. 8 , 2 , 163 - 173 . RAAFAT, H., YANG, Z., AND GAUTHIER, D. 1994. Relational spatial topologies for historical geographic information. Int. J. Geograph. Inf. Syst. 8, 2, 163-173.

10.1109/32.6141

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. 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.

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 . 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.

SNODGRASS , R. T. 1995. The TSQL2 Temporal Query Language . Kluwer Academic Publishers, Hingham , MA. SNODGRASS, R. T. 1995. The TSQL2 Temporal Query Language. Kluwer Academic Publishers, Hingham, MA.

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. 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.

TILOVE , R. B. 1980 . Set membership classification: A unified approach to geometric intersection problems . IEEE Trans. Comput. C-29 , 874 - 883 . TILOVE, R. B. 1980. Set membership classification: A unified approach to geometric intersection problems. IEEE Trans. Comput. C-29, 874-883.

10.1007/s005300050094

WORBOYS , F. 1994 . A unified model for spatial and temporal information . Comput. J. 37 , 1 , 25 - 34 . WORBOYS, F. 1994. A unified model for spatial and temporal information. Comput. J. 37, 1, 25-34.

Thông tin
Thông tin xuất bản

ACM Transactions on Database Systems

Tập 25 Số 1

1-42

Thông tin tác giả