Optimistic Algorithm

Assumption

Optimistic Concurrency Control Algorithms are based on the assumption that conflicts do not occur during execution time. No synchonization is performed when a transaction is executed. However, a check is performed at the end of the transaction to make sure that no conflicts have occured. If there is a conflict, the transaction will be aborted. Otherwise, the transaction is commited. Since conflicts do not occur very often, this algoritm is very efficient compared to other locking algorithms.

Kung-Robinson Algorithm

• Kung and Robinson were the first to propose an optimistic method for concurrency control.


• The optimistic situation for this algorithm happens when
  • conflicts are unlikely to happen
  • the system consists mainly read-only transactions (such as a query dominant system)


• Basic Idea: No synchonization check is performed during transaction processing time, however, a validation is performed to make sure there is no conflicts occurred. If a conflict is found, the tentative write is discarded and the transaction is restarted.

The algorithm

Divide the execution of transaction into three phases:





• read phase: data objects are read, the intended computation of the transaction is done, and writes are made on a temporary storage.


• validation phase: check to see if writes made by the transaction violate the consistency of the database. If the check finds out any conflicts, the data in the temporary storage will be discarded. Otherwise, the write phase will write the data into the database.
  
  The validation process can be described as:
  

  T: a transaction
  ts: the highest sequence number at the start of T 
  tf: the highest sequence number at the beginning 
      of its validation phase 
  
  valid:=true;
  for t:=ts+1 to tf do
    if (writeset(t) & readset[T] != {} ) then    
       valid :=false;
  if valid then {write phase; increment counter, assign T a sequence number}
  
  

• write phase: If the validation phase passes ok, write will be performed to the database. If the validation phase fails to pass, all temporary written data will be aborted.

Improvement

In the Kung-Robinson method, read transactions are treated in the same way as update transactions, and thus, are subject to a validation check with the risk of restart.
Schlageter proposed an improvement to the Kung-Robinson method: a read transaction always proceeds without validation check and thus without the risk of restarts.