SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 53
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 53 of 90

Serializability and recoverability

serializabilityconflicting operationsconflict equivalenceconflict serializabilityprecedence graph testview equivalenceview serializabilityblind writerecoverable schedulecascading rollbackcascadeless schedulestrict schedulecounting serial and conflict-equivalent schedules numericals

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:

  1. they belong to different transactions,
  2. they access the same data item,
  3. 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):

  1. one node per transaction;
  2. for each pair of conflicting operations where Ti's operation comes first, an edge Ti → Tj ("Ti must come before Tj");
  3. a cycle → not conflict serializable;
  4. 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) and w3(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) with w2(B).
  • Conflict equivalent to T1 T2: w2(B) must come after r1(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) before r1(B), and r1(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

  1. Is r1(A) w2(A) r2(B) w1(B) conflict serializable?
  2. Is w1(A) r2(A) w2(B) c2 a1 recoverable?
  3. Write your own schedule that is view serializable but not conflict serializable.
  4. In section 9, how many schedules are conflict equivalent to T2 T1?
Solutions
  1. r1(A) before w2(A) gives T1 → T2; r2(B) before w1(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
  1. 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.
  2. 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
  1. 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

  1. 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.
  2. When do two operations conflict? Different transactions, same item, at least one write.
  3. How do you test conflict serializability? Build the precedence graph; acyclic means conflict serializable, and a topological order gives the serial order.
  4. 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.
  5. What is a blind write? A write without a prior read of that item by the same transaction.
  6. What is a recoverable schedule? Each transaction commits only after every transaction it read from has committed.
  7. 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).
  8. Strict vs cascadeless? Strict also forbids writing an item whose last writer hasn't finished.
  9. Order the classes. Strict ⊂ cascadeless ⊂ recoverable; serial ⊂ CS ⊂ VS.
  10. 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.