These are the notes for CS Fundamentals for Placements, episode 53. Episode 52 showed that concurrent schedules are fast but can go wrong. Here we invent the test that says which ones are safe: serializability. The obvious test (same final result) fails, so we define conflicting operations, conflict equivalence and conflict serializability, code the precedence graph test, meet blind writes and view serializability, then add aborts: recoverable, cascadeless and strict schedules and cascading rollback. We finish with the GATE-style counting numericals. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.
All program outputs below are real: every Python program was run with python3 (Python 3.13) on Linux x86-64 on 10 November 2026.
From episode 52 you need: transaction, read(X) / write(X), commit / abort, schedule, serial and concurrent schedules, the notation r1(A), w2(A), c1, a1, and the five anomalies (dirty read, lost update, unrepeatable read, phantom read, incorrect summary).
1. What we want: serializability
- Serializable schedule: a concurrent schedule that is equivalent to some serial schedule of the same transactions. Since every serial schedule is correct, so is every schedule equivalent to one.
- The question is what "equivalent" should mean.
2. First try: same final result (it fails)
Result equivalence: two schedules are result equivalent if they leave the same final values in the database. T1 doubles A and T2 triples A; compare serial T1 T2 with the interleaving r1(A) r2(A) w1(A) w2(A):
# T1: A = A * 2 T2: A = A * 3
def serial(A): # T1 then T2
A = A * 2
A = A * 3
return A
def interleaved(A): # r1(A) r2(A) w1(A) w2(A)
t1 = A # r1(A)
t2 = A # r2(A)
A = t1 * 2 # w1(A)
A = t2 * 3 # w2(A)
return A
for start in [0, 100]:
s, i = serial(start), interleaved(start)
print(f"A = {start:3}: serial {s}, interleaved {i}",
"same!" if s == i else "DIFFERENT")
Output:
A = 0: serial 0, interleaved 0 same!
A = 100: serial 600, interleaved 300 DIFFERENT
For an empty account (A = 0) both give 0, so the test says "equivalent". For A = 100 they differ (600 vs 300): it was the lost update all along. Why it failed: final values depend on the data, and a lucky starting value hides the bug. We need a test that looks only at the order of operations, so it holds for every possible data.
3. Conflicting operations
Two operations conflict when all three hold:
- they belong to different transactions,
- they access the same data item,
- at least one of them is a write.
| Pair | Conflict? | Why |
|---|---|---|
| r1(A), r2(A) | No | two reads never change anything |
| r1(A), w2(A) | Yes | read-write conflict |
| w1(A), r2(A) | Yes | write-read conflict |
| w1(A), w2(A) | Yes | write-write conflict |
| w1(A), w2(B) | No | different items |
| r1(A), w1(A) | No | same transaction |
Swapping two adjacent, non-conflicting operations can never change what any transaction reads or what is finally written. Swapping two conflicting ones can.
4. Conflict equivalence and conflict serializability
- Conflict equivalent: schedule S can be turned into S' by a sequence of swaps of adjacent non-conflicting operations. Equivalently: every pair of conflicting operations is in the same order in S and S'.
- Conflict serializable (CS): conflict equivalent to some serial schedule.
Example: r1(A) w1(A) r2(A) w2(A) r1(B) w1(B). Swap w2(A) with r1(B), then r2(A) with r1(B), then do the same for w1(B), and you get r1(A) w1(A) r1(B) w1(B) r2(A) w2(A) = serial T1 T2. It is conflict serializable.
The lost update r1(A) r2(A) w1(A) w2(A): r1(A) before w2(A) forces T1 first; r2(A) before w1(A) forces T2 first. Both cannot hold, so it is not conflict serializable, for any data.
5. The precedence graph test
Precedence graph (serialization graph):
- one node per transaction;
- for each pair of conflicting operations where Ti's operation comes first, an edge Ti → Tj ("Ti must come before Tj");
- a cycle → not conflict serializable;
- no cycle → conflict serializable. The equivalent serial schedules are the topological orders of the graph: orders in which every edge points forward.
import re
from itertools import permutations
def parse(s): return re.findall(r"([rw])(\d)\((\w)\)", s)
def conflict(p, q): # different transactions, same item, at least one write
return p[1] != q[1] and p[2] == q[2] and "w" in (p[0], q[0])
def precedence(s):
ops = parse(s)
return {(p[1], q[1]) for i, p in enumerate(ops) for q in ops[i+1:] if conflict(p, q)}
def serial_orders(s): # orders that agree with every edge = topological orders
ts = sorted({op[1] for op in parse(s)})
E = precedence(s)
return ["T" + " T".join(o) for o in permutations(ts)
if all(o.index(a) < o.index(b) for a, b in E)]
for s in ["r1(A) w1(A) r2(A) w2(A) r1(B) w1(B) r2(B) w2(B)",
"r1(A) r2(A) w1(A) w2(A)",
"r1(A) r2(B) r3(C) w1(A) w3(C) r2(A)"]:
E = sorted(precedence(s))
print(s)
print(" edges:", ", ".join(f"T{a}->T{b}" for a, b in E))
o = serial_orders(s)
print(" conflict serializable:", bool(o), o if o else "(cycle)")
Output:
r1(A) w1(A) r2(A) w2(A) r1(B) w1(B) r2(B) w2(B)
edges: T1->T2
conflict serializable: True ['T1 T2']
r1(A) r2(A) w1(A) w2(A)
edges: T1->T2, T2->T1
conflict serializable: False (cycle)
r1(A) r2(B) r3(C) w1(A) w3(C) r2(A)
edges: T1->T2
conflict serializable: True ['T1 T2 T3', 'T1 T3 T2', 'T3 T1 T2']
- Schedule 1: one edge T1 → T2; equivalent to T1 T2.
- Schedule 2 (lost update): edges both ways, a cycle.
- Schedule 3: only T1 → T2, T3 is unconstrained, so three serial orders: every order with T1 before T2.
The code tries every order of the transactions and keeps those where every edge points forward; an empty result means the graph has a cycle. For large graphs one would use a depth-first search for cycles and a topological sort instead (episode-style DSA).
6. Blind writes and view serializability
S = r1(A) w2(A) w1(A) w3(A). Edges: T1 → T2 (r1 before w2), T2 → T1 (w2 before w1), T1 → T3, T2 → T3. A cycle: not conflict serializable. Yet only T1 reads, it reads the original A, and T3's write is the last. Running T1, T2, T3 serially gives the same reads and the same final value.
- Blind write: a write of an item the transaction never read first.
w2(A)andw3(A)are blind writes. Real-life: setting a new password, where the old one doesn't matter. - View equivalent: S and S' are view equivalent when 1. initial reads match: the same transaction reads the initial value of each item, 2. reads-from matches: if Tj reads X written by Ti in S, it does in S', 3. final writes match: the same transaction writes each item last.
- View serializable (VS): view equivalent to some serial schedule.
import re
from itertools import permutations
def parse(s): return re.findall(r"([rw])(\d)\((\w)\)", s)
def view(ops): # who each read reads from, and who writes each item last
last, reads = {}, []
for k, t, x in ops:
if k == "r": reads.append((t, x, last.get(x, "initial")))
else: last[x] = t
return sorted(reads), last
S = parse("r1(A) w2(A) w1(A) w3(A)")
print("S view:", view(S))
for order in permutations("123"):
serial = [op for t in order for op in S if op[1] == t]
print("T" + " T".join(order), "view-equivalent:", view(serial) == view(S))
Output:
S view: ([('1', 'A', 'initial')], {'A': '3'})
T1 T2 T3 view-equivalent: True
T1 T3 T2 view-equivalent: False
T2 T1 T3 view-equivalent: False
T2 T3 T1 view-equivalent: False
T3 T1 T2 view-equivalent: False
T3 T2 T1 view-equivalent: False
Facts (source: Wikipedia, "Serializability", fetched 10 Nov 2026): all conflict-serializable schedules are view-serializable (CS ⊂ VS); schedules that are view- but not conflict-serializable involve a blind write; deciding view serializability is NP-complete, so real systems enforce conflict serializability.
7. Aborts: recoverable schedules
Real-life: Ravi deposits a cheque (T1 writes his balance, not yet committed), spends the money (T2 reads it and commits), then the cheque bounces (T1 aborts). T2 cannot be undone, because committed is permanent (durability). The database cannot return to a correct state.
- Tj reads from Ti: Tj reads a value of some item that Ti wrote.
- Recoverable schedule: whenever Tj reads from Ti, Ti commits before Tj commits.
w1(A) r2(A) c2 c1: not recoverable (T2 commits first).w1(A) r2(A) c1 c2: recoverable; if T1 aborted, T2 could still be aborted too.- Cascading rollback (cascading abort): one abort forces every transaction that read its data to abort, and then everyone who read from those, and so on.
import re
def parse(s): return re.findall(r"([rwca])(\d)(?:\((\w)\))?", s)
S = "w1(A) r2(A) w2(B) r3(B) w3(C) r4(D) a1"
last, depends = {}, {} # depends[t] = transactions t read from
for k, t, x in parse(S):
if k == "w": last[x] = t
if k == "r" and x in last and last[x] != t:
depends.setdefault(t, set()).add(last[x])
print(f"T{t} reads {x} written by T{last[x]}")
must_abort, changed = {"1"}, True
while changed: # anyone who read from an aborted one aborts too
changed = False
for t, ws in depends.items():
if t not in must_abort and ws & must_abort:
must_abort.add(t); changed = True
print("T1 aborts -> must also abort:", sorted(must_abort - {"1"}))
print("untouched:", sorted({t for _, t, _ in parse(S)} - must_abort))
Output:
T2 reads A written by T1
T3 reads B written by T2
T1 aborts -> must also abort: ['2', '3']
untouched: ['4']
8. Cascadeless and strict schedules
- Cascadeless schedule (ACA, "avoids cascading aborts"): a transaction reads only committed values. If Tj reads from Ti, Ti has already committed before that read. No dirty reads, so no cascading rollback.
- Strict schedule: no transaction reads or writes X until the last transaction that wrote X has committed or aborted. Undoing an abort is then just restoring the old value (the "before image").
- Strict ⊂ cascadeless ⊂ recoverable.
import re
def parse(s): return re.findall(r"([rwca])(\d)(?:\((\w)\))?", s)
def classify(s):
ops, writer, done = parse(s), {}, set() # writer[x] = last uncommitted writer
rec = cascadeless = strict = True
reads_from = [] # (reader, writer)
for k, t, x in ops:
if k in "rw" and x in writer and writer[x] != t and writer[x] not in done:
strict = False # touched an uncommitted write
if k == "r": cascadeless = False; reads_from.append((t, writer[x]))
if k == "w": writer[x] = t
if k in "ca": done.add(t)
if k == "c" and any(r == t and w not in done for r, w in reads_from):
rec = False # committed before its writer
return rec, cascadeless, strict
for s in ["w1(A) r2(A) c2 c1",
"w1(A) r2(A) c1 c2",
"w1(A) c1 r2(A) c2",
"w1(A) w2(A) c1 c2",
"w1(A) c1 w2(A) r2(A) c2"]:
r, cl, st = classify(s)
yn = lambda b: "yes" if b else "no "
print(f"{s:24} recoverable {yn(r)} cascadeless {yn(cl)} strict {yn(st)}")
Output:
w1(A) r2(A) c2 c1 recoverable no cascadeless no strict no
w1(A) r2(A) c1 c2 recoverable yes cascadeless no strict no
w1(A) c1 r2(A) c2 recoverable yes cascadeless yes strict yes
w1(A) w2(A) c1 c2 recoverable yes cascadeless yes strict no
w1(A) c1 w2(A) r2(A) c2 recoverable yes cascadeless yes strict yes
| Schedule | Recoverable | Cascadeless | Strict | Why |
|---|---|---|---|---|
w1(A) r2(A) c2 c1 |
No | No | No | T2 commits before its writer |
w1(A) r2(A) c1 c2 |
Yes | No | No | dirty read, but commits in order |
w1(A) c1 r2(A) c2 |
Yes | Yes | Yes | reads only committed data |
w1(A) w2(A) c1 c2 |
Yes | Yes | No | no dirty read, but overwrites an uncommitted write |
w1(A) c1 w2(A) r2(A) c2 |
Yes | Yes | Yes | waits for c1 before touching A |
9. Numericals: counting schedules
T1 = r1(A) w1(A) r1(B), T2 = r2(B) w2(B).
- All schedules: 5! / (3! × 2!) = 10.
- Conflicts: A is used only by T1, so the only conflict is
r1(B)withw2(B). - Conflict equivalent to T1 T2:
w2(B)must come afterr1(B), so it is last;r2(B)conflicts with nothing in T1, so it can go in any of 4 places → 4. - Conflict equivalent to T2 T1:
w2(B)beforer1(B), andr1(B)is T1's last operation, so place T2's two operations among the first four slots with T1's first two: 4! / (2! × 2!) = 6 (homework 4).
import re
from itertools import combinations
def parse(s): return re.findall(r"([rw])(\d)\((\w)\)", s)
def conflict(p, q): return p[1] != q[1] and p[2] == q[2] and "w" in (p[0], q[0])
def edges(ops): return {(p[1], q[1]) for i, p in enumerate(ops)
for q in ops[i+1:] if conflict(p, q)}
T1 = parse("r1(A) w1(A) r1(B)")
T2 = parse("r2(B) w2(B)")
n = len(T1) + len(T2)
total = equiv = 0
for pos in combinations(range(n), len(T1)):
a, b = iter(T1), iter(T2)
s = [next(a) if i in pos else next(b) for i in range(n)]
total += 1
if edges(s) <= {("1", "2")}: # same conflict order as T1 -> T2
equiv += 1
print("all schedules:", total)
print("conflict-equivalent to T1 T2:", equiv)
Output:
all schedules: 10
conflict-equivalent to T1 T2: 4
Other common questions: the number of serial schedules of n transactions is n!; the number of schedules conflict equivalent to a given serial order is the number of interleavings that keep every conflicting pair in that order.
The whole chain
| Problem you felt | What you invented |
|---|---|
| "Same final result" was right only by luck | Serializability, defined on the order of steps |
| Which steps can be reordered? | Conflicting operations, conflict serializability |
| Too many swaps to try | Precedence graph test |
| A correct schedule failed the test | Blind write, view serializability |
| A committed transaction read an aborted value | Recoverable schedules |
| One abort dragged others down | Cascading rollback, cascadeless, strict |
Common mistakes
| Mistake | What you get | Why | Fix |
|---|---|---|---|
| Counting two reads as a conflict | an extra edge, a fake cycle | reads never conflict | at least one write |
| Edges between operations of the same transaction | a self-loop | conflicts need different transactions | only Ti ≠ Tj |
| "Cycle → not view serializable" | wrongly rejecting r1(A) w2(A) w1(A) w3(A) |
CS ⊂ VS | look for blind writes |
| "Recoverable = cascadeless" | w1(A) r2(A) c1 c2 called cascadeless |
recoverable still allows dirty reads | cascadeless = read committed values only |
| Testing serializability with final values | "A = 0: same!" | depends on the data | test the operation order |
Mini project: a schedule analyser
Combine the programs above into one analyse(schedule) that prints the precedence-graph edges, whether the schedule is conflict serializable (and its serial orders), whether it is view serializable (brute force), and whether it is recoverable, cascadeless and strict. Test it on every schedule in these notes.
Practice
- Is
r1(A) w2(A) r2(B) w1(B)conflict serializable? - Is
w1(A) r2(A) w2(B) c2 a1recoverable? - Write your own schedule that is view serializable but not conflict serializable.
- In section 9, how many schedules are conflict equivalent to T2 T1?
Solutions
r1(A)beforew2(A)gives T1 → T2;r2(B)beforew1(B)gives T2 → T1. A cycle: not conflict serializable.
import re
from itertools import permutations, combinations
def parse(s): return re.findall(r"([rw])(\d)\((\w)\)", s)
def conflict(p, q): return p[1] != q[1] and p[2] == q[2] and "w" in (p[0], q[0])
def edges(ops): return {(p[1], q[1]) for i, p in enumerate(ops)
for q in ops[i+1:] if conflict(p, q)}
# 1) is r1(A) w2(A) r2(B) w1(B) conflict serializable?
print("1) edges:", sorted(edges(parse("r1(A) w2(A) r2(B) w1(B)"))))
# 4) schedules of T1 = r1(A) w1(A) r1(B), T2 = r2(B) w2(B) equivalent to T2 T1
T1, T2 = parse("r1(A) w1(A) r1(B)"), parse("r2(B) w2(B)")
count = 0
for pos in combinations(range(5), 3):
a, b = iter(T1), iter(T2)
s = [next(a) if i in pos else next(b) for i in range(5)]
if edges(s) <= {("2", "1")}: count += 1
print("4) conflict-equivalent to T2 T1:", count)
Output:
1) edges: [('1', '2'), ('2', '1')]
4) conflict-equivalent to T2 T1: 6
- No. T2 reads A from T1 and commits (
c2) while T1 is still running; then T1 aborts and T2's committed work used a value that never existed. - Example:
r2(A) w1(A) w2(A) w3(A). Edges T2 → T1 and T1 → T2 (a cycle), but T2 reads the initial A and T3 writes last, exactly as in serial T2 T1 T3 (checked with the view program):
import re
from itertools import permutations
def parse(s): return re.findall(r"([rw])(\d)\((\w)\)", s)
def view(ops): # who each read reads from, and who writes each item last
last, reads = {}, []
for k, t, x in ops:
if k == "r": reads.append((t, x, last.get(x, "initial")))
else: last[x] = t
return sorted(reads), last
S = parse("r2(A) w1(A) w2(A) w3(A)")
print("S view:", view(S))
for order in permutations("123"):
serial = [op for t in order for op in S if op[1] == t]
print("T" + " T".join(order), "view-equivalent:", view(serial) == view(S))
Output:
S view: ([('2', 'A', 'initial')], {'A': '3'})
T1 T2 T3 view-equivalent: False
T1 T3 T2 view-equivalent: False
T2 T1 T3 view-equivalent: True
T2 T3 T1 view-equivalent: False
T3 T1 T2 view-equivalent: False
T3 T2 T1 view-equivalent: False
- 6 (see the output of solution 1's program, line 4).
Quick quiz
Is r1(A) r2(B) w1(B) w2(A) conflict serializable? (A) Yes, ≡ T1 T2 (B) Yes, ≡ T2 T1 (C) No, there is a cycle (D) Yes, both orders
Answer
(C). r1(A) before w2(A) gives T1 → T2; r2(B) before w1(B) gives T2 → T1. A cycle.
Interview questions
- What is serializability and why do we want it? A concurrent schedule is serializable if equivalent to a serial one; it gives concurrency without anomalies.
- When do two operations conflict? Different transactions, same item, at least one write.
- How do you test conflict serializability? Build the precedence graph; acyclic means conflict serializable, and a topological order gives the serial order.
- Conflict vs view serializability? View is weaker (more schedules qualify); every CS schedule is VS; the extra VS schedules contain blind writes; VS testing is NP-complete.
- What is a blind write? A write without a prior read of that item by the same transaction.
- What is a recoverable schedule? Each transaction commits only after every transaction it read from has committed.
- What is a cascading rollback and how do you avoid it? One abort forcing readers of its data to abort; avoid it with cascadeless schedules (read only committed data).
- Strict vs cascadeless? Strict also forbids writing an item whose last writer hasn't finished.
- Order the classes. Strict ⊂ cascadeless ⊂ recoverable; serial ⊂ CS ⊂ VS.
- Why is result equivalence not used? It depends on the data values, so it can't be checked from the schedule alone.
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Serializable | Equivalent to some serial schedule | ≡ T1 T2 |
| Result equivalence | Same final values (depends on data: not used) | equal for A = 0 only |
| Conflicting operations | Different transactions, same item, at least one write | r1(A), w2(A) |
| Read-write / write-read / write-write conflict | The three kinds of conflicting pairs | w1(A), r2(A) |
| Adjacent swap | Exchanging two neighbouring operations | w2(A) ↔ r1(B) |
| Conflict equivalent | Same order of every conflicting pair | |
| Conflict serializable (CS) | Conflict equivalent to a serial schedule | |
| Precedence graph (serialization graph) | Node per transaction, edge Ti → Tj for each conflict with Ti first | T1 → T2 |
| Cycle | A path of edges that returns to its start | T1 → T2 → T1 |
| Topological order | An order of nodes where every edge points forward | T1 T3 T2 |
| Blind write | A write of an item not read first by that transaction | w2(A) |
| Initial read | Reading an item's original value | T1 reads initial A |
| Reads-from | Tj reads a value written by Ti | T2 reads A from T1 |
| Final write | The last write of an item | w3(A) |
| View equivalent | Same initial reads, reads-from and final writes | |
| View serializable (VS) | View equivalent to a serial schedule | r1(A) w2(A) w1(A) w3(A) |
| NP-complete | No known fast (polynomial-time) algorithm | testing VS |
| Recoverable schedule | Commit only after everyone you read from has committed | w1(A) r2(A) c1 c2 |
| Cascading rollback | One abort forcing a chain of aborts | T1 → T2 → T3 |
| Cascadeless (ACA) schedule | Read only committed values | w1(A) c1 r2(A) |
| Strict schedule | No read or write of X until X's last writer has ended | w1(A) c1 w2(A) |
| Before image | The old value of an item, restored on undo | |
itertools.permutations |
Python: every ordering of items | serial orders |
re.findall |
Python: every match of a pattern in a string | parsing "r1(A)" |
Summary
- Same final values is not a safe test: equal for A = 0, different for A = 100 (live).
- Conflicting operations: different transactions, same item, at least one write. Conflict serializable = conflict equivalent to a serial schedule.
- Precedence graph: a cycle means not CS; otherwise the topological orders are the equivalent serial schedules (live).
- View serializability is looser; the difference is blind writes; testing it is NP-complete (live, brute force).
- Recoverable → no committed reader of an aborted writer; cascadeless → no cascading rollback; strict → simple undo. Strict ⊂ cascadeless ⊂ recoverable (live).
- Counting: 10 schedules of a 3-step and a 2-step transaction, 4 conflict equivalent to T1 T2, 6 to T2 T1 (live).
Next episode: concurrency control 1, locking and two-phase locking.