First-order complete and computationally complete query languages for spatio-temporal databases

ABSTRACT

We address a fundamental question concerning spatio-temporal database systems: “What are exactly spatio-temporal queries?” We define spatio-temporal queries to be computable mappings that are also generic, meaning that the result of a query may only depend to a limited extent on the actual internal representation of the spatio-temporal data. Genericity is defined as invariance under groups of geometric transformations that preserve certain characteristics of spatio-temporal data (e.g., collinearity, distance, velocity, acceleration, …). These groups depend on the notions that are relevant in particular spatio-temporal database applications. These transformations also have the distinctive property that they respect the monotone and unidirectional nature of time.

We investigate different genericity classes with respect to the constraint database model for spatio-temporal databases and we identify sound and complete languages for the first-order and the computable queries in these genericity classes. We distinguish between genericity determined by time-invariant transformations, genericity notions concerning physical quantities and genericity determined by time-dependent transformations.

REFERENCES

• 1: Proceedings of the Third International Symposium on Advances in Spatial Databases, June 1993
• 2: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 3: Allen, J. F. and Ferguson, G. 1994. Actions and events in interval temporal logic. J. Logic Comput. 4, 5, 531--579.
• 4: Bochnak, J., Coste, M., and Roy, M. 1987. Géométrie Algébrique Réelle. Springer-Verlag, Berlin, Germany.
• 5: Böhlen, M. H., Jensen, C. S., and Scholl, M., Eds. 1999. Proceedings of the International Workshop on Spatio Temporal Database Management (STDBM'99). Lecture Notes in Computer Science, vol. 1678. Springer-Verlag, New York.
• 6: Proceedings of the First Symposium on Design and Implementation of Large Spatial Databases, July 1989
• 7: Chandra, A. K. and Harel, D. 1980. Computable queries for relational data bases. J. Comp. Syst. Sci. 21, 2, 156--178.
• 8: Chen, C. X. and Zaniolo, C. 2000. SQLST: A spatio-temporal data model and query language. In Conceptual Modeling, 19th International Conference on Conceptual Modeling (ER'00), A. H. F. Laender, S. W. Liddle, and V. C. Storey, Eds. Lecture Notes in Computer Science, vol. 1920. Springer-Verlag, New York, 96--111.
• 9: Jan Chomicki , Peter Z. Revesz, Constraint-Based Interoperability of Spatiotemporal Databases, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.142-161, July 15-18, 1997
• 10: Jan Chomicki , Peter Z. Revesz, A Geometric Framework for Specifying Spatiotemporal Objects, Proceedings of the Sixth International Workshop on Temporal Representation and Reasoning, p.41, May 01-02, 1999
• 11: Desloge, E. 1982. Classical Mechanics. Wiley, New York.
• 12: Proceedings of the 4th International Symposium on Advances in Spatial Databases, August 1995
• 13: Martin Erwig , Ralf Hartmut Güting , Markus Schneider , Michalis Vazirgiannis, Spatio-Temporal Data Types: An Approach to Modeling and Querying Moving Objects in Databases, Geoinformatica, v.3 n.3, p.269-296, September 1999 [doi>10.1023/A:1009805532638]
• 14: Andrew Frank , Stephane Grumbach , Ralf Hartmut Güting , Christian S. Jensen , Manolis Koubarakis , Nikos Lorentzos , Yannis Manolopoulos , Enrico Nardelli , Barbara Pernici , Hans-Jörg Schek , Michel Scholl , Timos Sellis , Babis Theodoulidis , Peter Widmayer, Chorochronos: a research network for spatiotemporal database systems, ACM SIGMOD Record, v.28 n.3, p.12-21, Sept. 1999 [doi>10.1145/333607.333609]
• 15: Stéphane Grumbach , Philippe Rigaux , Luc Segoufin, Spatio-temporal data handling with constraints, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.106-111, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288712]
• 16: 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]
• 17: Proceedings of the 2nd symposium on Advances in spatial databases, June 1991
• 18: Güting, R., Ed. 1999. Advances in Spatial Databases---6th Symposium (SSD'99). Lecture Notes in Computer Science, vol. 1651. Springer-Verlag, New York.
• 19: Güting, R. and Schneider, M. 2005. Moving Object Databases. Morgan Kaufmann, San Francisco, CA.
• 20: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 21: Marc Gyssens , Jan Van den Bussche , Dick Van Gucht, Complete geometric query languages, Journal of Computer and System Sciences, v.58 n.3, p.483-511, June 1999 [doi>10.1006/jcss.1999.1630]
• 22: 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]
• 23: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
• 24: Bart Kuijpers , Jan Paredaens , Dirk Van Gucht, Towards a Theory of Movie Database Queries, Proceedings of the Seventh International Workshop on Temporal Representation and Reasoning (TIME'00), p.95, July 07-09, 2000
• 25: Kuper, G. and Scholl, M. 2000. Geographic information systems. In Constraint Databases, J. Paredaens, G. Kuper, and L. Libkin, Eds. Springer-Verlag, New York, Chapter 2, 175--198.
• 26: Leonid Libkin, Variable Independence, Quantifier Elimination, and Constraint Representations, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.260-271, July 09-15, 2000
• 27: Yuri V. Matiyasevich, Hilbert's tenth problem, MIT Press, Cambridge, MA, 1993
• 28: Paredaens, J., Kuper, G., and Libkin, L., Eds. 2000. Constraint databases. Springer-Verlag, New York.
• 29: 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]
• 30: Dieter Pfoser , Nectaria Tryfona, Requirements, definitions, and notations for spatiotemporal application environments, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.124-130, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288715]
• 31: Peter Revesz, Introduction to constraint databases, Springer-Verlag New York, Inc., New York, NY, 2002
• 32: Rigaux, P., Scholl, M., and Voisard, A. 2000. Introduction to Spatial Databases: Applications to GIS. Morgan Kaufmann, Reading, MA.
• 33: Proceedings of the 5th International Symposium on Advances in Spatial Databases, July 1997
• 34: Schwabhäuser, W., Szmielew, W., and Tarski, A. 1983. Metamathematische Methoden in der Geometrie. Springer-Verlag, New York.
• 35: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 36: Jianwen Su , Haiyan Xu , Oscar H. Ibarra, Moving Objects: Logical Relationships and Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.3-19, July 12-15, 2001
• 37: Van den Bussche, J. 2000. Constraint Databases, queries and query languages. In Constraint Databases, J. Paredaens, G. Kuper, and L. Libkin, Eds. Springer-Verlag, New York, Chapter 2, 21--54.
• 38: Ouri Wolfson, Moving Objects Information Management: The Database Challenge, Proceedings of the 5th International Workshop on Next Generation Information Technologies and Systems, p.75-89, June 24-25, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.0 General

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Design, Languages, Theory

Keywords:
Constraint databases, moving objects, query languages, spatial databases, spatio-temporal databases