A History That Passes the Precedence Test but Fails the Rollback Test
An online reservation service runs three transactions over data items A and B. Timestamps are T1 = 10, T2 = 20, T3 = 30, with lower meaning older. The scheduler's log shows exactly this history: r1(A) w1(A) r2(A) w2(B) c2 r3(B) w3(B) c3 a1. The documented concurrency policy is strict two-phase locking: an item is locked when first accessed, and all locks are held until commit or abort. The service has no budget for cascading rollback - the operations team requires that any abort stay confined to one transaction, because a committed reservation cannot be silently undone. A junior engineer wants to accept the history, pointing out that the precedence graph contains no cycle. The DBA wants the trace declared invalid and the lock manager audited. Separately, for a new deployment the team is considering a wait-die deadlock-resolution scheme keyed on the same timestamps.
1. Build the precedence (conflict) graph for the history and determine whether it is conflict-serializable. If it is, list every equivalent serial order.
Read the worked answer
Compute conflicts from operations on the same item by different transactions, where at least one is a write, and order them by their position in the history.
- w1(A) precedes r2(A): T1 → T2 (write-read on A)
- w2(B) precedes r3(B): T2 → T3 (write-read on B)
- w2(B) precedes w3(B): T2 → T3 (write-write on B)
- T1 touches only A and T3 touches only B: no edge
Graph: T1 → T2 → T3, acyclic. So the history is conflict-serializable, and the only serial order consistent with the edge set is T1, T2, T3 - a single serial order, since the chain is total. The junior engineer's graph claim is correct as far as it goes.
That is also why the case is a trap: conflict-serializability asks only whether the interleaving is equivalent to some serial execution, assuming every transaction eventually commits. It says nothing about what happens when one of them aborts, and here T1 aborts.
2. Is the history recoverable or cascadeless? Trace what the system must do at a1, and show what strict two-phase locking would have done at r2(A).
Read the worked answer
No on both counts.
Recoverability. r2(A) reads a value written by T1, which has not committed. T2 then commits at c2, and T1 aborts later at a1. A history is recoverable only if every transaction that reads uncommitted data commits after the writer; here c2 precedes a1, so the history is non-recoverable. Physically, the reservation derived from T1's uncommitted write of A is already visible to customers and cannot be rolled back, and T2's commit is invalid because the serial order T1, T2, T3 it relies on never happened.
Cascadelessness. T2 read dirty data, so the history is also not cascadeless; recovering consistency would force T2 (and, if T3 had read from T2, T3) to roll back - the cascading rollback the operations team forbids.
Strict 2PL check. w1(A) requires an exclusive lock on A held by T1 until T1 terminates. r2(A) therefore needs a shared lock on A while T1 still holds X(A). Under strict 2PL the lock manager would block T2 at that point; the write w2(B) and the read r3(B) would then also be delayed until c1, making T3 unable to read B before T2 commits. Since the recorded trace shows r2(A) before a1, no correct strict-2PL lock manager could have produced it. Either locking was bypassed or X(A) was released early. Consequence: conflict-serializability alone is not a sufficient acceptance test; strict 2PL would have delivered both serializability and recoverability, which is why the DBA rejects the trace and audits the lock manager.
3. Under wait-die with the given timestamps, what happens when T3 requests a shared lock on B while T2 holds it exclusively? Contrast with the reverse request and explain why the scheme cannot deadlock.
Read the worked answer
Wait-die compares timestamps only when a request conflicts: the older requester waits, the younger requester dies (aborts immediately and restarts with its original timestamp).
- T3 (ts 30) requests S(B) while T2 (ts 20) holds X(B). T3 is younger than the holder, so T3 is aborted and restarted, still with ts 30, so it stays young and cannot starve into priority inversion.
- Reverse case: T2 (20) requests a lock held by T3 (30). The requester is older, so T2 waits until T3 releases.
No deadlock is possible because a wait edge always points from an older transaction to a younger one, so the wait-for graph is acyclic by construction - timestamps strictly decrease along every wait edge and cannot cycle. The price is wasted work: the younger transaction is repeatedly killed rather than allowed to wait. Under the alternative wound-wait rule the roles invert (older preempts by aborting the younger holder, younger waits), which is preferable when old transactions are short and restart cost is high.