Validation Based Protocol

The Validation-Based Protocol, also known as Optimistic Concurrency Control (OCC), is a concurrency control technique that assumes transactions rarely conflict with one another. Instead of checking for conflicts during execution, each transaction executes independently and validates its operations before committing.

In this approach, all updates made by a transaction are applied to local copies of data items rather than directly to the database. When the transaction reaches the end of its execution, the validation phase checks whether the transaction can be committed without violating serializability. If validation succeeds, the changes are written to the database; otherwise, the transaction is rolled back and restarted.

Optimistic concurrency control is called optimistic because it assumes that conflicts between transactions are infrequent, reducing the overhead of locking and waiting.

Phases of Validation-Based Protocol

A transaction passes through the following three phases:

1. Read Phase

In this phase, the transaction reads data items from the database and performs all computations. Any changes are made only to temporary local variables and are not written to the actual database.

2. Validation Phase

In this phase, the system checks whether committing the transaction would violate serializability. The transaction is validated against other concurrently executing transactions to detect possible conflicts.

3. Write Phase

If the validation phase is successful, the changes stored in local variables are written to the database and the transaction is committed. If validation fails, the transaction is rolled back and restarted.

Timestamps Used in Validation-Based Protocol

To perform validation, each transaction is assigned different timestamps that help the system determine whether transactions overlap and whether their execution order preserves serializability. These timestamps are used during the validation process to decide whether a transaction can safely commit.

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

Validation (T_i): It contains the time when Ti finishes its read phase and starts its validation phase.

Finish(Ti): It contains the time when Ti finishes its write phase.

• This protocol is used to determine the time stamp for the transaction for serialization using the time stamp of the validation phase, as it is the actual phase which determines if the transaction will commit or rollback.
• Hence TS(T) = validation(T).
• The serializability is determined during the validation process. It can't be decided in advance.
• While executing the transaction, it ensures a greater degree of concurrency and also less number of conflicts.
• Thus it contains transactions which have less number of rollbacks.

A transaction T can complete its validation phase successfully if at least one of the following conditions is satisfied:

• All older transaction i.e. the transactions with smaller timestamps must have completed before the requesting transaction started.
• If a transaction T starts before earlier one finishes then the transaction T should not read the data items written by the earlier transactions. This rule guarantees that write of earlier transactions are not read by other transaction T.
• If a transaction T starts before earlier one finishes then the earlier transaction should complete its write phase before transaction T enters its validation phase. So this rule guarantees that writes are done serially ensuring that there is no conflict.

When validating a transaction T, the first condition is checked for the preceding transaction. If it is false, only condition 2 is checked. If condition 2 is false, only condition 3 is checked. If any one of these three conditions evaluates to true, there is no conflict and T is successfully validated. The validation phase of transaction T fails if none of these three conditions are true and it is then rolled back and restarted later.

Advantages of Validation-Based Protocol

The main idea for using validation based protocol is:

• Minimum Overhead: All the data items are updated at the end of the transaction so minimum overhead is caused during the execution of transaction.
• No cascade rollback: Since the rollbacks involve only a local copy of data and no database is involved, so there will not be any cascading rollbacks.
• No locking required: This technique allows greater concurrency then traditional protocols since no locking is required.
• Efficient: This technique is very efficient when conflicts are rare. Occasionally conflicts results in transaction rollbacks.

Limitations of Validation-Based Protocol

The main disadvantage of using validation based protocols is:

• If the rolled back transaction is very long then valuable processing time will be lost.
• These techniques do not work well when there is a lot of interference between transactions because the results of the transaction that is committed to completion will be discarded and must be restarted.