🔀

Serializability in DBMS

Conflict-serializable schedules — the formal test for "is this interleaving safe?" Get the speed of concurrency with the correctness of serial execution, proven with one mechanical tool: the precedence graph.

Schedules Conflicts Precedence Graph Cycle Test

Press Next → or use ← → arrow keys

Section 01

The Story — Two Chefs, One Kitchen

👨‍🍳 REAL-WORLD ANALOGY

Interleaving is fine — until they touch the same pot

Chef T1 bakes a cake; chef T2 makes soup. Working one-after-another is always correct — that's a serial schedule — but it wastes the kitchen. Interleaving (T1 uses the oven while T2 chops) is faster and usually fine. Trouble strikes only when both touch the same ingredient and at least one changes it — T2 salts a stock T1 already tasted. Now the result depends on who touched it when.

❓

The Core Question

"Can this interleaved schedule produce the same result as some serial one?" If yes, it's safe — concurrency and correctness. That property is serializability.

Section 02

Serial · Non-Serial · Serializable

🧱

Serial

Transactions run back-to-back, no interleaving. Always correct — but wastes parallelism. With n transactions there are n! serial orders.

🔀

Non-serial

Operations of different transactions are mixed. Fast, but some interleavings corrupt data — only some are safe.

✅

Serializable

A non-serial schedule whose outcome equals some serial one — the speed of interleaving with the safety of serial.

🪜

The Hierarchy

Serial ⊂ Conflict Serializable ⊂ View Serializable ⊂ All Schedules. Every conflict-serializable schedule is serializable — but not every serializable one is conflict-serializable (that wider class is view serializability, which is NP-hard to test).

Section 03

When Do Two Operations Conflict?

Two operations conflict if — and only if — all three hold at once:

1️⃣

Different transactions

Same-transaction order is fixed by the program — never a conflict.

2️⃣

Same data item

Operations on different items never interfere.

3️⃣

At least one Write

Two reads can't change any outcome.

Pair (same item X, different txns)	Conflict?	Name	Reason
Read(X) … Read(X)	NO	—	Two reads never change a result
Read(X) … Write(X)	YES	RW	Swap and the read sees a different value
Write(X) … Read(X)	YES	WR	Read depends on whether the write came first
Write(X) … Write(X)	YES	WW	Final value depends on which write is last

🪤

The Exam Trap

Different items → never conflict. Same transaction → never conflict. Read–Read is the only same-item, different-transaction pair that is safe.

Section 04

Conflict Equivalence by Swapping

Two schedules are conflict equivalent if one becomes the other by swapping only adjacent, non-conflicting operations. A schedule is conflict serializable if it's conflict-equivalent to some serial schedule.

🔧 PROVING S ≡ SERIAL BY SWAPS · items X, Y

S

R1(X) W1(X) R2(X) R1(Y) W2(X) W1(Y)

1

Swap R1(Y) & R2(X) — different items → R1(X) W1(X) R1(Y) R2(X) W2(X) W1(Y)

2

Swap W1(Y) past W2(X) then R2(X) — different items → R1(X) W1(X) R1(Y) W1(Y) R2(X) W2(X)

✓

That's the serial schedule T1 → T2. So S is conflict serializable.

💡

Swapping by Hand Is Slow

For anything bigger than a toy schedule, we need a faster, mechanical test — the precedence graph.

Section 05

The Precedence Graph Test

📐 FOUR MECHANICAL STEPS

1

One node per transaction — never a node for a data item.

2

Add edge Ti → Tj whenever an op of Ti conflicts with a later op of Tj (RW, WR, WW on the same item). Duplicate edges collapse.

3

Check for a cycle. No cycle → conflict serializable. Any cycle → not. (Linear time.)

4

Topological sort the acyclic graph → an equivalent serial order. Edge Ti → Tj means "Ti before Tj."

⚡

The Speed Technique

Hunt conflicts item by item, not line by line: list each item's operations in time order and draw edges only between pairs where at least one is a Write.

Numerical 1

A Serializable Schedule

Schedule S1

Time	T1	T2
t1	R1(A)
t2	W1(A)
t3		R2(A)
t4		W2(A)
t5	R1(B)
t6	W1(B)

Item B: only T1 touches it → no conflict.

✅

Conflict Serializable — order T1 → T2

All three conflicts on A (WR, RW, WW) collapse into the single edge T1 → T2. One arrow can't form a cycle → acyclic → serializable. The interleaving behaves like running T1 fully, then T2 fully.

Numerical 2

A Non-Serializable Schedule — The Cycle

Schedule S2 · the lost-update pattern

Time	T1	T2
t1	R1(X)
t2		R2(X)
t3		W2(X)
t4	W1(X)

✗

NOT Conflict Serializable

R1(X) before W2(X) gives T1 → T2; R2(X) before W1(X) gives T2 → T1. Two opposing arrows = a cycle. T1 must come both before and after T2 — impossible. A real DBMS would abort one transaction (deadlock victim / serialization failure).

Numerical 3

Three Transactions — Exam Level

Schedule S3

Time	T1	T2	T3
t1	R1(X)
t2			R3(X)
t3		R2(Y)
t4	W1(Y)
t5		W2(X)
t6			W3(Y)

✗

NOT Conflict Serializable

Edges: T1→T2, T3→T2, T2→T1, T2→T3, T1→T3. The two-node cycle T1 → T2 → T1 settles it (T2 ⇄ T3 exists too). One cycle is enough to reject.

Solved · Serializable

Reading Off the Serial Order

S: R1(x) R3(y) R3(x) R2(y) R2(z) W3(y) W2(z) R1(z) W1(x) W1(z)

🔍

Conflicts, item by item

x: R3(x) before W1(x) → T3→T1
y: R2(y) before W3(y) → T2→T3
z: W2(z)/R1(z), R2(z)/W1(z), W2(z)/W1(z) → T2→T1

✅

Acyclic → Serial Order T2 → T3 → T1

Edges T2→T1, T2→T3, T3→T1 all flow one way. T2 has no incoming edge, then T3, then T1. Equivalent serial schedule: T2 → T3 → T1.

Pattern

Three Shapes, Three Verdicts

➡️

One-way triangle

All arrows flow one direction → acyclic → exactly one serial order.

🔄

Any two-way pair

Ti ⇄ Tj → instant cycle → reject immediately. One cycle is enough.

🔱

Unconnected nodes

No edge between two nodes → multiple valid serial orders (e.g. T2→T3→T1 and T3→T2→T1).

🎯

Reading the Graph at a Glance

A node with no incoming edges goes first in the serial order. If two such nodes exist, either can lead — that's why some schedules have more than one correct answer.

Section 10

Counting Schedules

Transactions T1 and T2 have m = 3 and n = 2 operations. How many schedules exist?

🔢

Total schedules

(m+n)! / (m! · n!) = 120 / 12 = 10. Choose which time slots belong to T1; each transaction's internal order is fixed.

🧱

Serial schedules

k! for k transactions = 2! = 2 (T1→T2 and T2→T1).

➖

Non-Serial = 10 − 2 = 8

Eight non-serial schedules — and only some of those are conflict serializable. Each must be tested with its own precedence graph.

Sections 04 & 11

Conflict vs View · Theory vs Practice

🎓

Conflict vs View serializability

Conflict serializability is stricter and tested in polynomial time (the graph). View serializability is broader — it accepts some schedules with blind writes that conflict-analysis rejects — but testing it is NP-hard. Every conflict-serializable schedule is view-serializable, not vice versa.

🏭

Industry reality

Engines don't test schedules after the fact — they prevent bad interleavings. 2PL guarantees conflict-serializable schedules by construction; MVCC / SSI (e.g. PostgreSQL) aborts a transaction when a dangerous cycle looms. Your app must retry on serialization-failure errors.

⚖️

The Engineering Trade-off

Stricter isolation → fewer anomalies but more blocking/aborts. Weaker → faster, but the app must reason about anomalies. Serializable is the only level where you never reason about interleavings at all.

Section 12

Rapid-Fire Concept Check

Question	Answer
Two reads on same item, different txns — conflict?	No (the only Write-free pair)
Test for conflict serializability	Precedence (serialization) graph
Graph has a cycle → verdict?	Not conflict serializable
Acyclic → how to get serial order?	Topological sort
Edge Ti → Tj means	Ti must precede Tj
Serial schedules for k transactions	k!
Broader class, NP-hard to test	View serializability
Protocol guaranteeing conflict-serializable schedules	Two-Phase Locking (2PL)

Section 13

Golden Rules of Serializability

🏆 NON-NEGOTIABLE PRINCIPLES

1

A conflict needs all three: different transactions, same item, at least one Write. Miss one → no edge.

2

Nodes = transactions, edges = conflicts (earlier op → later op's transaction). Never draw a node for a data item.

3

One cycle is enough to reject — stop as soon as you find it. To accept, check all conflict pairs.

4

Hunt conflicts item by item, listing each item's ops in time order — faster and less error-prone than line by line.

5

An acyclic graph's topological order is your equivalent serial schedule — and multiple orders can all be valid.

6

Hierarchy: Serial ⊂ Conflict ⊂ View ⊂ All. Industry prevents via 2PL / SSI — always retry on serialization failures.

FINAL

Draw the Graph, Find the Cycle

1Node per transaction

RW·WR·WWConflict types

Cycle= not serializable

TopoSort= serial order

🎯

The Whole Method in One Breath

A schedule is safe if it behaves like some serial order. To check: draw one node per transaction, add an edge for every conflict (same item, at least one write, earlier→later), and look for a cycle. No cycle → conflict serializable, and any topological order is your equivalent serial schedule. A cycle → reject.

🧠

One Sentence to Remember

Conflicts become arrows; arrows that loop mean "impossible order." No loop = safe — next stop: recoverability and the locking protocols (2PL) that enforce all this live.

🔀 End of tutorial · Press ← to review, or click Restart