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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" 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/vldb7588 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

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

References

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