The previous lecture discussed Two-Phase Locking (2PL), a pessimistic concurrency control method. This lecture introduces Timestamp Ordering (T/O), an optimistic approach where transactions do not require explicit locking during data access.

The core concept of T/O uses timestamps to define a serial execution order for transactions: if TS(T_i) < TS(T_j), the system must ensure that the actual schedule is equivalent to executing T_i first followed by T_j.

A timestamp is a unique identifier with a fixed length that must:

• Increase monotonically over time
• Be distinct for each transaction

Timestamp generation can use various mechanisms:

• System clock
• Logical counter
• Hybrid approaches

Basic Timestamp Ordering (BASIC T/O)

Basic T/O implements a specific variant of T/O where transactions access data without locks. Each data item maintains two timestamps:

• W_TS(X): timestamp of the last write operation
• R_TS(X): timestamp of the last read operation

At transaction completion, Basic T/O validates all operations for future data access and aborts transactions if conflicts are detected.

Read Operation Logic

func read(X) val {
    if TS(T_i) < W_TS(X) {
        abort_and_restart(T_i)
    } else {
        val := read_data(X)
        R_TS(X) = max(R_TS(X), TS(T_i))
        return val
    }
}

If a transaction attempts to read data written in the future, it's aborted and restarted with a new timestamp. Otherwise, it proceeds with reading, updating the read timestamp and maintaining a local copy for repeatable reads.

Write Operation Logic

func write(X, val) {
    if TS(T_i) < R_TS(X) || TS(T_i) < W_TS(X) {
        abort_and_restart(T_i)
    } else {
        X = val
        W_TS(X) = max(W_TS(X), TS(T_i))
    }
}

When a transaction tries to write data that was already read or written in the future, it's aborted and restarted. Otherwise, it proceeds with writing, updating the write timestamp and maintaining a local copy.

Thomas Write Rule (TWR) Optimization

In some cases, Basic T/O unnecessarily aborts transactions. For example, if T_2 writes to A, T_1's subsequent write to A will never be accessed. Therefore, TWR allows ignoring such writes instead of aborting T_1.

func write(X, val) {
    if TS(T_i) < R_TS(X) {
        abort_and_restart(T_i)
        return
    }
    if TS(T_i) < W_TS(X) {
        return
    }
    X = val
    W_TS(X) = TS(T_i)
}

TWR improves concurrency by allowing certain writes to proceed without aborting transactions.

Recoverable Schedules

A schedule is recoverable if all transactions that modify data read by another transaction commit before that transaction does. Basic T/O may produce non-recoverable schedules.

Advantages of Basic T/O:

• No deadlocks due to no waiting
• Efficient for short transactions with minimal overlap

Disadvantages:

• Long-running transactions may starve
• Additional overhead from copying data and managing timestamps
• Potential for non-recoverable schedules
• Bottlenecks in high-concurrency environments

Optimistic Concurrency Control (OCC)

OCC, proposed by H.T. Kung, operates in three phases:

1. Read Phase: Records read/write sets to private workspace
2. Validation Phase: Checks for conflicts upon commit
3. Write Phase: Applies changes if valid, otherwise aborts

During validation, OCC checks whether concurrent transactions conflict through either forward or backward validation methods.

Forward validation checks against committed transactions, while backward validation checks against uncommitted ones.

OCC excels when conflicts are rare, particularly in read-heavy workloads with low data contention.

Partition-Based T/O

Database partitions allow independent timestamp ordering within segments. Transactions acquire locks on required partitions before execution.

Read operations are allowed once partition locks are obtained. Write operations modify data local with rollback buffers.

Performance depends on:

• Early identification of required partitions
• Prevalence of single-partition transactions

Dynamic Database Considerations

Insertion and deletion operations introduce phantom problems, where repeated queries return different results.

Solutions include:

• Re-execution of scans
• Predicate locking (using logical expressions)
• Index locking (locking index pages)
• Locking without indexes (locking antire tables)

Isolation Levels

Isolation levels determine how much transaction modifications are visible to concurrent transactions:

• Serializable: Highest isolation level, prevents all anomalies
• Repeatable Read: Prevents dirty and non-repeatable reads
• Read Committed: Allows dirty reads, prevents lost updates
• Read Uncommitted: Lowest isolation, allows all enomalies

Different databases implement varying default and maximum isolation levels. For instance:

Additional levels like Cursor Stability and Snapshot Isolation offer trade-offs between consistency and performance.

SQL-92 defines commands for setting isolation levels:

SET TRANSACTION ISOLATION LEVEL <level>;
BEGIN TRANSACTION ISOLATION LEVEL <level>;

Access modes specify whether transactions modify data:

SET TRANSACTION <mode>;
BEGIN TRANSACTION <mode>;

Where mode can be READ WRITE or READ ONLY.