Validation-Based Scheduler

This is a Scheduler that gives Conflict-Serializable Schedule

This scheduler is optimistic (similar idea to Timestamp-Based Scheduler):

  • it allows any sequence of action
  • periodically it checks if everything is okay. yes - continue, no - abort the transaction and restart


Rules

for every transaction $T$ we record

  • a set of database items $RS(T)$ that were read by $T$
  • a set of database items $WS(T)$ that is wants to write / were written by $T$

All transactions are executed in 3 phases

  • transactions are only allowed to read
    • when an item $X$ is read by $T$, $X$ is added to $RS(T)$
  • the scheduler validated the schedule based on
    1. actions read by $T$: $RT(T)$
    2. actions $T$ wants to write: $WS(T)$ (but has not written yet)
    if validation fails, $T$ is restarted
  • $T$ can write all items from $WS(T)$


Problematic Situations

Problematic Situation 1

Actions:

  1. $U_\text{start},$
  2. $T_\text{start},$
  3. ${\color{red}{T \text{ reads } X}},$
  4. $U_\text{validate},$
  5. ${\color{red}{U \text{ writes } X}},$
  6. $T_\text{validate},$
  7. ...

The problem:

  • $U$ should have written $X$ before $T$ reads it
  • not consistent with the serial schedule $(U, T)$
  • i.e. it should be $U \text{ writes } X, T \text{ reads } X$

For every transaction $T$ we records

  • $\text{START}(T)$ - the time when $T$ starts
  • $\text{VAL}(T)$ - the time when $T$ validates
  • $\text{FIN}(T)$ - the time when $T$ finishes

$T$ can successfully validate if

  • $RS(T)$ is disjoint with $WS(U)$: $RS(T) \cap WS(U) = \varnothing$
    • $RS(T)$ - reads by the current transactions
    • $WS(U)$ - writes by other transactions $U$
    • $U$ - all transactions that already validated, but have not finished when $T$ started
    • (i.e. those $U$ for which $\text{FIN}(U) > \text{START}(T)$)

In this problematic example we have:

  • $X \in WS(U)$ - $U$ has already validated, but has not finished
  • $RT(T) \cap WS(U) = \{ X \}$: $T$ read $X$ that was later modified by $Y$
  • $T$ will be restarted


Problematic Situation 2

Actions:

  1. $U_\text{validate},$
  2. $T_\text{validate},$
  3. ${\color{red}{T \text{ writes } X}},$
  4. $U \text{ writes } X,$
  5. $U_\text{finish},$
  6. $...$

The problem:

  • $T$ writes $X$ first - before $U$
    • not consistent with the serial schedule $(U, T)$
  • should be first write by $U$, then write by $T$
  • after validation they are allowed to write in any order, but we have to make sure it respects the $(U, T)$ order

$T$ can successfully validate if

  • $WS(T) \cap WS(U) = \varnothing$
    • $WS(T)$ - items that $T$ wants to write (before validation - means "it wants to write")
    • $WS(U)$ - items that $U$ writes (after validation - means either "it wants to write" or "it has written")
  • should hold for all previously validated $U$ that did not finish before $T$ validated,
    • i.e. for such $U$ that $\text{FIN}(U) > \text{VAL}(T)$

In this problematic example we have:

  • $WS(T) \cap WS(U) = \{ X \}$
    • $T$ wants to write $X$
    • $U$ also wants to write $X$, but $U$ was validated before $T$
  • therefore $T$ is not allowed to start


Summary

$T$ passes validation if

  • $RS(T) \cap WS(U) = \varnothing$ for all $U$ s.t. $\text{FIN}(U) > \text{START}(T)$
  • $WS(T) \cap WS(U) = \varnothing$ for all $U$ s.t. $\text{FIN}(U) > \text{VAL}(T)$

Everything that doesn't pass the validation is aborted and restarted


Sources