Transactions and Concurrency Control in DBMS – ACID, Serializability and 2PL
What You Will Learn
- Transaction concept and ACID properties
- Transaction states and state diagram
- Concurrency problems: dirty read, lost update, unrepeatable read, phantom read
- Serializability: conflict and view serializability with precedence graph
- Two-phase locking (2PL): basic, strict, rigorous variants
- Timestamp ordering and deadlock handling in DBMS
- GATE PYQs with complete solutions
GATE Weightage: 1–2 marks. Conflict serializability and 2PL are the most tested subtopics.
1. ACID Properties
ACID properties define the reliability guarantees for database transactions in DBMS.
| Property | Definition | Enforced By |
|---|---|---|
| Atomicity | All operations execute or none do — no partial transactions | UNDO logs, rollback |
| Consistency | Transaction brings DB from one valid state to another | Integrity constraints, triggers |
| Isolation | Concurrent transactions don’t interfere; appear serial | Concurrency control (2PL, MVCC) |
| Durability | Committed changes persist despite system failures | REDO logs, write-ahead logging |
2. Transaction States
| State | Description |
|---|---|
| Active | Transaction is currently executing operations |
| Partially Committed | Final operation executed; output may still be in volatile storage |
| Committed | All changes permanently written to database; cannot be undone |
| Failed | Normal execution cannot proceed (error detected) |
| Aborted | Transaction rolled back; database restored to before-transaction state |
| Terminated | After commit or abort — transaction is done |
3. Concurrency Problems
| Problem | Description | Example |
|---|---|---|
| Dirty Read | T2 reads data written by T1 before T1 commits; if T1 aborts, T2 has wrong data | T1 writes X=100, T2 reads X=100, T1 aborts (X should be 50) |
| Lost Update | Two transactions read-then-write same data; one update overwrites the other | Both T1 and T2 read X=50; T1 writes X=60, T2 writes X=70 → T1’s update lost |
| Unrepeatable Read | T1 reads same item twice; T2 modifies it between the reads; T1 gets different values | T1 reads X=50, T2 updates X=60, T1 reads X=60 (different) |
| Phantom Read | T1 executes a query twice; T2 inserts/deletes rows in between; T1 sees different rows | T1 counts employees (N=10), T2 inserts employee, T1 counts again (N=11) |
4. Serializability
A schedule is serializable if its outcome is equivalent to some serial (non-interleaved) execution of the same transactions.
Conflict Operations
Two operations conflict if they:
- Belong to different transactions
- Access the same data item
- At least one is a Write
Conflict pairs: R-W, W-R, W-W (NOT R-R)
Conflict Serializability — Precedence Graph Test
1. Create a node for each transaction Ti
2. For each conflict between operations of Ti and Tj where Ti’s op comes first:
Draw an edge Ti → Tj
3. If the graph has NO cycle → Conflict Serializable
4. If the graph has a CYCLE → NOT conflict serializable
T1: R(A), R(B), W(A)
T2: R(A), W(A), R(B), W(B)
Interleaved: R1(A), R2(A), W2(A), R1(B), W1(A), R2(B), W2(B)
Conflicts:
R1(A) before W2(A) → edge T1 → T2
W2(A) before W1(A) → edge T2 → T1
Graph: T1 → T2 and T2 → T1 → CYCLE → Not conflict serializable
View Serializability
Broader than conflict serializability. Schedule S is view-equivalent to serial schedule S’ if:
- Same initial reads (first read of each item comes from same transaction)
- Same reads-from (each read of an item reads the value written by the same transaction)
- Same final write (same transaction performs the last write of each item)
Every conflict-serializable schedule is view serializable.
View-but-not-conflict-serializable schedules contain blind writes.
5. Two-Phase Locking (2PL)
2PL is the most widely used concurrency control protocol. It guarantees conflict serializability.
Lock Types
- Shared lock (S-lock / read lock): Multiple transactions can hold simultaneously; no write allowed
- Exclusive lock (X-lock / write lock): Only one transaction; no other S or X locks
Lock Compatibility Matrix
| Requested \ Held | S-lock | X-lock |
|---|---|---|
| S-lock | Compatible (grant) | Incompatible (wait) |
| X-lock | Incompatible (wait) | Incompatible (wait) |
2PL Variants
| Variant | Rule | Prevents |
|---|---|---|
| Basic 2PL | Two phases: growing then shrinking | Guarantees CSR; allows cascading rollbacks |
| Strict 2PL | Hold X-locks until commit/abort | Dirty reads + cascading rollbacks |
| Rigorous 2PL | Hold ALL locks (S + X) until commit/abort | All above; simplest to implement |
6. Deadlock in DBMS
Wait-For Graph
Node per transaction. Edge Ti → Tj means Ti is waiting for a lock held by Tj. A cycle in the wait-for graph indicates deadlock.
Deadlock Prevention Protocols
| Protocol | Rule | Effect |
|---|---|---|
| Wait-Die | Older waits for younger; younger aborts (dies) if waiting for older | Non-preemptive; older always waits |
| Wound-Wait | Older wounds (aborts) younger; younger waits for older | Preemptive; older never waits |
→ T1 WAITS (older waits for younger)
T2 (younger, TS=5) wants lock held by T1 (older, TS=1)
→ T2 DIES (aborted, will restart with original timestamp)
Wound-Wait: T1 (older) wants lock held by T2 (younger)
→ T1 WOUNDS T2 (T2 is aborted)
T2 (younger) wants lock held by T1 (older)
→ T2 WAITS
7. Timestamp Ordering
Each transaction Ti gets a unique timestamp TS(Ti) at start. Operations are ordered by timestamps — no locks needed.
W-timestamp(Q) = max TS of any transaction that successfully wrote Q
R-timestamp(Q) = max TS of any transaction that successfully read Q
Read rule: If TS(Ti) < W-timestamp(Q): Ti is reading an outdated value → ABORT Ti
Write rule: If TS(Ti) < R-timestamp(Q): Ti’s write is too late → ABORT Ti
If TS(Ti) < W-timestamp(Q): a newer write already happened → ignore (Thomas Write Rule)
8. GATE Examples
GATE 2014: Consider the schedule: R1(X), R2(X), W1(X), W2(X). Is this conflict serializable?
View Solution
Conflicts (different transactions, same item, at least one write):
R2(X) before W1(X) → T2 → T1
W1(X) before W2(X) → T1 → T2
Precedence graph: T2 → T1 and T1 → T2 → CYCLE
Not conflict serializable.
Equivalent serial schedules would be T1,T2 or T2,T1 — but neither matches due to the conflict ordering.
GATE 2016: Which of the following properties does Strict 2PL guarantee over Basic 2PL?
View Solution
Basic 2PL: guarantees conflict serializability; allows cascading rollbacks (dirty reads).
Strict 2PL: also guarantees conflict serializability AND prevents cascading rollbacks by holding X-locks until commit.
Answer: Strict 2PL prevents cascading rollbacks (dirty reads) in addition to guaranteeing serializability.
GATE 2018: Schedule S: R1(A), W2(A), R2(B), W1(B), C1, C2. Draw the precedence graph and determine serializability.
View Solution
Conflicts:
R1(A) before W2(A): T1 → T2
R2(B) before W1(B): T2 → T1
Precedence graph: T1 → T2 and T2 → T1 = cycle.
Not conflict serializable.
9. Common Mistakes
- R-R is not a conflict: Two reads from different transactions on the same item do NOT conflict. Conflict requires at least one write. Only pairs that conflict: R-W, W-R, W-W.
- Precedence graph edges: Edge goes from the transaction whose conflicting operation appears FIRST in the schedule. Ti → Tj means Ti’s conflicting operation comes before Tj’s.
- 2PL and deadlock: 2PL guarantees serializability but does NOT prevent deadlocks. Deadlocks are handled separately by detection (wait-for graph) or prevention (wait-die, wound-wait).
- Strict 2PL vs Rigorous 2PL: Strict 2PL holds only X-locks (write locks) until commit. Rigorous 2PL holds ALL locks (S + X) until commit. Both prevent cascading rollbacks, but Rigorous is more restrictive.
- View serializable but not conflict serializable: This is possible when blind writes exist. A blind write is a write not preceded by a read of the same item by the same transaction.
10. Frequently Asked Questions
What are the ACID properties of transactions in DBMS?
Atomicity: all-or-nothing execution, enforced by rollback/undo. Consistency: valid state to valid state, enforced by constraints. Isolation: concurrent transactions behave as if serial, enforced by 2PL or MVCC. Durability: committed changes survive crashes, enforced by write-ahead logging. In GATE, questions often ask which subsystem enforces which property — isolation is concurrency control, durability is recovery management.
What is conflict serializability in DBMS?
A schedule is conflict serializable if its precedence (conflict) graph is acyclic. To build the graph: node per transaction; edge Ti→Tj if Ti has a conflicting operation before Tj’s conflicting operation on the same item (conflict = different transactions + same item + at least one write). An acyclic precedence graph means a topological sort gives the equivalent serial schedule.
What is two-phase locking (2PL) in concurrency control?
2PL has two phases: growing (acquire locks, don’t release) and shrinking (release locks, don’t acquire). Guarantees conflict serializability. Strict 2PL holds write locks until commit/abort, preventing cascading rollbacks. Rigorous 2PL holds all locks until commit/abort. 2PL can still cause deadlocks, handled by wait-for graph detection and victim selection.
What is the difference between conflict serializable and view serializable schedules?
Conflict serializability: determined by precedence graph acyclicity. Stricter and efficiently checkable. View serializability: determined by equivalence of initial reads, reads-from relations, and final writes. Broader — includes some non-conflict-serializable schedules (those with blind writes). Every conflict-serializable schedule is view serializable. Checking view serializability is NP-complete; conflict serializability is polynomial, hence used in practice.