View Serializability
Press Next → or use ← → arrow keys
The Story — The Whiteboard Photo
A schedule S is view serializable if it is view equivalent to some serial schedule of the same transactions. It's a result-based test — what matters is the final picture, not the exact conflict order.
The Three Rules of View Equivalence
Two schedules are view equivalent iff all three hold for every data item:
"Same first read, same who-wrote-what-you-read, same last write." Agree on all three, for every item, and the two schedules are indistinguishable by result.
Blind Writes — The Source of the Gap
A blind write Wi(X) is a write of X by Ti that is not preceded by Ri(X) in the same transaction. Ti overwrites X without knowing its current value.
| Transaction ops | Blind? | Reason |
|---|---|---|
| W(A) | YES | Writes A with no prior read |
| R(A), W(A) | NO | R(A) precedes W(A) |
| R(B), W(A) | YES | Reading B doesn't inform W(A) — blindness is per item |
| W(A), R(A), W(A) | YES | First W(A) blind; second is informed by R(A) |
| W(A), W(A) | YES | Both blind — an earlier write doesn't count as a "read" |
Blindness is per item (reading B never informs W(A)) and per transaction (another transaction's read doesn't inform your write). When in doubt: "Did THIS transaction read THIS item before this Write?"
Blind Writes in Real SQL
| SQL statement | Blind? | Why |
|---|---|---|
| INSERT INTO orders VALUES (…) | YES | Inserts create new rows — no prior read possible |
| UPDATE accounts SET balance = 0 WHERE id = 7 | YES | New value doesn't depend on the old; no SELECT precedes it |
| UPDATE accounts SET balance = balance + 100 … | NO | The right-hand side reads balance first — an implicit read |
| SELECT … FOR UPDATE then UPDATE | NO | The explicit SELECT supplies the prior read |
| DELETE FROM cache WHERE key = 'x' | YES | DELETE writes without needing to read first |
Without blind writes, view serializability and conflict serializability are equivalent. Blind writes are the only source of the gap between the two classes.
The Hierarchy of Schedule Classes
Every conflict-serializable schedule is view serializable — but not vice versa. The thin ring between View and Conflict exists only because of blind writes: "useless" intermediate writes overwritten before anyone reads them.
Why Industry Skips View Serializability
| Class | Test cost | What it catches | Used in practice? |
|---|---|---|---|
| Serial | O(1) | Trivially safe | Too slow |
| Conflict serializable | Polynomial | Most useful safe schedules | Yes — 2PL, SSI |
| View serializable | NP-complete | A few extra with blind writes | No — theoretical |
| All schedules | — | Includes anomalous ones | Not safe |
Testing view serializability is NP-complete — you may have to try all k! serial orders. Real engines never compute it; they use conflict serializability (2PL, SSI) and accept losing a few blind-write schedules.
How to Check View Serializability
If the precedence graph is acyclic you're finished — VS is free. Only a cycle forces you to hunt for blind writes and test serial orders.
View Serializable — But NOT Conflict
S1: R1(A) W2(A) W1(A) W3(A)
| Time | T1 | T2 | T3 |
|---|---|---|---|
| t1 | R(A) | ||
| t2 | W(A) | ||
| t3 | W(A) | ||
| t4 | W(A) |
Edges on A: T1→T2 (RW), T2→T1 (WW), plus T2→T3, T1→T3. The cycle T1 ⇄ T2 → not conflict serializable.
T2 and T3 write A with no prior read → both blind. So we test serial orders.
First read = T1 ✓, no cross read-froms ✓, last write = T3 ✓. View serializable. W2(A) is overwritten by W3(A) and never read — its order is irrelevant.
Neither View nor Conflict
S2: R1(A) R2(A) W1(A) W2(A) — the classic lost update
| Time | T1 | T2 |
|---|---|---|
| t1 | R(A) | |
| t2 | R(A) | |
| t3 | W(A) | |
| t4 | W(A) |
R1(A) before W2(A) → T1→T2; R2(A) before W1(A) → T2→T1; W1 before W2 → T1→T2. Cycle T1 ⇄ T2.
Both T1 and T2 do R(A) then W(A) — neither is blind.
Cycle in the graph and no blind write → the verdict is final. No need to test any serial order. This is the classic lost-update anomaly.
Blind Write Present — Yet Still Not VS
S3: R1(A) W2(A) R3(A) W1(A)
| Time | T1 | T2 | T3 |
|---|---|---|---|
| t1 | R(A) | ||
| t2 | W(A) | ||
| t3 | R(A) | ||
| t4 | W(A) |
Preserve: initial read = T1 · T3 reads-from T2 · final write = T1.
Edges give cycle T1 ⇄ T2; T2's W(A) is blind — so we must test serial orders.
T2→T3→T1: first read becomes T3 ✗. T1→T2→T3: first read T1 ✓, T3-from-T2 ✓, but last write becomes T2, not T1 ✗. All others fail too.
A blind write is necessary but not sufficient for "VS but not CS." Here no serial order preserves initial read and read-from and final write together.
The Three Numericals, Side by Side
| # | Schedule | Cycle? | Blind writes? | Serial match? | Verdict |
|---|---|---|---|---|---|
| 1 | R1(A) W2(A) W1(A) W3(A) | Yes | Yes (T2, T3) | Yes — T1→T2→T3 | ✅ VS only |
| 2 | R1(A) R2(A) W1(A) W2(A) | Yes | No | — | ❌ Neither |
| 3 | R1(A) W2(A) R3(A) W1(A) | Yes | Yes (T2) | No | ❌ Neither |
Acyclic → VS. Cyclic + no blind write → not VS. Cyclic + blind write → test serial orders (may go either way). The exam's "VS but not CS" answer always hides a blind write overwritten before anyone reads it.
Conflict vs View Serializability
| Aspect | Conflict serializable | View serializable |
|---|---|---|
| Based on | Conflict order (RW/WR/WW) | Final result (the three rules) |
| Test | Precedence graph — polynomial | Try serial orders — NP-complete |
| Class size | Smaller (subset) | Larger (superset) |
| Extra schedules | — | Ones with harmless blind writes |
| Used in real DBMS | Yes — 2PL, SSI | No — teaching / theory |
Conflict serializability cares how you got there (the order of conflicts). View serializability cares only where you ended up (the final photo). Blind writes are what let the paths differ but the destination match.
Rapid-Fire Concept Check
| Question | Answer |
|---|---|
| The three rules of view equivalence | Initial read · updated read · final write |
| A write with no prior read in that txn | Blind write |
| Conflict serializable ⇒ view serializable? | Yes (always) |
| View serializable ⇒ conflict serializable? | Not necessarily |
| Without blind writes, VS = ? | CS |
| Complexity of testing VS | NP-complete |
| Cycle + no blind write → verdict? | Not view serializable |
| Cycle + blind write → verdict? | Test serial orders — may go either way |
| What real engines use instead | Conflict serializability (2PL, SSI) |
Golden Rules of View Serializability
Same Photo, Different Path
View serializability judges a schedule by its final result — same first read, same read-from, same last write — not by conflict order. That lets a few extra schedules through, always ones with blind writes overwritten before they're read. It's a strictly broader class than conflict serializability, but NP-complete to test, so real engines stick with the precedence graph.
Acyclic graph? View serializable. Cyclic with no blind write? Not. Cyclic with a blind write? Test the serial orders — next stop: recoverability and the locking protocols that enforce all this live.
📸 End of tutorial · Press ← to review, or click Restart