Serializability
Serializability is the property of a concurrent schedule producing exactly the same result as some serial execution of the same transactions. It is checked through conflict serializability, which reorders non-conflicting operations into a serial schedule, or view serializability, a broader check; every conflict serializable schedule is also view serializable, but not the reverse.
Serializability is the formal property that determines whether a concurrent (interleaved) schedule is actually safe: it's safe if the result it produces is identical to what some serial execution of those same transactions would have produced. It's the theoretical foundation behind why database concurrency control mechanisms are designed the way they are.
Two practical ways to check serializability
- Conflict serializability: two operations "conflict" if they're from different transactions, access the same data item, and at least one of them is a write. A schedule is conflict serializable if you can reorder its non-conflicting operations (swap adjacent operations that don't conflict) until it becomes a serial schedule.
- View serializability: a broader, more permissive check based on whether transactions read the same initial values, produce the same intermediate reads, and leave the same final write as some serial schedule. Every conflict serializable schedule is also view serializable, but not the other way around, view serializability is harder to check efficiently in practice, which is why real databases rely on conflict serializability instead.
A worked example: checking conflict serializability
Schedule S1: T1: R(A), T1: W(A), T2: R(A), T2: W(A), T1: R(B), T1: W(B)
The standard test is a precedence graph: one node per transaction, and an edge Ti -> Tj for every pair of conflicting operations where Ti's operation comes first. The schedule is conflict serializable if and only if this graph has no cycle.
In S1, the only conflicts are on A: T1's write of A comes before T2's read and T2's write of A, so there is an edge T1 -> T2 and nothing pointing back. T2 never touches B, so T1's operations on B conflict with nothing. The graph has no cycle, so S1 is conflict serializable: it is equivalent to running T1 completely, then T2.
Schedule S2: T1: R(A), T2: R(A), T1: W(A), T2: W(A)
In S2, T2's read of A comes before T1's write of A (edge T2 -> T1), and T1's write of A comes before T2's write of A (edge T1 -> T2). That is a cycle, so S2 is NOT conflict serializable. It is a lost update: T2 overwrites T1's write using a value it read before T1 wrote, and neither serial order gives that result.
The earlier lost-update example, T1: R(A), T2: R(A), T2: W(A), T1: W(A), fails the same way: T1 read A before T2 wrote it (T1 -> T2) and T2 wrote A before T1 did (T2 -> T1), another cycle.
Where this matters in real systems
Real databases don't run an explicit serializability check on every schedule as it happens, that would be too slow. Instead, they use concurrency control protocols (like two-phase locking) that are mathematically proven to only ever produce conflict-serializable schedules by construction, guaranteeing safety without needing to verify it after the fact for every single transaction.
What interviewers actually ask about serializability
- "What does it mean for a schedule to be serializable?" It produces the exact same result as some serial execution of the same transactions, even though it was actually interleaved.
- "What's the difference between conflict serializability and view serializability?" Conflict serializability is based on reordering non-conflicting operations into a serial order; view serializability is a broader, more permissive check based on matching reads and final writes, harder to verify efficiently.
- "Which one do real databases actually use?" Conflict serializability, since it's efficiently checkable and concurrency control protocols can be designed to guarantee it by construction.
- "How do you check if two operations conflict?" They're from different transactions, access the same data item, and at least one of them is a write.
Key takeaways
- Serializability means a concurrent schedule's result matches what some serial execution would have produced.
- Conflict serializability checks whether non-conflicting operations can be reordered into a serial schedule.
- View serializability is broader but harder to check efficiently, so real databases rely on conflict serializability instead.
- Real concurrency control protocols are designed to guarantee conflict serializability by construction, not by checking after the fact.
More in Transaction Processing
Browse all DBMS topics
Log in to save which topics you've read across every subject.
Frequently asked questions
What does it mean for a schedule to be serializable?
It produces the exact same result as some serial execution of the same transactions, even though it was actually interleaved.
What's the difference between conflict serializability and view serializability?
Conflict serializability is based on reordering non-conflicting operations into a serial order; view serializability is a broader, more permissive check based on matching reads and final writes, harder to verify efficiently.
Which one do real databases actually use?
Conflict serializability, since it's efficiently checkable and concurrency control protocols can be designed to guarantee it by construction.
How do you check if two operations conflict?
They're from different transactions, access the same data item, and at least one of them is a write.