Logical and Physical Versioning in Main Memory Databases.

Rajeev Rastogi, S. Seshadri, Philip Bohannon, Dennis W. Leinbaugh, Abraham Silberschatz, S. Sudarshan: Logical and Physical Versioning in Main Memory Databases. VLDB 1997: 86-95
  author    = {Rajeev Rastogi and
               S. Seshadri and
               Philip Bohannon and
               Dennis W. Leinbaugh and
               Abraham Silberschatz and
               S. Sudarshan},
  editor    = {Matthias Jarke and
               Michael J. Carey and
               Klaus R. Dittrich and
               Frederick H. Lochovsky and
               Pericles Loucopoulos and
               Manfred A. Jeusfeld},
  title     = {Logical and Physical Versioning in Main Memory Databases},
  booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very
               Large Data Bases, August 25-29, 1997, Athens, Greece},
  publisher = {Morgan Kaufmann},
  year      = {1997},
  isbn      = {1-55860-470-7},
  pages     = {86-95},
  ee        = {db/conf/vldb/BohannonLRSSS97.html},
  crossref  = {DBLP:conf/vldb/97},
  bibsource = {DBLP,}


We present a design for multi-version concurrency control and recovery in a main memory database, and describe logical and physical versioning schemes that allow read-only transactions to execute without obtaining data item locks or system latches. These schemes enable a system to guarantee that updaters will never interfere with read-only transactions, and that read-only transactions will not be delayed as long as the operating system provides them with sufficient cycles. Our contributions include several space saving techniques for the main memory implementation. We extend the T-tree index structure (designed for main-memory databases) to support concurrent access and latch-free traversals, and demonstrate the performance benefits of our extensions. Some of these schemes have been implemented on a widely-used software platform within Bell Labs., and the full scheme is implemented in the Dali main memory storage manager.

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

Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, Manfred A. Jeusfeld (Eds.): VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece. Morgan Kaufmann 1997, ISBN 1-55860-470-7
Contents BibTeX

Electronic Edition

From CS Dept., University Trier (Germany)


URL for additional information on the research/development described in the paper:


Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
Paul M. Bober, Michael J. Carey: On Mixing Queries and Transactions via Multiversion Locking. ICDE 1992: 535-545 BibTeX
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
Arvola Chan, Stephen Fox, Wen-Te K. Lin, Anil Nori, Daniel R. Ries: The Implementation of an Integrated Concurrency Control and Recovery Scheme. SIGMOD Conference 1982: 184-191 BibTeX
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX
Vibby Gottemukkala, Tobin J. Lehman: Locking and Latching in a Memory-Resident Database System. VLDB 1992: 533-544 BibTeX
H. V. Jagadish, Daniel F. Lieuwen, Rajeev Rastogi, Abraham Silberschatz, S. Sudarshan: Dalí: A High Performance Main Memory Storage Manager. VLDB 1994: 48-59 BibTeX
H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX
Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303 BibTeX
Udi Manber, Richard E. Ladner: Concurrency Control in a Dynamic Search Structure. PODS 1982: 268-282 BibTeX
C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380 BibTeX
C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405 BibTeX
C. Mohan, Hamid Pirahesh, Raymond A. Lorie: Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions. SIGMOD Conference 1992: 124-133 BibTeX
Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX
Kenneth Salem, Hector Garcia-Molina: System M: A Transaction Processing Testbed for Memory Resident Data. IEEE Trans. Knowl. Data Eng. 2(1): 161-172(1990) BibTeX

Referenced by

  1. William O'Connell, Felipe Cariño, G. Linderman: Optimizer and Parallel Engine Extensions for Handling Expensive Methods Based on Large Objects. ICDE 1999: 304-313
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:15 2009