Question 8 of 8

Question 8 (6+6+8=20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Part (a) — schedule w1(x) r2(x) w2(x) commit2 commit1.

Approach. Build the conflict-precedence graph (edge T_i→T_j whenever T_i's operation precedes a conflicting operation of T_j on the same item) and check for cycles; separately compare the COMMIT order to the graph's implied serial order.

1. (i) Serializability. Two conflicting pairs touch x: w₁(x)–r₂(x) (write-read) and w₁(x)–w₂(x) (write-write), both with T1's operation first — both give the same edge T1→T2. The precedence graph is a single edge, T1→T2, which is trivially acyclic. Yes, the schedule is conflict-serializable, equivalent to the serial order T1 then T2.
2. (ii) Commit order. The schedule's actual commit order is commit₂ THEN commit₁ — the reverse of the T1-then-T2 order the precedence graph requires. Worse, T2's read of x (r₂(x)) reads a value T1 wrote WHILE T1 was still uncommitted (T1 does not commit until after T2 already has), and T2 then commits before T1 does. No, the schedule is not in commit order. This is exactly the textbook illustration of why non-strict 2PL guarantees conflict-serializability but NOT recoverability: if T1 were to abort after commit₂, T2's already-committed result (based on T1's since-undone write) could never be undone — a violation of the recoverability requirement that a transaction may only commit after every transaction whose writes it read has itself committed.

Part (b) — a READ COMMITTED lost update. READ COMMITTED prevents dirty reads (reading another transaction's uncommitted write) but does nothing to stop two transactions from reading the SAME committed value and then overwriting each other's update. Example, starting from x=100 (a bank balance): T1 reads x (100); T2 reads x (100), computes 100−10=90, writes x=90, and COMMITS; T1 — still holding its OWN earlier read of 100, since READ COMMITTED does not require it to re-read — computes 100−20=80, writes x=80, and commits. Final x=80. The correct sequential result of applying both withdrawals to x=100 is 100−10−20=70; T2's −10 update was silently lost because T1's write overwrote it using a stale value that never reflected T2's change. READ COMMITTED does not prevent this because it only guards against reading data that was never committed — it says nothing about a transaction blindly overwriting a value it read earlier in its OWN lifetime, after someone else has since changed and committed a newer value.

Part (c) — schedule r1(x) r1(y) w1(x) r2(y) r2(x) w1(y) commit2 commit1 at REPEATABLE READ.

Approach. REPEATABLE READ is implemented by strict two-phase locking with SHARED locks held to commit (not just released after the read, as READ COMMITTED would do) — simulate the operations in order against an S/X lock-compatibility table and watch for blocking.

1. Trace the lock requests in order. r₁(x): T1 gets S(x). r₁(y): T1 gets S(y). w₁(x): T1 upgrades to X(x) — no other holder, granted. r₂(y): T2 requests S(y); S is compatible with T1's existing S(y), so this is GRANTED (both hold S(y) simultaneously). r₂(x): T2 requests S(x); T1 holds X(x), and S is NOT compatible with X — T2 blocks, waiting on T1. w₁(y): T1 requests to upgrade to X(y); but T2 ALSO holds S(y) at this point, and X is not compatible with an S-lock held by another transaction — T1 blocks, waiting on T2.
2. Detect the cycle. T2 is waiting for T1 (to release X(x)), and T1 is waiting for T2 (to release S(y)) — a cycle in the wait-for graph, i.e. a deadlock. Neither transaction can proceed to its later operations (T1 never gets to issue w₁(y) successfully, T2 never gets to issue r₂(x)); the commit₂/commit₁ at the end of the printed schedule can never actually be reached as written.
3. Resolution. The DBMS's deadlock detector (periodic wait-for-graph cycle check, or a timeout) picks a victim — typically the transaction that has done less work or has lower priority, e.g. T2, since it is younger — and aborts it, releasing its locks; T1's blocked X(y) request then succeeds, T1 completes and commits, and T2 restarts from scratch.

All three parts;T2 edge in (a), and a small S/X lock simulator replays (c)'s operation sequence and confirms the T1↔T2 wait-for cycle.