Transaction Processing & Concurrency Control

Transaction Processing & Concurrency Control

A Transaction is a single logical unit of work that accesses and possibly modifies the contents of a database. It can consist of one or many SQL statements. To maintain database consistency, a transaction must be executed entirely, or not at all.

1. ACID Properties

1. Atomicity (All or Nothing): The entire transaction takes place at once or doesn't happen at all. If a transaction fails halfway, all previous changes made by it are rolled back.
2. Consistency: A transaction must transform the database from one consistent state to another consistent state, obeying all integrity constraints (like Primary/Foreign keys).
3. Isolation: Concurrent transactions must execute without interfering with each other. The intermediate state of a transaction should remain invisible to other transactions.
4. Durability: Once a transaction is successfully completed (committed), its changes must persist in the database, even in the event of a system failure (like a power outage).

2. Transaction States

• Active: The initial state where the transaction is executing its instructions.
• Partially Committed: Executed the final operation but data is still in memory buffer, not yet permanently written to disk.
• Committed: Changes are permanently saved to the disk. The transaction is successful.
• Failed: An error or system crash occurs, preventing completion.
• Aborted: The transaction has been rolled back to its initial state to undo any partial changes.

3. Concurrency Problems

1. Dirty Read (Uncommitted Dependency): Transaction T1 updates a row but hasn't committed. Transaction T2 reads this uncommitted value. If T1 fails and rolls back, T2 is now working with 'dirty' (invalid) data.
2. Non-Repeatable Read: Transaction T1 reads a row. Before T1 finishes, T2 updates or deletes that exact row and commits. If T1 reads the row again, it gets a completely different value.
3. Phantom Read: T1 executes a query that returns a set of rows. T2 then inserts a new row that matches T1's query condition. If T1 re-executes the query, a 'phantom' row magically appears in the result set.

4. Schedules & Serializability

• Serial Schedule: Transactions execute one after another without any interleaving. It is safe but slow.
• Concurrent Schedule: Operations from multiple transactions are interleaved. Faster, but can lead to inconsistencies.

4.1 Serializability

• Conflict Serializability: Two operations conflict if they belong to different transactions, access the same data item, and at least one is a WRITE. If a concurrent schedule can be transformed into a serial schedule by swapping non-conflicting operations, it is Conflict Serializable.
• View Serializability: A more relaxed form. Two schedules are view equivalent if they read the same initial values, read the same values written by other transactions, and write the same final values.

5. Concurrency Control Protocols

5.1 Lock-Based Protocols

• Shared Lock (S): Required to READ a data item. Multiple transactions can hold a Shared Lock on the same item simultaneously.
• Exclusive Lock (X): Required to WRITE (update/delete). Only one transaction can hold an Exclusive Lock. It blocks all other locks. Two-Phase Locking (2PL) Protocol: Ensures conflict serializability. A transaction divides its execution into two phases:

1. Growing Phase: The transaction can acquire locks but cannot release any lock.
2. Shrinking Phase: Once the transaction releases its first lock, it enters this phase. It can release locks but cannot acquire any new locks.

• Strict 2PL: Holds all Exclusive (X) locks until the transaction commits/aborts. Prevents cascading rollbacks.
• Rigorous 2PL: Holds ALL locks (S and X) until commit/abort.

5.2 Timestamp Ordering Protocol

• If T1 starts before T2, then TS(T1) < TS(T2).
• It ensures that conflicting READ and WRITE operations are executed in timestamp order.
• Unlike locking, it does not cause deadlocks because transactions are never made to wait; instead, they are rolled back and restarted with a new timestamp if order is violated.

6. Deadlocks

Deadlock Handling Techniques:

1. Deadlock Prevention: Ensures the system never enters a deadlock state.
   • Wait-Die Scheme: Older transaction waits for the younger one. If younger requests a lock held by older, younger is rolled back (dies).
   • Wound-Wait Scheme: Older transaction preempts (wounds) the younger one by forcing it to roll back. If younger requests a lock held by older, younger waits.
2. Deadlock Detection: Allows deadlocks to happen. Periodically checks a Wait-For Graph (WFG). If a cycle exists in the graph, a deadlock has occurred.
3. Deadlock Recovery: Once detected, the system breaks the cycle by selecting a 'victim' transaction, rolling it back, and releasing its locks.