Unit-8: Transaction Management

Concept of Transaction

A transaction is a logical unit of work that performs one or more operations (e.g., read, write, insert, delete) on a database. It represents a single, complete execution of a program or an operation that accesses and updates database content. For the database to remain consistent, either all operations within a transaction must be completed successfully, or none of them should be.

ACID Properties

To ensure data integrity and reliability, transactions must adhere to a set of properties known as ACID properties:

1. Atomicity:

• Definition: Atomicity ensures that a transaction is treated as a single, indivisible unit of work. Either all of its operations are executed successfully, or none of them are. There are no partial transactions.

• Example: Transferring money from account A to account B. This involves debiting A and crediting B. If debiting A succeeds but crediting B fails, the entire transaction must be undone to maintain atomicity.
2. Consistency:

• Definition: Consistency ensures that a transaction brings the database from one valid state to another valid state. It must obey all defined rules, constraints, and triggers (e.g., referential integrity, unique constraints).

• Example: If a balance cannot be negative, a transaction that attempts to make a balance negative must be aborted to maintain consistency.
3. Isolation:

• Definition: Isolation ensures that concurrent transactions appear to execute in isolation from each other. The intermediate state of one transaction is not visible to other transactions.

• Example: If two transactions are simultaneously updating the same bank account, the database system ensures that they don't interfere with each other, and the final state is as if they executed sequentially.
4. Durability:

• Definition: Durability ensures that once a transaction has been committed, its changes are permanent and will survive even in the event of a system failure (e.g., power outage, crash).

• Example: After a money transfer transaction commits, the updated balances are stored permanently and will persist even if the system crashes immediately after the commit.

Transaction State

A transaction progresses through various states during its lifetime. Understanding these states is crucial for managing transactions effectively.

Transaction State Transitions

• A transaction enters the active state when it begins execution.
• When it finishes its final statement, it enters the partially committed state.
• If the transaction is successfully committed and its effects are durable, it enters the committed state.
• If a failure occurs during the active or partially committed states, the transaction enters the failed state.
• From the failed state, the transaction enters the aborted state after its effects are rolled back. An aborted transaction can be restarted or permanently terminated.

Implementation of Atomicity and Durability

Atomicity and Durability are primarily implemented using logging (write-ahead logging) and recovery managers.

Implementing Atomicity (Undo Logging)

Atomicity is ensured by recording all database modifications in a log file before they are applied to the actual database. This log contains enough information to undo (rollback) any changes if the transaction fails.

• Log Record: Each operation that modifies the database creates a log record. A log record typically includes:
• Transaction ID (TID)
• Operation type (insert, delete, update)
• Data item modified
• Old value (before modification)
• New value (after modification)
• Rollback (Undo): If a transaction fails before committing, the system uses the log records to undo all changes made by that transaction. For each write operation in the log, the old value is written back to the database.

Implementing Durability (Redo Logging)

Durability is ensured by guaranteeing that once a transaction commits, its changes are permanently stored and can be recovered even after a system crash.

• Write-Ahead Logging (WAL) Principle: For durability, the log record for a write operation must be written to stable storage before the corresponding data item is written to the database disk.
• Commit Record: When a transaction commits, a <T, commit> log record is written to stable storage. Once this record is written, the transaction is considered committed.
• Recovery (Redo): If a system crash occurs, the recovery manager reads the log from stable storage. For all committed transactions whose changes might not have been written to disk (due to buffering), the recovery manager uses the log records to redo these changes. For each write operation of a committed transaction, the new value is written to the database.

Concurrent Execution

Concurrent execution refers to the interleaving of operations from multiple transactions. Instead of running one transaction completely and then starting the next, parts of several transactions are run in an interleaved fashion.

Advantages of Concurrent Execution

• Increased Throughput: More transactions can be processed in a given unit of time.
• Reduced Waiting Time: Users experience quicker response times because their transactions don't have to wait for other long transactions to complete entirely.
• Better Resource Utilization: CPU and I/O devices can be utilized more efficiently, as one transaction can use the CPU while another performs I/O, minimizing idle time.

Problems Caused by Concurrent Execution

Without proper control mechanisms, concurrent execution can lead to several anomalies, violating the Isolation property:

1. Lost Update Problem:
• When two transactions read the same data item, modify it, and then write it back, one update might overwrite the other without considering its effect.
• Example: T1 reads X (value 100), T2 reads X (value 100). T1 updates X to 110. T2 updates X to 90. If T2 writes last, T1's update is lost.
2. Dirty Read Problem (Uncommitted Dependency):
• A transaction reads data written by another transaction that has not yet committed. If the writing transaction later aborts, the reading transaction will have read invalid (dirty) data.
• Example: T1 writes X=100. T2 reads X=100. T1 aborts (X reverts to original value, e.g., 50). T2 has an invalid value of X.
3. Unrepeatable Read Problem:
• A transaction reads the same data item twice but gets different values, because another committed transaction modified the data item between the two reads.
• Example: T1 reads X=100. T2 updates X to 120 and commits. T1 reads X again and gets 120. T1's reads are inconsistent.
4. Phantom Read Problem:
• A transaction executes a query and gets a set of rows. If another transaction inserts or deletes rows that satisfy the query's WHERE clause and commits, the first transaction's subsequent execution of the same query will yield a different set of rows (phantoms appear or disappear).
• Example: T1 queries all employees with salary > 50000. T2 inserts a new employee with salary 60000 and commits. T1 repeats the query and sees the new employee, a 'phantom' row.

Serializability

Definition: Serializability is a property of a schedule of concurrent transactions that guarantees that the final result of the concurrent execution is equivalent to the result of some serial execution of the same set of transactions. A serial execution is one where transactions execute one after another, without any interleaving. Serial schedules are always correct.

Achieving serializability is the main goal of concurrency control mechanisms to preserve database consistency.

Conflict Serializability

A schedule is conflict serializable if it is conflict equivalent to some serial schedule. Two operations are in conflict if they belong to different transactions, access the same data item, and at least one of them is a write operation.

Types of conflicts:

• Read-Write (RW) conflict: A transaction reads an item, and another transaction writes the same item.
• Write-Read (WR) conflict: A transaction writes an item, and another transaction reads the same item.
• Write-Write (WW) conflict: A transaction writes an item, and another transaction writes the same item.

Precedence Graph (Serializability Graph)

To test for conflict serializability, a precedence graph (also known as a serializability graph) is used:

1. For each transaction T_i in the schedule, create a node in the graph.
2. Draw a directed edge from T_i to T_j if one of the following conditions holds:
• T_i reads an item that T_j later writes. (RW conflict)
• T_i writes an item that T_j later reads. (WR conflict)
• T_i writes an item that T_j later writes. (WW conflict)
3. If the precedence graph contains no cycles, the schedule is conflict serializable. Otherwise, it is not.

View Serializability

A schedule is view serializable if it is view equivalent to some serial schedule. Two schedules are view equivalent if:

1. They have the same initial read for each data item (i.e., if T_i reads the initial value of item X in one schedule, it must do so in the other).
2. For any data item X, if T_i reads the value of X written by T_j in one schedule, it must do so in the other.
3. For any data item X, the transaction that performs the final write on X is the same in both schedules.

View serializability is a broader concept than conflict serializability (every conflict serializable schedule is view serializable, but not vice versa). However, testing for view serializability is NP-complete, so conflict serializability is more commonly used in practice.

Recoverability

Definition: Recoverability refers to the property of a schedule that ensures that if a transaction T_j reads data written by a transaction T_i, and T_i later aborts, T_j must also abort. This prevents T_j from committing based on invalid data.

A recoverable schedule ensures that transactions only commit after all transactions whose updates they have read are committed.

Cascading Rollback

Cascading rollback occurs when a transaction T_j reads data written by an uncommitted transaction T_i, and T_i then aborts. T_j must then also abort, which might cause other transactions that read T_j's data to abort, leading to a chain reaction of rollbacks. This is highly undesirable as it can lead to significant wasted work.

Types of Recoverable Schedules

1. Recoverable Schedules:
• A schedule S is recoverable if for every pair of transactions T_i and T_j such that T_j reads a data item previously written by T_i, T_i commits before T_j commits.
• This ensures no transaction commits on dirty data.
2. Non-Cascading Schedules (Cascadeless Schedules):
• A schedule S is non-cascading if for every pair of transactions T_i and T_j such that T_j reads a data item previously written by T_i, T_i commits before T_j performs the read operation.
• This stricter condition prevents dirty reads and thus cascading rollbacks. It is more desirable.
3. Strict Schedules:
• A schedule S is strict if for every pair of transactions T_i and T_j, if T_j reads a data item written by T_i, or T_j writes a data item written by T_i, then T_i must commit or abort before T_j performs its read or write.
• Strict schedules eliminate dirty reads, unrepeatable reads, and lost updates, providing a high degree of isolation and recoverability. They are typically implemented using strict 2PL.

Implementation of Isolation

Isolation is primarily implemented through concurrency control protocols. These protocols ensure that interleaved transactions behave as if they were executed serially. The main categories include locking, timestamping, and validation protocols.

Locking Protocols

Locking is the most common mechanism. Transactions acquire locks on data items before accessing them. Locks prevent other transactions from conflictingly accessing the same data item.

• Types of Locks:
• Shared Lock (S-lock / Read lock): Allows multiple transactions to read an item concurrently. A transaction must hold an S-lock to read an item.
• Exclusive Lock (X-lock / Write lock): Allows only one transaction to access and modify an item. A transaction must hold an X-lock to write an item.
• Compatibility Matrix:

  	S-Lock (Request)	X-Lock (Request)
  S-Lock (Held)	Compatible (Yes)	Incompatible (No)
  X-Lock (Held)	Incompatible (No)	Incompatible (No)

• Two-Phase Locking (2PL) Protocol:

• Definition: 2PL ensures serializability by dividing a transaction's lock operations into two phases: a growing phase and a shrinking phase.

• Growing Phase: Transaction can acquire locks but cannot release any locks.
• Shrinking Phase: Transaction can release locks but cannot acquire any new locks.
• Once a transaction releases a lock, it cannot acquire any more locks.
• Strict Two-Phase Locking (Strict 2PL): A stricter variant where exclusive locks are held until the transaction commits or aborts. This prevents dirty reads and cascading rollbacks.
• Rigorous Two-Phase Locking (Rigorous 2PL): All locks (shared and exclusive) are held until the transaction commits or aborts. This is even stricter and easier to implement, preventing all anomalies.

Timestamp-Based Protocols

Instead of locks, transactions are assigned unique timestamps. The system ensures that operations are executed in timestamp order to maintain serializability.

• Each transaction T_i is assigned a unique fixed timestamp, TS(T_i), when it starts.
• The protocol ensures that if an operation of T_i conflicts with an operation of T_j, the one with the smaller timestamp precedes the one with the larger timestamp.
• Operations that violate the timestamp order are typically aborted and restarted with a new timestamp.

Validation-Based Protocols (Optimistic Concurrency Control)

These protocols assume that conflicts are rare. Transactions execute without explicit locking and are validated before commit.

• Each transaction proceeds through three phases:
1. Read Phase: Transaction executes, reading data items from the database. All writes are made to local copies of data items (private workspace).
2. Validation Phase: Before commit, the transaction is validated to check if it conflicts with any currently executing or recently committed transactions.
3. Write Phase: If validation is successful, changes from the private workspace are made permanent to the database. If validation fails, the transaction is rolled back.
• This approach avoids delays caused by locking, but may involve more rollbacks if conflicts are frequent.

Testing for Serializability

Testing for serializability ensures that a concurrent schedule will produce the same result as some serial execution, thus preserving database consistency.

Testing Conflict Serializability using Precedence Graph

The primary method for testing conflict serializability is by constructing and analyzing the precedence graph (or serializability graph) of a schedule.

Steps to Test Conflict Serializability:

1. Create a Node for Each Transaction: For every transaction T_i participating in the schedule, draw a node (vertex) in the graph.
2. Identify Conflicting Operations: Scan the schedule for pairs of conflicting operations (Read-Write, Write-Read, Write-Write) on the same data item, where the operations belong to different transactions.
3. Draw Directed Edges: For each conflict:
• If T_i performs an operation on a data item X, and then T_j performs a conflicting operation on X later in the schedule, draw a directed edge from T_i to T_j.
• Specifically, an edge T_i → T_j is drawn if:
• T_i reads X, then T_j writes X. (RW conflict)
• T_i writes X, then T_j reads X. (WR conflict)
• T_i writes X, then T_j writes X. (WW conflict)
4. Check for Cycles: After drawing all necessary edges, examine the precedence graph for the presence of any cycles.
• If the precedence graph contains a cycle, the schedule is NOT conflict serializable.
• If the precedence graph contains no cycles (it is a Directed Acyclic Graph - DAG), the schedule IS conflict serializable. The topological sort of the graph provides one or more equivalent serial schedules.

Example:

Consider the schedule S:

• T1: R(A)
• T2: R(A)
• T1: W(A)
• T2: W(A)

Precedence Graph Construction:

1. Nodes: T1, T2
2. Conflicts:
• T1 reads A, then T2 reads A. (No conflict, both are reads)
• T2 reads A, then T1 writes A. (WR conflict: T2 R(A) → T1 W(A)) → Edge T2 → T1
• T1 writes A, then T2 writes A. (WW conflict: T1 W(A) → T2 W(A)) → Edge T1 → T2
3. Edges: T2 → T1 and T1 → T2
4. Cycle Check: The graph has a cycle T1 → T2 → T1. Therefore, schedule S is not conflict serializable.