OneNoughtOne
0/278
Loading content...
Read aloud is unavailable in this browser.
In our study of conflict serializability, we learned that two schedules are conflict equivalent if one can be transformed into the other by swapping non-conflicting operations. This gives us a powerful, efficient method for determining schedule correctness. However, conflict equivalence is conservative—it may reject schedules that are, in fact, correct.
Consider a provocative question: What if a schedule produces the exact same final database state as a serial schedule, even though we cannot transform one into the other via non-conflicting swaps? Should such a schedule be considered correct?
This question leads us to view equivalence—a more fundamental, semantically-grounded definition of schedule equivalence based on what transactions see (read) and what the database retains (final writes).
By the end of this page, you will understand the formal definition of view equivalence, the three conditions that must hold for two schedules to be view equivalent, why view equivalence captures a broader class of correct schedules than conflict equivalence, and the semantic intuition behind each condition.
Let's begin by understanding why we need a concept beyond conflict equivalence. The fundamental goal of concurrency control is to ensure that concurrent execution produces results indistinguishable from some serial execution. Conflict serializability achieves this, but it does so by being restrictive.
The Limitation of Conflict Equivalence:
Conflict equivalence examines the order of conflicting operations (reads and writes on the same data item by different transactions). If we can reorder non-conflicting operations to arrive at a serial schedule, the concurrent schedule is conflict serializable.
However, consider this scenario:
Consider two transactions that both write to the same data item X:
T₁: W₁(X)
T₂: W₂(X)
Schedule S: W₁(X) W₂(X) — both write to X, T₂'s write is the final valueSerial Schedule T₁;T₂: W₁(X) W₂(X) — produces the same final value
Serial Schedule T₂;T₁: W₂(X) W₁(X) — produces a different final valueExplanation
Schedule S matches the outcome of serial schedule T₁;T₂ exactly. The final value of X is what T₂ wrote. However, notice that W₁(X) and W₂(X) are conflicting operations (writes to the same item by different transactions). Since they conflict, their order cannot be swapped. Thus, S is already in a form equivalent to T₁;T₂ under conflict equivalence. But what if we had a more complex scenario where swaps wouldn't work?
The key insight is that conflict equivalence focuses on the structure of operation ordering (which conflicts come before which), but it doesn't directly reason about the semantics—specifically:
What values do reads see? — If a read operation reads the value written by a specific write, does that relationship hold in both schedules?
What value is final? — For each data item, which write operation's value is the final value in the database?
View equivalence addresses these semantic properties directly. Two schedules are view equivalent if, for every data item:
This approach can identify correct schedules that conflict serializability would reject.
View equivalence asks: 'Do both schedules give the same experience to every transaction (what it reads) and produce the same final state?' If yes, the schedules are view equivalent—regardless of whether one can be transformed into the other by swapping non-conflicting operations.
We now present the rigorous, formal definition of view equivalence. This definition is foundational to understanding view serializability.
Definition: Two schedules S and S' over the same set of transactions are view equivalent, written S ≡ᵥ S', if and only if the following three conditions hold:
Condition 1: Initial Read Preservation
If a transaction Tᵢ reads the initial value of data item X in schedule S (meaning Tᵢ reads X before any write to X occurs), then Tᵢ must also read the initial value of X in schedule S'.
Formally: If Rᵢ(X) reads the initial value in S, then Rᵢ(X) reads the initial value in S'.
Condition 2: Read-From Relationship Preservation
If a transaction Tᵢ reads the value of data item X written by transaction Tⱼ in schedule S (denoted as Tⱼ →X Tᵢ, meaning 'Tⱼ writes X and Tᵢ reads that written value'), then the same read-from relationship must hold in schedule S'.
Formally: If Tⱼ →X Tᵢ in S (Rᵢ(X) reads the value written by Wⱼ(X) in S), then Tⱼ →X Tᵢ in S' (Rᵢ(X) reads the value written by Wⱼ(X) in S').
Condition 3: Final Write Preservation
If a transaction Tᵢ performs the final write to data item X in schedule S (meaning Wᵢ(X) is the last write operation to X in S), then Tᵢ must also perform the final write to X in schedule S'.
Formally: If Wᵢ(X) is the last write to X in S, then Wᵢ(X) is the last write to X in S'.
These conditions capture what matters for correctness: (1) Initial state access must be consistent—transactions reading before any writes must see the original database values. (2) Data flow must be preserved—if Tᵢ's computation depends on Tⱼ's output, that dependency must exist in both schedules. (3) Final state must match—the persistent database state after execution must be the same.
| Condition | What It Preserves | Formal Statement | Intuition |
|---|---|---|---|
| Initial Read | Access to original data | If Rᵢ(X) reads initial value in S, it reads initial value in S' | Transactions that 'see' the starting state must see it in both schedules |
| Read-From | Data flow between transactions | If Tⱼ →X Tᵢ in S, then Tⱼ →X Tᵢ in S' | Every 'sees the value written by' relationship is identical |
| Final Write | Persistent database state | If Wᵢ(X) is last write to X in S, then same in S' | The database ends up with the same values for all data items |
Notation and Terminology:
Read-From Relationship (Tⱼ →X Tᵢ): Transaction Tᵢ reads the value of X that was written by transaction Tⱼ. This means:
Initial Value: The value a data item had before any transaction in the schedule began. Think of this as a 'virtual' transaction T₀ that wrote all initial values before the schedule started.
Final Write: The last write operation to a data item in the schedule. This is the value that persists in the database after the schedule completes.
Let's work through a comprehensive example to solidify understanding. We'll analyze two schedules and determine whether they are view equivalent.
Setup:
Analysis of View Equivalence:
Step 1: Check Initial Read Preservation
In Schedule S:
In Schedule S':
✓ Initial read condition satisfied.
Step 2: Check Read-From Relationships
In Schedule S:
In Schedule S':
✓ Read-from relationships match.
Step 3: Check Final Write Preservation
In Schedule S:
In Schedule S':
✓ Final write condition satisfied.
Conclusion: Schedules S and S' are view equivalent (S ≡ᵥ S').
All three conditions hold: initial reads match, read-from relationships are preserved, and final writes are the same. Therefore, S ≡ᵥ S'. Since S' is a serial schedule, S is view serializable.
To deepen understanding, let's examine a case where two schedules are not view equivalent. This illustrates how violations of any of the three conditions break view equivalence.
Setup:
Analysis:
Check Initial Read Preservation:
❌ Violation! In S₁, T₂ reads the initial value. In T₁;T₂, T₂ reads T₁'s written value.
The read-from relationships differ:
Conclusion: S₁ is not view equivalent to T₁;T₂.
Let's check the other serial schedule T₂;T₁:
Analysis against S₁:
❌ Violation! R₁(X) reads initial value in S₁ but reads T₂'s value in T₂;T₁.
Also, final writes differ:
❌ Final write violation!
Conclusion: S₁ is not view equivalent to any serial schedule, so S₁ is not view serializable.
This schedule (S₁) is also not conflict serializable. In fact, any schedule that is conflict serializable is also view serializable. But view serializability can accept more schedules than conflict serializability—schedules that conflict serializability rejects. We'll explore this relationship in a later page.
One of the key scenarios where view equivalence differs from conflict equivalence is the case of blind writes.
Definition: A blind write is a write operation that occurs without a preceding read of the same data item by the same transaction. In other words, the transaction writes a value to X without first reading X's current value.
Example:
W₁(X) with no preceding R₁(X) in T₁ is a blind writeWhy Blind Writes Matter:
Blind writes create a situation where the order of certain writes doesn't affect the final outcome if those writes get overwritten by a later write. Consider:
Schedule S:
Serial Schedule T₁; T₂; T₃:
Serial Schedule T₂; T₁; T₃:
Schedule S is view equivalent to T₁; T₂; T₃:
S is view serializable.
With blind writes, intermediate write values that get overwritten don't affect correctness. View equivalence captures this: if a write's value is never read and gets overwritten, its exact position relative to other writes (that also get overwritten) is flexible. Conflict equivalence is stricter—it treats all write-write conflicts as order-sensitive.
Critical Insight:
The difference between view and conflict serializability primarily manifests in schedules with blind writes. When transactions always read before writing, conflict and view serializability typically coincide. Blind writes create scenarios where conflict serializable would reject schedules that are, in fact, correct under view serializability.
In practice:
A powerful way to understand view equivalence is through the concept of data flow graphs. Every schedule implicitly defines how data flows between transactions and between the initial database state and transactions.
Data Flow Graph Construction:
For a schedule S over data item X:
View Equivalence in Terms of Data Flow:
Two schedules are view equivalent if and only if they have identical data flow graphs. This beautifully captures all three conditions:
If the data flow graph is the same, the schedules are view equivalent. The specific ordering of operations may differ, but the semantic information flow is preserved.
The data flow graph perspective makes view equivalence intuitive: two executions that route data through the system identically (same sources for each read, same final writers) are indistinguishable in their effect. The path data takes through the transaction network defines the execution's correctness.
We have established the foundational concept of view equivalence, which underlies view serializability. Let's consolidate the key points:
What's Next:
Now that we understand view equivalence, we're ready to formally define view serializability—the class of schedules that are view equivalent to some serial schedule. We'll explore how to determine if a schedule is view serializable and examine the relationship between view serializable and conflict serializable schedules.
You now understand view equivalence—the semantic foundation for view serializability. You can identify the three conditions, apply them to schedules, and understand why view equivalence captures a broader class of correct executions than conflict equivalence.