Solving the phantom problem is a common requirement for concurrent access in database systems. The predicate locking and the next-key locking are conventional techniques for solving the phantom problem. However, they have limitations: the predicate locking has expensive execution cost, and the next-key locking is applicable only to the file structures that store the objects in the sorted order according to their key values.
In this thesis we propose \it hierarchical key-range locking as an efficient solution to the phantom problem. Hierarchical key-range locking allows a transaction to lock key ranges both at coarse granularity and at fine granularity by organizing key ranges into a hierarchy. It thereby achieves high concurrency while requiring only small number of locks. In this thesis we propose a method using hierarchical key-range locking that solves the phantom problem in multidimensional file structures. Since, hierarchical key-range locking does not have limitations caused by specific file structures, it can be directly applied to multidimensional file structures as well.
