Abstract
Traditional approaches to addressing historical queries assume asingle line of time evolution; that is, a system (database, relation) evolves over time through a sequence of transactions. Each transaction always applies to the unique, current state of the system, resulting in a new current state. There are, however, complex applications where the system's state evolves intomultiple lines of evolution. In general, this creates a tree (hierarchy) of evolution lines, where each tree node represents the time evolution of a particular subsystem. Multiple lines create novel historical queries, such asvertical orhorizontal historical queries. The key characteristic of these problems is that portions of the history are shared; answering historical queries should not necessitate duplication of shared histories as this could increase the storage requirements dramatically. Both the vertical and horizontal historical queries have two parts: a “search” part, where the time of interest is located together with the appropriate subsystem, and a reconstruction part, where the subsystem's state is reconstructed for that time. This article focuses on the search part; several reconstruction methods, designed for single evolution lines can be applied once the appropriate time of interest is located. For both the vertical and the horizontal historical queries, we present algorithms that work without duplicating shared histories. Combinations of the vertical and horizontal queries are possible, and enable searching in both dimensions of the tree of evolutions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahn, I. and Snodgrass, R. Performance evaluation of a temporal database management system.Proceedings of the ACM SIGMOD Conference on the Management of Data, Washington, DC, 1986.
Becker, B., Gschwind, S., Ohler, T., Seeger, B., and Widmayer, P. On optimal multiversion access structures.Workshop on Advances in Spatial Databases, Singapore, 1993.
Cole, R. Searching and storing similar lists.Journal of Algorithms, 7:202–220, 1986.
Dietz, P. and Sleator, D.D. Two algorithms for maintaining order in a list.Proceedings of the ACM Symposium on the Theory of Computers, New York, NY, 1987.
Driscoll, J.R., Sarnak, N., Sleator, D.D., and Tarjan, R.E. Making data structures persistent.Journal of Computer and System Sciences, 38:86–124, 1989.
van Emde Boas, P., Kaas, R., and Zijlstra, E. Design and implementation of an efficient priority queue.Mathematical Systems Theory, 10:99–127, 1977.
Elmasri, R., Wuu, G., and Kim, Y. The time index: An access structure for temporal data.Proceedings of the Sixteenth Conference on Very Large Data Bases, Brisbane, Australia, 1990.
Jensen, C.S., Mark, L., and Roussopoulos, N. Incremental implementation model for relational databases with transaction time.IEEE Transactions on Knowledge and Data Engineering, 3(4):461–473, 1991.
Katz, R.H. Toward a unified framework for version modeling in engineering databases.ACM Computing Surveys, 22(4):375–408, 1990.
Kolovson, C. Indexing for historical databases. In: Tansel, A., Clifford, J., Gadia, S.K., Jajodia, S., Segev, A., and Snodgrass, R., eds.Temporal Databases: Theory, Design, and Implementation, Redwood City, CA: Benjamin/Cummings, 1993, pp 418–432.
Kolovson, C. and Stonebraker, M. Indexing techniques for historical databases.Proceedings of the Fifth IEEE International Conference on Data Engineering, Los Angeles, CA, 1989.
Kolovson, C. and Stonebraker, M. Segment indexes: Dynamic indexing techniques for multi-dimensional interval data.Proceedings of the ACM SIGMOD Conference on the Management of Data, Denver, CO, 1991.
Lanka, S. and Mays, E. Fully persistentB+ trees.Proceedings of the ACM SIGMOD Conference on the Management of Data, Denver, CO, 1991.
Leung, T.Y.C. and Muntz, R.R. Stream processing: Temporal query processing and optimization. In: Tansel, A., Clifford, J., Gadia, S.K., Jajodia, S., Segev, A., and Snodgrass, R., eds.Temporal Databases: Theory, Design, and Implementation, Redwood City, CA: Benjamin/Cummings, 1993, pp. 329–355.
Lomet, D. and Salzberg, B. Access methods for multiversion data.Proceedings of the ACM SIGMOD Conference on the Management of Data, Portland, OR, 1989.
Lomet, D. and Salzberg, B. The performance of a multiversion access method.Proceedings of the ACM SIGMOD Conference on the Management of Data, Portland, OR, 1990.
Lomet, D. and Salzberg, B. Transaction-time databases. In: Tansel, A., Clifford, J., Gadia, S.K., Jajodia, S., Segev, A., and Snodgrass, R., eds.Temporal Databases: Theory, Design, and Implementation, Redwood City, CA: Benjamin/Cummings, 1993, pp. 388–417.
Lum, V., Dadam, P., Erbe, R., Guenauer, J., Pistor, P., Walch, G., Werner, H., and Woodfill, J. Designing DBMS support for the temporal database.Proceedings of the ACM SIGMOD Conference on the Management of Data, Boston, MA, 1984.
Manolopoulos, Y. and Kapetanakis, G. OverlappingB+ trees for temporal data.Proceedings of the Fifth JCIT Conference, Jerusalem, 1990.
Marshall, S. Xerox Webster Research Center, private communication, 1991.
Salzberg, B. and Tsotras, V.J. A comparison of access methods for time-evolving data. Technical report CATT-TR-94-81, Polytechnic University, or technical report NU-CCS-94-21, Northeastern University, 1994.
Segev, A. and Gunadhi, H. Event-join optimization in temporal relational databases.Proceedings of the Fifteenth Conference on Very Large Data Bases, 1989.
Segev, A. and Gunadhi, H. Efficient indexing methods for temporal relations.IEEE Transactions on Knowledge and Data Engineering, 5(3):496–509, 1993.
Snodgrass, R. and Ahn, I. Temporal databases.IEEE Computer, 19(9):35–42, 1986.
Tsotras, V.J. and Gopinath, B. Efficient algorithms managing the history of evolving databases.Proceedings of the Third International Conference on Database Theory, Paris, 1990.
Tsotras, V.J. and Gopinath, B. Optimal versioning of objects.Proceedings of the Eighth IEEE International Conference on Data Engineering, Phoenix, AZ, 1992.
Tsotras, V.J., Gopinath, B., and Hart, G.W. Efficient management of time-evolving databases.IEEE Transactions on Knowledge and Data Engineering, 7(4), 1994.
Tsotras, V.J. and Kangelaris, N. The snapshot index, an I/O-optimal access method for snapshot queries. CATT-Tech.Information Systems, 20(3):237–260, 1994.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Landau, G.M., Schmidt, J.P. & Tsotras, V.J. Historical queries along multiple lines of time evolution. VLDB Journal 4, 703–726 (1995). https://doi.org/10.1007/BF01354880
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01354880