Page 5: Serializability - Testing Schedule Correctness

Conflict Serializability

What Causes Conflicts?

Two operations conflict if:

1. They belong to different transactions

2. They access the same data item

3. At least one is a write operation

Conflict Cases:

• read(A), read(A): No conflict (both just read)

• read(A), write(A): Conflict! (order matters)

• write(A), read(A): Conflict! (order matters)

• write(A), write(A): Conflict! (final value depends on order)

Testing with Precedence Graph

Step 1: Draw the Graph

• Each transaction = vertex

• Add edge Ti → Tj if Ti's operation must come before Tj's operation

Step 2: Check for Cycles

• No cycle: Schedule is conflict serializable ✓

• Has cycle: Schedule is NOT conflict serializable ✗

Example: Good Schedule

CopyT₁: read(A), write(A), read(B), write(B)
T₂:                   read(A), write(A), read(B), write(B)

Edge: T₁ → T₂ (T₁ writes A before T₂ reads A) Graph: T₁ → T₂ (no cycle) ✓

Example: Bad Schedule

CopyT₁: read(A), write(A)           read(B), write(B)
T₂:           read(A), write(A), read(B)

Edges: T₁ → T₂ (A access) AND T₂ → T₁ (B access) Graph: T₁ ⟷ T₂ (cycle detected) ✗

View Serializability (Weaker Condition)

Two schedules are view equivalent if:

1. Same initial reads

2. Same intermediate reads (who reads what from whom)

3. Same final writes

Some schedules are view serializable but not conflict serializable.