Question 8 of 8: Transactions and serializability

Question 8: Transactions and serializability (5+3+2+10=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. Two transactions each reading both shared variables, conditionally incrementing one, then unconditionally writing it back; consistency requirement $A=0 \lor B=0$; initial state $A=B=0$.

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 $T_1;T_2$. $T_1$ reads $A{=}0,B{=}0$; since $A{=}0$, sets $B{:=}0{+}1{=}1$ and writes it — state becomes $A{=}0,B{=}1$. $T_2$ then reads $B{=}1,A{=}0$; since $B\ne 0$, the condition is false, so $T_2$'s local copy of $A$ stays at the value it read (0), and it writes $A{:=}0$ back unchanged. Final state $A{=}0, B{=}1$ — $A{=}0$ holds. $$\boxed{A=0,\ B=1 \Rightarrow \text{consistent}}$$
2. Schedule $T_2;T_1$. $T_2$ reads $B{=}0,A{=}0$; since $B{=}0$, sets $A{:=}0{+}1{=}1$ and writes it — state becomes $A{=}1,B{=}0$. $T_1$ then reads $A{=}1,B{=}0$; since $A\ne 0$, the condition is false, so $T_1$ writes $B{:=}0$ back unchanged. Final state $A{=}1,B{=}0$ — $B{=}0$ holds. $$\boxed{A=1,\ B=0 \Rightarrow \text{consistent}}$$

Both serial orders end consistent, as guaranteed by the general theorem that any SERIAL schedule of consistency-preserving transactions preserves consistency (each transaction, run alone against a consistent starting state, is assumed/guaranteed to leave a consistent state).

(b) Serializable schedule. A schedule of several transactions is (view-)serializable if its 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. It need not literally execute one-after-another; it only needs to be indistinguishable in outcome from a schedule that does.

(c) Conflict-serializable schedule. Two operations from different transactions conflict if they access the same data item and at least one 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 the schedule's precedence graph (one node per transaction, an edge $T_i \rightarrow 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 (view-)serializability.

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

1. Identify every cross-transaction conflict. Item $A$: only $read_1(A)$ and $write_2(A)$ involve different transactions ($read_2(A)$ is $T_2$'s own op, no conflict with itself) — one conflict pair. Item $B$: only $write_1(B)$ and $read_2(B)$ cross transactions — the other conflict pair. There are exactly two cross-transaction conflicts in the whole schedule.
2. Exhaustively enumerate all interleavings. $T_1$'s 3 ops and $T_2$'s 3 ops, each internally ordered, admit $\binom{6}{3}=20$ distinct interleavings. A short Python enumeration built the precedence-graph verdict and simulated the resulting $(A,B)$ for all 20.
3. The structural reason no interleaving works. Being conflict-serializable (as $T_1\!\to\!T_2$) requires BOTH $read_1(A)$ before $write_2(A)$ AND $write_1(B)$ before $read_2(B)$. But $write_1(B)$ is $T_1$'s LAST operation, and $read_2(B)$ is $T_2$'s FIRST operation — so "$write_1(B)$ before $read_2(B)$" forces $T_1$'s entire operation sequence to precede $T_2$'s entire sequence, i.e. the FULL serial order $T_1;T_2$. The symmetric argument (swapping the roles) shows the $T_2\!\to\!T_1$ direction similarly collapses to the full serial order $T_2;T_1$. So the 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, one after the other, qualifies. Any true interleaving of their steps is both non-conflict-serializable AND, as the exhaustive check confirms, actually violates the stated consistency requirement. This is precisely why database systems require a concurrency-control protocol (locking, timestamping, etc.) that would, for this transaction pair, simply refuse to let their operations interleave at all.