Beyond Conflict Serializability: Blind Writes and View Equivalence
In database management systems, Conflict Serializability is the industry standard for verifying the correctness of concurrent schedules because it can be verified in polynomial time (O(V + E)) via Precedence Graphs.
However, Conflict Serializability is merely a sufficient condition, not a necessary one.
There exists a broader class of safe schedules: View Serializable Schedules.
1. The 3 Rules of View Equivalence
A concurrent schedule S is View Equivalent to a serial schedule S' if and only if it satisfies three strict invariants:
-
Initial Read: For each data item
Q, if transactionT_ireads the initial value ofQinS, thenT_imust also read the initial value ofQinS'. -
Intermediate Read: If
T_ireads a value ofQproduced byT_jinS, thenT_imust read the value produced byT_jinS'. -
Final Write: For each data item
Q, the transaction that performs the final write onQinSmust also perform the final write onQinS'.
2. The Role of Blind Writes
What allows a schedule to be View Serializable while failing Conflict Serializability?
A Blind Write: An operation where a transaction executes
W(Q)without readingQfirst.
Consider schedule S:
T₁: R(A)T₂: W(A)T₁: W(A)T₃: W(A)
In this schedule, T₂ and T₃ perform blind writes. The precedence graph contains conflicting dependencies (T₁ → T₂ and T₂ → T₁), forming a cycle. It is not conflict serializable.
Yet S is View Equivalent to the serial order T₁ → T₂ → T₃:
-
T₁reads the initial value. - Zero intermediate reads.
-
T₃performs the final write.
The Inclusion Theorem:
Conflict Serializable ⊂ View Serializable
Theorem: If a schedule contains no blind writes, then Conflict Serializability is identical to View Serializability!
3. Why Databases Don't Use View Serializability
Testing whether an arbitrary schedule is View Serializable requires testing potential equivalent serial permutations, a problem formally proved to be NP-Complete.
Because transaction schedulers must make routing decisions in microseconds, production engines universally enforce the simpler, polynomial-time Conflict Serializability (using Two-Phase Locking or MVCC).
Explore full database concurrency control architectures at Binary Dose.
Top comments (0)