Concurrency and Recovery in Generalized Search Trees.

Marcel Kornacker, C. Mohan, Joseph M. Hellerstein: Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997: 62-72

@inproceedings{DBLP:conf/sigmod/KornackerMH97,
  author    = {Marcel Kornacker and
               C. Mohan and
               Joseph M. Hellerstein},
  editor    = {Joan Peckham},
  title     = {Concurrency and Recovery in Generalized Search Trees},
  booktitle = {SIGMOD 1997, Proceedings ACM SIGMOD International Conference
               on Management of Data, May 13-15, 1997, Tucson, Arizona, USA},
  publisher = {ACM Press},
  year      = {1997},
  pages     = {62-72},
  ee        = {http://doi.acm.org/10.1145/253260.253272, db/conf/sigmod/KornackerMH97.html},
  crossref  = {DBLP:conf/sigmod/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

This paper presents general algorithms for concurrency control in tree-based access methods as well as a recovery protocol and a mechanism for ensuring repeatable read. The algorithms are developed in the context of the Generalized Search Tree (GiST) data structure, an index structure supporting an extensible set of queries and data types. Although developed in a GiST context, the algorithms are generally applicable to many tree-based access methods. The concurrency control protocol is based on an extension of the link technique originally developed for B-trees, and completely avoids holding node locks during I/Os. Repeatable read isolation is achieved with a novel combination of predicate locks and two-phase locking of data records. To our knowledge, this is the first time that isolation issues have been addressed outside the context of B-trees. A discussion of the fundamental structural differences between B-trees and more general tree structures like GiSTs explains why the algorithms developed here deviate from their B-tree counterparts. An implementation of GiSTs emulating B-trees in DB2/Common Server is underway.

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

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'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/smod9397 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

BibTeX

Printed Edition

Joan Peckham (Ed.): SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA. ACM Press 1997 BibTeX , SIGMOD Record 26(2), June 1997
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1548 KB]

References

[BS77]: Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
[EGLT76]: Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[GR93]: Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
[Gra78]: Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[Gut84]: Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[HNP95]: Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573 BibTeX
[Jag90]: H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319 BibTeX
[Js93]: Theodore Johnson, Dennis Shasha: The Performance of Current B-Tree Algorithms. ACM Trans. Database Syst. 18(1): 51-101(1993) BibTeX
[KB95]: Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145 BibTeX
[KKAD89]: ...
[KL80]: H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX
[LJF94]: King-Ip Lin, H. V. Jagadish, Christos Faloutsos: The TV-Tree: An Index Structure for High-Dimensional Data. VLDB J. 3(4): 517-542(1994) BibTeX
[Lom93]: David B. Lomet: Key Range Locking Strategies for Improved Concurrency. VLDB 1993: 655-664 BibTeX
[LS90]: David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990) BibTeX
[LS92]: David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360 BibTeX
[LY81]: Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
[MHL+92]: C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992) BibTeX
[ML92]: 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
[Moh90a]: 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
[Moh90b]: C. Mohan: Commit_LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems. VLDB 1990: 406-418 BibTeX
[Moh95]: ...
[Sag86]: Yehoshua Sagiv: Concurrent Operations on B*-Trees with Overtaking. J. Comput. Syst. Sci. 33(2): 275-296(1986) BibTeX
[SC91]: V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425 BibTeX
[SG88]: Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX
[SRF87]: Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

Referenced by

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)
C. Mohan: Repeating History Beyond ARIES. VLDB 1999: 1-17
Marcel Kornacker: High-Performance Extensible Indexing. VLDB 1999: 699-708
Kaushik Chakrabarti, Sharad Mehrotra: Efficient Concurrency Control in Multidimensional Access Methods. SIGMOD Conference 1999: 25-36
Rasa Bliujute, Simonas Saltenis, Giedrius Slivinskas, Christian S. Jensen: Developing a DataBlade for a New Index. ICDE 1999: 314-323
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
Kaushik Chakrabarti, Sharad Mehrotra: Dynamic Granular Locking Approach to Phantom Protection in R-Trees. ICDE 1998: 446-454
Paul M. Aoki: Generalizing ``Search'' in Generalized Search Trees (Extended Abstract). ICDE 1998: 380-389
Stefan Deßloch, Nelson Mendonça Mattos: Integrating SQL Databases with Content-Specific Search Engines. VLDB 1997: 528-537

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]