Unit 5: Transaction Management

Unit 5: Transaction Management

Transaction Management is a crucial component of Database Management Systems (DBMS) that ensures the integrity, consistency, and reliability of data. This unit explores the fundamental concepts of transactions, how concurrent execution of transactions is managed, and the mechanisms used to maintain data consistency.

5.1 Basic Transaction Concepts

5.1.1 Definition

A transaction is a logical unit of work that contains one or more SQL statements. A transaction is an atomic unit; the effects of all the SQL statements in a transaction can be either all committed (applied to the database) or all rolled back (undone from the database).

For example, consider a banking system where a user transfers $100 from Account A to Account B. This operation involves two main steps:

  1. Deduct $100 from Account A.
  2. Add $100 to Account B.

If a failure occurs after step 1 but before step 2, the database would be in an inconsistent state (Account A lost $100, but Account B never received it). By treating these two steps as a single transaction, the DBMS ensures that either both steps succeed, or neither step is applied.

SQL

5.1.2 State Transition Diagram

During its execution, a transaction passes through several states. The transaction state transition diagram outlines the lifecycle of a transaction within the DBMS.

  1. Active State: This is the initial state. The transaction stays in this state while it is executing its operations (reads and writes).
  2. Partially Committed State: A transaction transitions to this state after its final operation has been executed. At this point, the transaction is complete, but the changes may still be residing in main memory (buffer) and have not yet been permanently written to disk.
  3. Committed State: If a transaction successfully completes its execution and all its changes are permanently recorded in the database, it enters the committed state. Once committed, a transaction cannot be aborted.
  4. Failed State: A transaction enters the failed state if a hardware, logical, or system error prevents it from continuing its normal execution, or if the concurrency control system decides to abort it to resolve a conflict (e.g., deadlock).
  5. Aborted State: After a transaction fails, it must be rolled back to restore the database to its state before the transaction began. Once the rollback is complete, the transaction is in the aborted state. From here, the transaction can either be restarted or killed.

5.1.3 ACID Properties

To maintain database reliability and consistency, every transaction must possess the following four properties, commonly known as the ACID properties:

  1. Atomicity (All or Nothing): This property dictates that a transaction is treated as a single, indivisible unit. Either all operations within the transaction are successfully completed and reflected in the database, or none of them are. If any operation fails, the entire transaction is aborted, and previous operations are rolled back.
  2. Consistency: A transaction must transform the database from one consistent state to another consistent state. It must adhere to all defined integrity constraints, rules, and validations of the database. For example, in a money transfer, the sum of balances in both accounts must remain the same before and after the transaction.
  3. Isolation: When multiple transactions execute concurrently, the execution of one transaction should be isolated from the execution of others. Intermediate states of a transaction should not be visible to other concurrently executing transactions until the transaction has committed.
  4. Durability: Once a transaction is successfully committed, its changes must be permanently saved in the database. Even in the event of a system crash, power failure, or software error, the committed data must not be lost.

5.1.4 Transaction Log

The transaction log (or write-ahead log) is a critical internal file maintained by the DBMS to ensure Atomicity and Durability. It records all modifications made to the database by transactions.

Whenever a transaction performs an operation (e.g., insert, update, delete), a corresponding log record is created in the transaction log before the actual data page is modified on disk. A log record typically contains:

  • Transaction ID
  • Data item being modified
  • Old value (before image)
  • New value (after image)

Types of log entries include:

  • [START T1]: Indicates transaction T1 has started.
  • [WRITE T1, X, 10, 20]: Indicates transaction T1 modified item X from 10 to 20.
  • [COMMIT T1]: Indicates transaction T1 has successfully completed.
  • [ABORT T1]: Indicates transaction T1 has failed and been rolled back.

In the event of a crash, the recovery manager uses the log to undo aborted/failed transactions (using old values) and redo committed transactions (using new values) that were not yet written to the database files.

5.2 Concurrency Control

5.2.1 Definition

Concurrency Control is the procedure in a DBMS that manages the simultaneous execution of multiple transactions. The goal is to allow multiple users to access and modify data concurrently while preventing transactions from interfering with each other and violating data consistency.

Benefits of concurrent execution include:

  • Improved Throughput: More transactions can be executed in a given amount of time.
  • Better Resource Utilization: While one transaction is waiting for disk I/O, the CPU can execute operations for another transaction.
  • Reduced Waiting Time: Short transactions do not have to wait for long-running transactions to complete.

5.2.2 Problems of Concurrency Control

If concurrent transactions are not properly managed, several anomalies or problems can occur, corrupting the database state.

1. Lost Update Problem (Write-Write Conflict)

This occurs when two transactions read the same data item and then update it concurrently. The update made by the first transaction is overwritten (lost) by the second transaction. Example: Transaction T1 reads value X (100) and Transaction T2 reads value X (100). T1 updates X to 110. T2 updates X to 120. The final value is 120, and the update made by T1 is completely lost.

2. Dirty Read Problem (Write-Read Conflict / Uncommitted Dependency)

This happens when a transaction reads a data item that has been updated by another uncommitted transaction. If the first transaction subsequently aborts, the second transaction has read "dirty" or invalid data. Example: Transaction T1 updates X to 200. Transaction T2 reads X (200). T1 fails and rolls back, restoring X to its original value. Now, T2 is working with a value (200) that officially never existed in the database.

3. Unrepeatable Read Problem (Read-Write Conflict)

This occurs when a transaction reads the same data item twice during its execution, but gets a different value each time because another transaction modified the item in between the reads. Example: Transaction T1 reads X (10). Transaction T2 updates X to 20 and commits. Transaction T1 reads X again and gets 20. T1 sees inconsistent values during its execution.

4. Phantom Read Problem

This anomaly happens when a transaction executes a query that retrieves a set of rows based on a search condition, and another transaction subsequently inserts or deletes rows that satisfy that condition. If the first transaction repeats the query, it sees a "phantom" row that appeared or disappeared.

5.2.3 Schedule and its types

A schedule (or history) is an execution sequence that indicates the chronological order in which operations of concurrent transactions are executed.

Schedules can be broadly classified into two types:

  1. Serial Schedule: In a serial schedule, transactions are executed one after the other, sequentially. There is no interleaving of operations. For example, all operations of T1 are executed, followed by all operations of T2. Serial schedules always guarantee database consistency, but they result in poor system performance and low resource utilization.
  2. Non-Serial (Concurrent) Schedule: In a non-serial schedule, the operations of multiple transactions are interleaved. This improves throughput and resource utilization but requires a concurrency control mechanism to prevent the anomalies discussed earlier.

5.3 Serializability of Transactions

To reap the benefits of concurrency while guaranteeing data consistency, we use the concept of serializability. A non-serial schedule is considered serializable if its final outcome (effect on the database) is equivalent to the outcome of some serial execution of those same transactions.

1. Conflict Serializability

Two operations are said to conflict if they belong to different transactions, access the same data item, and at least one of them is a write operation. The three types of conflicts are:

  • Read-Write (RW) conflict
  • Write-Read (WR) conflict
  • Write-Write (WW) conflict

Two schedules are conflict equivalent if the order of any two conflicting operations is the same in both schedules. A schedule is conflict serializable if it is conflict equivalent to some serial schedule.

Testing for Conflict Serializability (Precedence Graph): To test if a schedule is conflict serializable, we draw a precedence graph (or serialization graph).

  • Create a node for each transaction.
  • Create a directed edge Ti→TjT_i \rightarrow T_j if an operation in TiT_i conflicts with an operation in TjT_j and the operation in TiT_i appears before the operation in TjT_j in the schedule.
  • Rule: If the precedence graph contains a cycle, the schedule is not conflict serializable. If it is acyclic, the schedule is conflict serializable.

2. View Serializability

View serializability is a slightly less restrictive notion than conflict serializability. Two schedules are view equivalent if they have the same initial reads, same write-read dependencies, and same final writes for every data item. A schedule is view serializable if it is view equivalent to a serial schedule. Every conflict serializable schedule is also view serializable, but there are some view serializable schedules that are not conflict serializable (these usually involve "blind writes," where a transaction writes a value without reading it first).

5.4 Locking Methods for Concurrency Control

Locking protocols are the most common mechanisms used to implement concurrency control and ensure serializability. A lock is a variable associated with a data item that describes the status of the item with respect to possible operations that can be applied to it.

5.4.1 Types of Locks

  • Shared Lock (S-lock): If a transaction T holds a shared lock on data item X, it can only read X. Multiple transactions can hold shared locks on the same item simultaneously.
  • Exclusive Lock (X-lock): If a transaction T holds an exclusive lock on data item X, it can both read and write X. No other transaction can obtain any lock (shared or exclusive) on X while the exclusive lock is held.

5.4.2 Two-Phase Locking (2PL) Protocol

The Two-Phase Locking protocol ensures conflict serializability by requiring that transactions acquire and release locks in two distinct phases:

  1. Growing Phase: A transaction may obtain new locks, but it cannot release any existing locks.
  2. Shrinking Phase: A transaction may release existing locks, but it cannot acquire any new locks.

Once a transaction releases its first lock, it transitions from the growing phase to the shrinking phase and can never request another lock. While standard 2PL guarantees serializability, it does not prevent deadlocks or cascading rollbacks.

5.4.3 Variations of 2PL

To address some of the drawbacks of basic 2PL, several variations are used:

  • Strict 2PL: A transaction must hold all its exclusive locks until it commits or aborts. This prevents cascading rollbacks (dirty reads).
  • Rigorous 2PL: A transaction must hold all its locks (both shared and exclusive) until it commits or aborts. It is easier to implement than Strict 2PL and also prevents cascading rollbacks.
  • Conservative (Static) 2PL: A transaction must acquire all the locks it will need before it begins execution. If all locks are not available, it waits. This protocol prevents deadlocks but significantly reduces concurrency and is difficult to implement since the required locks must be known in advance.

5.4.4 Deadlocks and Starvation

  • Deadlock: A situation where two or more transactions are waiting for locks held by each other, resulting in a cycle of dependencies where none of the transactions can proceed. DBMS handles deadlocks using Deadlock Prevention (e.g., wait-die, wound-wait schemes) or Deadlock Detection and Recovery (e.g., using wait-for graphs and aborting a victim transaction).
  • Starvation: Occurs when a transaction waits indefinitely for a lock because other transactions are continually jumping ahead of it in the queue (e.g., a write transaction continuously waiting because read transactions keep acquiring shared locks). This can be mitigated by using a strict First-In-First-Out (FIFO) queue for lock requests.