DSA, Database System & Operating System — Transaction Processing, Concurrency Control & Recovery, NEC licence examination syllabus (Nepal Engineering Council).
Serializability
The correctness criterion for concurrent execution — and the precedence graph that tests it mechanically.
🌍 Where this lives: serializability is the definition of "correct" that every concurrency-control algorithm is trying to achieve. It matters because it is the only criterion that lets a programmer reason about a transaction in isolation — you write your logic as if nothing else is running, and the system guarantees the outcome is as if that were true. Every alternative (eventual consistency, snapshot isolation) shifts some reasoning burden back onto you, which is why distributed systems that weaken it publish long documents explaining which anomalies you must now handle yourself. Search "serializability the gold standard isolation".
Conflicting operations
Two operations CONFLICT if they belong to DIFFERENT
transactions, access the SAME data item, and at least one is
a WRITE.
T2: READ T2: WRITE
T1: READ no conflict CONFLICT
T1: WRITE CONFLICT CONFLICT
· read–read never conflicts (order does not matter)
· read–write conflicts (RW)
· write–read conflicts (WR)
· write–write conflicts (WW)
WHY IT MATTERS: only conflicting operations constrain the
order. Non-conflicting operations may be swapped freely
without changing the outcome, and that swapping is exactly how
we test equivalence.
CONFLICT SERIALIZABILITY
A schedule S is conflict-serializable if it can be
transformed into SOME serial schedule by swapping only
NON-CONFLICTING adjacent operations.
If it can, the schedule produces the same result as that
serial one, so it is correct.
VIEW SERIALIZABILITY — a weaker, more permissive criterion.
Every conflict-serializable schedule is view-serializable,
but not the reverse. Testing view serializability is
NP-complete, so no real DBMS uses it.
Conflict serializability ⊂ View serializability
Practical consequence: real systems test conflict
serializability, which means they occasionally reject a
schedule that was in fact harmless. That is an acceptable
trade for a polynomial-time test.
The precedence graph test
ALGORITHM — the standard exam procedure.
1. Draw one NODE per transaction.
2. Draw an EDGE Ti → Tj whenever an operation of Ti
CONFLICTS with a LATER operation of Tj on the same item:
Ti: R(X) ... Tj: W(X) RW edge
Ti: W(X) ... Tj: R(X) WR edge
Ti: W(X) ... Tj: W(X) WW edge
3. The schedule is CONFLICT-SERIALIZABLE if and only if the
graph is ACYCLIC.
4. If acyclic, a TOPOLOGICAL SORT gives an equivalent
serial order.
WORKED EXAMPLE 1 — serializable
S1: T1:R(A) T2:R(A) T1:W(B) T2:W(A) T1:R(B)
Find the conflicts:
T1:R(A) … T2:W(A) → edge T1 → T2 (RW on A)
T2:R(A) … T2:W(A) same transaction, ignore
T1:W(B) … T1:R(B) same transaction, ignore
Graph: T1 → T2 no cycle ✔ SERIALIZABLE
Equivalent serial order: T1, T2
WORKED EXAMPLE 2 — NOT serializable
S2: T1:R(A) T2:W(A) T2:C T1:W(A) T1:C
Conflicts:
T1:R(A) … T2:W(A) → T1 → T2 (RW)
T2:W(A) … T1:W(A) → T2 → T1 (WW)
Graph: T1 ⇄ T2 CYCLE ✗ NOT SERIALIZABLE
And indeed this is the LOST UPDATE anomaly: T1 read A,
T2 wrote it, T1 overwrote. No serial order produces this.
WORKED EXAMPLE 3 — three transactions
S3: T1:R(X) T2:R(Y) T3:W(X) T1:W(Y) T2:R(X)
Conflicts:
T1:R(X) … T3:W(X) → T1 → T3 (RW on X)
T3:W(X) … T2:R(X) → T3 → T2 (WR on X)
T2:R(Y) … T1:W(Y) → T2 → T1 (RW on Y)
Graph: T1 → T3 → T2 → T1 CYCLE ✗ NOT SERIALIZABLE
Three edges forming a cycle of length 3. This is why you
must check ALL conflicts, not just pairs — a cycle can
span any number of transactions.
WORKED EXAMPLE 4 — acyclic with three transactions
S4: T1:R(A) T1:W(A) T2:R(A) T2:W(A) T3:R(A) T3:W(A)
Conflicts (all on A):
T1:W(A) … T2:R(A) → T1 → T2
T1:W(A) … T2:W(A) → T1 → T2 (same edge)
T2:W(A) … T3:R(A) → T2 → T3
T2:W(A) … T3:W(A) → T2 → T3 (same edge)
Graph: T1 → T2 → T3 acyclic ✔ SERIALIZABLE
Serial order: T1, T2, T3 — which is in fact what the
schedule already is.
Recoverability — a second, independent requirement
Serializability is not enough. A schedule must also be
RECOVERABLE, meaning an abort never forces you to undo an
already-committed transaction.
THREE CLASSES, from weakest to strongest:
1. RECOVERABLE SCHEDULE
If Tj reads a value written by Ti, then Ti must COMMIT
BEFORE Tj commits.
NON-RECOVERABLE example:
T1: W(A)
T2: R(A) ← reads T1's uncommitted value
T2: COMMIT ← commits first!
T1: ABORT ← now T2 must be undone, but it is
already committed. IMPOSSIBLE.
→ this schedule must never be allowed.
2. CASCADELESS (avoids cascading rollback)
Tj may read a value written by Ti only AFTER Ti has
committed.
CASCADING ROLLBACK example (recoverable but not
cascadeless):
T1: W(A)
T2: R(A) W(B)
T3: R(B) W(C)
T1: ABORT → T2 must abort → T3 must abort
One abort cascades into three. Recoverable, but expensive
and unpredictable.
3. STRICT SCHEDULE
Tj may neither READ nor WRITE an item until the
transaction that last wrote it has committed or aborted.
→ makes recovery simple: undo is just restoring the
before-image, because no one else touched it.
Strict ⊂ Cascadeless ⊂ Recoverable
STRICT 2PL produces strict schedules, which is why it is the
protocol real systems use — it gives serializability AND
strictness together.
THE TWO INDEPENDENT AXES, which exam answers often conflate:
serializability → is the RESULT correct?
recoverability → can an ABORT be handled?
A schedule can be serializable and non-recoverable, or
recoverable and non-serializable. Both properties are
required.
Testing a schedule — the full procedure
test_schedule.txt
GIVEN SCHEDULE
T1: R(A) W(A) R(B) W(B) C
T2: R(A) W(A) C
T3: R(B) W(B) C
Written as a linear sequence:
1. T1:R(A)
2. T2:R(A)
3. T2:W(A)
4. T1:W(A)
5. T3:R(B)
6. T1:R(B)
7. T1:W(B)
8. T1:C
9. T2:C
10. T3:W(B)
11. T3:C
STEP 1 — list every conflicting pair (different transactions,
same item, at least one write):
op1 T1:R(A) vs op3 T2:W(A) → T1 → T2 RW on A
op2 T2:R(A) vs op4 T1:W(A) → T2 → T1 RW on A
op3 T2:W(A) vs op4 T1:W(A) → T2 → T1 WW on A
op5 T3:R(B) vs op7 T1:W(B) → T3 → T1 RW on B
op7 T1:W(B) vs op10 T3:W(B) → T1 → T3 WW on B
STEP 2 — build the graph:
T1 ──RW──► T2
T2 ──RW,WW──► T1 ← already a cycle
T3 ──RW──► T1
T1 ──WW──► T3 ← another cycle
STEP 3 — check for cycles:
T1 → T2 → T1 CYCLE
T1 → T3 → T1 CYCLE
→ NOT CONFLICT-SERIALIZABLE ✗
STEP 4 — also check recoverability:
Does any transaction read an uncommitted write?
op4 T1:W(A) happens after op3 T2:W(A), and T2 commits at
op9 AFTER T1 commits at op8 — a write-write dependency
with the writer committing later.
op10 T3:W(B) writes an item T1 wrote, and T1 committed at
op8 first, so that part is fine.
The A-conflict makes this non-strict as well.
CONCLUSION: reject the schedule. A concurrency-control
protocol must prevent it from arising, which is exactly what
2PL does — under 2PL, T2 could not have written A while T1
still held a read lock on it.
🌍 Go further: the precedence graph is a beautiful test that no production DBMS actually runs — building it requires knowing the whole schedule in advance, and a live system does not. Real systems use protocols that guarantee acyclicity by construction (two-phase locking) or detect cycles incrementally at runtime (PostgreSQL's SSI tracks read-write dependencies and aborts a transaction when a dangerous structure forms). The theory tells you what correct means; the protocol is how you get there online. Search "serializable snapshot isolation dangerous structure" — the "pivot" in the error message from the previous topic is exactly that.
💡 Exam angle: the precedence graph test is the guaranteed question — draw nodes for transactions, add an edge for each conflicting pair in schedule order, and declare serializable iff acyclic, giving the topological order as the equivalent serial schedule. State the conflict matrix (only read–read is safe). Distinguish conflict from view serializability and note the latter is NP-complete to test. Know the three recoverability classes (recoverable ⊃ cascadeless ⊃ strict) and that serializability and recoverability are independent requirements.
Syllabus points
Conflict & view serializability
Precedence graph (numerical)
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.
Related topics in Transaction Processing, Concurrency Control & Recovery