Validation (Optimistic) Concurrency Control Techniques
the concurrency control techniques we have discussed so far, a certain degree
of checking is done before a database
operation can be executed. For example, in locking, a check is done to
determine whether the item being accessed is locked. In timestamp ordering, the
transaction timestamp is checked against the read and write timestamps of the
item. Such checking represents overhead during transaction execution, with the
effect of slowing down the transactions.
In optimistic concurrency control techniques,
also known as validation or certification techniques, no
checking is done while the
transaction is executing. Several
theoretical concurrency control methods are based on the validation technique.
We will describe only one scheme here. In this scheme, updates in the
trans-action are not applied directly
to the database items until the transaction reaches its end. During transaction
execution, all updates are applied to local
copies of the data items that are kept for the transaction.6 At
the end of transaction execution, a validation
phase checks whether any of the transaction’s updates violate
serializability. Certain information needed by the validation phase must be
kept by the system. If serializability is not violated, the transaction is
committed and the database is updated from the local copies; otherwise, the
transaction is aborted and then restarted later.
three phases for this concurrency control protocol:
phase. A transaction can read values of committed data items from the database. However, updates are applied
only to local copies (versions) of the data items kept in the transaction
phase. Checking is performed to ensure that serializability will not be violated if the transaction
updates are applied to the database.
phase. If the validation phase is successful, the transaction updates are applied to the database; otherwise,
the updates are discarded and the trans-action is restarted.
behind optimistic concurrency control is to do all the checks at once; hence,
transaction execution proceeds with a minimum of overhead until the validation
phase is reached. If there is little interference among transactions, most will
be validated successfully. However, if there is much interference, many
transactions that execute to completion will have their results discarded and
must be restarted later. Under these circumstances, optimistic techniques do
not work well. The techniques are called optimistic
because they assume that little interference will occur and hence that there is
no need to do checking during transaction execution.
optimistic protocol we describe uses transaction timestamps and also requires
that the write_sets and read_sets of the transactions be kept by
the system. Additionally, start and end times for some of the three phases
need to be kept for each transaction. Recall that the write_set of a transaction is the set of
items it writes, and the read_set is the
set of items it reads. In the validation phase for transaction Ti, the protocol checks that Ti does not interfere with
any committed transactions or with any other transactions currently in their
validation phase. The validation phase for Ti
checks that, for each such
transaction Tj that is
either committed or is in its validation phase, one of the following conditions holds:
completes its write phase before Ti
starts its read phase.
its write phase after Tj completes
its write phase, and the read_set of Ti has no items in common
with the write_set of Tj.
Both the read_set and write_set of Ti have no items in common with the write_set of Tj, and Tj completes its read phase before Ti completes its read phase.
validating transaction Ti,
the first condition is checked first for each transaction Tj, since (1) is the simplest condition to check. Only
if condition 1 is false is condition 2 checked, and only if (2) is false is
condition 3—the most complex to evaluate—checked. If any one of these three
conditions holds, there is no interference and Ti is validated successfully. If none of these three conditions holds, the validation of
transaction Ti fails and
it is aborted and restarted later because interference may have occurred.