In the previous chapter, Schedules & Serializability, we learned that a concurrent schedule is acceptable if it is equivalent to some serial schedule. We also saw that comparing final values ("result equivalence") is unreliable, because results can match by coincidence.
So how does a DBMS actually decide whether a schedule is serializable, without looking at data values? It looks only at the order of reads and writes. There are two standard ways to do this:
Conflict serializability → based on the order of conflicting operations. Simple and fast to test with a precedence graph.
View serializability → based on who reads what from whom and who writes last. More permissive, but much harder to test.
This chapter explains both, with step-by-step tests and worked examples. These tests are among the most frequently asked topics in GATE and university exams.
Conflicting Operations
Two operations conflict if (1) they belong to different transactions, (2) they access the same data item, and (3) at least one of them is a write.
All three conditions must be true. Here are the four possible pairs on the same item X from different transactions:
Pair | Conflict? | Why |
|---|---|---|
| No | Both just read. Either order gives both the same value. |
| Yes (R–W) | If the read comes first, Ti sees the old value; if the write comes first, Ti sees Tj's new value. |
| Yes (W–R) | Same reason: the order decides what Tj reads. |
| Yes (W–W) | The order decides which value remains in the database at the end. |
And operations that never conflict:
Operations on different data items (
W1(A)andW2(B))Operations of the same transaction (their order is fixed anyway)
Two reads
Why conflicts are the key idea
If two adjacent operations in a schedule do not conflict, we can swap them, and nothing changes: every transaction reads the same values, and the database ends in the same state. But if they do conflict, swapping them may change what someone reads or what value survives.
So the order of conflicting operations is what really determines the outcome of a schedule. Everything else can be shuffled freely.
Conflict Equivalence and Conflict Serializability
Two schedules are conflict equivalent if one can be turned into the other by a series of swaps of adjacent non-conflicting operations. Equivalently, they contain the same operations and order every pair of conflicting operations the same way.
A schedule is conflict serializable if it is conflict equivalent to some serial schedule.
Example 1: Proving conflict serializability by swapping
Take the "good" interleaved transfer schedule from the previous chapter:
S: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B)
Our goal is to move T1's B operations up, before T2's A operations. R1(B) does not conflict with W2(A) or R2(A) (different items), so it can move past them:
Start: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B)
swap W2(A),R1(B): R1(A) W1(A) R2(A) R1(B) W2(A) W1(B) R2(B) W2(B)
swap R2(A),R1(B): R1(A) W1(A) R1(B) R2(A) W2(A) W1(B) R2(B) W2(B)
swap W2(A),W1(B): R1(A) W1(A) R1(B) R2(A) W1(B) W2(A) R2(B) W2(B)
swap R2(A),W1(B): R1(A) W1(A) R1(B) W1(B) R2(A) W2(A) R2(B) W2(B)
\_____ T1 _____________/ \_____ T2 _____________/
Every swap was between operations on different items, so each step is legal. We reached the serial schedule T1 → T2. Therefore S is conflict serializable, which matches what we found by computing values (A = 3200, B = 4800).
Swapping works, but it is slow and error-prone for bigger schedules. There is a much better test.
The Precedence Graph Test
A precedence graph (also called a serialization graph or conflict graph) captures the order of all conflicting pairs.
Algorithm
Draw one node for each transaction in the schedule. (Strictly, the test is applied to the transactions that commit; in exam questions every transaction is assumed to commit unless an abort is shown.)
For every pair of conflicting operations where an operation of
Ticomes before an operation ofTj, draw an edgeTi → Tj. In other words, addTi → Tjif:TidoesW(X)beforeTjdoesR(X), orTidoesR(X)beforeTjdoesW(X), orTidoesW(X)beforeTjdoesW(X).
If the graph has a cycle, the schedule is not conflict serializable.
If the graph is acyclic, the schedule is conflict serializable. Any topological order of the graph gives an equivalent serial schedule.
An edge Ti → Tj means "in any equivalent serial schedule, Ti must come before Tj". A cycle like T1 → T2 → T1 demands that T1 comes before T2 and T2 comes before T1, which is impossible.
Example 2: Lost update (not conflict serializable)
S: R1(A) R2(A) W1(A) W2(A) R1(B) W1(B) R2(B) W2(B)
Look at item A first:
R1(A)beforeW2(A)→ T1 → T2R2(A)beforeW1(A)→ T2 → T1W1(A)beforeW2(A)→ T1 → T2 (already have it)
+----+ ----------> +----+
| T1 | | T2 |
+----+ <---------- +----+
Cycle T1 → T2 → T1 ⇒ NOT conflict serializable
We can stop as soon as we find a cycle. This matches the previous chapter, where this schedule turned ₹8,000 into ₹9,000.
Example 3: Three transactions
Step: 1 2 3 4 5 6 7 8
S: R1(X) R2(Y) R3(Y) W2(Y) W1(X) W3(X) R2(X) W2(X)
List every conflicting pair (same item, different transactions, at least one write), in schedule order:
Item | Earlier op | Later op | Edge |
|---|---|---|---|
Y | R3(Y) (step 3) | W2(Y) (step 4) | T3 → T2 |
X | R1(X) (1) | W3(X) (6) | T1 → T3 |
X | R1(X) (1) | W2(X) (8) | T1 → T2 |
X | W1(X) (5) | W3(X) (6) | T1 → T3 |
X | W1(X) (5) | R2(X) (7) | T1 → T2 |
X | W1(X) (5) | W2(X) (8) | T1 → T2 |
X | W3(X) (6) | R2(X) (7) | T3 → T2 |
X | W3(X) (6) | W2(X) (8) | T3 → T2 |
Note that R2(Y) and R3(Y) do not conflict (both reads), and R2(Y) / W2(Y) are in the same transaction.
The distinct edges are T1 → T2, T1 → T3 and T3 → T2:
T1
/ \
v v
T3 ---> T2
No cycle, so S is conflict serializable. For the topological order: T1 has no incoming edges, so it goes first. Remove it; now T3 has no incoming edges, so it goes next; then T2.
Equivalent serial schedule: T1 → T3 → T2 (the only one)
Example 4: More than one serial order
S: R1(A) R1(B) W2(A) W3(B)
Edges: R1(A) before W2(A) gives T1 → T2; R1(B) before W3(B) gives T1 → T3. T2 and T3 touch different items, so there is no edge between them.
T1
/ \
v v
T2 T3
Topological orders: T1 → T2 → T3 and T1 → T3 → T2
The schedule is conflict equivalent to both serial schedules. Exam questions often ask "how many conflict-equivalent serial schedules exist?"; the answer is the number of topological orders, here 2.
Example 5: A three-node cycle
S: R1(A) W2(A) R2(B) W3(B) R3(C) W1(C)
R1(A) before W2(A) → T1 → T2
R2(B) before W3(B) → T2 → T3
R3(C) before W1(C) → T3 → T1
T1 → T2 → T3 → T1 ⇒ cycle ⇒ NOT conflict serializable
No single pair of transactions looks bad here. The problem appears only when you follow the whole cycle, which is exactly why we draw the graph.
View Serializability
Conflict serializability is strict: it treats every W–W pair as important. But sometimes a write is overwritten before anyone reads it, so its order does not really matter. View serializability captures this.
View equivalence
Two schedules S and S' (over the same transactions and operations) are view equivalent if these three conditions hold for every data item X:
Initial read: if Ti reads the initial value of X in S (no one wrote X before it), then Ti also reads the initial value of X in S'.
Reads-from (updated read): if Ti reads a value of X written by Tj in S, then Ti also reads the value of X written by Tj in S'.
Final write: the transaction that performs the last write on X in S also performs the last write on X in S'.
The intuition: conditions 1 and 2 make sure every transaction sees the same values (the same "view"), so it computes the same things. Condition 3 makes sure the database ends in the same state.
A schedule is view serializable if it is view equivalent to some serial schedule.
Blind writes
A blind write is a write of X by a transaction that has not read X before (in that transaction). The transaction writes a value without looking at the current one, for example "set status = 'CLOSED'".
Example 6: View serializable but not conflict serializable
S: R1(X) W2(X) W1(X) W3(X)
Conflict test first.
R1(X) before W2(X) → T1 → T2
W2(X) before W1(X) → T2 → T1 ⇒ cycle T1 ⇄ T2
(also T1 → T3 and T2 → T3)
NOT conflict serializable
View test. Collect the three facts from S:
Initial read: T1 reads the initial value of X.
Reads-from: no transaction reads a value written by another one.
Final write: T3 writes X last.
Now look for a serial order that satisfies them. T1 must read the initial X, so T1 must come before T2 and T3 (both of them write X). T3 must write last, so T3 is at the end. That leaves:
Serial T1 → T2 → T3: R1(X) W1(X) W2(X) W3(X)
Initial read: T1 reads initial X ✓
Reads-from: nobody reads another's X ✓
Final write: T3 ✓
So S is view serializable (equivalent to T1 → T2 → T3) even though it is not conflict serializable.
Why is this OK? W2(X) and W1(X) are both blind as far as anyone else is concerned: nobody ever reads the values they write, because T3 overwrites X at the end. Their order cannot affect anything. Conflict serializability is too strict to notice that; view serializability notices it.
Example 7: A blind write is not enough
S: R1(A) R2(A) W1(A) W2(A) W3(A)
T3's write is blind and is the final write. Is it view serializable?
Both T1 and T2 read the initial value of A.
In any serial order, whichever of T1 or T2 runs second would read the value written by the first (both write A).
So at most one of them can read the initial value. The initial-read condition fails for every serial order.
Not view serializable. This shows that having a blind write is necessary for "view serializable but not conflict serializable", but it is not sufficient.
Relationship Between the Two
+--------------------------------------------------+
| All schedules |
| +------------------------------------------+ |
| | View serializable | |
| | +----------------------------------+ | |
| | | Conflict serializable | | |
| | | +--------------------------+ | | |
| | | | Serial | | | |
| | | +--------------------------+ | | |
| | +----------------------------------+ | |
| +------------------------------------------+ |
+--------------------------------------------------+
Every serial schedule is conflict serializable.
Every conflict-serializable schedule is view serializable. (Conflict equivalence keeps every R–W, W–R and W–W order, so the reads-from and final-write relations are preserved.)
A schedule that is view serializable but not conflict serializable must contain at least one blind write.
So, if a schedule is not conflict serializable and has no blind writes, it is not view serializable either. This shortcut saves a lot of time in exams.
Aspect | Conflict serializability | View serializability |
|---|---|---|
Based on | Order of all conflicting pairs | Initial reads, reads-from, final writes |
Test | Cycle check in precedence graph | No efficient general test (NP-complete) |
Time to test | Polynomial (fast) | Exponential in the worst case |
Schedules accepted | Fewer | More (adds some with blind writes) |
Used in real DBMSs | Yes, guaranteed by 2PL and timestamp ordering | Mostly theoretical |
Because testing view serializability is NP-complete, real systems aim for conflict serializability. The few extra schedules that view serializability would allow are not worth the cost.
Step-by-Step Exam Method
1. Draw the precedence graph.
2. No cycle? → Conflict serializable (hence also view serializable).
Serial order(s) = topological order(s).
3. Cycle? → Not conflict serializable. Now check for blind writes.
4. No blind writes? → Not view serializable either. Done.
5. Blind writes? → Check the three view conditions:
- who reads initial values → must come before every other writer of that item
- who reads from whom → writer before reader, no other writer in between
- who writes last on each item → must be last among that item's writers
If some serial order satisfies all → view serializable, else not.
Practice Problems
P1. Is R1(A) R2(B) W1(B) W2(A) conflict serializable? View serializable?
Show answer
R2(B) before W1(B) gives T2 → T1. R1(A) before W2(A) gives T1 → T2. Cycle, so not conflict serializable. There are blind writes (T1 writes B without reading B, and T2 writes A without reading A), so we must check the view conditions: T1 reads initial A, so T1 must come before T2 (T2 writes A). T2 reads initial B, so T2 must come before T1 (T1 writes B). Contradiction, so not view serializable.
P2. Find the equivalent serial schedule for R2(X) R1(X) W2(Y) W1(X) R3(Y) W3(X).
Show answer
Conflicts: R2(X) before W1(X) → T2 → T1; R2(X) before W3(X) → T2 → T3; R1(X) before W3(X) → T1 → T3; W1(X) before W3(X) → T1 → T3; W2(Y) before R3(Y) → T2 → T3. Edges T2 → T1, T2 → T3, T1 → T3. Acyclic, so conflict serializable, with the only serial order T2 → T1 → T3.
P3. Is W1(A) R2(A) W3(A) W2(A) view serializable? If yes, to which serial order?
Show answer
Precedence graph: T1 → T2 (W1 before R2), T1 → T3, T2 → T3 (R2 before W3), T3 → T2 (W3 before W2). Cycle T2 ⇄ T3, so not conflict serializable. T3's write is blind, so check view conditions: T2 reads A from T1; T2 writes A last. So T1 must come before T2 with no other writer of A between them, and T2 must be last. The only option is T3 → T1 → T2: T3 writes A, T1 overwrites it, T2 reads T1's value and writes last. All three conditions hold, so it is view serializable, with T3 first even though T3's operation appears late in the schedule.
Common Mistakes
Adding edges for two reads.
R1(X)andR2(X)never conflict.Adding edges within one transaction. Conflicts are only between different transactions.
Getting the edge direction backwards. The edge goes from the transaction whose operation comes first to the one whose operation comes later.
Only checking adjacent operations. A conflict exists between any earlier and any later operation, even if they are far apart in the schedule.
Concluding "not serializable" from a cycle alone. A cycle means "not conflict serializable". The schedule might still be view serializable if it has blind writes.
Thinking any blind write makes a schedule view serializable. Blind writes are necessary, not sufficient (Example 7).
Interview Questions
1. When do two operations conflict?
When they are from different transactions, access the same data item, and at least one of them is a write.
2. How do you test conflict serializability?
Build the precedence graph with an edge Ti → Tj for each conflicting pair where Ti's operation comes first. The schedule is conflict serializable if and only if the graph has no cycle.
3. How do you get the equivalent serial schedule?
Take a topological sort of the precedence graph. Each topological order is an equivalent serial schedule.
4. State the three conditions of view equivalence.
Same initial reads, same reads-from relationships, and same final writer for every data item.
5. Is every view-serializable schedule conflict serializable?
No. Every conflict-serializable schedule is view serializable, but a view-serializable schedule with blind writes may not be conflict serializable.
6. What is a blind write?
A write to a data item by a transaction that has not read that item first.
7. Why do real DBMSs use conflict serializability instead of view serializability?
Testing view serializability is NP-complete, while conflict serializability can be checked (and enforced by protocols like 2PL) efficiently.
Summary
Two operations conflict if they are from different transactions, on the same item, and at least one is a write.
A schedule is conflict serializable if swapping adjacent non-conflicting operations can turn it into a serial schedule.
Test: precedence graph. No cycle ⇒ conflict serializable; topological orders give the serial schedules.
View equivalence requires the same initial reads, reads-from pairs, and final writes.
Conflict serializable ⊂ view serializable. The extra schedules always involve blind writes.
View serializability is NP-complete to test, so practical systems enforce conflict serializability.
Serializability tells us whether an interleaving is correct when every transaction commits. But what if one aborts? In the next chapter, Recoverable & Cascadeless Schedules, we look at schedules from the point of view of failures and rollbacks.