Transactions & Concurrency Control
Transactions ensure database consistency under concurrent access. GATE tests ACID properties, serializability, conflict serializability, and lock-based protocols including 2PL.
Key Points
- ·ACID: Atomicity (all or nothing), Consistency (invariants preserved), Isolation (concurrent = serial), Durability (committed data persists)
- ·Schedule: ordering of operations from multiple transactions
- ·Serial schedule: transactions execute one after another — always correct
- ·Serializable schedule: equivalent to some serial schedule
- ·Conflict serializability: check conflict graph (precedence graph) for cycles
- ·Two operations conflict if: same data item, different transactions, at least one is write
- ·2PL (Two-Phase Locking): growing phase (acquire locks) + shrinking phase (release locks)
- ·Strict 2PL: hold all write locks until commit — prevents cascading aborts
- ·Deadlock in 2PL: use wait-die or wound-wait schemes
What is a Transaction?
Analogy: A bank transfer — move ₹1000 from account A to account B.
This requires TWO steps: 1. Subtract ₹1000 from A 2. Add ₹1000 to B
What if the system crashes after step 1? The money disappears! A transaction ensures either BOTH steps happen, or NEITHER happens.
ACID Properties — The 4 Guarantees
A = Atomicity: ALL operations succeed, OR none happen (no halfway state)
"Transfer succeeds fully or fails completely"
C = Consistency: DB stays in a valid state (all rules satisfied) after transaction
"Total money before = Total money after"
I = Isolation: Concurrent transactions behave as if they ran one-at-a-time
"You cannot see another transaction's half-finished work"
D = Durability: Once committed, changes survive crashes (written to disk)
"Your bank receipt is permanent"
| Property | Enforced by |
|---|---|
| Atomicity | Undo log (rollback on failure) |
| Consistency | Application + DB constraints |
| Isolation | Concurrency control (locking) |
| Durability | Redo log (recover after crash) |
Schedules — Order of Operations
Serial schedule: T1 runs completely, then T2. Always correct (but slow).
Concurrent schedule: T1 and T2 interleave. Faster, but might cause problems.
Serializable schedule: A concurrent schedule that produces the SAME result as some serial schedule.
Conflict Operations — When Do Two Operations Interfere?
Two operations conflict if ALL THREE conditions hold:
1. They belong to DIFFERENT transactions
2. They access the SAME data item
3. At LEAST ONE is a WRITE
Conflicting pairs: (Read_i, Write_j), (Write_i, Read_j), (Write_i, Write_j)
Non-conflicting: (Read_i, Read_j) ← two reads never conflict
Conflict Serializability — The Cycle Test
Build a conflict graph (precedence graph):
Step 1: One node per transaction
Step 2: Draw edge Ti → Tj if Ti has a conflicting operation that comes BEFORE Tj's conflicting op on the same item
Schedule is CONFLICT SERIALIZABLE iff this graph has NO cycles (is a DAG)
Worked Example:
Schedule: R1(A), R2(A), W1(A), W2(A)
Conflicts:
W1(A) vs R2(A): T1 wrote after T2 read (but R2 is before W1)
→ R2(A) before W1(A): edge T2 → T1
W1(A) vs W2(A): W1 before W2: edge T1 → T2
Graph: T2 → T1 → T2 ← CYCLE! Not serializable.
Two-Phase Locking (2PL)
The rule: Every transaction must go through two phases:
Phase 1 - GROWING: Can acquire locks, CANNOT release any lock
↓
[Lock point] ← moment of last lock acquired
↓
Phase 2 - SHRINKING: Can release locks, CANNOT acquire new locks
Key Guarantee: If ALL transactions follow 2PL → schedule is conflict serializable.
BUT: 2PL does NOT prevent deadlocks!
Variants of 2PL
Basic 2PL: Growing + shrinking phases
Strict 2PL: Hold WRITE locks until COMMIT (prevents cascading rollbacks)
Rigorous 2PL: Hold ALL locks until COMMIT (simplest recovery)
Deadlock
Analogy: T1 holds lock on A, waiting for B. T2 holds lock on B, waiting for A. Neither can proceed!
Prevention strategies (using timestamps):
Wait-Die: Older transaction waits; younger DIES (aborts)
Wound-Wait: Older WOUNDS (aborts) younger; younger waits
Detection: build "waits-for" graph; cycle = deadlock → abort one transaction
Isolation Levels (SQL Standard)
Problem types:
Dirty Read: Read uncommitted data from another transaction
Non-repeatable Read: Re-read gives different value (another committed write)
Phantom Read: New rows appear in re-executed query
┌─────────────────┬────────────┬──────────────────┬─────────┐
│ Isolation Level │ Dirty Read │ Non-repeatable │ Phantom │
├─────────────────┼────────────┼──────────────────┼─────────┤
│ Read Uncommitted│ ✓ │ ✓ │ ✓ │
│ Read Committed │ ✗ │ ✓ │ ✓ │
│ Repeatable Read │ ✗ │ ✗ │ ✓ │
│ Serializable │ ✗ │ ✗ │ ✗ │
└─────────────────┴────────────┴──────────────────┴─────────┘
Quick Check
Q1. Is (Read_i, Read_j) on the same item a conflict? Why? Answer: No. Two reads never conflict — they just read the same value, no issue.
Q2. T1: W(A), W(B). T2: R(A), R(B). What edges go in the conflict graph?
If schedule is: W1(A), R2(A), W1(B), R2(B)
W1(A) before R2(A) → edge T1 → T2
W1(B) before R2(B) → edge T1 → T2
Graph: T1 → T2 (no cycle) → Conflict serializable, equivalent to T1 then T2
Q3. Can 2PL cause deadlock? Answer: Yes! 2PL prevents non-serializable schedules but does NOT prevent deadlock. Need separate deadlock handling.
Key Formulas
- Conflict graph: Schedule CS ⟺ precedence graph is a DAG (no cycles)
- 2PL guarantee: All transactions obey 2PL ⟹ conflict serializable
GATE Exam Tips
- ★Build the precedence graph and check for cycles — this is the most tested GATE approach.
- ★2PL guarantees conflict serializability but does NOT prevent deadlocks.
- ★Strict 2PL additionally prevents dirty reads and cascading rollbacks.
- ★View serializable ⊇ conflict serializable — every CS schedule is VS, not vice versa.
Finished reading this topic?
Mark it complete to track your study progress.