Question 8 of 8

Question 8 (5+5+5+5=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.

Given. T1: read(x); read(y); if x=1 then y:=y+2; write(y). T2: read(y); read(x); if y=1 then x:=x+2; write(x). Consistency requirement: x=1 ∨ y=1. Initial values x=y=1.

Find. (a) both serial orders preserve consistency; (b)/(c) the two definitions; (d) whether ANY genuinely concurrent (non-serial) execution of these two specific transactions can still be conflict-serializable.

(a) Every serial execution preserves consistency.

1. Schedule T1;T2. T1 reads x=1, y=1; since x=1, sets y:=1+2=3 and writes it — state becomes x=1, y=3. T2 then reads y=3, x=1; since y≠1, the condition is false, so T2's local copy of x stays at the value it read (1), and it writes x:=1 back unchanged. Final state x=1, y=3 — x=1 holds. $$\boxed{x=1,\ y=3 \Rightarrow \text{consistent}}$$
2. Schedule T2;T1. T2 reads y=1, x=1; since y=1, sets x:=1+2=3 and writes it — state becomes x=3, y=1. T1 then reads x=3, y=1; since x≠1, the condition is false, so T1 writes y:=1 back unchanged. Final state x=3, y=1 — y=1 holds. $$\boxed{x=3,\ y=1 \Rightarrow \text{consistent}}$$

Both serial orders end consistent, exactly as the general theorem guarantees: any serial execution of individually consistency-preserving transactions preserves consistency, since each transaction is run alone against an already-consistent state.

(b) Serializable schedule. A schedule of several transactions is (view-)serializable if its overall effect on the database — the final state, and every value any transaction reads — is identical to the effect of running those same transactions one at a time in SOME serial order. The transactions need not literally run one-after-another; the schedule only has to be indistinguishable in outcome from one that does.

(c) Conflict-serializable schedule. Two operations from different transactions conflict if they access the same data item and at least one of them is a write. A schedule is conflict-serializable if its conflicting operations can be reordered, by repeatedly swapping adjacent NON-conflicting operations, into some serial schedule — equivalently, if its precedence graph (one node per transaction, an edge T_i→T_j whenever an operation of T_i precedes a conflicting operation of T_j) is acyclic. Conflict-serializability is a sufficient, easily testable, but not necessary condition for full (view-)serializability.

(d) Is there a concurrent (non-serial) execution that is conflict-serializable?

1. Identify every cross-transaction conflict. Item x: only read₁(x) and write₂(x) involve different transactions (read₂(x) is T2's own read, no self-conflict) — one conflict pair. Item y: only write₁(y) and read₂(y) cross transactions — the other conflict pair. Exactly two cross-transaction conflicts exist in the whole schedule.
2. Exhaustively enumerate all interleavings. T1's 3 ops (read₁(x), read₁(y), write₁(y)) and T2's 3 ops (read₂(y), read₂(x), write₂(x)), each internally ordered, admit (⁶₃)=20 distinct interleavings. A short Python enumeration built the precedence-graph verdict AND simulated the resulting (x,y) state for all 20.
3. The structural reason no interleaving works. Being conflict-serializable as T1→T2 requires BOTH read₁(x) before write₂(x) AND write₁(y) before read₂(y). But write₁(y) is T1's LAST operation and read₂(y) is T2's FIRST operation — so "write₁(y) before read₂(y)" forces T1's ENTIRE operation sequence to precede T2's entire sequence, i.e. the full serial order T1;T2. The symmetric argument (swapping the roles of x/y and T1/T2) shows the T2→T1 direction collapses to the full serial order T2;T1 the same way. So the only conflict-serializable schedules for this specific pair of transactions are exactly the two serial ones.

Answer: No. There is no genuinely concurrent (interleaved) execution of these two specific transactions that is conflict-serializable — only running them fully serially qualifies. The exhaustive check additionally confirms that EVERY one of the other 18 interleavings actually violates the stated consistency requirement (x=1 ∨ y=1), not merely fails the conflict-serializability test — for this transaction pair, avoiding an interleaving is not just a serializability nicety but the only way to keep the database consistent at all. This is exactly why a real DBMS concurrency-control protocol (2PL, timestamping, etc.) would, for this transaction pair, refuse to let their operations interleave in the first place.