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