Previous [1] [2] [3] [4] [5]

Journal of Inforamtion Science and Engineering, Vol.5 No.1, pp.51-72 (January 1989)
Concurrent Operations in Multi-Dimensional
Extendible Hashing*

Pao-Chung Ho, Wei-Pang Yang and Meichun Hsu+
Institute of Computer Science and Information Engineering
National Chiao-Tung University
Hsinchu, Taiwan 30050, Republic of China.
+Center for Research in Computing Technology
Aiken Computation Laboratory, Harvard University
Cambridge, MA 02138, U.S.A.

An algorithm for synchronizing concurrent operations on multidimensional extendible hash files is presented. The algorithm is deadlock free and allows the search and partial-match operations to proceed concurrently with the insertion operations without having to acquire any locks. It also allows concurrent insertion/deletion operations to proceed without having to acquire locks on the directory entries. The algorithm combines the notion of verification, the principle of the optimistic concurrency control algorithm, and the special and known semantics of operations in multi-dimensional extendible hash files. A correctness argument for the proposed algorithm is also presented.

Keywords: concurrency control, extendible hashing, algorithm, database

Received May 2, 1988; revised August 1, 1988.
Communicated by Chin-Chen Chang.
*Part of this paper was presented in the Twenty-Second Annual Conference on Information Science and Systems, Princeton, New Jersey, U.S.A., March 1988.
This research was supported by the National Science Council, Taiwan, Reputlic of China, under contract NSC78-0408-E009-01 (1988).