ACM SIGMOD Anthology VLDB dblp.uni-trier.de

The LHAM Log-Structured History Data Access Method.

Peter Muth, Patrick E. O'Neil, Achim Pick, Gerhard Weikum: The LHAM Log-Structured History Data Access Method. VLDB J. 8(3-4): 199-221(2000)
@article{DBLP:journals/vldb/MuthOPW00,
  author    = {Peter Muth and
               Patrick E. O'Neil and
               Achim Pick and
               Gerhard Weikum},
  title     = {The LHAM Log-Structured History Data Access Method},
  journal   = {VLDB J.},
  volume    = {8},
  number    = {3-4},
  year      = {2000},
  pages     = {199-221},
  ee        = {db/journals/vldb/MuthOPW00.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Numerous applications such as stock market or medical information systems require that both historical and current data be logically integrated into a temporal database. The underlying access method must support different forms of "time-travel" queries, the migration of old record versions onto inexpensive archive media, and high insertion and update rates. This paper presents an access method for transaction-time temporal data, called the log-structured history data access method (LHAM) that meets these demands. The basic principle of LHAM is to partition the data into successive components based on the timestamps of the record versions. Components are assigned to different levels of a storage hierarchy, and incoming data is continuously migrated through the hierarchy. The paper discusses the LHAM concepts, including concurrency control and recovery, our full-fledged LHAM implementation, and experimental performance results based on this implementation. A detailed comparison with the TSB-tree, both analytically and based on experiments with real implementations, shows that LHAM is highly superior in terms of insert performance, while query performance is in almost all cases at least as good as for the TSB-tree; in many cases it is much better.

Key Words

Index structures - Storage systems - Performance - Temporal databases - Data warehouses

Copyright © 2000 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.


Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

References

[AGL98]
Rakesh Agrawal, Dimitrios Gunopulos, Frank Leymann: Mining Process Models from Workflow Logs. EDBT 1998: 469-483 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Arge95]
Lars Arge: The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract). WADS 1995: 334-345 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bec96]
Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: An Asymptotically Optimal Multiversion B-Tree. VLDB J. 5(4): 264-275(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BSW97]
Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB 1997: 406-415 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CACM98]
...
[EKW91]
Ramez Elmasri, Yeong-Joon Kim, Gene T. J. Wuu: Efficient Implementation Techniques For the Time Index. ICDE 1991: 102-111 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EWK93]
Ramez Elmasri, Gene T. J. Wuu, Vram Kouramajian: The Time Index and the Monotonic B+-tree. Temporal Databases 1993: 433-456 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fal96]
...
[GP87]
Jim Gray, Gianfranco R. Putzolu: The 5 Minute Rule for Trading Memory for Disk Accesses and The 10 Byte Rule for Trading Memory for CPU Time. SIGMOD Conference 1987: 395-398 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GR93]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gut84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jag97]
H. V. Jagadish, P. P. S. Narayan, S. Seshadri, S. Sudarshan, Rama Kanneganti: Incremental Organization for Data Recording and Warehousing. VLDB 1997: 16-25 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kol93]
Curtis P. Kolovson: Indexing Techniques for Historical Databases. Temporal Databases 1993: 418-432 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KMH97]
Marcel Kornacker, C. Mohan, Joseph M. Hellerstein: Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997: 62-72 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lom93]
David B. Lomet: Key Range Locking Strategies for Improved Concurrency. VLDB 1993: 655-664 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LS89]
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
[LS90]
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
[Moh96]
...
[MOPW98]
Peter Muth, Patrick E. O'Neil, Achim Pick, Gerhard Weikum: Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method. VLDB 1998: 452-463 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MSS95]
...
[OCGO96]
Patrick E. O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth J. O'Neil: The Log-Structured Merge-Tree (LSM-Tree). Acta Inf. 33(4): 351-385(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OW93]
Patrick E. O'Neil, Gerhard Weikum: A Log-Structured History Data Access Method (LHAM). HPTS 1993: 0- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RO92]
Mendel Rosenblum, John K. Ousterhout: The Design and Implementation of a Log-Structured File System. ACM Trans. Comput. Syst. 10(1): 26-52(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sno90]
Richard T. Snodgrass: Temporal Databases - Status and Research Directions. SIGMOD Record 19(4): 83-89(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SOL94]
Han Shen, Beng Chin Ooi, Hongjun Lu: The TP-Index: A Dynamic and Efficient Indexing Mechanism for Temporal Databases. ICDE 1994: 274-281 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ST99]
Betty Salzberg, Vassilis J. Tsotras: Comparison of Access Methods for Time-Evolving Data. ACM Comput. Surv. 31(2): 158-221(1999) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tan93]
Abdullah Uz Tansel, James Clifford, Shashi K. Gadia, Sushil Jajodia, Arie Segev, Richard T. Snodgrass (Eds.): Temporal Databases: Theory, Design, and Implementation. Benjamin/Cummings 1993, ISBN 0-8053-2413-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TK95]
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

Copyright © Fri Mar 12 17:34:27 2010 by Michael Ley (ley@uni-trier.de)