Conflict serializability: conflicting ops, precedence graph, equivalent serial orders

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. When does a directed graph have a topological order? from Lesson 6.4.1
2. How many schedules do two transactions of 3 operations each have? from Lesson 6.3.1
3. What is a dirty read? from Lesson 6.2.1

1 · The Hook

A non-serial schedule is acceptable if it gives the same effect as some serial schedule. Testing that by running every serial order is hopeless. Instead, look only at pairs of operations whose order matters (conflicts). Draw an arrow for each, and the schedule is serializable exactly when the arrows have no cycle. This is the single most important GATE transaction question.

2 · Predict First

Schedule: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B). It is interleaved, yet every operation of T1 on A comes before T2's on A, and the same for B. Is it equivalent to a serial schedule? Which?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Yes, T1 then T2. Every pair of operations whose order matters puts T1 first. Swapping the non-conflicting middle operations (W2(A) with R1(B) W1(B), which touch different items) turns it into the serial T1;T2.

Conflicting operations

Two operations conflict if all three hold:

1. they belong to different transactions,
2. they access the same data item,
3. at least one is a write.

So R–W, W–R and W–W on the same item conflict; R–R never conflicts. Swapping two adjacent operations that do not conflict cannot change any result.

Conflict equivalence and conflict serializability

• Two schedules are conflict equivalent if one can be turned into the other by swapping adjacent non-conflicting operations; equivalently, they order every conflicting pair the same way.
• A schedule is conflict serializable (CS) if it is conflict equivalent to some serial schedule.

Precedence graph test

1. One vertex per transaction.
2. For every pair of conflicting operations where Ti's operation comes before Tj's, draw Ti → Tj (once).
3. CS ⇔ the graph is acyclic.
4. The equivalent serial orders are exactly the topological orders of the graph.

Example 1 (CS)

S = R2(A) R1(B) W2(A) R3(A) W1(B) W3(A) R2(B) W2(B).

• On A: W2(A) before R3(A) and W3(A) → T2 → T3. R2(A) before W3(A) → T2 → T3.
• On B: R1(B) before W2(B), W1(B) before R2(B) and W2(B) → T1 → T2.

Edges T1 → T2, T2 → T3: acyclic. CS, equivalent to T1, T2, T3 only.

Example 2 (not CS)

S = R1(X) R2(Y) W2(X) R3(Y) W1(Y) W3(X).

• R1(X) before W2(X): T1 → T2. R1(X) before W3(X): T1 → T3. W2(X) before W3(X): T2 → T3.
• R2(Y) before W1(Y): T2 → T1. R3(Y) before W1(Y): T3 → T1.

Cycle T1 → T2 → T1. Not CS.

Counting conflict-equivalent schedules (GATE type)

"How many schedules of T1, T2 are conflict equivalent to the serial T1;T2?" Keep each conflicting pair in T1-first order and count the interleavings left. For T1 = R1(A) W1(A) R1(B) W1(B) and T2 = R2(A) W2(A) R2(B) W2(B): T2's A-operations must follow W1(A), T2's B-operations must follow W1(B), so only R2(A) W2(A) can interleave with R1(B) W1(B): C(4, 2) = 6 schedules.

4 · Visual

Left: Example 1, acyclic → serial order T1, T2, T3. Right: Example 2, cycles (T1 ⇄ T2, T1 ⇄ T3) → not conflict serializable.

5 · Worked Examples

Example 1 Easy

Do these conflict: (a) R1(A), R2(A); (b) R1(A), W2(B); (c) W1(A), R1(A); (d) R1(A), W2(A)?

Solution

Only (d). (a) both reads; (b) different items; (c) same transaction.

Example 2 Medium

Is R1(A) R2(A) W1(A) W2(A) conflict serializable?

Solution

R1(A) before W2(A): T1 → T2. R2(A) before W1(A): T2 → T1. Cycle: not CS (this is the lost-update pattern).

Example 3 GATE

S = R1(A) R2(B) R3(C) W1(B) W2(C) W3(A). Conflict serializable?

Solution

R2(B) before W1(B): T2 → T1. R3(C) before W2(C): T3 → T2. R1(A) before W3(A): T1 → T3. Cycle T1 → T3 → T2 → T1: not CS.

8 · Connect the Dots

Lesson 6.4.1 gave graphs; this lesson built the precedence graph and the CS test. Some correct schedules still fail it. Next: the weaker, more permissive view serializability, and the blind writes that create the gap.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Conflicts

Which pair of operations conflicts?

1. (A) R1(X), R2(X)
2. (B) R1(X), W1(X)
3. (C) W1(X), W2(Y)
4. (D) R1(X), W2(X)

Q2 · MCQ · 2 mark(s) — Precedence graph

S = R1(A) W2(A) R2(B) W1(B). The precedence graph has:

1. (A) T1 → T2 only
2. (B) T2 → T1 only
3. (C) T1 → T2 and T2 → T1
4. (D) no edges

Q3 · MCQ · 2 mark(s) — CS

S = R2(A) R1(B) W2(A) R3(A) W1(B) W3(A) R2(B) W2(B) is equivalent to which serial schedule?

1. (A) T3, T2, T1
2. (B) none: not CS
3. (C) T2, T1, T3
4. (D) T1, T2, T3

Q4 · NAT · 2 mark(s) — Counting

T1 = R1(A) W1(A) and T2 = R2(B) W2(B) (different items). How many schedules are conflict equivalent to the serial schedule T1;T2?

Numerical answer: ________

Q5 · MSQ · 2 mark(s) — Not CS

Which schedules are not conflict serializable?

1. (A) R1(A) R2(A) W1(A) W2(A)
2. (B) R1(A) W1(A) R2(A) W2(A)
3. (C) R1(X) R2(X) W1(Y) W2(Y) R1(Y) R2(Y)
4. (D) R1(A) R2(B) W1(A) W2(B)

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

conflicting operationsconflict equivalenceconflict serializability (CS)precedence (serialization) graphequivalent serial order