Concurrency Control in DBMS - Database Management System (DBMS) - Computer

Introduction

Concurrency control deals with interleaved execution of more than one transaction on a shared database. Interleaving increases system throughput and resource utilisation but may produce incorrect results unless controlled. This chapter explains transactions, schedules, serializability, anomalies, recovery-related schedule properties and the main concurrency-control protocols used in practice.

What is a Transaction?

A transaction is a sequence of logically related database operations that must be executed as a unit to preserve database consistency. Typical low-level operations used to describe transactions are:

• Read(A) or R(A): Read the value of item A from the database into a local buffer (main memory).
• Write(A) or W(A): Write the value of item A from the local buffer back to the database.

Note: A write operation in a transaction often updates a buffer first; the buffer may not be flushed to disk immediately. This is why dirty read anomalies can occur unless the concurrency protocol prevents them.

Example - a simple debit transaction on account A:

• R(A);
• A := A - 1000; (update performed in local buffer)
• W(A);

If A = 5000 initially, the sequence yields A = 4000 after W(A). If the transaction fails before W(A), the database still holds A = 5000; recovery or roll-back must ensure atomic behaviour.

Commit and Rollback

• Commit: When a transaction finishes successfully, the DBMS makes its changes permanent.
• Rollback (Abort): If a transaction cannot complete, the DBMS undoes its changes so the database returns to a state as if the transaction never executed.

ACID Properties

Transactions are characterised by the ACID properties. Each is essential to maintain correctness in multi-user environments.

• Atomicity: A transaction is atomic: either all its operations take effect, or none do.
• Consistency: A transaction when executed from a consistent database must leave the database in a consistent state. Application constraints (such as account sum invariants) remain satisfied.
• Isolation: The intermediate state of a transaction must not be visible to other transactions. A transaction's effects become visible to others only after commit.
• Durability: Once a transaction commits, its effects persist despite subsequent failures; committed updates are not lost.

What is a Schedule?

A schedule is an interleaving (sequence) of operations from a set of transactions. Schedules describe the order in which operations of concurrent transactions are executed by the DBMS.

• Serial schedule: One transaction executes completely before the next begins. Serial schedules preserve correctness easily but have low concurrency.
• Concurrent (interleaved) schedule: Operations of different transactions are interleaved. Concurrent schedules raise the need for concurrency control because interleaving can produce incorrect results.

Example of an anomaly from interleaving

Consider T1: debit Rs.1000 from A and T2: credit Rs.500 to A, with initial A = 5000.

• T1 reads A (5000) to its buffer.
• T2 reads A (5000) to its buffer.
• T1 updates buffer to 4000 and writes it back.
• T2 updates its buffer to 5500 and writes it back.

Final value 5500 shows T1's effect was lost. This inconsistency must be prevented by concurrency control protocols.

Table 1 

Properties of Schedules Related to Recovery

Some schedule classes are defined to ensure recoverability and avoid undesirable cascaded aborts. These properties are important when devising concurrency control mechanisms.

• Recoverable schedule: If a transaction Tj reads a value written by Ti, then Tj must commit only after Ti commits. This prevents Tj from committing based on a value that might later be undone if Ti aborts.
• Cascadeless schedule: A stronger condition: transactions may only read committed values. That is, no transaction reads from an uncommitted write of another transaction. Cascadeless schedules prevent cascading aborts.
• Strict schedule: Even stronger: a transaction may neither read nor write a data item modified by another uncommitted transaction. Strict schedules greatly simplify recovery because when a transaction aborts, no other transaction has read the dirty values and no cascading aborts are needed.

Serializability

Serializability is the principal correctness criterion for concurrent schedules. A concurrent schedule is correct if its outcome is equivalent to some serial execution of the same transactions.

Types of Serializability

• Conflict serializability: A schedule is conflict serialisable if it can be transformed to a serial schedule by swapping non-conflicting adjacent operations. Conflicting operations are pairs of operations by different transactions that access the same data item and at least one of them is a write.
• View serializability: A schedule is view serialisable if it produces the same final values and read-from relationships as some serial schedule. View serializability is more general than conflict serializability but harder to test.

Conflict Graph (Precedence Graph) Method

To test conflict serializability construct a precedence graph (also called a conflict graph):

• Each transaction is a node.
• For every pair of conflicting operations (one from Ti and one from Tj) on the same data item, add a directed edge Ti → Tj if Ti's operation precedes Tj's in the schedule.
• If the precedence graph is acyclic, the schedule is conflict serialisable; topological order of the graph gives an equivalent serial order.

Example: Checking conflict serializability

Given a schedule S, identify all read/write and write/write conflicts and build the graph. If a cycle exists, S is not conflict serialisable.

Common Anomalies (Phenomena)

Database textbooks list canonical anomalies to classify concurrency problems. Some important ones are:

• Dirty read: A transaction reads a value written by another uncommitted transaction.
• Non-repeatable read: A transaction reads the same item twice and gets different values because another transaction updated and committed in between.
• Phantom read: A transaction re-executes a query and finds rows inserted or deleted by another committed transaction.

Concurrency Control Protocols

Several protocols enforce serialisability (or weaker guarantees) while allowing concurrent execution. The most commonly used are locking protocols, timestamp ordering, and optimistic (validation) concurrency control.

Locking-based Protocols

Locking is the most widely used technique. Two basic lock modes are:

• Shared lock (S): Allows concurrent reads but prevents writes.
• Exclusive lock (X): Allows read and write by the locking transaction only; prevents others from reading or writing.

Transactions must acquire locks before accessing data and release them later according to the locking protocol.

Two-Phase Locking (2PL)

Two-phase locking (2PL) enforces serialisability by forcing each transaction to operate in two phases:

• Growing phase: The transaction acquires all the locks it needs; it may not release any lock in this phase.
• Shrinking phase: The transaction releases locks; it may not acquire new locks.

When all transactions follow 2PL, schedules are guaranteed to be conflict serialisable.

Variants of 2PL

• Basic 2PL: As above; ensures conflict serialisability.
• Strict 2PL: A transaction holds all its exclusive locks until it commits or aborts. This yields strict schedules that simplify recovery since no other transaction reads uncommitted writes.
• Rigorous 2PL: All locks (both shared and exclusive) are held until commit; this provides even stronger guarantees and simplifies concurrency control but reduces concurrency.

Deadlocks and Their Handling

Locking can cause deadlock, where two or more transactions wait forever for locks held by each other. Common approaches to handle deadlocks:

• Deadlock prevention: Impose an ordering or use timestamp-based rules (wait-die, wound-wait) to avoid cyclic waits.
• Deadlock detection: Build a wait-for graph; if a cycle is detected, choose a victim transaction to abort and release its locks.
• Deadlock avoidance: Use techniques like immediate abort on conflict or optimistic concurrency where blocking is minimised.

Multi-Granularity Locks and Intention Locks

To allow locking at different granularities (database, table, page, row), DBMSs use intention locks (e.g., IS, IX) to indicate that a transaction intends to acquire finer-grained locks. Multi-granularity locking protocols enable concurrency control efficiently over large data structures.

Timestamp Ordering (TO)

Timestamp ordering assigns each transaction a unique timestamp when it starts. The protocol ensures the execution order is consistent with timestamp order using read and write timestamps associated with each data item. If an operation violates timestamp order, either the operation is aborted or the write may be discarded based on rules.

Thomas's write rule: An optimisation for timestamp ordering that allows ignoring obsolete writes (if a write is older than the last read by a newer transaction) without aborting the writing transaction. This can increase concurrency while preserving serialisability under certain conditions.

Optimistic Concurrency Control (Validation)

Optimistic methods allow transactions to execute without restrictions and validate at commit time whether serialisability would be violated. Typical validation has three phases:

• Read phase: Transaction reads and makes updates to local copies.
• Validation phase: At commit, check whether the transaction is serialisable with respect to other committed transactions.
• Write phase: If validation succeeds, apply changes; otherwise abort and retry.

Optimistic methods work well for workloads with low conflict rates.

Recoverability, Cascading Aborts and Strictness - Examples

Consider three transactions Ti, Tj and Tk where Tj reads a value written by Ti and Tk reads a value written by Tj. If Ti aborts, both Tj and Tk may need to be rolled back if they had read uncommitted values - this is a cascading abort. Cascadeless and strict schedules prevent such chains and simplify recovery.

Practical Considerations and Performance

When choosing a concurrency control strategy DBMS designers trade off between:

• Degree of concurrency allowed (throughput).
• Cost and likelihood of aborts and rollbacks.
• Implementation complexity (locks, timestamp maintenance, validation phases).
• Recovery simplicity (strict schedules simplify recovery logic and logging).

Most commercial DBMSs use variants of locking (strict or rigorous 2PL) with deadlock detection; some systems use MVCC (multi-version concurrency control) which combines timestamp ideas to provide high concurrency for read-heavy workloads.

Exam Question (Preserved)

Q. Consider the following transaction involving two bank accounts x and y: 
1. read(x);
2. x := x - 50;
3. write(x);
4. read(y);
5. y := y + 50;
6. write(y);
The constraint that the sum of the accounts x and y should remain constant is that of? 
(a) Atomicity
(b) Consistency
(c) Isolation
(d) Durability
Ans: (b)
Solution: As discussed in properties of transactions, consistency properties says that sum of accounts x and y should remain constant before starting and after completion of transaction. So, the correct answer is B.

Summary

This chapter presented transactions and schedules, explained why concurrent execution needs careful control, and defined serialisability as the main correctness criterion. It introduced conflict and view serialisability, the precedence-graph test, recoverability/cascading/strict schedules, and the major concurrency control families: locking (2PL variants), timestamp ordering (and Thomas's rule), and optimistic validation. Practical DBMS design chooses protocols based on workload characteristics, recovery needs and desired concurrency.