Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method.

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

@inproceedings{DBLP:conf/vldb/MuthOPW98,
  author    = {Peter Muth and
               Patrick E. O'Neil and
               Achim Pick and
               Gerhard Weikum},
  editor    = {Ashish Gupta and
               Oded Shmueli and
               Jennifer Widom},
  title     = {Design, Implementation, and Performance of the LHAM Log-Structured
               History Data Access Method},
  booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
               Large Data Bases, August 24-27, 1998, New York City, New York,
               USA},
  publisher = {Morgan Kaufmann},
  year      = {1998},
  isbn      = {1-55860-566-5},
  pages     = {452-463},
  ee        = {db/conf/vldb/MuthOPW98.html},
  crossref  = {DBLP:conf/vldb/98},
  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 intoa 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 insert and update rates. This paper introduces a new 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 interms of insert performance while query performance is in almost all casesat least as good as for the TSB-tree; in many cases it is much better.

Copyright © 1998 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.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/Disc99_1 or /cdrom

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents

References

[Bec96]: Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: An Asymptotically Optimal Multiversion B-Tree. VLDB J. 5(4): 264-275(1996)
[BSW97]: Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB 1997: 406-415
[EKW91]: Ramez Elmasri, Yeong-Joon Kim, Gene T. J. Wuu: Efficient Implementation Techniques For the Time Index. ICDE 1991: 102-111
[EWK93]: ...
[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
[GR93]: Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents
[Gut84]: Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
[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
[Kol93]: ...
[KMH97]: Marcel Kornacker, C. Mohan, Joseph M. Hellerstein: Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997: 62-72
[Lom93]: David B. Lomet: Key Range Locking Strategies for Improved Concurrency. VLDB 1993: 655-664
[LS89]: David B. Lomet, Betty Salzberg: Access Methods for Multiversion Data. SIGMOD Conference 1989: 315-324
[LS90]: David B. Lomet, Betty Salzberg: The Performance of a Multiversion Access Method. SIGMOD Conference 1990: 353-363
[Moh96]: ...
[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)
[OW93]: Patrick E. O'Neil, Gerhard Weikum: A Log-Structured History Data Access Method (LHAM). HPTS 1993: 0-
[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)
[Sno90]: Richard T. Snodgrass: Temporal Databases - Status and Research Directions. SIGMOD Record 19(4): 83-89(1990)
[SOL94]: Han Shen, Beng Chin Ooi, Hongjun Lu: The TP-Index: A Dynamic and Efficient Indexing Mechanism for Temporal Databases. ICDE 1994: 274-281
[ST94]: ...
[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
[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)