Concurrency control algorithms for database systems exploiting the semantics of read-only transactions.

Abstract

This thesis proposes new locking-based concurrency control algorithms for both centralized and distributed databases. The concurrency control algorithms proposed exploit the semantics of read-only transactions to improve concurrency. In addition, the distributed concurrency control algorithms presented are resilient to site failures and/or network partitioning. This research is motivated by the fact that the semantics of read-only transactions can be easily provided by the users. Three semantics of read-only transactions are defined: (a) serializability, (b) weak consistency, and (c) semi-weak consistency. The read-only transactions that are non-serializable, i.e., that are either weakly consistent or semi-weakly consistent, are allowed to be non-two-phase, and this helps to improve concurrency. The concurrency control algorithms proposed require that all the non-serializable read-only transactions are specified as either weakly consistent or semi-weakly consistent. The concurrency control algorithms designed ensure strong update serializability only if the non-serializable read-only transactions are specified as weakly consistent; however, if the non-serializable read-only transactions are specified as semi-weakly consistent, then these concurrency control algorithms ensure weak update serializability. In addition, the concurrency control algorithms proposed ensure serializability in the absence of non-serializable read-only transactions. The proof of correctness of these concurrency control algorithms is also given. Simulation results indicate that the performance of these concurrency control algorithms is superior to that of the two-phase locking protocol in both centralized and distributed databases. This thesis also presents a model of distributed systems that is helpful to describe a distributed database system under failure. Using this model of distributed systems, we propose an algorithm that enables each operational site of a partition of a distributed database system to have the same view of the distributed database system. This algorithm also ensures that all the operational sites of a distributed database system will have the same view of a failed site. Furthermore, this model of distributed systems is used to design a resiliency control scheme for replicated distributed databases. Using this resiliency control scheme, we present a distributed resiliency control algorithm that can be used to make a basic 2PL-like distributed locking protocol resilient to site failures and/or network partitioning. The distributed resiliency control algorithm is used to make the distributed locking protocol, viz., the distributed SGN 2PL protocol proposed in this thesis, resilient to site failures and/or network partitioning. In addition, a site recovery and partition merge algorithm is also developed using the same scheme as that used by the distributed resiliency control algorithm.