Trajectory databases: data models, uncertainty and complete query languages. (English) Zbl 1197.68040
Summary: Moving objects produce trajectories. We describe a data model for trajectories and trajectory samples and an efficient way of modeling uncertainty via beads for trajectory samples. We study transformations of the ambient space for which important physical properties of trajectories, such as speed, are invariant. We also determine which transformations preserve beads. We give conceptually easy first-order complete query languages and computationally complete query languages for trajectory databases, which allow to talk directly about speed and uncertainty in terms of beads. The queries expressible in these languages are invariant under speed- and bead-preserving transformations.
MSC:
| 68P15 | Database theory |
Keywords:
moving objects databases; spatio-temporal databases; constraint databases; trajectories; trajectory samples; beads; uncertaintyReferences:
| [1] | Allen, J. F., Maintaining knowledge about temporal intervals, Comm. ACM, 26, 11, 832-843 (1983) · Zbl 0519.68079 |
| [2] | Allen, J. F.; Ferguson, G., Actions and events in interval temporal logic, J. Logic Comput., 4, 5, 531-579 (1994) · Zbl 0815.68100 |
| [4] | Egenhofer, M.; Hornsby, K., Modeling moving objects over multiple granularities, Ann. Math. Artif. Intell., 36, 1-2, 177-194 (2002) · Zbl 1001.68135 |
| [5] | Geerts, F.; Haesevoets, S.; Kuijpers, B., First-order complete and computationally complete query languages for spatio-temporal databases, ACM Trans. Comput. Log., 9, 2 (2008) · Zbl 1367.68087 |
| [6] | Geerts, F.; Kuijpers, B., Linear approximation of planar spatial databases using transitive-closure logic, (Proceedings of the 19th ACM SIGACT-SIGART-SIGMOD Symposium on Principles of Database Systems (PODS’00) (2000), ACM Press), 126-135 |
| [7] | Geerts, F.; Kuijpers, B.; Van den Bussche, J., Linearization and completeness results for terminating transitive closure queries on spatial databases, SIAM J. Comput., 35, 6, 1386-1439 (2006) · Zbl 1115.68064 |
| [8] | Geerts, Floris, Moving objects and their equations of motion, (Constraint Databases (CDB’04). Constraint Databases (CDB’04), Lecture Notes in Comput. Sci., vol. 3074 (2004), Springer-Verlag), 41-52 · Zbl 1080.68574 |
| [9] | Geerts, Floris; Haesevoets, Sofie; Kuijpers, Bart, First-order complete and computationally complete query languages for spatio-temporal databases, ACM Trans. Comput. Log., 9, 2 (2008) · Zbl 1367.68087 |
| [10] | Güting, R.; Schneider, M., Moving Object Databases (2005), Morgan Kaufmann |
| [11] | Gyssens, M.; Van den Bussche, J.; Van Gucht, D., Complete geometric query languages, J. Comput. System Sci., 58, 3, 483-511 (1999) · Zbl 0939.68026 |
| [12] | Hägerstrand, T., What about people in regional science?, Papers Reg. Sci. Assoc., 24, 7-21 (1970) |
| [13] | Kuijpers, B.; Othman, W., Trajectory databases: Data models, uncertainty and complete query languages, (Proceedings of the 11th International Conference on Database Theory (ICDT’07). Proceedings of the 11th International Conference on Database Theory (ICDT’07), Lecture Notes in Comput. Sci., vol. 4353 (2007)), 224-238 |
| [14] | Miller, H. J., A measurement theory for time geography, Geographical Anal., 37, 1, 17-45 (2005) |
| [15] | O’Neill, Barrett, Elementary Differential Geometry (1997), Academic Press, 482 p. · Zbl 0974.53001 |
| [16] | (Paredaens, J.; Kuper, G.; Libkin, L., Constraint Databases (2000), Springer-Verlag) · Zbl 0935.00022 |
| [17] | Pfoser, D.; Jensen, C. S., Capturing the uncertainty of moving-object representations, (Advances in Spatial Databases (SSD’99). Advances in Spatial Databases (SSD’99), Lecture Notes in Comput. Sci., vol. 1651 (1999)), 111-132 |
| [18] | Polyanin, A. D.; Zaitsev, V. F.; Moussiaux, A., Handbook of First Order Partial Differential Equations (2002), Taylor & Francis · Zbl 1031.35001 |
| [19] | Revesz, P., Introduction to Constraint Databases (2002), Springer-Verlag · Zbl 0995.68035 |
| [20] | Schwabhäuser, W.; Szmielew, W.; Tarski, A., Metamathematische Methoden in der Geometrie (1983), Springer-Verlag · Zbl 0564.51001 |
| [21] | Su, J.; Xu, H.; Ibarra, O., Moving objects: Logical relationships and queries, (Advances in Spatial and Temporal Databases (SSTD’01). Advances in Spatial and Temporal Databases (SSTD’01), Lecture Notes in Comput. Sci., vol. 2121 (2001), Springer-Verlag), 3-19 · Zbl 0997.68616 |
| [22] | Wolfson, O., Moving objects information management: The database challenge, (Proceedings of the 5th Intl. Workshop Next Generation Information Technologies and Systems (2002), Springer-Verlag), 75-89 · Zbl 1015.68725 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
