DEV Community

Cover image for Beyond Conflict Serializability: Blind Writes and View Equivalence
Binary Dose
Binary Dose

Posted on Originally published at binarydose.in

Beyond Conflict Serializability: Blind Writes and View Equivalence

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:

  1. Initial Read: For each data item Q, if transaction T_i reads the initial value of Q in S, then T_i must also read the initial value of Q in S'.
  2. Intermediate Read: If T_i reads a value of Q produced by T_j in S, then T_i must read the value produced by T_j in S'.
  3. Final Write: For each data item Q, the transaction that performs the final write on Q in S must also perform the final write on Q in S'.

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 reading Q first.

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
Enter fullscreen mode Exit fullscreen mode

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)