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}
}
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.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
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 
,
SIGMOD Record 26(2),
June 1997
Contents
[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)
- [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)
- [GR93]
- Jim Gray, Andreas Reuter:
Transaction Processing: Concepts and Techniques.
Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents - [Gra78]
- Jim Gray:
Notes on Data Base Operating Systems.
Advanced Course: Operating Systems 1978: 393-481
- [Gut84]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57
- [HNP95]
- Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer:
Generalized Search Trees for Database Systems.
VLDB 1995: 562-573
- [Jag90]
- H. V. Jagadish:
Spatial Search with Polyhedra.
ICDE 1990: 311-319
- [Js93]
- Theodore Johnson, Dennis Shasha:
The Performance of Current B-Tree Algorithms.
ACM Trans. Database Syst. 18(1): 51-101(1993)
- [KB95]
- Marcel Kornacker, Douglas Banks:
High-Concurrency Locking in R-Trees.
VLDB 1995: 134-145
- [KKAD89]
- ...
- [KL80]
- H. T. Kung, Philip L. Lehman:
Concurrent Manipulation of Binary Search Trees.
ACM Trans. Database Syst. 5(3): 354-382(1980)
- [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)
- [Lom93]
- David B. Lomet:
Key Range Locking Strategies for Improved Concurrency.
VLDB 1993: 655-664
- [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)
- [LS92]
- David B. Lomet, Betty Salzberg:
Access Method Concurrency with Recovery.
SIGMOD Conference 1992: 351-360
- [LY81]
- Philip L. Lehman, S. Bing Yao:
Efficient Locking for Concurrent Operations on B-Trees.
ACM Trans. Database Syst. 6(4): 650-670(1981)
- [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)
- [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
- [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
- [Moh90b]
- C. Mohan:
Commit_LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems.
VLDB 1990: 406-418
- [Moh95]
- ...
- [Sag86]
- Yehoshua Sagiv:
Concurrent Operations on B*-Trees with Overtaking.
J. Comput. Syst. Sci. 33(2): 275-296(1986)
- [SC91]
- V. Srinivasan, Michael J. Carey:
Performance of B-Tree Concurrency Algorithms.
SIGMOD Conference 1991: 416-425
- [SG88]
- Dennis Shasha, Nathan Goodman:
Concurrent Search Structure Algorithms.
ACM Trans. Database Syst. 13(1): 53-90(1988)
- [SRF87]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518
Copyright © Mon Dec 14 20:19:13 2009
by Michael Ley (ley@uni-trier.de)
