View serializability; blind writes; relation to conflict serializability

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. When is a schedule conflict serializable? from Lesson 6.4.2
2. Do two reads of the same item by different transactions conflict? from Lesson 6.4.2
3. How many topological orders does a 3-vertex graph with no edges have? from Lesson 6.4.1

1 · The Hook

S = R1(A) W2(A) W1(A) W3(A). The precedence graph has T1 → T2 and T2 → T1: not conflict serializable. Yet run it and compare with the serial T1, T2, T3: T1 reads the initial A in both, and T3 writes the final A in both. Nobody reads what T1 or T2 wrote, so their writes do not matter. The schedule is perfectly fine. View serializability recognises such schedules.

2 · Predict First

In S = R1(A) W2(A) W1(A) W3(A), which transaction's write of A is the one left in the database at the end? Does anybody ever read the values written by T1 or T2?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

T3's write is final. Nobody reads T1's or T2's writes. So any order where T1 reads first and T3 writes last gives the same result: S is view equivalent to T1, T2, T3.

View equivalence

Schedules S and S′ (same transactions) are view equivalent if, for every data item X:

1. Initial reads: if Ti reads the initial value of X in S, it does so in S′.
2. Reads-from: if Ti reads the value of X written by Tj in S, it reads the value written by Tj in S′.
3. Final writes: the transaction that performs the last write of X in S does so in S′.

Reads see the same values and the final database is the same, so the two schedules are indistinguishable.

View serializability (VS)

S is view serializable if it is view equivalent to some serial schedule.

Relationship with conflict serializability

• Every CS schedule is VS.
• A schedule that is VS but not CS always contains a blind write: a write of an item the transaction never read first (W2(A), W3(A) above).
• If a schedule has no blind writes, VS ⇔ CS.

Testing VS (small schedules)

1. If CS → VS. Done.
2. If not CS and there is no blind write → not VS.
3. Otherwise compute, for each item, the initial readers, the reads-from pairs and the final writer, and try the serial orders consistent with them. (Testing VS in general is NP-complete; exam schedules are small.)

Worked check

S = R1(A) W2(A) W1(A) W3(A).

• Initial read of A: T1. Reads-from: none. Final write of A: T3.
• Serial order must put T1 before any writer of A that it would otherwise read from (T1 must read the initial A → T1 before T2 and T3) and T3 last. Order T1, T2, T3 works. VS, not CS.

Another example (not VS)

S = R1(A) R2(A) W1(A) W2(A) (lost update). No blind writes and not CS → not VS. Check: both read initial A, final writer T2. Serial T1;T2 makes T2 read T1's A. Serial T2;T1 makes T1 read T2's A and T1 the final writer. Neither matches.

4 · Visual

S = R1(A)  W2(A)  W1(A)  W3(A)

initial read of A : T1          reads-from : none          final write of A : T3

serial T1,T2,T3 = R1(A) W1(A) W2(A) W3(A)
  initial read T1 ✓   reads-from none ✓   final write T3 ✓     -> view equivalent

precedence graph: T1->T2 (R1 before W2), T2->T1 (W2 before W1): cycle -> not CS
blind writes W2(A), W3(A) make VS possible without CS

5 · Worked Examples

Example 1 Easy

Is every conflict serializable schedule view serializable?

Solution

Yes. CS ⊂ VS.

Example 2 Medium

S = W1(A) W2(A) W2(B) W1(B). VS? CS?

Solution

Precedence: W1(A) before W2(A): T1 → T2; W2(B) before W1(B): T2 → T1 → not CS. Final writers: A → T2, B → T1; no reads. Serial T1;T2 gives final B by T2; T2;T1 gives final A by T1. Neither matches: not VS (blind writes alone do not guarantee VS).

Example 3 GATE

S = R1(A) W2(A) R3(A) W1(A) W3(A). VS?

Solution

Initial read: T1 (R1(A)). Reads-from: R3(A) reads from T2. Final write: T3. Serial order needs T1 first (reads initial), T2 before T3 (T3 reads T2's A, so T1 cannot write between them), T3 last: try T1, T2, T3 = R1 W1 W2 R3 W3: T3 reads from T2 ✓, final T3 ✓, T1 initial ✓. VS. (Not CS: R1(A) → W2(A) gives T1 → T2, W2(A) before W1(A) gives T2 → T1.)

8 · Connect the Dots

Chapter 6.4 is complete: conflict and view serializability. Serializability says nothing about what happens when a transaction aborts. Next: the Chapter 6.4 Lock-in, then recoverability: recoverable, cascadeless and strict schedules.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — VS vs CS

A schedule is view serializable but not conflict serializable. It must contain:

1. (A) an abort
2. (B) a blind write
3. (C) a dirty read
4. (D) a deadlock

Q2 · MCQ · 2 mark(s) — Test

S = R1(A) W2(A) W1(A) W3(A) is:

1. (A) CS and VS
2. (B) VS but not CS
3. (C) neither
4. (D) CS but not VS

Q3 · MCQ · 2 mark(s) — Test

S = R1(A) R2(A) W1(A) W2(A) is:

1. (A) CS
2. (B) serial
3. (C) VS but not CS
4. (D) neither CS nor VS

Q4 · MSQ · 2 mark(s) — Facts

Which are true?

1. (A) Every schedule with a blind write is VS.
2. (B) Testing VS is in general harder than testing CS.
3. (C) If a schedule has no blind writes, VS implies CS.
4. (D) CS ⊂ VS.

Q5 · MCQ · 2 mark(s) — Final writer

In S = W1(X) R2(X) W3(X) W2(X), which transaction makes the final write of X?

1. (A) T2
2. (B) T3
3. (C) none
4. (D) T1

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

view equivalenceinitial readreads-fromfinal writeview serializability (VS)blind writeCS ⊂ VS