CONCURRENT OPERATIONS IN MULTIATTRIBUTE LINEAR HASHING

Linear hashing is a dynamic hash structure in which the address space may vary dynamically when the database size is changed. Multi-attribut e linear hasing is a generalization of linear hashing. It supports ope rations for associative search and may have wider applicability. This paper presents an algorithm for synchronizing concurrent operations in multi-attribute linear hashing with particular attention paid to the treatment of concurrent partial-match operations. Unlike the previous non-two-phase methods, the algorithm employs the principle of optimist ic concurrency control technique, which leads an operation to ''retry' ' when interference from concurrent conflicting operations occurs. The method also uses a strictly increasing counter to filter out a signif icant number of unnecessary retries, thus allowing search, partial-mat ch, insert, and delete operations to proceed concurrently with split a nd merge operations. The search and partial-match operations do not ne ed to set any lock, and no operations need to set locks on any shared global variables. Therefore, the operations potentially allow a higher degree of concurrency in the system. An argument for the correctness based on the notions of weak consistency and a discussion for the perf ormance of the proposed algorithm are also present.