ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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

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 ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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

Copyright © Tue Mar 16 02:22:05 2010 by Michael Ley (ley@uni-trier.de)