Transaction Processing and Concurrency Control
Open in the Padhaiko app7.1 Transaction and transaction model - State diagram
A transaction is a logical unit of database work (one or more read(X), write(X), or SQL statements) that accesses and possibly updates various data items, executing either completely or not at all.
Five States of a Transaction
- Active: The initial state; the transaction stays in this state while it is executing its read/write instructions.
- Partially Committed: Reached immediately after the final statement of the transaction has executed, before its log records and modifications are safely flushed to non-volatile disk storage.
- Committed: Reached once all changes are guaranteed permanent (durable) in stable storage; the transaction has completed successfully and cannot be aborted.
- Failed: Reached from Active or Partially Committed if normal execution can no longer proceed (e.g., constraint violation, deadlock abort, hardware crash, or explicit
ROLLBACK). - Aborted: Reached after the transaction has been rolled back and the database is restored to its exact state prior to the start of the transaction. From Aborted, the system either restarts the transaction (if caused by hardware/concurrency error) or kills it (if caused by internal logic error).
+-------------------+
| Partially |----(Durable Flush)---> [ Committed ]
| Committed |
+-------------------+
^ \
(Last Statement) | \ (Disk/Write Failure)
| v
(Start) ----------> [ Active ] -------> [ Failed ]
(Executing) (Error/Abort) |
| (Rollback Complete)
v
[ Aborted ] ---> (Restart / Kill)7.2 Acid properties
To preserve database integrity despite concurrent users and system crashes, every transaction must satisfy four ACID properties:
| Property | Formal Meaning | Enforced By |
|---|---|---|
| A — Atomicity | "All or nothing": either all operations of the transaction reflect properly in the database, or none do. | Recovery Manager (Undo logging / rollback) |
| C — Consistency | Execution of a transaction in isolation (from a consistent state) preserves all database consistency invariants (e.g., total sum of accounts remains unchanged). | Application Programmer + DBMS Integrity Constraints |
| I — Isolation | Even when multiple transactions execute concurrently, each transaction is unaware of others; intermediate dirty updates are hidden until commit, producing an effect equivalent to serial execution. | Concurrency Control Manager (Locking / Timestamps / MVCC) |
| D — Durability | Once a transaction commits, its updates persist permanently even if a power loss or system crash occurs immediately afterward. | Recovery Manager (Redo logging / WAL flush to stable disk) |
7.3 Concurrent execution of transactions
Executing transactions concurrently (interleaving their CPU and disk operations) improves system throughput (more transactions per second) and reduces average response time (short transactions do not wait behind long disk-bound ones). However, uncontrolled interleaving causes severe concurrency anomalies:
| Anomaly | Description |
|---|---|
| Lost Update (W–W) | and both read , modify it, and write back; the second write overwrites and erases the first update. |
| Dirty Read (W–R) | updates , reads the uncommitted , and then aborts—leaving holding phantom invalid data. |
| Unrepeatable Read (R–W–R) | reads ; modifies and commits ; re-reads and gets a different value within the same transaction. |
| Phantom Read | executes a range query (WHERE Dept='CS'), inserts a new 'CS' row and commits, and 's repeat query sees a "phantom" row. |
Schedules and Recoverability
A schedule is an ordering of the instructions of a set of concurrent transactions that preserves the relative order of instructions within each individual transaction. For transactions with operations, there are serial schedules (no interleaving) and total valid schedules.
- Recoverable Schedule: For every pair where reads a value written by , must commit before commits (otherwise could commit dirty data before aborts!).
- Cascadeless Schedule (ACA — Avoids Cascading Aborts): Every transaction reads only committed data ( commits before even reads 's written item). Every cascadeless schedule is recoverable.
- Strict Schedule: No transaction may read or overwrite an item written by until commits or aborts. Strict schedules guarantee both cascadeless recovery and simple physical undo.
7.4 Serializability (Conflict and view serializability)
A concurrent schedule is serializable if its net effect on the database is identical to some serial schedule of the same transactions.
Conflict Serializability vs. View Serializability
- Conflicting Instructions: Two consecutive instructions (from ) and (from , ) conflict if they access the same data item and at least one of them is a
write(Q):- and : Do NOT conflict (order can be swapped).
- and , and , and : CONFLICT (order matters).
- Conflict Equivalence & Conflict Serializability: Schedule is conflict equivalent to if can be transformed into by swapping adjacent non-conflicting instructions. Schedule is conflict serializable if it is conflict equivalent to some serial schedule.
- View Equivalence & View Serializability: Schedules and are view equivalent if for every data item :
- (Initial Read) Whichever transaction reads the initial value of in also does so in .
- (Reads-From) If reads a value of written by in , it does so in .
- (Final Write) Whichever transaction performs the final
write(Q)in also performs the finalwrite(Q)in . Schedule is view serializable if it is view equivalent to a serial schedule.
Precedence Graph Test for Conflict Serializability
Construct a directed precedence (serialization) graph where vertices are the transactions , and add a directed edge whenever an operation of precedes and conflicts with an operation of on the same data item (, , or ).
- Theorem: A schedule is conflict serializable if and only if its precedence graph is acyclic (contains no directed cycles).
- If acyclic, any topological sort of gives an equivalent serial execution order.
- Every conflict-serializable schedule is view-serializable, but the converse is false only when blind writes (writing without first reading ) occur.
7.5 Lock based protocols
A lock controls concurrent access to a data item using two standard lock modes:
- Shared Lock (
S): Obtained beforeread(Q); multiple transactions can holdSlocks on simultaneously. - Exclusive Lock (
X): Obtained beforewrite(Q)(or read+write); only one transaction may hold anXlock on , blocking all otherSandXrequests.
| Requested \ Held | Shared (S) | Exclusive (X) |
|---|---|---|
Shared (S) | True (Compatible) | False (Wait) |
Exclusive (X) | False (Wait) | False (Wait) |
Two-Phase Locking (2PL) Protocols
Simply locking and unlocking immediately around individual reads/writes does not guarantee serializability. Two-Phase Locking (2PL) guarantees conflict serializability by dividing each transaction into two distinct phases:
- Growing Phase: A transaction may acquire locks (and upgrade
SX), but may not release any lock. - Shrinking Phase: A transaction may release locks (and downgrade
XS), but may not acquire any new locks. (The point where the transaction holds its maximum locks and releases its first lock is the lock point, which defines the equivalent serial order!)
| Aspect | Basic 2PL | Strict 2PL & Rigorous 2PL |
|---|---|---|
| Basic 2PL | Any lock may be released as soon as the shrinking phase starts. | Guarantees conflict serializability, but vulnerable to cascading aborts and deadlocks. |
| Strict 2PL | All exclusive (X) locks are held until the transaction commits or aborts; S locks may release earlier. | Guarantees conflict serializability, strictness, and cascadeless (ACA) recovery. (Industry standard!) |
| Rigorous 2PL | All locks (S and X) are held until commit or abort. | Same as Strict 2PL, plus commit order directly matches the serialization order. |
7.6 Deadlock handling and prevention
A system is in deadlock when a cycle of two or more transactions exists where every transaction is waiting for a lock held by the next transaction in the cycle (e.g., holds X(A) and waits for X(B) while holds X(B) and waits for X(A)).
1. Deadlock Prevention (Timestamp-Based Schemes)
Assign each transaction a unique startup timestamp (smaller timestamp = older transaction). When requests a lock held by :
| Aspect | Wait-Die Scheme (Non-Preemptive) | Wound-Wait Scheme (Preemptive) |
|---|---|---|
| is OLDER () | is allowed to WAIT for . | WOUNDS (preempts/aborts) , forcing to roll back and release the lock. |
| is YOUNGER () | DIES (aborts itself and restarts with the same original timestamp). | is allowed to WAIT for . |
| Key Characteristic | Older transactions wait for younger ones; prevents cycles without preemption, though younger ones may abort repeatedly. | Older transactions never wait for younger ones; fewer aborts overall. Retaining the original timestamp on restart prevents starvation in both schemes! |
(Timeout-based prevention simply aborts any transaction that waits longer than a threshold; simple to implement but risks unnecessary rollbacks under heavy load.)
2. Deadlock Detection and Recovery
- Detection: Maintain a directed Wait-For Graph (WFG) where edge means is waiting for a lock held by . Periodically search for cycles in the WFG.
- Recovery: Break each cycle by selecting a victim transaction to abort and roll back (total or partial rollback to a savepoint). Victim selection minimizes rollback cost (preferring transactions that have run briefly, hold few locks, update few items, and haven't been rolled back repeatedly to prevent starvation).
7.7 Multiple granularity
Real databases contain data items of vastly different sizes. Locking only tuples incurs huge lock-manager overhead on full-table scans, whereas locking only entire tables destroys concurrency for single-row updates. Multiple granularity locking organizes items into a tree hierarchy:
To allow locking at any level safely without scanning the whole subtree for conflicting lower-level locks, intention locks are placed on ancestor nodes first:
Intention Lock Modes
IS(Intention-Shared): Indicates explicitSlocks are being requested at a lower level of the subtree.IX(Intention-Exclusive): Indicates explicitX(orS) locks are being requested at a lower level of the subtree.SIX(Shared and Intention-Exclusive): Holds anSlock on the entire subtree rooted at this node plus anIXintention to acquireXlocks on specific lower-level descendants (equivalent toS+IX).
| Requested \ Held | IS | IX | S | SIX | X |
|---|---|---|---|---|---|
IS | True | True | True | True | False |
IX | True | True | False | False | False |
S | True | False | True | False | False |
SIX | True | False | False | False | False |
X | False | False | False | False | False |
- Protocol Rules: Locking proceeds top-down (root to target: must hold
IX/SIXon parent before acquiringX/IXon child, andIS/IX/S/SIXon parent beforeS/ISon child); unlocking proceeds strictly bottom-up (leaf to root).
Worked Out Examples
7.1
Test the following two schedules for conflict serializability using precedence graphs; if conflict serializable, give an equivalent serial schedule:
Analyzing Schedule : Check all conflicting operation pairs (same item, different transactions, at least one Write):
- On item :
- .
- and are both in (no edge); and do not conflict.
- On item :
- (same tx); .
- On item : only appears (no conflict).
- Edges of : . No cycle exists!
- Result for : Conflict serializable; unique topological order is .
Analyzing Schedule : Check conflicts in :
- On item :
- .
- .
- .
- On item :
- .
- Now look at the edges: and form a -cycle (, as well as )!
- Result for : Not conflict serializable.
- is conflict serializable (acyclic precedence graph ; equivalent serial schedule: ).
- is not conflict serializable (contains cycle ).
7.2
Examine the schedule with a blind write:
Show that is not conflict serializable, yet is view serializable (and find the equivalent serial schedule).
Conflict Serializability Test (Precedence Graph): Every pair of operations accesses with at least one write:
- .
- .
- .
Because forms a cycle, is not conflict serializable.
View Serializability Test (Three View-Equivalence Conditions on ):
Check the three view conditions in :
- Initial Read: reads the initial database value of .
- Reads-From: No transaction reads any value written by another transaction in .
- Final Write: performs the final
write(Q).
Now test the serial schedule ():
- Initial Read: reads initial (matches ).
- Reads-From: None (matches ).
- Final Write: performs the final
write(Q)(matches ).
All three conditions hold!
is not conflict serializable (precedence graph has cycle ), but is view serializable and view-equivalent to the serial schedule .
7.3
- Three transactions arrive with timestamps , , . Suppose holds an
Xlock on item . Determine what happens under (a) Wait-Die and (b) Wound-Wait when:- Case 1: requests
X(A) - Case 2: requests
X(A)
- Case 1: requests
- If two transactions and each have operations (), how many total valid schedules and how many non-serial (interleaved) schedules exist? Also how many serial schedules exist for transactions?
Wait-Die vs. Wound-Wait Outcomes: Remember: smaller timestamp = older transaction ( is older than , and is younger than ).
- Case 1 ( older requests item held by younger):
- Wait-Die: Older WAITS for .
- Wound-Wait: Older WOUNDS (aborts) younger and takes the lock.
- Case 2 ( younger requests item held by older):
- Wait-Die: Younger DIES (aborts and restarts) with original timestamp .
- Wound-Wait: Younger WAITS for older .
Counting Serial and Interleaved Schedules:
- For transactions, number of serial schedules .
- For () and (), total schedules preserving intra-transaction order:
- Subtracting the serial schedules ( and ) leaves interleaved (non-serial) schedules.
- Case 1 (): Wait-Die: waits; Wound-Wait: is wounded (aborted). Case 2 (): Wait-Die: dies (aborts); Wound-Wait: waits.
- transactions have serial schedules; two -operation transactions have total schedules ( interleaved, serial).
Exercises
Practice Exercises — Transactions & Concurrency
Draw the transaction state diagram and explain each of the five states (Active, Partially Committed, Committed, Failed, Aborted). Explain the ACID properties of a transaction with a banking transfer example.
Transaction States: A transaction begins in Active, moves to Partially Committed after its final operation, and enters Committed once log records/writes are flushed durably to disk. If any error or abort occurs during Active or Partially Committed, it moves to Failed, rolls back all partial changes, and reaches Aborted (where it is killed or restarted).
ACID Properties (Transferring from Account to ):
- Atomicity: Either both debit() and credit() happen, or neither happens.
- Consistency: Total money before and after the transfer remains identical.
- Isolation: Another concurrent balance-check query cannot observe debited before is credited.
- Durability: Once committed, the updated balances survive a crash immediately afterward.
The five states are Active Partially Committed Committed, or Failed Aborted. ACID stands for Atomicity (all-or-nothing), Consistency (invariant preservation), Isolation (concurrent invisibility), and Durability (post-commit persistence).
Differentiate between recoverable, cascadeless (ACA), and strict schedules. Give a concrete two-transaction example of a non-recoverable schedule and explain why strict schedules are preferred in practice.
Schedule Hierarchy:
- Recoverable: If reads an item written by , must commit before commits.
- Cascadeless (ACA): may only read items written by after has committed (prevents cascading rollbacks).
- Strict: may neither read nor write any item written by until commits or aborts. (Inclusion: .)
Non-Recoverable Example and Why Strict Is Preferred: Consider . Here commits after reading 's uncommitted write, then aborts— cannot be undone, violating durability/atomicity! Strict schedules are preferred because they completely prevent cascading aborts and allow simple physical before-image undo without overwriting another uncommitted write.
Recoverable commits writers before dependent readers; cascadeless delays reads until the writer commits; strict delays both reads and writes until the writer commits/aborts. Strict schedules are preferred because they eliminate cascading rollbacks and simplify undo recovery.
State the Two-Phase Locking (2PL) protocol and contrast Basic 2PL, Strict 2PL, and Rigorous 2PL. Does Basic 2PL prevent deadlocks? Explain.
Two-Phase Locking Variants: Under 2PL, every transaction has a Growing Phase (acquires locks, never releases) followed by a Shrinking Phase (releases locks, never acquires).
- Basic 2PL: Releases any lock once the shrinking phase begins; guarantees conflict serializability, but allows dirty reads / cascading aborts if
Xlocks are released early. - Strict 2PL: Holds all
Xlocks untilCOMMIT/ABORT; guarantees conflict serializability and strict/cascadeless schedules. - Rigorous 2PL: Holds all
SandXlocks untilCOMMIT/ABORT; commit order matches serialization order.
2PL and Deadlocks: No—Basic (and Strict/Rigorous) 2PL does NOT prevent deadlocks. For example, acquires S(A), acquires S(B), then requests X(B) (waits for ) and requests X(A) (waits for ). Both are still in their growing phases, yet they are deadlocked!
2PL enforces a Growing Phase (acquire only) followed by a Shrinking Phase (release only). Strict 2PL holds X locks until commit/abort (cascadeless recovery) and Rigorous 2PL holds all locks until commit/abort. None of them prevents deadlocks, which must be handled via detection or timestamp prevention.
Explain Multiple Granularity Locking using intention locks (IS, IX, SIX). Suppose transaction wants to read a single tuple in table Student while wants to update every tuple in Student. Which lock modes must and acquire from Database down to Tuple, and can they run concurrently?
Lock Acquisition Paths:
- (reads one tuple in
Student):ISonDatabaseISonStudent(table)ISonPagecontainingSon tuple
- (updates the entire
Studenttable):IXonDatabaseXonStudent(table—no need to lock individual pages or tuples!)
Concurrency Check Using Compatibility Matrix:
- At
Database: requestsISand holdsIXCompatible. - At
Student: requestsISwhile holdsXIncompatible! (ISconflicts withX).
Therefore, must wait until releases X(Student), preventing from reading partially updated rows.
acquires IS(Database) IS(Student) IS(Page) S(t); acquires IX(Database) X(Student). They cannot run concurrently because IS and X are incompatible on Student.
- Test the schedule for conflict serializability using a precedence graph.
- How many serial schedules exist for transactions? For transactions each having operations, how many non-serial (interleaved) schedules exist?
Precedence Graph for : Inspect conflicts on each data item:
- On : .
- On : .
- On : .
The graph contains the directed -cycle , so is not conflict serializable.
Schedule Counting:
- Serial schedules for transactions: .
- Total schedules for two -operation transactions:
- Subtracting the serial schedules gives interleaved (non-serial) schedules.
- is not conflict serializable (cycle ).
- transactions have serial schedules; two -operation transactions have non-serial schedules ( total minus serial).