The Five Color Concurrency Control Protocol

Bücher

Angebote / Angebote:

Excerpt from The Five Color Concurrency Control Protocol: Non-Two-Phase Locking in General Databases, April, 1986 Concurrency control protocols that are based on 2-phase locking are a popular family of locking protocols that preserved serializability in general (unstructured database systems. This paper presents a concurrency control algorithm (for databases with no inherent structure) that is practical, non-2-phase and allows varieties of serializable logs not possible with any commonly known locking schemes. The protocol achieves high concurrency by anticipating the existence (or absence) of possible conflicts using information about transaction read and write sets. It is well known that serializability is characterized by acyclicity of the conflict graph representation of interleaved executions. The 2-phase locking protocols allow only forward growth of the paths in the graph. The Five Color protocol allows the conflict graph to grow in any direction (avoiding 2-phase constraints) and prevents cycles in the graph by maintaining transaction access information in the form of data-item markers. The read and write set information can also be used to provide relative immunity from deadlocks. This protocol allows higher concurrency and lower deadlock frequencies than 2-phase locking, according to our simulation studies. This paper presents a concurrency control mechanism that uses five kinds of locks. Unlike the 2-phase locking protocol, the Five Color protocol uses early release of locks to enhance concurrency. The early release of locks causes the protocol to be non-two phase in its locking behavior. It has been shown that 2-phase locking is a necessary condition for serializability in general databases. However we show how serializability can be achieved using a non-two phase protocol by addition of a validation phase. The Five Color protocol does not assume any inherent structures in the database. We first present a brief introduction to the to the concepts of serializability, the model of a multiuser database, the factors that limit concurrency in 2-phase locking and some related work. Section 2 contains a comprehensive description of the Five Color protocol, including an intuitive description of how it functions and why it ensures serializability. Section 3 explains the formal properties of the protocol and derives a proof of correctness. About the Publisher Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully, any imperfections that remain are intentionally left to preserve the state of such historical works.