ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Historical Queries Along Multiple Lines of Time Evolution.

Gad M. Landau, Jeanette P. Schmidt, Vassilis J. Tsotras: Historical Queries Along Multiple Lines of Time Evolution. VLDB J. 4(4): 703-726(1995)
@article{DBLP:journals/vldb/LandauST95,
  author    = {Gad M. Landau and
               Jeanette P. Schmidt and
               Vassilis J. Tsotras},
  title     = {Historical Queries Along Multiple Lines of Time Evolution},
  journal   = {VLDB J.},
  volume    = {4},
  number    = {4},
  year      = {1995},
  pages     = {703-726},
  ee        = {db/journals/vldb/LandauST95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Traditional approaches to addressing historical queries assume a single 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 into multiple 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 as vertical or horizontal historical queries. The key characteristics 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.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Key Words

Rollback databases, CAD databases, access methods, data-structures.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[Ahn & Snodgrass 1986]
Ilsoo Ahn, Richard T. Snodgrass: Performance Evaluation of a Temporal Database Management System. SIGMOD Conference 1986: 96-107 BibTeX
[Becker et al. 1993]
Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: On Optimal Multiversion Access Structures. SSD 1993: 123-141 BibTeX
[Cole 1986]
Richard Cole: Searching and Storing Similar Lists. J. Algorithms 7(2): 202-220(1986) BibTeX
[Dietz & Sleator 1987]
Paul F. Dietz, Daniel Dominic Sleator: Two Algorithms for Maintaining Order in a List. STOC 1987: 365-372 BibTeX
[Driscoll et al. 1989]
James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan: Making Data Structures Persistent. J. Comput. Syst. Sci. 38(1): 86-124(1989) BibTeX
[Van Emde Boas et al. 1977]
Peter van Emde Boas, R. Kaas, E. Zijlstra: Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory 10: 99-127(1977) BibTeX
[Elmasri et al. 1990]
Ramez Elmasri, Gene T. J. Wuu, Yeong-Joon Kim: The Time Index: An Access Structure for Temporal Data. VLDB 1990: 1-12 BibTeX
[Jensen et al. 1991]
Christian S. Jensen, Leo Mark, Nick Roussopoulos: Incremental Implementation Model for Relational Databases with Transaction Time. IEEE Trans. Knowl. Data Eng. 3(4): 461-473(1991) BibTeX
[Katz 1990]
Randy H. Katz: Towards a Unified Framework for Version Modeling in Engineering Databases. ACM Comput. Surv. 22(4): 375-408(1990) BibTeX
[Kolovson 1993]
...
[Kolovson & Stonebraker 1989]
Curtis P. Kolovson, Michael Stonebraker: Indexing Techniques for Historical Databases. ICDE 1989: 127-137 BibTeX
[Kolovson & Stonebraker 1991]
Curtis P. Kolovson, Michael Stonebraker: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conference 1991: 138-147 BibTeX
[Lanka & Mays 1991]
Sitaram Lanka, Eric Mays: Fully Persistent B+-trees. SIGMOD Conference 1991: 426-435 BibTeX
[Leung & Muntz 1993]
...
[Lomet & Salzberg 1989]
David B. Lomet, Betty Salzberg: Access Methods for Multiversion Data. SIGMOD Conference 1989: 315-324 BibTeX
[Lomet & Salzberg 1990]
David B. Lomet, Betty Salzberg: The Performance of a Multiversion Access Method. SIGMOD Conference 1990: 353-363 BibTeX
[Lomet & Salzberg 1993]
...
[Lum et al. 1984]
Vincent Y. Lum, Peter Dadam, R. Erbe, Jürgen Günauer, Peter Pistor, Georg Walch, H. Werner, John Woodfill: Designing DBMS Support for the Temporal Dimension. SIGMOD Conference 1984: 115-130 BibTeX
[Manalopoulos & Kapetanakis 1990]
...
[Marshall 1991]
...
[Salzberg & Tsotras 1994]
...
[Segev & Gunadhi 1989]
Arie Segev, Himawan Gunadhi: Event-Join Optimization in Temporal Relational Databases. VLDB 1989: 205-215 BibTeX
[Segev & Gunadhi 1993]
Himawan Gunadhi, Arie Segev: Efficient Indexing Methods for Temporal Relations. IEEE Trans. Knowl. Data Eng. 5(3): 496-509(1993) BibTeX
[Snodgrass & Ahn 1986]
Richard T. Snodgrass, Ilsoo Ahn: Temporal Databases. IEEE Computer 19(9): 35-42(1986) BibTeX
[Tsotras & Gopinath 1990]
Vassilis J. Tsotras, B. Gopinath: Efficient Algorithms for Managing the History of Evolving Databases. ICDT 1990: 141-174 BibTeX
[Tsotras & Gopinath 1992]
Vassilis J. Tsotras, B. Gopinath: Optimal Versioning of Objects. ICDE 1992: 358-365 BibTeX
[Tsotras et al. 1994]
Vassilis J. Tsotras, B. Gopinath, George W. Hart: Efficient Management of Time-Evolving Databases. IEEE Trans. Knowl. Data Eng. 7(4): 591-608(1995) BibTeX
[Tsotras & Kangelaris 1994]
Vassilis J. Tsotras, Nickolas Kangerlaris: The Snapshot Index: An I/O-optimal access method for timeslice queries. Inf. Syst. 20(3): 237-260(1995) BibTeX

Referenced by

  1. Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos: Designing Access Methods for Bitemporal Databases. IEEE Trans. Knowl. Data Eng. 10(1): 1-20(1998)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:25 2009