DATA INTEGRITY - Database Design and Development: An Essential Guide for IT Professionals - page 467

tion T1 starts earlier than transaction T2, Timestamp (T1) < Timestamp (T2). The
earlier transaction has the smaller value of the timestamp.
Two schemes are available for deadlock prevention, both using transaction time-
stamps for taking appropriate action. Assume that transaction T1 is attempting to
lock data item D that is locked by transaction T2 with a conflicting lock.
Wait-die. (1) T1 is older than T2. Timestamp (T1) < Timestamp (T2). T1 is permit-
ted to wait. T1 waits. (2) T1 is younger than T2. Timestamp (T1) > Timestamp (T2).
Abort T1 and restart it later with the same timestamp. T1 dies.
Wound-wait. (1) T1 is older than T2. Timestamp (T1) < Timestamp (T2). Abort T2
and restart it later with the same timestamp. T1 wounds T2. (2) T1 is younger than
T2. Timestamp (T1) > Timestamp (T2). Allow T1 to wait. T1 waits.
Both schemes end up aborting the younger transaction. It can be easily shown
that both techniques are deadlock-free. However, both schemes may abort some
younger transactions and restart them unnecessarily even though these younger
transactions may never cause a deadlock.
In wait-die, the older transaction waits on the younger transaction. A younger
transaction requesting a lock on a data item locked by the older transaction
is aborted and restarted. Because transactions only wait on younger transactions,
no cycle is generated on the wait-for graph. Therefore, this scheme prevents
deadlock.
In wound-wait, the younger transaction is allowed to wait on the older one. An
older transaction requesting a lock on a data item locked by the younger transac-
tion preempts the younger transaction and aborts it. Because transactions only wait
on older transactions, no cycle is generated on the wait-for graph. Therefore, this
scheme prevents deadlock.
Timestamp-Based Resolution
From our discussion on lock-based concurrency control, you have perceived that
use of locks on the basis of 2PL ensures serializability of schedules. Locking of data
items according to 2PL determines the order in which transactions are made to
execute. A transaction waits if the data item it needs is already locked by another
transaction. The order of execution of transactions is implicitly determined by such
waits for locks to be released. Essentially, the ordering of transaction execution
guarantees serializability.
There is another method in use to produce the same effect. This method does
not use locks. Right away, because of the absence of locks, the problem of dead-
locks does not occur. This method orders transaction execution by means of time-
stamps. Lock-based protocols prevent conflicts by forcing transactions to wait for
locks to be released by other transactions. However, transactions do not have to
wait in the timestamp method. When a transaction runs into a conflict, it is aborted
and restarted. The timestamp-ordering protocol also guarantees serializability.
How are timestamps used to determine the serializability order? If Time-
stamp(T1) < Timestamp(T2), then the DBMS must ensure that the schedule
produced by timestamp ordering is equivalent to a serial schedule where T1
precedes T2.