Advanced Database (BSc CSIT, CSC461): the questions likely to come

Concurrency Control

Concurrency control is the activity of coordinating the concurrent (interleaved) execution of transactions in a multi-user database so that the result is equivalent to some serial execution (serializability), while preserving the ACID properties. Without it, anomalies such as lost update, dirty read, and unrepeatable read can occur.

Two-Phase Locking (2PL) Protocol

2PL is a lock-based protocol. A transaction must obtain a shared lock (S) before reading and an exclusive lock (X) before writing a data item. Locking proceeds in two phases:

1. Growing phase — the transaction may acquire locks but cannot release any.
2. Shrinking phase — the transaction may release locks but cannot acquire any new lock.

The point after the last lock is acquired is the lock point. 2PL guarantees conflict serializability.

Variants: Strict 2PL holds all exclusive locks until commit/abort (prevents cascading rollback); Rigorous 2PL holds all locks until commit.

Example:

T1: lock-X(A); read(A); A=A-50; write(A);
    lock-X(B); release(A); read(B); B=B+50; write(B); release(B);

All locks are acquired before any is released, so T1 obeys 2PL. A drawback is the possibility of deadlock.

Timestamp-Based Ordering Protocol

Each transaction $T_i$ gets a unique timestamp $TS(T_i)$ at start. Each data item $X$ has two values: W-timestamp(X) (largest timestamp of a transaction that wrote X) and R-timestamp(X) (largest timestamp that read X). The protocol orders transactions by their timestamps and ensures the schedule is equivalent to executing them in timestamp order.

Read rule (Ti reads X):

• If $TS(T_i) < W\text{-}TS(X)$ → $T_i$ is too late; reject and roll back $T_i$.
• Else read is allowed; set $R\text{-}TS(X) = \max(R\text{-}TS(X), TS(T_i))$.

Write rule (Ti writes X):

• If $TS(T_i) < R\text{-}TS(X)$ or $TS(T_i) < W\text{-}TS(X)$ → reject and roll back $T_i$.
• Else write is allowed; set $W\text{-}TS(X) = TS(T_i)$.

Example: Suppose $TS(T_1)=5$, $TS(T_2)=10$. If $T_2$ writes $X$ (so $W\text{-}TS(X)=10$) and then $T_1$ (timestamp 5) tries to write $X$, since $TS(T_1)=5 < W\text{-}TS(X)=10$, $T_1$ is rolled back and restarted with a new timestamp.

Timestamp ordering is deadlock-free (no waiting) but can cause repeated rollbacks/starvation.