Basic Timestamp Ordering
Every transaction is issued a timestamp based on when it enters the system. Suppose, if an old transaction Ti has timestamp TS(Ti), a new transaction Tj is assigned timestamp TS(Tj) such that TS(Ti) < TS(Tj). The protocol manages concurrent execution such that the timestamps determine the serializability order. The timestamp ordering protocol ensures that any conflicting read and write operations are executed in timestamp order. Whenever some Transaction T tries to issue a R_item(X) or a W_item(X), the Basic TO algorithm compares the timestamp of T with R_TS(X) & W_TS(X) to ensure that the Timestamp order is not violated. This describes the Basic TO protocol in the following two cases.
- Whenever a Transaction T issues a W_item(X) operation, check the following conditions:
- If R_TS(X) > TS(T) and if W_TS(X) > TS(T), then abort and rollback T and reject the operation. else,
- Execute W_item(X) operation of T and set W_TS(X) to TS(T).
- Whenever a Transaction T issues a R_item(X) operation, check the following conditions:
- If W_TS(X) > TS(T), then abort and reject T and reject the operation, else
- If W_TS(X) <= TS(T), then execute the R_item(X) operation of T and set R_TS(X) to the larger of TS(T) and current R_TS(X).
Whenever the Basic TO algorithm detects two conflicting operations that occur in an incorrect order, it rejects the latter of the two operations by aborting the Transaction that issued it. Schedules produced by Basic TO are guaranteed to be conflict serializable. Already discussed that using Timestamp can ensure that our schedule will be deadlock free.
One drawback of the Basic TO protocol is that Cascading Rollback is still possible. Suppose we have a Transaction T1 and T2 has used a value written by T1. If T1 is aborted and resubmitted to the system then, T2 must also be aborted and rolled back. So the problem of Cascading aborts still prevails. Let’s gist the Advantages and Disadvantages of Basic TO protocol:
- Timestamp Ordering protocol ensures serializability since the precedence graph will be of the form:
Precedence Graph for TS ordering
- Timestamp protocol ensures freedom from deadlock as no transaction ever waits.
- But the schedule may not be cascade free, and may not even be recoverable.
Timestamp based Concurrency Control
Timestamp-based concurrency control is a method used in database systems to ensure that transactions are executed safely and consistently without conflicts, even when multiple transactions are being processed simultaneously. This approach relies on timestamps to manage and coordinate the execution order of transactions. Refer to the timestamp of a transaction T as TS(T).