JISE

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

Journal of Information Science and Engineering, Vol. 5 No. 1, pp. 51-72

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

Retrieve PDF document (JISE_198901_04.pdf)