dblp.uni-trier.de www.dagstuhl.de www.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        = {http://www.vldb.org/journal/VLDBJ4/P703.pdf},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

References

[Ahn & Snodgrass 1986]
Ilsoo Ahn, Richard T. Snodgrass: Performance Evaluation of a Temporal Database Management System. SIGMOD Conference 1986: 96-107 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Becker et al. 1993]
Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: On Optimal Multiversion Access Structures. SSD 1993: 123-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cole 1986]
Richard Cole: Searching and Storing Similar Lists. J. Algorithms 7(2): 202-220(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dietz & Sleator 1987]
Paul F. Dietz, Daniel Dominic Sleator: Two Algorithms for Maintaining Order in a List. STOC 1987: 365-372 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Katz 1990]
Randy H. Katz: Towards a Unified Framework for Version Modeling in Engineering Databases. ACM Comput. Surv. 22(4): 375-408(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kolovson 1993]
...
[Kolovson & Stonebraker 1989]
Curtis P. Kolovson, Michael Stonebraker: Indexing Techniques for Historical Databases. ICDE 1989: 127-137 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kolovson & Stonebraker 1991]
Curtis P. Kolovson, Michael Stonebraker: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conference 1991: 138-147 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lanka & Mays 1991]
Sitaram Lanka, Eric Mays: Fully Persistent B+-trees. SIGMOD Conference 1991: 426-435 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Leung & Muntz 1993]
...
[Lomet & Salzberg 1989]
David B. Lomet, Betty Salzberg: Access Methods for Multiversion Data. SIGMOD Conference 1989: 315-324 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lomet & Salzberg 1990]
David B. Lomet, Betty Salzberg: The Performance of a Multiversion Access Method. SIGMOD Conference 1990: 353-363 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Segev & Gunadhi 1993]
Himawan Gunadhi, Arie Segev: Efficient Indexing Methods for Temporal Relations. IEEE Trans. Knowl. Data Eng. 5(3): 496-509(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Snodgrass & Ahn 1986]
Richard T. Snodgrass, Ilsoo Ahn: Temporal Databases. IEEE Computer 19(9): 35-42(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tsotras & Gopinath 1990]
Vassilis J. Tsotras, B. Gopinath: Efficient Algorithms for Managing the History of Evolving Databases. ICDT 1990: 141-174 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tsotras & Gopinath 1992]
Vassilis J. Tsotras, B. Gopinath: Optimal Versioning of Objects. ICDE 1992: 358-365 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Fri Sep 14 18:29:10 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page