Concurrency-control questions rarely look like definitions: they arrive as interleaved reads, writes, locks and commits. The reliable route is computational: identify conflicts, derive the precedence graph, test for a cycle, and then check recoverability separately. The same sequence also clarifies lost updates, 2PL, timestamp rules and deadlock prevention.
Why concurrency control exists: the four anomalies
When transactions interleave on shared data, the DBMS should preserve a result equivalent to running them one after another. Without control, four classic anomalies can appear: lost update, dirty read, unrepeatable read and phantom.
Take an account X with balance 1000. T1 withdraws 200, while T2 deposits 500:
T1 reads X = 1000.
T2 reads X = 1000.
T1 computes 1000 - 200 = 800 and writes X = 800.
T2 computes 1000 + 500 = 1500 and writes X = 1500.
The final balance is 1500, but the correct serial result is 1000 - 200 + 500 = 1300. T2 used a stale value and overwrote T1's write, so the 200 withdrawal was lost. Serialising the two updates forces the later write to see the earlier transaction's effect.
A dirty read reads data written by a transaction that later aborts. An unrepeatable read gets a different value when the same row is read twice inside one transaction. A phantom appears when a repeated range query returns new rows. These are the failures; serializability and locking are the machinery used to stop them.
Schedules and serializability: the core vocabulary
A serial schedule runs one transaction from start to finish before beginning another. It is safe but gives up useful concurrency. A non-serial schedule interleaves operations for better throughput, but it needs a correctness test. A schedule is serializable when its effect is equivalent to some serial schedule.
Start with the transaction-level foundation in DBMS Transactions: ACID, Serializability, 2PL Explained. Conflict serializability is the usual hand-computation test. View serializability is weaker and harder to test. Two operations conflict only when they belong to different transactions, access the same item and at least one is a write. Therefore Write-Read, Read-Write and Write-Write conflict. Read-Read never does.
The precedence graph method, worked end to end
The method is mechanical:
Draw one node for each transaction.
For every conflicting pair, draw Ti -> Tj when Ti's operation appears first.
Check the graph for a cycle.
If it is acyclic, a topological order gives the equivalent serial order.
Consider this schedule over A and B:
R1(A)
W1(A)
R3(A)
W3(A)
R2(B)
W2(B)
R1(B)
W1(B)
On A, W1(A) comes before R3(A), W1(A) comes before W3(A), and R1(A) comes before W3(A). Every conflict produces T1 -> T3. On B, W2(B) comes before R1(B), W2(B) comes before W1(B), and R2(B) comes before W1(B). Every conflict produces T2 -> T1.
The distinct edges are T2 -> T1 and T1 -> T3. There is no cycle, so the schedule is conflict serializable. Its topological order is T2, T1, T3.
The same technique exposes a bad schedule. If T1 writes A before T2 reads it, but T2 then writes A before T1 reads it, the graph contains T1 -> T2 and T2 -> T1. That two-node cycle says each transaction must come before the other, which is impossible.
Locking protocols: Two-Phase Locking and strict 2PL
A precedence graph checks a completed schedule. Locks help the DBMS produce a safe schedule at run time. A shared lock permits reading and can coexist with other shared locks. An exclusive lock permits writing and excludes every other lock on that item.
Under Two-Phase Locking (2PL), each transaction has two phases. In the growing phase it acquires locks but releases none. In the shrinking phase it releases locks but acquires no new ones. The final acquisition is the lock point. Every schedule produced under 2PL is conflict serializable, although basic 2PL can still deadlock and can allow cascading aborts.
Now let A = 100. T1 performs A = A + 50, and T2 performs A = A × 2. Under strict 2PL, T1 can acquire X-lock(A) first. T2's X-lock(A) request then blocks until T1 commits and releases the lock.
Only two serial outcomes remain:
T1 then T2: (100 + 50) × 2 = 150 × 2 = 300.
T2 then T1: (100 × 2) + 50 = 200 + 50 = 250.
Neither outcome loses an update. Strict 2PL holds every exclusive lock until commit or abort, which also prevents dirty reads of those writes and cascading rollback.
Timestamp ordering and deadlock prevention
Locking is pessimistic: a transaction blocks and waits. Timestamp ordering gives every transaction a unique timestamp at start and requires conflicting operations to respect that order. An operation that would violate the order is rejected, and its transaction restarts with a new timestamp.
Lock-based systems can deadlock, so compare the prevention rules using Ti with timestamp 5 and Tj with timestamp 10. Ti is older because the smaller timestamp started first.
Scheme | Older requests younger's lock | Younger requests older's lock |
|---|---|---|
Wait-Die, non-preemptive | Ti waits | Tj dies and restarts with the same timestamp |
Wound-Wait, preemptive | Ti wounds Tj, forcing Tj to abort | Tj waits |
The memory hook is simple: the older transaction is favoured. In wait-die it is allowed to wait, while the younger one dies. In wound-wait it can abort the younger, while the younger must wait. Retaining the original timestamp after a restart prevents repeated restarts from causing starvation. For the operating-systems angle on the same coordination problem, see Process Synchronization and Semaphores.
Recoverability: the piece students skip
Serializability is not enough. A recoverable schedule commits a reader only after every transaction whose data it read has committed. A cascadeless schedule is stronger: transactions read only committed data, so one abort cannot trigger a chain of aborts.
Suppose T1 writes X, T2 reads that uncommitted X and commits, then T1 aborts. T2 has committed using a value that never officially existed, so the schedule is non-recoverable. Making T2 delay its commit until T1 commits makes it recoverable. Making T2 wait before reading X makes it cascadeless, which strict 2PL provides by retaining T1's exclusive lock.
Common concurrency-control traps
Treating Read-Read as a conflict: it never conflicts. Check that at least one operation is a write before drawing an edge.
Equating conflict and view serializability: every conflict-serializable schedule is view serializable, but the reverse need not hold. Blind writes create the important exception. Test conflict serializability first unless view serializability is asked explicitly.
Assuming 2PL prevents deadlock: 2PL guarantees conflict serializability, not deadlock freedom.
Reversing wait-die and wound-wait: start from “older is favoured,” then derive whether the younger transaction waits or aborts.
Ignoring recoverability: a schedule can be conflict serializable and still be non-recoverable.
For any schedule question, follow the same sequence: list conflicts, build the graph, check for a cycle, then check recoverability separately. Follow it with DBMS Transaction MCQs: 12 Solved (ACID, Locking) to practise ACID, serializability and 2PL together.
How GATE and interviews test concurrency control, and the short version
GATE questions commonly present an interleaved schedule and ask whether it is conflict serializable, how many serial orders are conflict-equivalent, or which locking or timestamp rule applies. The official GATE CS syllabus published by IIT Guwahati lists “Transactions and concurrency control” under Databases. Confirm the scope against the current cycle's official brochure. Interviews usually ask for a concrete lost update or why strict 2PL is safer than basic 2PL.
Keep the chain straight:
Anomalies are the disease.
Serializability is the correctness test, and the precedence graph is the tool.
2PL, strict 2PL and timestamps enforce safe ordering at run time.
Recoverability is the separate final box to tick.
For structured GATE CS coverage, GATE Guidance by Sanchit Sir places concurrency control inside the wider DBMS sequence. If you are building the interview base from scratch, use CS Fundamentals for Placements by Sanchit Sir.
