🔄 CONCURRENCY CONTROL IN DBMS

🔄 CONCURRENCY CONTROL IN DBMS

Locks • 2PL • Strict 2PL • Rigorous 2PL • Conservative 2PL • Timestamp

📘 What is Concurrency Control?

Concurrency control is a collection of techniques used by a DBMS to control the simultaneous execution of multiple transactions.

The main purpose is to maintain:
✔ Consistency
✔ Isolation
✔ Serializability
✔ Correct database results

This module explains both: Lock-Based Concurrency Control and Timestamp-Based Concurrency Control.

🔄 Why Concurrency Control?

When several transactions execute at the same time, their operations may overlap. Without proper concurrency control, the database may produce incorrect results.

Common Problems

Problem	Description
Lost Update	One transaction overwrites another transaction's update.
Dirty Read	A transaction reads uncommitted data.
Non-Repeatable Read	The same data gives different values during a transaction.
Incorrect Summary	A calculation reads inconsistent intermediate values.

Goal: Concurrent transactions should produce a result equivalent to a correct serial execution.

📖 READ and WRITE Operations

A transaction generally performs two fundamental operations:

READ(X) → Read the value of X.

WRITE(X) → Modify the value of X.

Example

T1
READ(A)
A = A - 100
WRITE(A)

Lost Update Example

1

T1 reads A = ₹1000.

2

T2 also reads A = ₹1000.

3

T1 changes A to ₹900.

4

T2 changes A to ₹800 using its earlier value.

One transaction's update can overwrite another transaction's update. → Lost Update

🔐 Locks

A lock is a mechanism used by a DBMS to control access to a data item while transactions execute concurrently.

Shared Lock — S Lock

S(X) → Shared Lock
Mainly used for READ

Multiple transactions can generally hold shared locks on the same data item.

Exclusive Lock — X Lock

X(X) → Exclusive Lock
Used for WRITE

An exclusive lock conflicts with both shared and exclusive locks.

📊 Lock Compatibility

Existing	Requested S	Requested X
S	✅ Allowed	❌ Not Allowed
X	❌ Not Allowed	❌ Not Allowed

Example

1

T1 has S(A).

2

T2 requests S(A).

S + S → Allowed because both transactions are reading.

3

T2 requests X(A).

S + X → Not allowed. T2 must wait.

2️⃣ Two-Phase Locking — 2PL

Two-Phase Locking divides transaction execution into two phases.

GROWING PHASE ↓ Acquire Locks ↓ SHRINKING PHASE ↓ Release Locks

Growing Phase

Locks can be acquired but no lock can be released.

Shrinking Phase

Locks can be released but no new lock can be acquired.

After the transaction releases its first lock, it cannot acquire a new lock under basic 2PL.

Example

X(A)
X(B)
READ / WRITE
UNLOCK(A)
UNLOCK(B)

🔒 Strict Two-Phase Locking

In Strict 2PL, a transaction holds all its exclusive locks until it commits or aborts.

X(A) ↓ WRITE(A) ↓ COMMIT ↓ UNLOCK(A)

Example

1

T1 obtains X(A).

2

T1 writes A.

3

T2 requests X(A).

4

T2 waits.

5

T1 commits.

6

T1 releases X(A).

T2 can now obtain X(A).

🛡️ Rigorous 2PL

In Rigorous 2PL, both shared and exclusive locks are retained until the transaction commits or aborts.

S(A) + X(B) ↓ READ(A) + WRITE(B) ↓ COMMIT ↓ RELEASE ALL LOCKS

Strict 2PL: X locks held until commit/abort.

Rigorous 2PL: ALL locks held until commit/abort.

⏳ Conservative 2PL

Conservative 2PL, also called Static 2PL, requires a transaction to obtain all the locks it needs before it begins execution.

REQUEST ALL LOCKS ↓ ALL AVAILABLE? ↓ YES → START

NO → WAIT

Example

T1 needs: X(A), X(B), S(C)

T1 requests all three locks before executing. If any required lock is unavailable, T1 waits without holding a partial set of locks.

This prevents deadlocks caused by incremental lock acquisition.

🏦 Transaction Example

T1: Transfer ₹500 from A to B

T2: Transfer ₹200 from B to A

Strict 2PL

1

T1 obtains X(A).

2

T1 obtains X(B).

3

T1 performs the transfer.

4

T2 requests X(B).

5

T2 waits.

6

T1 commits.

7

T1 releases locks.

8

T2 continues.

⚠️ Deadlock

Deadlock occurs when transactions wait for each other indefinitely.

T1 holds X(A)
T2 holds X(B)

T1 → requests X(B)
T2 → requests X(A)

T1 waits for T2.
T2 waits for T1.

DEADLOCK ❌

Conservative 2PL avoids lock-acquisition deadlock by requiring all locks to be obtained before execution.

✅ Serializability

A schedule is serializable if its final result is equivalent to the result of some serial execution of the transactions.

Serial:
T1 → T2

Concurrent:
T1 → T2 → T1 → T2

2PL guarantees conflict serializability.

⏱️ Timestamp-Based Concurrency Control

Timestamp Ordering is a concurrency-control technique that uses timestamps instead of locks to determine the correct order of conflicting operations.

Every transaction receives a unique timestamp.

Transaction Timestamp

TS(T1) = 10
TS(T2) = 20
TS(T3) = 30

Smaller timestamp → Older transaction

Larger timestamp → Newer transaction

Therefore: T1 → T2 → T3

Data Item Timestamps

For every data item X, the DBMS maintains:

RTS(X) = largest timestamp of a transaction that successfully read X.

WTS(X) = largest timestamp of a transaction that successfully wrote X.

📖 Timestamp READ Rule

Suppose transaction T wants to perform:

READ(X)

The DBMS compares: TS(T) with WTS(X).

Rule

IF TS(T) < WTS(X) ↓ READ REJECTED ↓ ABORT / RESTART

IF TS(T) ≥ WTS(X) ↓ READ ALLOWED

Numerical Example

TS(T1) = 10
WTS(A) = 5

T1 → READ(A)

1

TS(T1) = 10

2

WTS(A) = 5

3

Compare 10 ≥ 5

READ(A) → ALLOWED ✅

Then:
RTS(A) = max(RTS(A),10)

✍️ Timestamp WRITE Rule

Suppose transaction T wants:

WRITE(X)

The DBMS checks: RTS(X) and WTS(X).

Rule 1

IF TS(T) < RTS(X) ↓ WRITE REJECTED ↓ ABORT / RESTART

Rule 2

IF TS(T) < WTS(X) ↓ WRITE REJECTED ↓ ABORT / RESTART

Otherwise

TS(T) ≥ RTS(X) AND TS(T) ≥ WTS(X) ↓ WRITE ALLOWED

After successful WRITE:

WTS(X) = TS(T)

🧮 Complete Timestamp Example

Initial Values

TS(T1) = 10
TS(T2) = 20

RTS(A) = 0
WTS(A) = 0

Step 1 — T1 READ(A)

1

TS(T1) = 10

2

WTS(A) = 0

3

10 ≥ 0

READ(A) → ALLOWED

RTS(A) = 10

Step 2 — T2 WRITE(A)

1

TS(T2) = 20

2

RTS(A) = 10 → 20 ≥ 10

3

WTS(A) = 0 → 20 ≥ 0

WRITE(A) → ALLOWED

WTS(A) = 20

Step 3 — T1 READ(A)

1

TS(T1) = 10

2

WTS(A) = 20

3

10 < 20

READ(A) → REJECTED ❌

T1 is older than the transaction that already wrote A. Under basic timestamp ordering: T1 → ABORT / RESTART

⚡ Thomas Write Rule

Thomas Write Rule is a modification of basic timestamp ordering. It can ignore certain obsolete WRITE operations rather than aborting the transaction.

Example

TS(T1) = 10
WTS(A) = 20

T1 → WRITE(A)

Here:

TS(T1) < WTS(A)
10 < 20

The write by T1 is obsolete because a newer transaction has already written A.

Under Thomas Write Rule, this obsolete WRITE can be ignored instead of aborting T1.

Thomas Write Rule is a modification of the basic timestamp-ordering WRITE rule; it does not mean that every failed write is automatically ignored.

⚖️ Concurrency Control Comparison

Feature	2PL	Timestamp Ordering
Basic Mechanism	Locks	Timestamps
Main Information	S/X Locks	TS, RTS, WTS
Waiting	Possible	Basic protocol generally avoids lock waiting
Lock Deadlock	Possible	No lock-based deadlock
Ordering	Lock protocol	Timestamp order
Serializability	Conflict serializability	Timestamp-order based serializability

Easy Memory Trick

2PL
LOCK → EXECUTE → UNLOCK

TIMESTAMP
COMPARE TIMESTAMP → ALLOW / REJECT

🎯 Complete Step-by-Step Comparison

Method 1 — Lock Based

T1 → X(A)
T1 → WRITE(A)
T1 → COMMIT
T1 → UNLOCK(A)

The lock controls whether another transaction can access A.

Method 2 — Timestamp Based

TS(T1) = 10
WTS(A) = 5

T1 → READ(A)

1

Compare TS(T1) and WTS(A).

2

10 ≥ 5.

3

READ(A) is allowed.

4

Update RTS(A).

Lock Based: Uses locks.

Timestamp Based: Uses timestamps.

❓ Important Questions & Answers

Q1. What is concurrency control?

Concurrency control is the collection of DBMS techniques used to manage simultaneous transactions while maintaining correctness, consistency and isolation.

Q2. What is Two-Phase Locking?

2PL divides transaction execution into a Growing Phase, where locks are acquired, and a Shrinking Phase, where locks are released.

Q3. What is Strict 2PL?

Strict 2PL keeps exclusive locks until the transaction commits or aborts.

Q4. What is Rigorous 2PL?

Rigorous 2PL keeps both shared and exclusive locks until commit or abort.

Q5. What is Conservative 2PL?

Conservative 2PL requires a transaction to obtain all required locks before it begins execution.

Q6. What is timestamp ordering?

Timestamp ordering is a concurrency-control technique that uses transaction timestamps to determine whether conflicting READ and WRITE operations are allowed.

Q7. What is RTS(X)?

RTS(X) is the largest timestamp of a transaction that has successfully read data item X.

Q8. What is WTS(X)?

WTS(X) is the largest timestamp of a transaction that has successfully written data item X.

Q9. What is the timestamp READ rule?

READ(X) is allowed when TS(T) is greater than or equal to WTS(X). If TS(T) is smaller than WTS(X), the read is rejected and the transaction normally aborts/restarts.

Q10. What is the timestamp WRITE rule?

Under basic timestamp ordering, WRITE(X) is allowed when TS(T) is greater than or equal to both RTS(X) and WTS(X). Otherwise the write is rejected and the transaction normally aborts/restarts.

Q11. What is Thomas Write Rule?

Thomas Write Rule allows certain obsolete write operations to be ignored instead of aborting the transaction.

Q12. What is the difference between 2PL and timestamp ordering?

2PL is lock-based concurrency control, whereas timestamp ordering uses timestamps and does not require lock-based coordination.

B.K. PAUL

Bhairab Ganguly College

DBMS • Concurrency Control • 2PL • Timestamp Ordering

Interactive Learning Module