View Serializability

Having established view equivalence as a semantic notion of schedule similarity, we now turn to the central question: Which schedules are correct according to view equivalence?

The answer defines view serializability—a schedule is view serializable if it is view equivalent to at least one serial schedule. This criterion captures the broadest class of schedules that can be considered correct from a semantic standpoint: they produce the same observable behavior as some sequential execution.

View serializability represents the theoretical upper bound on what schedules we can safely permit while maintaining database consistency. Any schedule that is not view serializable produces results that no sequential execution could produce—a clear indicator of incorrect concurrent behavior.

Definition: A schedule S over a set of transactions {T₁, T₂, ..., Tₙ} is view serializable if there exists a serial schedule S' over the same transactions such that S is view equivalent to S'.

Formally: S is view serializable ⟺ ∃ serial schedule S' such that S ≡ᵥ S'

Unpacking the Definition:

1. Serial Schedule: A schedule where transactions execute one at a time, with no interleaving. For n transactions, there are n! possible serial schedules.

2. View Equivalent (≡ᵥ): As defined in the previous page—same initial reads, same read-from relationships, same final writes.

3. Existence Quantifier (∃): We only need to find ONE serial schedule to which S is view equivalent. S doesn't need to be view equivalent to all serial schedules—just at least one.

The set of all view serializable schedules is denoted VSR (View Serializable Schedules).

The Naive Testing Approach:

Given the definition, one might consider this algorithm to test view serializability:

For each permutation π of transactions (there are n! of them):
    Construct serial schedule S_π based on order π
    If S ≡ᵥ S_π:
        Return "S is view serializable"
Return "S is not view serializable"

This approach is correct but has factorial time complexity—O(n!) permutations to check, each requiring polynomial time to verify view equivalence. For even modest numbers of transactions, this becomes intractable.

However, understanding this naive approach is pedagogically valuable: it makes explicit that view serializability is defined relative to the existence of at least one equivalent serial schedule.

Let's work through a detailed example demonstrating a view serializable schedule.

Setup:

• Three transactions: T₁, T₂, T₃
• Two data items: X, Y
• Initial values: X = 0, Y = 0

Transaction Operations:

• T₁: R₁(X), W₁(X), W₁(Y)
• T₂: R₂(Y)
• T₃: W₃(X)

Analysis: Check Against Serial Schedule T₃; T₁; T₂

Serial Schedule T₃; T₁; T₂:

1. W₃(X) — T₃ writes X
2. R₁(X) — T₁ reads X written by T₃
3. W₁(X) — T₁ writes X (overwrites T₃'s value)
4. W₁(Y) — T₁ writes Y
5. R₂(Y) — T₂ reads Y written by T₁

Check View Equivalence (S vs T₃; T₁; T₂):

Condition 1: Initial Read Preservation

• In S: R₁(X) reads initial value of X (before any write)
• In T₃; T₁; T₂: R₁(X) reads value written by T₃ (NOT initial value)

❌ This serial schedule doesn't match!

Try Serial Schedule T₁; T₃; T₂:

1. R₁(X) — T₁ reads initial X ✓
2. W₁(X) — T₁ writes X
3. W₁(Y) — T₁ writes Y
4. W₃(X) — T₃ writes X (overwrites T₁'s value)
5. R₂(Y) — T₂ reads Y written by T₁

Check View Equivalence (S vs T₁; T₃; T₂):

Condition 1: Initial Read Preservation

• In S: R₁(X) reads initial value ✓
• In T₁; T₃; T₂: R₁(X) reads initial value ✓

Condition 2: Read-From Relationships

• In S: R₂(Y) reads value written by W₁(Y) → T₁ →Y T₂
• In T₁; T₃; T₂: R₂(Y) reads value written by W₁(Y) → T₁ →Y T₂ ✓

Condition 3: Final Write Preservation

• In S: Final write to X is W₁(X), final write to Y is W₁(Y)
• In T₁; T₃; T₂: Final write to X is W₃(X), final write to Y is W₁(Y)

❌ Final writes to X don't match! S has T₁'s write as final, but T₁; T₃; T₂ has T₃'s write as final.

Try Serial Schedule T₃; T₁; T₂ (revisited with correct understanding):

Wait—let me reconsider the original schedule S more carefully:

• S: R₁(X), W₃(X), W₁(X), W₁(Y), R₂(Y)
• The final write to X in S is W₁(X) (it comes after W₃(X))

We need a serial schedule where:

1. R₁(X) reads initial value (no writes to X before R₁(X))
2. R₂(Y) reads T₁'s write to Y (T₁ →Y T₂)
3. Final write to X is by T₁
4. Final write to Y is by T₁

Serial Schedule T₁; T₂; T₃:

1. R₁(X) — reads initial ✓
2. W₁(X) — writes X
3. W₁(Y) — writes Y
4. R₂(Y) — reads T₁'s Y ✓
5. W₃(X) — writes X (final write to X is T₃!) ❌

Serial Schedule T₁; T₃; T₂:

• Final write to X is T₃ ❌

Serial Schedule T₃; T₁; T₂:

1. W₃(X) — writes X
2. R₁(X) — reads T₃'s X (not initial) ❌

Corrected Example: A Truly View Serializable Schedule

Setup:

• Two transactions: T₁, T₂
• One data item: X (initial value = 0)
• T₁: W₁(X) — blind write, sets X = 10
• T₂: W₂(X) — blind write, sets X = 20

Schedule S: W₁(X), W₂(X)

Analysis:

• No reads occur, so initial read condition is trivially satisfied
• No read-from relationships exist (no reads), so that condition is trivially satisfied
• Final write to X is W₂(X)

Serial Schedule T₁; T₂:

• W₁(X), W₂(X) — same order!
• Final write is W₂(X) ✓

Conclusion: S ≡ᵥ (T₁; T₂), so S is view serializable.

This is actually the same as the serial schedule, so it's trivially view serializable. Let's create a more interesting example.

The most instructive examples of view serializability involve blind writes. These schedules are view serializable but NOT conflict serializable—showcasing the extra permissiveness of view serializability.

Setup:

• Three transactions: T₁, T₂, T₃
• One data item: X (initial value irrelevant since no reads of initial value)
• T₁: R₁(X), W₁(X)
• T₂: W₂(X) — blind write
• T₃: W₃(X) — blind write

Find a View-Equivalent Serial Schedule:

We need a serial schedule where:

1. R₁(X) reads the initial value (T₁ must be first, or at least before any writes to X)
2. Final write to X is by T₃
3. No other read-from relationships (only R₁(X) reads, and it reads initial)

Candidate: Serial Schedule T₁; T₂; T₃

1. R₁(X) — reads initial value ✓
2. W₁(X) — writes X
3. W₂(X) — writes X (overwrites T₁)
4. W₃(X) — writes X (final write) ✓

Verify View Equivalence:

Conclusion: S ≡ᵥ (T₁; T₂; T₃), so S is view serializable.

Key Insight:

The schedule S is view serializable because:

• T₂'s write to X is blind (no preceding read)
• T₂'s value is never read by any transaction
• T₂'s value is overwritten before any read could occur

In such cases, the exact position of T₂'s write relative to other operations is flexible—as long as the initial reads, read-from relationships, and final writes are preserved.

This flexibility is exactly what distinguishes view serializability from conflict serializability. Conflict serializability treats all conflicts as order-sensitive; view serializability realizes that some conflicts are semantically irrelevant.

Understanding what makes a schedule not view serializable is equally important. A schedule fails to be view serializable when its read-from relationships and/or final writes cannot be matched by any serial schedule.

Setup:

• Two transactions: T₁, T₂
• Two data items: X, Y (initial values = 0)
• T₁: R₁(X), W₁(Y)
• T₂: R₂(Y), W₂(X)

Analysis Against All Serial Schedules:

Serial Schedule T₁; T₂:

1. R₁(X) — reads initial X
2. W₁(Y) — writes Y
3. R₂(Y) — reads Y written by T₁ (NOT initial!)
4. W₂(X) — writes X

In S: R₂(Y) reads initial Y. In T₁;T₂: R₂(Y) reads T₁'s Y.

❌ Read-from relationship mismatch!

Serial Schedule T₂; T₁:

1. R₂(Y) — reads initial Y
2. W₂(X) — writes X
3. R₁(X) — reads X written by T₂ (NOT initial!)
4. W₁(Y) — writes Y

In S: R₁(X) reads initial X. In T₂;T₁: R₁(X) reads T₂'s X.

❌ Read-from relationship mismatch!

Conclusion: S is view equivalent to neither serial schedule. Therefore, S is NOT view serializable.

The Impossibility Explained:

In schedule S:

• T₁ reads X before T₂ writes X (R₁(X) sees initial value)
• T₂ reads Y before T₁ writes Y (R₂(Y) sees initial value)

But in any serial schedule (T₁;T₂ or T₂;T₁), the second transaction's reads will occur AFTER the first transaction's writes. There is no way to serialize the transactions while preserving the fact that both read initial values.

This is a form of circular dependency:

• T₁ must be 'first' for R₁(X) to read initial X (before T₂ writes X)
• T₂ must be 'first' for R₂(Y) to read initial Y (before T₁ writes Y)

Both cannot be 'first' simultaneously in a serial schedule.

We can characterize view serializable schedules through their read-from relationships and final writes. A schedule is view serializable if and only if there exists a total ordering of transactions that is consistent with these relationships.

The Ordering Constraints:

Given a schedule S, define the following ordering requirements for any potential equivalent serial schedule:

1. Initial Read Constraint: If Tᵢ reads the initial value of X in S, then no transaction that writes to X can precede Tᵢ in the serial order.

2. Read-From Constraint: If Tⱼ →X Tᵢ in S (Tᵢ reads X from Tⱼ), then:

   • Tⱼ must precede Tᵢ in the serial order
   • No other transaction Tₖ that writes to X can appear between Tⱼ and Tᵢ in the serial order

3. Final Write Constraint: If Tᵢ performs the final write to X in S, then:

   • Any other transaction Tⱼ that writes to X must precede Tᵢ in the serial order

Testing View Serializability:

A schedule S is view serializable ⟺ there exists a serial ordering of transactions that satisfies ALL the above constraints simultaneously.

This is equivalent to asking: can we find a topological ordering of the transactions that respects all the constraints derived from S's read-from relationships and final writes?

Unfortunately, testing this is computationally hard—NP-complete in general. We'll explore this in detail in a later page.

View serializability has several important properties that define its place in the hierarchy of correctness criteria.

Property 1: VSR ⊇ CSR (Superset Relationship)

Every conflict serializable schedule is also view serializable, but not vice versa.

• CSR ⊂ VSR (proper subset)
• If a schedule is conflict serializable, it is view serializable
• If a schedule is not view serializable, it is not conflict serializable

The schedules in VSR but not in CSR are exactly those with blind writes where the order of writes that get overwritten can be rearranged.

Property 2: View Serializability Preserves Database Consistency

If each transaction in isolation transforms a consistent database state to another consistent state, then any view serializable schedule will also preserve consistency.

This follows from view equivalence to a serial schedule: the serial schedule preserves consistency (by sequential consistency guarantee), and view equivalence ensures the same final state.

Property 3: View Serializability is Testing-Intractable

Determining whether a schedule is view serializable is NP-complete. This is a critical difference from conflict serializability, which can be tested in polynomial time using precedence graphs.

Property 4: Composability

View serializability has limited composability: the union of two view serializable schedules (over disjoint transaction sets or data items) may not be view serializable. This makes it challenging to use in distributed systems without global coordination.

Property 5: Recoverable Schedules

View serializability is orthogonal to recoverability. A view serializable schedule may or may not be recoverable. For practical use, we need schedules that are both view serializable AND recoverable (or cascadeless/strict).

We have established the concept of view serializability—the broadest semantically-grounded correctness criterion for concurrent schedules. Let's consolidate the key points:

What's Next:

Having established both view serializability and conflict serializability, we're ready to explore their detailed comparison. We'll examine exactly when they differ, why conflict serializability is preferred in practice, and what theoretical insights view serializability provides.