ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Concurrent Operations in Extendible Hashing.

Meichun Hsu, Wei-Pang Yang: Concurrent Operations in Extendible Hashing. VLDB 1986: 241-247
@inproceedings{DBLP:conf/vldb/HsuY86,
  author    = {Meichun Hsu and
               Wei-Pang Yang},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {Concurrent Operations in Extendible Hashing},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {241-247},
  ee        = {db/conf/vldb/HsuY86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

An algorithm for synchronizing concurrent operations on extendible hash files is presented. The algorithm is deadlock free and allows the search operations to proceed concurrently with insertion operations without having to acquire locks on the directory entries or the data pages. It also allows concurrent insertion/deletion operations to proceed without having to acquire locks on the directory entries. The algorithm is also unique in that it combines the notion of verification, fundamental to the optimistic concurrency control algorithm, and the special and known semantics of the operations in extendible hash files. A proof of correctness for the proposed algorithm is also presented.

Copyright © 1986 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 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BS77]
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FNPS79]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HC85]
Meichun Hsu, Arvola Chan: Partitioned Two-Phase Locking. HPTS 1985: 0- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HM83]
Meichun Hsu, Stuart E. Madnick: Hierarchical Database Decomposition - A Technique for Database Concurrency Control. PODS 1983: 182-191 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KP79]
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KR81]
H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS83]
Zvi M. Kedem, Abraham Silberschatz: Locking Protocols: From Exclusive to Shared Locks. J. ACM 30(4): 787-804(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LY81]
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MR85]
Yehudit Mond, Yoav Raz: Concurrency Control in B+-Trees Databases Using Preparatory Operations. VLDB 1985: 331-334 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[O'Neil85]
Patrick E. O'Neil: Escrow Transactions Permitting Concurrent Record Updates. HPTS 1985: 0- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Papadimitriou79]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SK80]
Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[YD84]
Wei-Pang Yang, M. W. Du: A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table. VLDB 1984: 245-254 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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