Mumbai University > Information Technology > Sem 3 > Database Management System

Marks: 10M

Year: Dec 2013

• In timestamp based concurrency control algorithms, each site maintains a logical clock.
• This clock is incremented when a transaction is submitted at that site and updated whenever the site receives a message with a higher clock value.
• Each transaction is assigned a unique timestamp and conflicting actions are executed in order of the timestamp of their transactions.
• Timestamps can be used in two ways:
• To determine the currency or out datedness of a request with respect to the data object it is operating on.

• To order events with respect to one another.

• In timestamp based concurrency control algorithms , the serialization order of transactions is selected a priori, and transactions are forced to follow this order

Timestamps

• Each transaction Ti, upon starting up, is assigned a timestamp TS(Ti).
• This can be implemented using either the system clock, or a logical counter that is incremented after a new timestamp is issued.
• Timestamps are used to determine the serializability order: if TS(Ti) < TS(Tj), then for a schedule to be valid, it must be equivalent to some serial schedule in which Ti appears before Tj.
• Each data item Q is associated with two timestamp values.
• WTS(Q): the timestamp of the most recent transaction that successfully executed write(Q).
• RTS(Q): the timestamp of the most recent transaction that successfully executed read(Q).

Timestamp-Ordering Protocol and Its Rules

1. When a transaction Ti issues a read(Q) instruction:
2. If TS(Ti) < WTS(Q), Ti would read a value of Q that was already overwritten by a newer transaction Tj 6= Ti
3. Hence, this read is rejected and Ti will be rolled back.
4. If TS(Ti) ≥ WTS(Q), the read is approved, and we set RTS(Q) := max{RTS(Q),TS(Ti)}.
5. Since multiple read(Q)’s are not conflict actions, there is no need to compare TS(Ti) and RTS(Q).
6. When a transaction Ti issues write(Q):
7. If TS(Ti) < RTS(Q), the write is rejected and Ti will be rolled back.
8. If TS(Ti) < WTS(Q), then Ti is trying to write an obsolete value of Q, and hence it’s not allowed and Ti is rolled back
9. Otherwise, the write is approved, and we set WTS(Q) := TS(Ti).Once again, a schedule must be equivalent to some serial schedule in which Ti appears before Tj, and this is the very reason behind all rejection rules specified above.