Concurrency Control in DBMS: Ensuring Transaction Integrity

Learn about the importance of concurrency control in database management systems (DBMS). Explore different protocols used to ensure atomicity, isolation, and serializability of concurrent transactions, including locking-based and timestamp-based methods.

DBMS - Concurrency Control

In a multiprogramming environment where multiple transactions can be executed simultaneously, controlling the concurrency of transactions is crucial. Concurrency control protocols are designed to ensure atomicity, isolation, and serializability of concurrent transactions. These protocols can be broadly classified into two categories:

  • Lock-Based Protocols
  • Timestamp-Based Protocols

Lock-Based Protocols

Database systems utilizing lock-based protocols implement a mechanism where a transaction must acquire the appropriate lock on a data item before it can read or write data. There are two main types of locks:

  • Binary Locks: A lock on a data item can exist in one of two states: locked or unlocked.
  • Shared/Exclusive Locks: This locking mechanism differentiates locks based on their usage:
    • An exclusive lock is required for write operations, preventing multiple transactions from writing to the same data item, thus avoiding inconsistencies.
    • Read locks are shared, as they do not change the data value.

Types of Lock Protocols

  • Simplistic Lock Protocol: Allows transactions to obtain a lock on every object before performing a write operation. After completing the write operation, transactions may unlock the data item.
  • Pre-Claiming Lock Protocol: Transactions evaluate their operations and list the data items requiring locks before execution. They request all necessary locks beforehand; if granted, the transaction proceeds and releases the locks after completion. If not all locks are granted, the transaction rolls back and waits.
  • Two-Phase Locking (2PL): This protocol divides transaction execution into three parts:
    1. The transaction requests all required locks at the start.
    2. All locks are acquired.
    3. Once the first lock is released, the transaction enters the third phase where it can only release locks, not acquire new ones.
    The two phases are growing (acquiring locks) and shrinking (releasing locks). To claim an exclusive (write) lock, a transaction must first obtain a shared (read) lock and then upgrade it.
  • Strict Two-Phase Locking (Strict-2PL): Similar to 2PL, but once all locks are acquired, they are held until the transaction reaches the commit point, releasing all locks simultaneously. This approach eliminates cascading aborts that may occur in 2PL.

Timestamp-Based Protocols

Timestamp-based protocols are among the most widely used concurrency control methods. They utilize either system time or a logical counter as a timestamp. Unlike lock-based protocols, which manage the order of conflicting transactions during execution, timestamp-based protocols operate as soon as a transaction is created.

Each transaction is assigned a timestamp, determining its age. For instance, a transaction initiated at 00:02 is older than any that starts afterward, like one at 00:04. Every data item also maintains the latest read and write timestamps, indicating the last read and write operations performed on it.

Timestamp Ordering Protocol

The timestamp-ordering protocol ensures serializability among transactions by managing conflicting read and write operations according to their timestamps:

  • If a transaction Ti issues a read(X) operation:
    • If TS(Ti) < W-timestamp(X), the operation is rejected.
    • If TS(Ti) >= W-timestamp(X), the operation is executed, and the timestamps of all data items are updated.
  • If a transaction Ti issues a write(X) operation:
    • If TS(Ti) < R-timestamp(X), the operation is rejected.
    • If TS(Ti) < W-timestamp(X), the operation is rejected and Ti is rolled back.
    • Otherwise, the operation is executed.

Thomas' Write Rule

According to this rule, if TS(Ti) < W-timestamp(X), the operation is rejected, and Ti is rolled back. However, timestamp ordering rules can be modified to ensure the schedule is view serializable by ignoring the write operation instead of rolling back the transaction.