Serializability

A schedule of concurrent transactions is serializable if its outcome is identical to some serial execution of those same transactions.

Serial vs Concurrent Schedules

• Serial Schedule → transactions run ONE AFTER ANOTHER, no overlap. Always consistent but slow.
• Concurrent Schedule → transactions INTERLEAVE. Fast but may be inconsistent.
• Serializable Schedule → concurrent but outcome equals some serial execution. Best of both worlds.

Two Types of Serializability

1. Conflict Serializability

Two operations conflict if they belong to different transactions, access the same data item, and at least one is a WRITE.

Operation Pair	Conflict?
Read — Read	No conflict (both just reading)
Read — Write	Conflict
Write — Read	Conflict
Write — Write	Conflict

2. View Serializability

Broader than conflict serializability. Every conflict serializable schedule is view serializable, but not vice versa. Harder to check → rarely used in practice.

Conflict Serializable ⊂ View Serializable ⊂ All Schedules

How to Check — Precedence Graph

• Draw a node for each transaction
• Draw edge T1 → T2 if T1 does an operation that conflicts with T2 AND T1's operation comes FIRST
• If graph has NO cycle → Conflict Serializable ✅
• If graph HAS a cycle → NOT Serializable ❌

Precedence Graph Example

Schedule:

T1: Read(A)
T2: Write(A) -- conflicts with T1 Read(A), T2 after T1 → T1→T2
T1: Write(B)
T2: Read(B)  -- conflicts with T1 Write(B), T1 before T2 → T1→T2

Edges: T1 → T2, T1 → T2. No cycle → Conflict Serializable ✅ (equivalent to T1 then T2)

Non-serializable example:

T1: Read(A)
T2: Write(A) -- T2 after T1 → edge T1→T2
T2: Read(B)
T1: Write(B) -- T1 after T2 → edge T2→T1

Cycle detected: T1→T2→T1 → NOT serializable ❌

Serial vs Serializable — Key Distinction

• Serial → IS a specific way of executing transactions (absolutely no interleaving)
• Serializable → IS a property of a schedule (outcome matches some serial execution)
• Every Serial schedule is Serializable ✅
• NOT every Serializable schedule is Serial ❌