Query Processing Techniques for Multiversion Access Methods.

Jochen Van den Bercken, Bernhard Seeger: Query Processing Techniques for Multiversion Access Methods. VLDB 1996: 168-179
  author    = {Jochen Van den Bercken and
               Bernhard Seeger},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Query Processing Techniques for Multiversion Access Methods},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {168-179},
  ee        = {db/conf/vldb/BerckenS96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP,}


Multiversion access methods have been emerged in the literature primarily to support queries on a transaction-time database where records are never physically deleted. For a popular class of efficient methods (including the multiversion B-tree), data records and index entries are occasionally duplicated to separate data according to time. In this paper, we present techniques for improving query processing in multiversion access methods. In particular, we address the problem of avoiding duplicates in the response sets. We first discuss traditional approaches that eliminate duplicates using hashing and sorting. Next, we propose two new algorithms for avoiding duplicates without using additional data structures. The one performs queries in a depth-first order starting from a root, whereas the other exploits links between data pages. These methods are discussed in full details and their main properties are identified. Preliminary performance results confirm the advantages of these methods in comparison to traditional ones according to CPU-time, disk accesses and storage.

Copyright © 1996 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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents BibTeX

Electronic Edition


Renato Barrera, Andrew U. Frank, Khaled K. Al-Taha: Temporal Relations in Geographic Information Systems: A Workshop at the University of Maine. SIGMOD Record 20(3): 85-91(1991) BibTeX
Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: On Optimal Multiversion Access Structures. SSD 1993: 123-141 BibTeX
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 BibTeX
Malcolm C. Easton: Key-Sequence Data Sets on Inedible Storage. IBM Journal of Research and Development 30(3): 230-241(1986) BibTeX
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
Curtis P. Kolovson, Michael Stonebraker: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conference 1991: 138-147 BibTeX
Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos: Access Methods for Bi-Temporal Databases. Temporal Databases 1995: 235-254 BibTeX
David B. Lomet, Betty Salzberg: Access Methods for Multiversion Data. SIGMOD Conference 1989: 315-324 BibTeX
David B. Lomet, Betty Salzberg: The Performance of a Multiversion Access Method. SIGMOD Conference 1990: 353-363 BibTeX
Peter Muth, Achim Kraiss, Gerhard Weikum: LoT: Dynamic Declustering of TSB-Tree Nodes for Parallel Access to Temporal Data. EDBT 1996: 553-572 BibTeX
Richard T. Snodgrass, Ilsoo Ahn: A Taxonomy of Time in Databases. SIGMOD Conference 1985: 236-246 BibTeX
Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 BibTeX
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
Michael Stonebraker: The Design of the POSTGRES Storage System. VLDB 1987: 289-300 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:10 2009