Access Methods for Multiversion Data.

@inproceedings{DBLP:conf/sigmod/LometS89,
  author    = {David B. Lomet and
               Betty Salzberg},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {Access Methods for Multiversion Data},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {315-324},
  ee        = {http://doi.acm.org/10.1145/67544.66956, db/conf/sigmod/LometS89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present an access method designed to provide a single integrated index structure for a versioned timestamped database with a non-deletion policy. Historical data (superceded versions) is stored separately from current data. Our access method is called the Time-Split B-tree. It is an index structure based on Malcolm Easton's Write Once B-tree.

The Write Once B-tree was developed for data stored entirely on a Write-Once Read-Many or WORM optical disk. The Time-Split B-tree differs from the Write Once B-tree in the following ways:

• Current data must be stored on an erasable random- access device.
• Historical data may be stored on any random-access device, including WORMS, erasable optical disks, and magnetic disks. The point is to use a faster and more expensive device for the current data and a slower cheaper device for the historical data.
• The splitting policies have been changed to reduce redundancy in the structure - the option of pure key splits as in B⁺-trees and a choice of split times for time-based splits enable this performance enhancement.
• When data is migrated from the current to the historical database, it is consolidated and appended to the end of the historical database, allowing for high space utilization in WORM disk sectors.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" 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/smod7592 or /cdrom

• 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

Online Edition: ACM Digital Library

References

[Chri]

Stavros Christodoulakis: Analysis of Retrieval Performance for Records and Objects Using Optical Disk Technology. ACM Trans. Database Syst. 12(2): 137-169(1987) BibTeX

[East]

Malcolm C. Easton: Key-Sequence Data Sets on Inedible Storage. IBM Journal of Research and Development 30(3): 230-241(1986) BibTeX

[Lome]

David B. Lomet: Partial Expansions for File Organizations with an Index. ACM Trans. Database Syst. 12(1): 65-84(1987) BibTeX

[McKe]

L. Edwin McKenzie: Bibliography: Temporal Databases. SIGMOD Record 15(4): 40-52(1986) BibTeX

[Rath]

Peter Rathmann: Dynamic Data Structures on Optical Disks. ICDE 1984: 175-180 BibTeX

[Salz]

Betty Salzberg: File Structures: An Analytic Approach. Prentice-Hall 1988, ISBN 0-13-314550-6
BibTeX

[SaTa]

Neil Sarnak, Robert Endre Tarjan: Planar Point Location Using Persistent Search Trees. Commun. ACM 29(7): 669-679(1986) BibTeX

[SeSh]

Arie Segev, Arie Shoshani: Logical Modeling of Temporal Data. SIGMOD Conference 1987: 454-466 BibTeX

[SnAh]

Richard T. Snodgrass, Ilsoo Ahn: A Taxonomy of Time in Databases. SIGMOD Conference 1985: 236-246 BibTeX

[Ston]

Michael Stonebraker: The Design of the POSTGRES Storage System. VLDB 1987: 289-300 BibTeX

[Vitt]

Jeffrey Scott Vitter: An Efficient I/O Interface for Optical Disks. ACM Trans. Database Syst. 10(2): 129-162(1985) BibTeX

Referenced by

1. 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)
2. Kjetil Nørvåg: The Persistent Cache: Improving OID Indexing in Temporal Object-Oriented Database Systems. VLDB 1999: 66-77
3. Kjetil Nørvåg: Efficient Use of Signatures in Object-Oriented Database Systems. ADBIS 1999: 367-381
4. Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos: Designing Access Methods for Bitemporal Databases. IEEE Trans. Knowl. Data Eng. 10(1): 1-20(1998)
5. Vassilis J. Tsotras, Christian S. Jensen, Richard T. Snodgrass: An Extensible Notation for Spatiotemporal Index Queries. SIGMOD Record 27(1): 47-53(1998)
6. 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
7. Yannis Theodoridis, Timos K. Sellis, Apostolos Papadopoulos, Yannis Manolopoulos: Specifications for Efficient Indexing in Spatiotemporal Databases. SSDBM 1998: 123-132
8. Shogo Nishida, Hiroshi Nozawa, Naoki Saiwaki: Proposal of Spatio-Temporal Indexing Methods for Moving Objects. ER Workshops 1998: 484-495
9. David B. Lomet, Betty Salzberg: Concurrency and Recovery for Index Trees. VLDB J. 6(3): 224-240(1997)
10. Peter J. Varman, Rakesh M. Verma: An Efficient Multiversion Access STructure. IEEE Trans. Knowl. Data Eng. 9(3): 391-409(1997)
11. Paul M. Bober, Michael J. Carey: Indexing for Multiversion Locking: Alternatives and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 9(1): 68-84(1997)
12. Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB 1997: 406-415
13. Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: An Asymptotically Optimal Multiversion B-Tree. VLDB J. 5(4): 264-275(1996)
14. Jochen Van den Bercken, Bernhard Seeger: Query Processing Techniques for Multiversion Access Methods. VLDB 1996: 168-179
15. Esa Falkenroth: Computational Indexes for Time Series. SSDBM 1996: 242-251
16. Jongho Won, Ramez Elmasri: Representing Retroactive and Proactive Versions in Bi-Temporal Databases. ICDE 1996: 85-94
17. Peter Muth, Achim Kraiss, Gerhard Weikum: LoT: Dynamic Declustering of TSB-Tree Nodes for Parallel Access to Temporal Data. EDBT 1996: 553-572
18. Gad M. Landau, Jeanette P. Schmidt, Vassilis J. Tsotras: Historical Queries Along Multiple Lines of Time Evolution. VLDB J. 4(4): 703-726(1995)
19. Vassilis J. Tsotras, B. Gopinath, George W. Hart: Efficient Management of Time-Evolving Databases. IEEE Trans. Knowl. Data Eng. 7(4): 591-608(1995)
20. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
21. Andreas Reuter, Friedemann Schwenkreis: ConTracts - A Low-Level Mechanism for Building General-Purpose Workflow Management-Systems. IEEE Data Eng. Bull. 18(1): 4-10(1995)
22. Vram Kouramajian, Ramez Elmasri: Archiving Techniques for Temporal Databases. DASFAA 1995: 413-421
23. Christian S. Jensen, Richard T. Snodgrass: Temporal Specialization and Generalization. IEEE Trans. Knowl. Data Eng. 6(6): 954-974(1994)
24. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441
25. Paul M. Bober, Michael J. Carey: Indexing Alternatives for Multiversion Locking. EDBT 1994: 145-158
26. Christian S. Jensen, Leo Mark, Nick Roussopoulos, Timos K. Sellis: Using Differential Techniques to Efficiently Support Transaction Time. VLDB J. 2(1): 75-111(1993)
27. David B. Lomet, Betty Salzberg: Exploiting A History Database for Backup. VLDB 1993: 380-390
28. Butler W. Lampson, David B. Lomet: A New Presumed Commit Optimization for Two Phase Commit. VLDB 1993: 630-640
29. Gad M. Landau, Jeanette P. Schmidt, Vassilis J. Tsotras: Efficient Support of Historical Queries for Multiple Lines of Evolution. ICDE 1993: 319-326
30. Junichi Takahashi: Temporal Query Processing for Scene Retrieval in Motion Image Databases. DASFAA 1993: 421-426
31. Umeshwar Dayal, Gene T. J. Wuu: A Uniform Approach to Processing Temporal Queries. VLDB 1992: 407-418
32. David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360
33. Vassilis J. Tsotras, B. Gopinath: Optimal Versioning of Objects. ICDE 1992: 358-365
34. Ramez Elmasri, Muhammad Jaseemuddin, Vram Kouramajian: Partitioning of Time Index for Optical Disks. ICDE 1992: 574-583
35. 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)
36. Curtis P. Kolovson, Michael Stonebraker: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conference 1991: 138-147
37. Ramez Elmasri, Yeong-Joon Kim, Gene T. J. Wuu: Efficient Implementation Techniques For the Time Index. ICDE 1991: 102-111
38. Ramez Elmasri, Gene T. J. Wuu, Yeong-Joon Kim: The Time Index: An Access Structure for Temporal Data. VLDB 1990: 1-12
39. David B. Lomet, Betty Salzberg: The Performance of a Multiversion Access Method. SIGMOD Conference 1990: 353-363
40. Stavros Christodoulakis, Daniel Alexander Ford: Retrieval Performance Versus Disc Space Utilization on WORM Optical Discs. SIGMOD Conference 1989: 306-314