DBMS Topics
Serializability
Last Updated : 21 May, 2026
A concurrent schedule is serializable if its outcome effect on the database is equivalent to the outcome of some serial schedule of the same transactions.
Definition
A concurrent schedule is serializable if its outcome (effect on the database) is equivalent to the outcome of some serial schedule of the same transactions.
Serializability is the standard correctness criterion for concurrent schedules.
Types of Serializability
Conflict Serializability — Deep Dive
Conflict Operations Recap
Two operations conflict if all three conditions hold:
- They belong to different transactions
- They access the same data item
- At least one is a write
| r_j(X) | w_j(X) | |
|---|---|---|
| r_i(X) | No conf | CONFLICT |
| w_i(X) | CONFLICT | CONFLICT |
Precedence Graph Construction
| Draw directed edge Ti | Tj |
| Test: If the graph has NO CYCLE | Conflict Serializable ✓ |
| If the graph has A CYCLE | NOT Conflict Serializable ✗ |
Worked Examples
Example 1 — Conflict Serializable
Schedule S1
T1: r(X) w(X)
T2: r(X) w(X)
Time: 1 2 3 4
Operations in order
1. T1: r(X)
2. T2: r(X)
3. T2: w(X)
4. T1: w(X)
Find conflicts (different transactions, same item, at least one write):
Op 3 (T2:w(X)) and Op 4 (T1:w(X)) → T2 comes first → T2 → T1
Op 1 (T1:r(X)) and Op 3 (T2:w(X)) → T1 comes first → T1 → T2
Precedence Graph
T1 ──► T2
T2 ──► T1
CYCLE EXISTS → NOT conflict serializable ✗
Example 2 — Conflict Serializable
Schedule S2
T1: r(X) r(Y) w(X) w(Y)
T2: r(X) w(X)
Operations in order
1. T1: r(X)
2. T2: r(X)
3. T1: r(Y)
4. T2: w(X)
5. T1: w(X)
6. T1: w(Y)
Conflicts
T2:w(X)[4] vs T1:w(X)[5] → T2 before T1 → T2 → T1
T1:r(X)[1] vs T2:w(X)[4] → T1 before T2 → T1 → T2
Precedence Graph
T1 → T2 and T2 → T1 → CYCLE → NOT serializable ✗
Example 3 — Serializable
| T1 | r(A) w(A) |
| T2 | r(A) w(A) r(B) w(B) |
| T3 | r(B) w(B) |
| Precedence Graph: T1 | T2 → T3 (no cycle) ✓ |
| Equivalent serial order | T1, T2, T3 |
View Serializability
View serializability is a weaker condition than conflict serializability. It allows more schedules to be considered correct.
View Equivalence Conditions
Schedules S and S' are view equivalent if for each data item X:
- Initial reads: If Ti reads the initial value of X in S → Ti reads the initial value of X in S'
- Updated reads: If Ti reads a value written by Tj in S → Ti reads the value written by Tj in S'
- Final writes: The same transaction performs the final write on X in both S and S'
Example — View Serializable but NOT Conflict Serializable
Schedule S
T1: w(X)
T2: w(X)
T3: w(X) (final write)
Conflict analysis
T1:w(X) → T2:w(X) → T1 → T2
T2:w(X) → T3:w(X) → T2 → T3
T1:w(X) → T3:w(X) → T1 → T3
Graph: T1→T2→T3 (no cycle) → IS conflict serializable ✓
Another Schedule S'
T1: w(X)
T3: w(X) (final write by T3)
T2: w(X) ← blind write (T2's result overwritten by nobody)
If final write semantics match some serial schedule → view serializable
Testing Serializability — Summary
Conflict Serializability
┌─────────────────────────────────────────────┐
│ 1. List all conflicting operation pairs │
│ 2. Build precedence graph │
│ 3. Check for cycles │
│ No cycle → SERIALIZABLE ✓ │
│ Cycle → NOT SERIALIZABLE ✗ │
└─────────────────────────────────────────────┘
View Serializability
NP-complete to test in general.
Usually tested on specific schedules only.
Equivalent Serial Order
If a schedule is conflict serializable, the topological sort of its precedence graph gives the equivalent serial order:
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Serializability.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this DBMS topic.
Search Terms
dbms, database management system, database notes, sql, unit, serializability
Related DBMS Topics