Concurrency Control: Conflict Serializability and Locking Protocols

Part 1: Transactions and the Need for Concurrency Control

A transaction is a single logical unit of work, which may consist of several operations like reads and writes. For a database to be reliable, every transaction must adhere to the ACID properties:

• Atomicity: A transaction is all-or-nothing. It either completes fully, or it is rolled back as if it never happened.
• Consistency: A transaction brings the database from one valid state to another.
• Isolation: Concurrent transactions should not interfere with each other. It should appear as if transactions are running one after another (serially), even though they are executing concurrently.
• Durability: Once a transaction is successfully committed, its changes are permanent and survive any subsequent system failure.

Our focus today is on Isolation. While executing transactions one by one (serially) would perfectly guarantee isolation, it would be terribly slow. The goal of concurrency control is to allow interleaved execution (a schedule) while upholding the isolation property. Without it, we face problems like:

• Dirty Read: A transaction reads data that has been written by another transaction that has not yet committed. If the writing transaction aborts, the first transaction has read "dirty" or invalid data.
• Lost Update: Two transactions read the same value, and then both update it. The second update overwrites the first, causing the first update to be "lost".

To solve these problems, we need to ensure that any interleaved schedule is "equivalent" to some serial schedule. This principle is called serializability.

Part 2: Conflict Serializability and the Precedence Graph

While serializability is the theoretical goal, checking for it directly is computationally difficult. Instead, we use a stricter but more practical condition called conflict serializability.

A schedule is conflict serializable if it can be transformed into a serial schedule by a series of non-conflicting swaps of adjacent operations. Two operations from different transactions conflict if they access the same data item and at least one of them is a write operation.

The three types of conflicting pairs are:

1. Read-Write (R-W): $T_i$ reads an item, then $T_j$ writes the same item.
2. Write-Read (W-R): $T_i$ writes an item, then $T_j$ reads the same item.
3. Write-Write (W-W): $T_i$ writes an item, then $T_j$ writes the same item.

A Read-Read pair is not a conflict.

The most reliable way to check for conflict serializability, and a standard method for GATE questions, is by constructing and analyzing a precedence graph (also called a serialization graph).

To summarize the algorithm:

1. Draw a node for each transaction $T_1,T_2,...,T_n$.
2. Scan the schedule for conflicting operations.
3. If an operation from $T_i$ comes before a conflicting operation from $T_j$, draw a directed edge $T_i\to T_j$.
4. If the resulting graph has a cycle, the schedule is not conflict serializable.
5. If the graph is acyclic, the schedule is conflict serializable, and any topological sort of the graph gives a valid equivalent serial execution order.

Part 3: Ensuring Serializability with Two-Phase Locking (2PL)

Testing for serializability after the fact is useful for analysis, but a database system needs a protocol to guarantee that only serializable schedules are produced. The most common method is Two-Phase Locking (2PL).

The protocol uses two types of locks:

• Shared (S) Lock: If a transaction $T$ holds an S-lock on an item, it can read the item but not write it. Multiple transactions can hold S-locks on the same item simultaneously.
• Exclusive (X) Lock: If a transaction $T$ holds an X-lock on an item, it can both read and write the item. Only one transaction can hold an X-lock on an item at a time. An X-lock is incompatible with any other lock (S or X).

The "Two-Phase" in 2PL refers to how a transaction handles its locks:

1. Growing Phase: The transaction can acquire locks (both S and X) but cannot release any lock.
2. Shrinking Phase: The transaction can release locks but cannot acquire any new locks.

The lock point of a transaction is the point in time when it acquired its last lock. This transition marks the end of the growing phase and the beginning of the shrinking phase. The crucial result is that any schedule that follows the 2PL protocol is guaranteed to be conflict serializable. The serialization order of the transactions is determined by the order of their lock points.

Limitations and Variants of 2PL

While 2PL guarantees serializability, it has a significant issue:

• Deadlock: Two or more transactions can get stuck waiting for each other to release locks. For example, $T_1$ has a lock on A and is waiting for B, while $T_2$ has a lock on B and is waiting for A. 2PL does not prevent deadlocks; database systems must use separate deadlock detection and recovery mechanisms.

To address other issues like cascading aborts (where the failure of one transaction forces others to roll back), stricter versions of 2PL are used:

• Strict 2PL: A transaction holds all its exclusive (X) locks until it commits or aborts. It can release shared locks earlier. This prevents other transactions from reading dirty data.
• Rigorous 2PL: A transaction holds all its locks (both S and X) until it commits or aborts. This is even stricter and is easier to implement.

For GATE, remember this hierarchy: all Rigorous 2PL schedules are also Strict 2PL, and all Strict 2PL schedules are also 2PL. All of them guarantee conflict serializability, but none of them prevent deadlock.

Conclusion

In this lesson, we explored the critical mechanisms for managing concurrent database operations. You've moved from designing a database's static schema to controlling its dynamic, real-time behavior.

Here are the key takeaways for your GATE preparation:

• Conflict Serializability is the practical standard for correct concurrent execution.
• You can definitively test for it by constructing a precedence graph and checking for cycles. An acyclic graph means the schedule is conflict serializable.
• Two-Phase Locking (2PL) is a protocol that proactively guarantees conflict serializability. It works by dividing a transaction's life into a growing phase (acquiring locks) and a shrinking phase (releasing locks).
• 2PL guarantees serializability but does not prevent deadlocks.
• Strict and Rigorous 2PL are stronger variants that also prevent cascading aborts by holding locks until the transaction ends.

You have now completed the core Database Management Systems topics for GATE. In our next lesson, we will begin the second major topic of this module: Computer Networks. We will start from the ground up, looking at the fundamental layered models (OSI and TCP/IP) and the functions of the Data Link Layer, including error detection and flow control.