Query Processing Techniques for Multiversion Access Methods.

Jochen Van den Bercken, Bernhard Seeger: Query Processing Techniques for Multiversion Access Methods. VLDB 1996: 168-179

@inproceedings{DBLP:conf/vldb/BerckenS96,
  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, http://dblp.uni-trier.de}
}

Abstract

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

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" 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/vldb8997 or /cdrom

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

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

Electronic Edition

References

[BFA86]: 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)
[BGO+93]: Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: On Optimal Multiversion Access Structures. SSD 1993: 123-141
[Bra84]: Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333
[CCS93]: ...
[Eas86]: Malcolm C. Easton: Key-Sequence Data Sets on Inedible Storage. IBM Journal of Research and Development 30(3): 230-241(1986)
[Fre87]: Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269
[Gut84]: Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
[Knu73]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
[KS91]: Curtis P. Kolovson, Michael Stonebraker: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conference 1991: 138-147
[KTF95]: Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos: Access Methods for Bi-Temporal Databases. Temporal Databases 1995: 235-254
[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
[MKW96]: Peter Muth, Achim Kraiss, Gerhard Weikum: LoT: Dynamic Declustering of TSB-Tree Nodes for Parallel Access to Temporal Data. EDBT 1996: 553-572
[Sa85]: Richard T. Snodgrass, Ilsoo Ahn: A Taxonomy of Time in Databases. SIGMOD Conference 1985: 236-246
[SK88]: Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
[SRF87]: Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518
[ST94]: ...
[Sto87]: Michael Stonebraker: The Design of the POSTGRES Storage System. VLDB 1987: 289-300