Project ForgeConsider two transactions T1: R1[x] W1[x] W1[y] and T2: R2[x] R2[y] W2[y], and four schedules S1-S4 of T1 and T2: S1: R1[x] R2[x] R2[y] W1[x] W1[y] W2[y]; S2: R1[x] R2[x] R2[y] W1[x] W2[y] W1[y]; S3: R1[x] W1[x] R2[x] W1[y] R2[y] W2[y]; S4: R2[x] R2[y] R1[x] W1[x] W1[y] W2[y]. Which of the above schedules are conflict-serializable?
- AS1 and S2
- S2 and S3
- CS3 only
- DS4 only
Explanation
Building each schedule's precedence graph: S1 has both T2->T1 (from x and one y conflict) AND T1->T2 (from the W1[y]-before-W2[y] conflict) — a cycle, so NOT serializable. S2 has only T2->T1 edges (W1[y] now comes AFTER W2[y]) — acyclic, serializable as T2,T1. S3 has only T1->T2 edges — acyclic, serializable as T1,T2. S4 again has both directions (T2->T1 from x/y reads, T1->T2 from the W1[y]-before-W2[y] conflict) — a cycle, NOT serializable. So S2 and S3 are conflict-serializable.
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.