How to use the Conflict Serializability and 2PL Schedule Checker
- 1. Type the scheduleOperations in time order: R1(A), W2(B), C1 for commit, A1 for abort.
- 2. Check the graphSee every conflicting pair, the precedence graph, any cycle and the equivalent serial orders.
- 3. Read the summarySee view serializability, recoverable, cascadeless and strict, and whether basic or strict 2PL could produce it.
Precedence graph test
Two operations conflict when they belong to different transactions, use the same item and at least one is a write (R-W, W-R or W-W). For each conflicting pair where an operation of Ti comes before one of Tj, draw an edge Ti → Tj.
A schedule is conflict serializable if and only if this graph has no cycle. A topological order of the graph gives an equivalent serial schedule. Every conflict-serializable schedule is also view serializable. A view-serializable schedule that is not conflict serializable always has a blind write.
Worked example (Korth style)
Schedule: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B). Every conflict on A and on B has T1 first, so the only edge is T1 → T2. No cycle: the schedule is conflict serializable and equivalent to T1, T2.
Now take R1(A) R2(A) W1(A) W2(A). R2(A) before W1(A) gives T2 → T1, and R1(A) before W2(A) gives T1 → T2: a cycle, so it is not conflict serializable.
R1(A) W2(A) W1(A) W3(A) has a cycle between T1 and T2, but it is view equivalent to T1, T2, T3 because W3(A) blindly overwrites A at the end.
Two-phase locking
Under 2PL a transaction gets all its locks before it releases any. The tool searches for a lock point for each transaction and prints one valid lock schedule. The default schedule works because T1 can lock B before it unlocks A. R1(x) W2(x) W3(y) W1(y) is conflict serializable (T3, T1, T2) but no 2PL placement exists: T1 must unlock x before W2(x), yet it needs y later.
Frequently asked questions
What is the difference between cascadeless and strict?
Cascadeless means no transaction reads data written by an uncommitted transaction. Strict also forbids overwriting it until that transaction commits or aborts.
Why are aborted transactions left out?
An aborted transaction's effects are undone, so serializability is judged on the committed part. Recoverability still looks at the whole schedule.
Is every conflict-serializable schedule possible under 2PL?
No. 2PL schedules are always conflict serializable, but some conflict-serializable schedules cannot be produced by 2PL.
What notation can I use?
R1(A) or r1(A), W2(B), C1, A1, and also T1:R(A). Square brackets like r1[x] work too.