Page 165 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Database Management Systems/Managing Database

Notes T ’s read and precedes T ’s write of the same object, this schedule is not conflict serializable. The
1 1
Thomas Write Rule relies on the observation that T ’s write is never seen by any transaction and
2
the schedule in table above is therefore equivalent to the serializable schedule obtained by
deleting this write action, which is shown in table below.
A Conflict Serializable Schedule

T1 T2
R(A)
Commit
W(A)
Commit

9.11 Validation based Protocols

In cases where a majority of transactions are read-only transactions, the rate of conflicts among
transactions may be low. Thus, many of these transactions, if executed without the supervision
of a concurrency-control scheme, would nevertheless leave the system in a consistent state.
A concurrency-control scheme imposes overhead of code execution and possible delay of
transactions. It may be better to use an alternative scheme that imposes less overhead. A difficulty
in reducing the overhead is that we do not know in advance which transactions will be involved
in a conflict. To gain that knowledge, we need a scheme for monitoring the system.
We assume that each transaction T executes in two or three different phases in its lifetime,
i
depending on whether it is a read-only or an update transaction. The phases are, in order,
1. Read phase: During this phase, the system executes transaction T . It reads the values of the
i
various data items and stores them in variables local to T . It performs all write operations
i
on temporary local variables, without updates of the actual database.
2. Validation phase: Transaction T performs a validation test to determine whether it can
i
copy to the database the temporary local variables that hold the results of write operations
without causing a violation of serializability.
3. Write phase: If transaction T succeeds in validation (step 2), then the system applies the
i
actual updates to the database. Otherwise, the system rolls back T .
i
Each transaction must go through the three phases in the order shown. However, all three
phases of concurrently executing transactions can be interleaved.
To perform the validation test; we need to know when the various phases of transactions T took
i
place. We shall, therefore, associate three different timestamps with transaction T :
i
1. Start(T ), the time when T started its execution.
i i
2. Validation(T ), the time when T finished its read phase and started its validation phase.
i i
3. Finish(T ), the time when T finished its write phase.
i i
We determine the serializability order by the timestamp-ordering technique, using the value of
the timestamp Validation(T ). Thus, the value TS(T ) = Validation(T ) and, if TS(T) < TS(T ), then
i i i j k
any produced schedule must be equivalent to a serial schedule in which transaction T appears
j
before transaction T The reason we have chosen Validation(T ), rather than Start(T ), as the
k. i i
timestamp of transaction T is that we can expect faster response time provided that conflict rates
i
among transactions are indeed low.

158 LOVELY PROFESSIONAL UNIVERSITY