Validation Based Protocols | Database Management System

Validation Based Protocols | Database Management System


If many transactions are read-only, concurrency control becomes a bottleneck and a major overhead.

  • Use a validation protocol to determine only potential conflicting transactions (optimistic concurrency control).

Execution of a transaction Ti is done in three phases.

  • Read and execution phase : Transaction Ti writes only to temporary local variables after performing
  • Validation phase : Transaction Ti performs a “validation test” to determine if local variables can be without violating serializability.
  • Write phase: if Tiis validated, the updates areapplied to the database; otherwise, Tiis rolledback. The three phases can be interleaved, but each transaction must go through the three phases in order.

Validation-Based Protocol (2)
Each transaction Ti has 3 timestamps :

  • Start(Ti) : the time when Ti started its execution
  • Validation(Ti) : the time when Ti entered validation phase
  • Finish(Ti) : the time when Ti finished its write phase
    Serializability order is determined by timestamp given at validation time. Thus TS(Ti)=Validation(Ti).

This protocol is useful and gives greater degree of concurrency if probability of conflicts is low. That is because the serializability order is not pre-decided and relatively less transactions will have to be rolled back.

Validation Test for Transaction Tj.

If for all Ti with TS (Ti) < TS (Tj) either one of the following condition holds:

  • finish (Ti) < start(Tj)
  • start(Tj) < finish (Ti) < validation (Tj) and the set of data items written by Ti does not intersect with the set of data items read by Tj.
  • Then validation succeeds and Tj can be committed. Otherwise, validation fails and Tj is aborted. Justification: Either first condition is satisfied (no overlap) OR the second condition is satisfied and :
  • The writes of Tido not affect reads of Ti since they occur after Ti has finished its reads.
  • The writes of Ti do not affect reads of Tj since Tj does not read any item written by Ti.

Schedule Produced by validation

Example of schedule produced using validation

Validation - Based Protocols