Imagine one cook in a kitchen preparing two dishes. They could finish dish 1 completely and only then start dish 2. That is safe, but slow: while the rice boils, the cook just stands there. A smart cook interleaves the work: chop vegetables for dish 2 while the rice for dish 1 is boiling.
Interleaving is faster, but it has a risk. If the cook mixes up which spice goes into which pot, both dishes are ruined.
A DBMS faces the same trade-off with transactions. Running them one after another is safe but slow. Interleaving them is fast but can corrupt data. To reason about this precisely, we use two ideas:
A schedule describes the exact order in which the operations of several transactions are executed.
Serializability tells us whether an interleaved schedule is just as correct as running the transactions one at a time.
A schedule is serializable if its effect on the database is equivalent to that of some serial schedule, that is, some order in which the same transactions run one after another without interleaving.
This chapter builds on Transactions & ACID Properties, where we saw that isolation is the property that protects concurrent transactions from each other. Serializability is the precise meaning of "correct isolation".
Our Two Example Transactions
We will use two transactions on accounts A and B throughout this chapter. Initially A = 5000 and B = 3000, so the total is ₹8,000.
T1: transfer ₹1000 from A to B T2: transfer 20% of A to B
read(A) read(A)
A := A - 1000 temp := A * 0.2
write(A) A := A - temp
read(B) write(A)
B := B + 1000 read(B)
write(B) B := B + temp
write(B)
Both transactions are correct on their own: each one keeps the total A + B unchanged.
In short notation (from the previous chapters), each transaction is:
T1: R1(A) W1(A) R1(B) W1(B)
T2: R2(A) W2(A) R2(B) W2(B)
What Is a Schedule?
A schedule is a chronological sequence of the operations of a set of transactions, in which the operations of each individual transaction appear in the same order as they do in that transaction.
Two key points hide in this definition:
A schedule contains all the operations of the transactions involved (a complete schedule also includes each transaction's commit or abort).
The DBMS may interleave operations of different transactions in any way, but it must never reorder operations within one transaction. T1's
W1(A)can never come before T1'sR1(A).
We usually draw schedules in columns, with time flowing downward:
Time T1 T2
1 R(A)
2 W(A)
3 R(A)
4 W(A)
5 R(B)
6 W(B)
7 R(B)
8 W(B)
The same schedule in one line is:
R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B)
Serial Schedules
A serial schedule is one in which the transactions run one after another: all operations of one transaction finish before any operation of the next transaction begins.
With two transactions there are exactly two serial schedules. Let us compute both with A = 5000 and B = 3000.
Serial schedule T1 → T2
T1 T2 A B
R(A) 5000
W(A) 4000 (5000 - 1000)
R(B) 3000
W(B) 4000 (3000 + 1000)
R(A) 4000
W(A) 3200 (temp = 800)
R(B) 4000
W(B) 4800 (4000 + 800)
Final: A = 3200, B = 4800, total = 8000
Serial schedule T2 → T1
T1 T2 A B
R(A) 5000
W(A) 4000 (temp = 1000)
R(B) 3000
W(B) 4000 (3000 + 1000)
R(A) 4000
W(A) 3000 (4000 - 1000)
R(B) 4000
W(B) 5000 (4000 + 1000)
Final: A = 3000, B = 5000, total = 8000
Notice something important: the two serial schedules give different final values, yet both are considered correct. Why?
Because each transaction, run alone on a consistent database, leaves it consistent. Running them one after another simply chains two correct steps. The DBMS does not promise any particular order; it only promises that the result matches some serial order. (If the order matters to the business, the application must enforce it, for example by not starting T2 until T1 has committed.)
Key idea: every serial schedule is correct. With
ntransactions there aren!serial schedules (3 transactions → 6, 4 → 24).
The problem with serial schedules is speed. If T1 is waiting for a slow disk read, T2 cannot use the idle CPU. That is why real systems run transactions concurrently.
Non-Serial (Concurrent) Schedules
A non-serial schedule interleaves the operations of different transactions. The schedule shown at the start of the "What Is a Schedule?" section is non-serial.
How many schedules are possible?
If transaction T1 has n1 operations and T2 has n2, a schedule is just a way of choosing which of the n1 + n2 time slots belong to T1 (the rest go to T2, and each transaction's internal order is fixed). So the number of schedules is:
(n1 + n2)!
schedules = ------------
n1! × n2!
and in general, for k transactions:
(n1 + n2 + ... + nk)!
schedules = -----------------------
n1! × n2! × ... × nk!
For our T1 and T2 (4 read/write operations each):
8! / (4! × 4!) = 40320 / (24 × 24) = 70 schedules
of which 2 are serial and 68 are non-serial
Another example: 3 transactions with 2 operations each give 6! / (2! × 2! × 2!) = 720 / 8 = 90 schedules, of which 3! = 6 are serial.
Some of these non-serial schedules are perfectly fine. Others are disastrous. Let us look at both kinds.
A Good Concurrent Schedule
Here T2 starts working on A as soon as T1 is done with A, while T1 moves on to B:
T1 T2 A B
R(A) 5000
W(A) 4000
R(A) 4000
W(A) 3200 (temp = 800)
R(B) 3000
W(B) 4000
R(B) 4000
W(B) 4800
Final: A = 3200, B = 4800, total = 8000
This is exactly the result of the serial schedule T1 → T2. Even though the operations were interleaved, the effect is as if T1 ran completely before T2. This schedule is serializable.
Problems Caused by Bad Interleaving
Now let us see what can go wrong. These classic problems are the reason concurrency control exists.
1. Lost Update (Write–Write conflict)
Two transactions read the same value, and the second write overwrites the first, as if the first never happened.
T1 T2 A B
R(A) 5000
R(A) 5000 (T2 also sees 5000)
W(A) 4000 (T1: 5000 - 1000)
W(A) 4000 (T2: 5000 - 1000, T1's debit is LOST)
R(B) 3000
W(B) 4000
R(B) 4000
W(B) 5000 (T2: 4000 + 1000)
Final: A = 4000, B = 5000, total = 9000 ✗
The bank has created ₹1,000 out of nothing. T1's write to A was overwritten by T2, which was working with a stale value. This schedule is not equivalent to either serial schedule (3200/4800 or 3000/5000).
2. Dirty Read (Write–Read conflict, uncommitted dependency)
A transaction reads a value written by another transaction that later aborts.
T1 T2
R(A) A = 5000
W(A) A = 4000
R(A) reads 4000 (uncommitted!)
... uses 4000 in its calculation ...
ABORT A back to 5000
T2 has used a value that, after T1's rollback, never officially existed. If T2 commits, its results are based on fiction. This problem also connects to recoverability, which we study in Recoverable & Cascadeless Schedules.
3. Unrepeatable Read (Read–Write conflict)
A transaction reads the same item twice and gets two different values, because another transaction changed it in between.
T1 T2
R(A) 5000
R(A) 5000
W(A) 4000
COMMIT
R(A) 4000 ← same item, different value
If T1 was, say, checking "is the balance enough?" and then using the balance, it now has two inconsistent views of the same account.
4. Incorrect Summary (Inconsistent Analysis)
One transaction computes an aggregate (like a total) while another is in the middle of updating the items. We saw this in the ACID chapter: a report computed ₹7,000 because it read A after T1's debit but B before T1's credit.
5. Phantom Read
A transaction runs the same query twice, for example "all accounts with balance > 4000", and the second time a new row appears (or one disappears), because another transaction inserted or deleted a matching row in between. The row is a "phantom". Unlike the others, this problem is about sets of rows rather than one data item, which is why simple item-level locking does not prevent it.
Problem | Conflict type | What goes wrong |
|---|---|---|
Lost update | W–W | One transaction's write is overwritten and lost |
Dirty read | W–R | Reading uncommitted data that is later rolled back |
Unrepeatable read | R–W | Same item read twice gives different values |
Incorrect summary | R–W mix | Aggregate computed over partly updated data |
Phantom read | Insert/delete vs. query | Same query returns a different set of rows |
Serializability: The Definition of "Correct"
We now have a clear goal. Serial schedules are always correct, but slow. Arbitrary interleavings are fast, but can be wrong. So we accept an interleaved schedule only if it is equivalent to some serial schedule.
A schedule S is serializable if there exists a serial schedule S' of the same transactions such that S is equivalent to S'.
Why is this the right definition? Because:
Each transaction alone is correct
↓
Any serial schedule is correct
↓
A schedule equivalent to a serial one is correct
Serializability does not care which serial order it matches. T1 → T2 and T2 → T1 are equally acceptable.
But what does "equivalent" mean?
This is the subtle part. There are several possible definitions of equivalence:
Result equivalence (too weak)
Two schedules are result equivalent if they produce the same final database state. It sounds natural, but it is unreliable, because the result can match by coincidence for some starting values and not for others.
Consider T1: X := X * 2 and T2: X := X + 5, interleaved as a lost update:
R1(X) R2(X) W1(X) W2(X) (T2's write overwrites T1's)
Start X = 0: schedule gives 5, T1→T2 gives 5, T2→T1 gives 10 → matches T1→T2!
Start X = 10: schedule gives 15, T1→T2 gives 25, T2→T1 gives 30 → matches nothing
For X = 0 the schedule "looks" serializable, but it is clearly a lost update. A definition of correctness that depends on the current data values is useless to a DBMS, which must decide on the order before knowing what the values will be.
Conflict equivalence and view equivalence (what DBMSs use)
Instead of looking at values, the DBMS looks only at the order of reads and writes. This leads to two practical notions:
Conflict serializability → based on the order of conflicting operations; easy to test with a precedence graph; this is what real concurrency-control protocols (like two-phase locking) guarantee.
View serializability → based on who reads whose writes and who writes last; more permissive but expensive to test.
Both are covered in detail, with step-by-step tests, in the next chapter, Conflict & View Serializability.
Serializability is a safe (conservative) rule
Because the DBMS ignores what the transactions actually compute, it will sometimes reject a schedule that happens to be correct. We checked all 70 schedules of our T1 and T2 by brute force with a small Python script:
Total schedules : 70
Conflict serializable : 12
Final A, B equal to a serial result : 14
Two schedules are correct but not conflict serializable. One of them is:
R1(A) W1(A) R2(A) W2(A) R2(B) W2(B) R1(B) W1(B)
A: 5000 → 4000 (T1) → 3200 (T2)
B: 3000 → 3800 (T2 adds 800) → 4800 (T1 adds 1000)
Final A = 3200, B = 4800 (same as T1 → T2)
It works only because both transactions add to B, and addition is commutative. The DBMS does not know that T1 and T2 are additions; for all it knows, they could be anything. So it plays safe and treats this schedule as non-serializable. That is the price of a rule that works for every possible transaction.
Classification of Schedules
Here is the big picture of schedule types, including those we will meet in the next two chapters:
Schedules
/ \
Serial Non-serial
(always OK) |
+-----+-------+
| |
Serializable Non-serializable
/ \ (may be wrong)
Conflict- View-
serializable serializable
Every serial schedule is conflict serializable,
every conflict-serializable schedule is view serializable,
but not the other way round.
Separately, schedules are classified by recoverability:
Recoverable ⊃ Cascadeless ⊃ Strict
Serializability is about correct interleaving (isolation). Recoverability is about what happens when a transaction aborts (atomicity). A good DBMS needs schedules that are both serializable and recoverable. Recoverability is covered in Recoverable & Cascadeless Schedules.
How Does a DBMS Ensure Serializability in Practice?
A DBMS does not generate a schedule, check it, and then run it. Transactions arrive unpredictably. Instead, it uses a concurrency-control protocol that only allows serializable schedules to happen in the first place:
Locking → a transaction must lock an item before using it; two-phase locking guarantees conflict serializability (Lock-Based Concurrency Control (2PL)).
Timestamp ordering → conflicting operations must happen in timestamp order (Timestamp Ordering Protocol).
Multi-version / snapshot techniques → readers see an older committed version, so they do not block writers (used by InnoDB, PostgreSQL, Oracle).
The theory in this chapter and the next is what lets us prove these protocols correct.
Common Mistakes
Thinking a serializable schedule must equal a specific serial order (like T1 → T2). Any serial order is acceptable.
Reordering operations inside one transaction. A schedule must keep each transaction's own operations in their original order.
Using final values to judge serializability. Matching results for one set of values proves nothing (result equivalence is unreliable). Use conflict or view equivalence.
Thinking "non-serializable" means "wrong for sure". It means "not guaranteed correct". Some non-serializable schedules happen to give correct results, but the DBMS cannot rely on that.
Getting the counting formula wrong. It is
(n1 + n2)! / (n1! n2!), not(n1 + n2)!, because each transaction's own operations cannot be reordered.
Interview Questions
1. What is a schedule?
The chronological order in which the operations of a set of transactions execute, keeping each transaction's own operations in their original order.
2. Why are serial schedules always correct?
Each transaction takes a consistent database to a consistent database, so running them one by one keeps the database consistent after each step.
3. If serial schedules are correct, why not always use them?
Poor performance. While one transaction waits for I/O, nothing else can run. Concurrency improves throughput and response time.
4. What is a serializable schedule?
A (possibly interleaved) schedule whose effect is equivalent to some serial schedule of the same transactions.
5. Name the problems caused by uncontrolled concurrency.
Lost update, dirty read, unrepeatable read, incorrect summary, and phantom read.
6. How many schedules are possible for two transactions with 3 and 2 operations?
5! / (3! × 2!) = 120 / 12 = 10, of which 2 are serial.
7. Why is result equivalence not used?
Because two schedules can give the same result for some initial values by coincidence and different results for others. The DBMS needs a test that does not depend on data values.
Summary
A schedule is an interleaving of transactions' operations that preserves each transaction's internal order.
Serial schedules run transactions one at a time; there are
n!of them and all are correct, though they may give different results.Number of schedules =
(n1 + ... + nk)! / (n1! ... nk!).Bad interleavings cause lost updates, dirty reads, unrepeatable reads, incorrect summaries and phantoms.
A schedule is serializable if it is equivalent to some serial schedule.
DBMSs use conflict and view equivalence, which look only at the order of reads and writes, not at data values.
Next, in Conflict & View Serializability, we will learn exactly how to test whether a given schedule is serializable, using precedence graphs and view-equivalence rules.