View Serializability

We now have two formal criteria for schedule correctness: conflict serializability and view serializability. Both aim to identify schedules that are 'equivalent' to some serial schedule, but they define 'equivalence' differently.

Conflict serializability focuses on the structure of operations—specifically, the order of conflicting operations. View serializability focuses on the semantics—what values transactions read and what values persist.

This distinction has profound implications:

• View serializability is more permissive (accepts more schedules)
• Conflict serializability is more practical (efficient to test)
• Understanding both illuminates the fundamental tradeoffs in concurrency control

This page provides a rigorous, comprehensive comparison that reveals when and why these criteria differ.

Before comparing view and conflict serializability specifically, let's situate them within the broader hierarchy of schedule classes.

The Complete Hierarchy (from most restrictive to least restrictive):

1. Serial Schedules — No interleaving; transactions execute one at a time
2. Conflict Serializable (CSR) — Conflict equivalent to some serial schedule
3. View Serializable (VSR) — View equivalent to some serial schedule
4. All Schedules — Any interleaving of transaction operations

Containment Relationships:

• Serial ⊂ CSR ⊂ VSR ⊂ All Schedules
• Each class is a proper subset of the next
• The differences between adjacent classes are non-empty

What Each Set Difference Contains:

Our focus is on VSR \ CSR: those schedules that view serializability accepts but conflict serializability rejects.

Let's briefly recap conflict serializability to enable precise comparison.

Conflict Definition:

Two operations conflict if:

1. They belong to different transactions
2. They access the same data item
3. At least one is a write operation

Types of Conflicts:

• Read-Write (RW): Rᵢ(X) and Wⱼ(X) — T₁ reads, Tⱼ writes
• Write-Read (WR): Wᵢ(X) and Rⱼ(X) — Tᵢ writes, Tⱼ reads
• Write-Write (WW): Wᵢ(X) and Wⱼ(X) — both write

Conflict Equivalence:

Two schedules S and S' are conflict equivalent if S' can be obtained from S by swapping non-conflicting adjacent operations.

Conflict Serializability:

A schedule S is conflict serializable if it is conflict equivalent to some serial schedule. Tested via precedence graph (acyclic = conflict serializable).

The Precedence Graph:

For a schedule S:

1. Create a node for each transaction
2. Add directed edge Tᵢ → Tⱼ if there's a conflict where Tᵢ's operation precedes Tⱼ's operation
3. S is conflict serializable ⟺ the precedence graph is acyclic

Key Property: Conflict serializability treats ALL conflicts as order-sensitive. If Wᵢ(X) precedes Wⱼ(X), this creates an edge Tᵢ → Tⱼ regardless of whether anyone reads between them. This is more conservative than necessary for semantic correctness.

Now let's recap view serializability with the same precision.

View Equivalence Conditions:

Two schedules S and S' are view equivalent (S ≡ᵥ S') if:

1. Same initial reads: Same transactions read initial values
2. Same read-from relationships: Tⱼ →X Tᵢ in S ⟺ Tⱼ →X Tᵢ in S'
3. Same final writes: Same transactions perform final writes to each data item

View Serializability:

A schedule S is view serializable if there exists a serial schedule S' such that S ≡ᵥ S'.

Key Property: View serializability cares about outcomes—what's read, what persists—not about the structural ordering of operations. If two writes to the same data item both get overwritten before any read, their relative order is semantically irrelevant.

Why View Serializability is More Permissive:

Conflict serializability considers ALL write-write conflicts as ordering constraints. But for view equivalence, a write-write conflict only matters if:

1. Some transaction reads the intermediate value, OR
2. The conflicting write is the final write to that data item

If a write is:

• A blind write (no preceding read)
• Never read by any transaction
• Overwritten by another write before any read

Then its position relative to other such writes is semantically irrelevant. View serializability recognizes this; conflict serializability does not.

Theorem: CSR ⊂ VSR (Proper Subset)

Proof:

Part 1: CSR ⊆ VSR (Every conflict serializable schedule is view serializable)

Let S be conflict serializable. Then S is conflict equivalent to some serial schedule S'. We show S ≡ᵥ S' (view equivalent):

1. Initial reads preserved: In transforming S to S', we only swap non-conflicting operations. Swapping doesn't change which reads occur before any writes (no R-W swap for the same item before that read). Initial reads are preserved.

2. Read-from preserved: If Tⱼ →X Tᵢ in S, then Wⱼ(X) precedes Rᵢ(X) with no intervening write to X. Swapping non-conflicting operations cannot change this relationship (any operation that could intervene would conflict with either Wⱼ(X) or Rᵢ(X)).

3. Final writes preserved: The last write Wᵢ(X) remains the last write after non-conflicting swaps. For another write Wⱼ(X) to become last, it would need to swap past Wᵢ(X), but Wⱼ(X) and Wᵢ(X) conflict—no swap possible.

Thus S ≡ᵥ S', so S is view serializable. ∎

Part 2: CSR ≠ VSR (There exist view serializable schedules that are not conflict serializable)

We've already seen the example with blind writes. This completes the proof that CSR ⊂ VSR (proper subset). ∎

We can precisely characterize when view serializability and conflict serializability differ.

Theorem: A schedule is in VSR \ CSR (view serializable but not conflict serializable) if and only if:

1. It is view serializable (view equivalent to some serial schedule), AND
2. It contains blind writes whose values are never read and are overwritten

Proof Sketch:

(⟹) If S ∈ VSR \ CSR, then S has a WW conflict with reversed order between S and its equivalent serial schedule S'. This WW conflict involves writes where:

• The earlier write in S (say Wᵢ(X)) becomes the later write in S'
• For this to preserve view equivalence, no transaction can read Wᵢ(X)'s value
• Thus Wᵢ(X) must be overwritten before being read → blind write overwritten

(⟸) If S has blind writes that are overwritten without being read, these writes can be reordered in a serial equivalent without affecting view equivalence, but the conflict equivalence would require preserving their order.

Analysis of the Example:

Conflict Serializability Test:

Precedence Graph Edges:

• R₁(A) before W₂(A): Conflict → T₁ → T₂
• W₂(A) before W₁(A): Conflict → T₂ → T₁
• W₁(A) before W₃(A): Conflict → T₁ → T₃

Cycle detected: T₁ → T₂ → T₁ ⟹ Not conflict serializable

View Serializability Test:

In S:

• R₁(A) reads initial value
• No transaction reads T₂'s value (W₂(A) is overwritten by W₁(A))
• No transaction reads T₁'s value (W₁(A) is overwritten by W₃(A))
• Final write is W₃(A)

Serial Schedule T₁; T₂; T₃:

• R₁(A) reads initial value ✓
• W₁(A), then W₂(A), then W₃(A)
• Final write is W₃(A) ✓
• Read-from: only initial read, preserved ✓

S ≡ᵥ (T₁; T₂; T₃) ⟹ View serializable

Given that view serializability accepts more schedules (potentially allowing more concurrency), why do real database systems use conflict serializability instead?

The answer is a fundamental tradeoff between theoretical permissiveness and practical feasibility.

An important observation: for many practical scenarios, conflict and view serializability are equivalent—any VSR schedule is also CSR.

Theorem: If a schedule contains no blind writes (every write is preceded by a read of the same item by the same transaction), then:

CSR = VSR

Proof Sketch:

We already know CSR ⊆ VSR. We need to show that without blind writes, VSR ⊆ CSR.

Without blind writes, every write Wᵢ(X) is preceded by Rᵢ(X). If S is view equivalent to serial S', then:

• All RW and WR conflicts must have the same relative order (otherwise read-from would differ)
• All WW conflicts must also have consistent orders because the preceding reads force a particular serialization

The lack of blind writes means WW conflict orders are determined by the corresponding RW/WR conflicts, leaving no room for VSR \ CSR schedules. ∎

Practical Implication:

In practice, most database applications use transactions with read-modify-write semantics:

-- Typical transaction pattern
BEGIN;
SELECT balance FROM accounts WHERE id = 123;  -- Read
UPDATE accounts SET balance = balance + 100 WHERE id = 123;  -- Write
COMMIT;

This pattern eliminates blind writes: the UPDATE is preceded by the SELECT. For such workloads, conflict serializability is not just a conservative approximation—it's equivalent to view serializability.

Blind writes typically occur in:

• Unconditional initializations (INSERT or UPDATE without prior read)
• Logging/auditing operations (write-only transactions)
• Eventual consistency systems with write-ahead patterns

These are relatively rare in traditional OLTP workloads.

We've comprehensively compared conflict serializability and view serializability. Let's consolidate the key insights:

What's Next:

Having compared view and conflict serializability, we'll now explore the computational complexity of testing view serializability in depth. Understanding why it's NP-complete illuminates fundamental limits of concurrency control and explains why practical systems avoid it.