The previous chapter introduced two-phase locking with a passing claim that any schedule following the protocol is guaranteed to be "conflict serializable," a term that was used but never precisely defined. This chapter fills in that gap. Serializability is the formal, mathematically precise concept that database theory uses to answer a deceptively simple question: given some concurrent schedule of interleaved transactions, was the outcome actually correct?
The word "correct" needs a concrete definition here, since concurrent schedules can produce results that look plausible on the surface while still being subtly wrong. Database theory settles on a very sensible benchmark for correctness: a concurrent schedule is considered correct if it produces exactly the same result as some serial schedule, meaning some way of running the same transactions strictly one after another, with no overlapping at all. Since serial schedules never suffer from any concurrency problems, any concurrent schedule that behaves identically to some serial schedule inherits that same guarantee of correctness.
In this tutorial, you will learn the two main forms of serializability studied in DBMS, conflict serializability and view serializability, how to test whether a given schedule is conflict serializable using a precedence graph, and a complete worked example showing this test applied step by step to a concrete schedule.
A schedule is called serializable if it is equivalent, in terms of the final effect it produces on the database, to some serial execution of the same set of transactions. Since a serial schedule runs one transaction fully to completion before starting the next, it is automatically free of every concurrency problem discussed in the previous chapter, such as lost updates or dirty reads. A serializable concurrent schedule, therefore, inherits that same freedom from concurrency problems, even though its operations were actually interleaved during execution.
There are two commonly used, increasingly strict definitions of what "equivalent" means in this context, giving rise to two related but distinct notions: conflict serializability and view serializability.
Before defining conflict serializability, it is necessary to understand exactly what makes two operations "conflict" with each other. Two operations from different transactions are said to conflict if all three of the following conditions hold: they belong to different transactions, they operate on the same data item, and at least one of them is a write operation.
| Operation Pair | Conflict? | Reason |
|---|---|---|
| Read(A) by T1, Read(A) by T2 | No | Both operations are reads; reading the same data simultaneously causes no interference. |
| Read(A) by T1, Write(A) by T2 | Yes | Different transactions, same data item, and at least one is a write. |
| Write(A) by T1, Write(A) by T2 | Yes | Different transactions, same data item, both are writes. |
| Write(A) by T1, Write(B) by T2 | No | The operations act on different data items entirely, so their relative order has no effect on either item. |
Swapping the order of two conflicting operations can change the final outcome of the database, while swapping the order of two non-conflicting operations never changes anything, since they either both just read the same value, or they touch completely unrelated data.
A schedule is conflict serializable if it can be transformed into some serial schedule by repeatedly swapping adjacent, non-conflicting operations, without ever swapping two conflicting operations. If such a sequence of swaps successfully turns the schedule into a serial one, the original schedule is guaranteed to produce the exact same final result as that serial schedule, making it correct.
Original Schedule S: T1: Read(A) T2: Read(A) T1: Write(A) T2: Write(A) Step 1: Identify conflicting pairs. T1: Read(A) and T2: Write(A) conflict. T2: Read(A) and T1: Write(A) conflict. T1: Write(A) and T2: Write(A) conflict. Attempting to reorder into a serial schedule (T1 fully before T2, or T2 fully before T1) would require swapping T2's Read(A) past T1's Write(A), which is a conflicting pair, so this particular swap is not allowed. Conclusion: This schedule is NOT conflict serializable, since no valid sequence of non-conflicting swaps can rearrange it into a serial order.
This exact schedule corresponds to the lost update problem introduced two chapters ago, and this result confirms mathematically what was already suspected intuitively: this particular interleaving does not correspond to any correct serial execution, which is precisely why it produces an incorrect result.
Manually attempting every possible sequence of swaps becomes impractical for anything beyond the smallest schedules, so a much more systematic tool is used in practice: the precedence graph, also called a serialization graph. This graph provides a reliable, mechanical test for conflict serializability without needing to try out any swaps at all.
1. Create one node for every transaction in the schedule. 2. For every pair of conflicting operations, where an operation from Ti occurs before a conflicting operation from Tj in the schedule, draw a directed edge from Ti to Tj. 3. Once every conflicting pair has been considered, examine the resulting graph. Rule: A schedule is conflict serializable if and only if its precedence graph contains no cycles. If the graph is acyclic, any topological ordering of its nodes gives a valid equivalent serial schedule.
Schedule S: T1: Read(A) T2: Write(A) T2: Read(B) T1: Write(B) T3: Read(A) T3: Write(A)
Identify every conflicting pair, in the order they occur in the schedule, and note the direction of each resulting edge.
Conflict 1: T1: Read(A) occurs before T2: Write(A) → edge T1 → T2 Conflict 2: T2: Write(A) occurs before T3: Read(A) → edge T2 → T3 Conflict 3: T2: Write(A) occurs before T3: Write(A) → edge T2 → T3 (already exists) Conflict 4: T2: Read(B) occurs before T1: Write(B) → edge T2 → T1 Conflict 5: T1: Read(A) occurs before T3: Read(A) → no edge (both reads, not a conflict) Conflict 6: T1: Read(A) occurs before T3: Write(A) → edge T1 → T3
Edges: T1 → T2, T2 → T3, T2 → T1, T1 → T3 Notice both T1 → T2 and T2 → T1 exist, forming a direct cycle between T1 and T2.
T1 ⇄ T2 → T3
Since this graph contains a cycle, specifically between T1 and T2, the schedule is not conflict serializable. This cycle makes intuitive sense: T1's Read(A) must logically happen before T2's Write(A), suggesting T1 should come before T2 in an equivalent serial order, yet T2's Read(B) must also happen before T1's Write(B), suggesting T2 should come before T1. These two requirements directly contradict each other, which is exactly what a cycle in the precedence graph reveals.
Schedule S': T1: Read(A) T1: Write(A) T2: Read(A) T2: Write(A) T3: Read(A) T3: Write(A)
Conflicts identified: T1: Write(A) before T2: Read(A) → edge T1 → T2 T2: Write(A) before T3: Read(A) → edge T2 → T3 Resulting graph: T1 → T2 → T3 No cycle exists in this graph.
Since this graph is acyclic, the schedule is conflict serializable, and the topological ordering of the graph directly reveals the equivalent serial schedule: T1, followed by T2, followed by T3, exactly matching the natural intuition of this particular schedule, since each transaction's operations happen to already be grouped together in this specific example.
View serializability offers a slightly more relaxed definition of equivalence between schedules, based on three specific conditions rather than the strict operation-by-operation conflict rule used above. Two schedules are considered view equivalent if all three of the following hold: every transaction reads the same initial values in both schedules, every transaction reads values written by the same other transaction in both schedules, and the final write to every data item is performed by the same transaction in both schedules.
Every conflict serializable schedule is automatically view serializable as well, but the reverse is not always true. Some schedules are view serializable without being conflict serializable, typically involving what are called blind writes, meaning a transaction writes a data item without ever having read it first.
Schedule S'': T1: Write(A) T2: Write(A) T3: Write(A)
This schedule involves three blind writes to the same data item, with no reads at all. Testing conflict serializability here would find write-write conflicts between every pair, forming edges that may create ambiguity depending on interpretation, yet the view equivalence conditions can sometimes still be satisfied by a different serial ordering than the conflict-based analysis would suggest, since only the very last write to A actually matters for the final database state. This subtlety is exactly why view serializability, though more difficult to test in general, captures a genuinely broader notion of correctness than conflict serializability alone.
| Aspect | Conflict Serializability | View Serializability |
|---|---|---|
| Definition Basis | Based on reordering non-conflicting operations without changing relative conflicting order. | Based on matching initial reads, source of reads, and final writes between schedules. |
| Testing Method | Precedence graph; check for cycles, a straightforward and efficient test. | Generally much harder to test computationally in the general case. |
| Relationship | Every conflict serializable schedule is also view serializable. | Some view serializable schedules are not conflict serializable, typically involving blind writes. |
Serializability provides the formal correctness standard that concurrency control mechanisms, such as the two-phase locking protocol from the previous chapter, are designed to guarantee. Rather than relying on intuition or spot-checking individual schedules by hand, database systems use these formal definitions and tools like the precedence graph to prove, in a mathematically rigorous way, that their scheduling algorithms will never produce an incorrect result, no matter how transactions happen to be interleaved in practice.
| Mistake | Correct Understanding |
|---|---|
| Assuming a serializable schedule must literally look like a serial schedule. | A serializable schedule can have heavily interleaved operations; it only needs to produce the same final result as some serial schedule, not resemble one visually. |
| Drawing precedence graph edges between non-conflicting operations. | Only conflicting operation pairs, different transactions, same data item, at least one write, generate edges in the precedence graph. |
| Believing view serializability is always easier to satisfy than conflict serializability. | View serializability is a broader, more relaxed condition, but it is generally harder to test computationally than conflict serializability in the general case. |
| Forgetting to check for a cycle correctly, missing edges pointing in both directions. | A cycle can be as short as two nodes with edges pointing in both directions between them, exactly as demonstrated in the first worked example in this chapter. |
Serializability provides the formal correctness benchmark that concurrency control techniques aim to guarantee, defining precisely when an interleaved, concurrent schedule can be trusted to produce the same result as some serial execution. Through conflicting operation pairs, the precedence graph method, and worked examples testing schedules for cycles, this chapter demonstrated a systematic, reliable way to verify conflict serializability, along with the more relaxed notion of view serializability that captures a slightly broader class of correct schedules.
In this tutorial, you learned what makes operations conflict, how conflict serializability is defined and tested using the precedence graph method with two fully worked examples, and how view serializability relaxes this definition to capture additional correct schedules involving blind writes. With this foundation, you are ready to move on to deadlock, a situation where transactions can become permanently stuck waiting for each other, a risk that even a properly serializable, lock-based schedule must still guard against.