Lock-based Protocols

Database systems equipped with lock-based protocols use a mechanism by which any transaction cannot read or write data until it acquires an appropriate lock on it.

Locks are of two kinds:

• Binary Locks − A lock on a data item can be in two states; it is either locked or unlocked.
• Shared/exclusive − This type of locking mechanism differentiates the locks based on their uses. If a lock is acquired on a data item to perform a write operation, it is an exclusive lock. Allowing more than one transaction to write on the same data item would lead the database into an inconsistent state. Read locks are shared because no data value is being changed.

There are four types of lock protocols available:

i. Simplistic Lock Protocol

Simplistic lock-based protocols allow transactions to obtain a lock on every object before a 'write' operation is performed. Transactions may unlock the data item after completing the ‘write’ operation.

ii. Pre-claiming Lock Protocol

Pre-claiming protocols evaluate their operations and create a list of data items on which they need locks. Before initiating an execution, the transaction requests the system for all the locks it needs beforehand. If all the locks are granted, the transaction executes and releases all the locks when all its operations are over. If all the locks are not granted, the transaction rolls back and waits until all the locks are granted.

iii. Two-Phase Locking 2PL

• This locking protocol divides the execution phase of a transaction into three parts. In the first part, when the transaction starts executing, it seeks permission for the locks it requires.
• The second part is where the transaction acquires all the locks. As soon as the transaction releases its first lock, the third phase starts. In this phase, the transaction cannot demand any new locks; it only releases the acquired locks.
• Two-phase locking has two phases, one is growing, where all the locks are being acquired by the transaction; and the second phase is shrinking, where the locks held by the transaction are being released.
• To claim an exclusive (write) lock, a transaction must first acquire a shared (read) lock and then upgrade it to an exclusive lock.

iv. Strict Two-Phase Locking

The first phase of Strict-2PL is same as 2PL. After acquiring all the locks in the first phase, the transaction continues to execute normally. But in contrast to 2PL, Strict-2PL does not release a lock after using it. Strict-2PL holds all the locks until the commit point and releases all the locks at a time. Strict-2PL does not have cascading abort as 2PL does.

Validation-Based Protocol

• Execution of transaction Ti is done in three phases:

  i. Read and execution phase: During this phase, the system executes transaction Ti. . It reads the values of the various data items and stores them in variable local to Ti. It performs all the write operations on temporary local variables without update of the actual database.

  ii. Validation phase: Transaction Ti performs a ``validation test'' to determine if local variables can be written without violating serializability.

  iii. Write phase: If Ti is validated, the updates are applied to the database; otherwise, Ti is rolled back.

• The three phases of concurrently executing transactions can be interleaved, but each transaction must go through the three phases in that order.
• Also called as optimistic concurrency control since transaction executes fully in the hope that all will go well during validation.

• Each transaction Ti has 3 timestamps:

  i. Start(Ti ) : the time when Ti started its execution

  ii. Validation(Ti ): the time when Ti entered its validation phase

  iii. Finish(Ti ) : the time when Ti finished its write phase.

• Serializability order is determined by timestamp given at validation time, to increase concurrency. Thus TS(Ti ) is given the value of 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

  i. 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.

  ii. Justification: Either first condition is satisfied, and there is no overlapped execution, or second condition is satisfied and

  • The writes of Tj do 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

  iii. Schedule Produced by Validation Example of schedule produced using validation