1. Timestamp Ordering Concurrency Control

Timestamp Ordering (T/O) determine serializability order of txns before they execute.

Use timestamps to determine the serializability order of txns.

If $TS(T_i ) < TS(T_j )$, then the DBMS must ensure that the execution schedule is equivalent to a serial schedule where $T_i$ appears before $T_j$ .

1.1 Allocation

Each txn $T_i$ is assigned a unique fixed timestamp that is monotonically increasing.

• Let $TS(T_i )$ be the timestamp allocated to txn $T_i$ .
• Different schemes assign timestamps at different times during the txn.

There are multiple timestamp allocation implementation strategies.

• The DBMS can use the system clock as a timestamp
  • but issues arise with edge cases like daylight shifting.
• Another option is to use a logical counter.
  • However, this has issues with overflow and with maintaining the counter across a distributed system with multiple machines.
• There are also hybrid approaches that use a combination of both methods.

2. Basic Timestamp Ordering (T/O) Protocol

Txns read and write objects without locks.

Every object X is tagged with timestamp of the last txn that successfully did read/write

Check timestamps for every operation:

• If a transaction tries to access an object in a way which violates the timestamp ordering, the transaction is aborted and restarted