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

Marks: 10 M

Year: Dec 2013

Time stamp based ordering

• 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:

• If TS(Ti) < WTS(Q), Ti would read a value of Q that was already overwritten by a newer transaction Tj 6= Ti
• Hence, this read is rejected and Ti will be rolled back.
• If TS(Ti) ≥ WTS(Q), the read is approved, and we set RTS(Q) := max{RTS(Q),TS(Ti)}.
• Since multiple read(Q)’s are not conflict actions, there is no need to compare TS(Ti) and RTS(Q).

2. When a transaction Ti issues write(Q):

• If TS(Ti) < RTS(Q), the write is rejected and Ti will be rolled back.
• 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
• 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.