Concurrency Control in DBMS

Serializability, Precedence Graphs, and Multiple Granularity Locking

In the previous article, we learned about schedules and the common problems caused by concurrent execution.
Now we will study:

  • How DBMS determines whether a concurrent schedule is correct
  • How to use a Graph-Based Concurrency Control Protocol
  • How locking at different granularities improves performance

1. Serializability Recap

A schedule is serializable if the result of concurrent execution is equivalent to the result of some serial (one-after-another) schedule.

There are two main types:

  1. Conflict Serializability
  2. View Serializability

Conflict serializability is easier to test and more commonly used in practical DBMS.

2. Graph-Based Concurrency Control Protocol

This protocol uses a precedence graph (also called a serialization graph) to check whether a given schedule is conflict serializable.
The graph helps determine whether the schedule can be reordered into a serial schedule without conflicts.

2.1 Constructing a Precedence Graph

A precedence graph is built using:

  • Nodes representing transactions
  • Directed edges representing ordering relationships due to conflicts

Steps to construct the graph:

  1. Create a node for every transaction in the schedule
  2. For each pair of conflicting operations (from different transactions) on the same data item:
    • Add an edge from transaction Ti to transaction Tj if Ti’s operation appears before Tj’s operation in the schedule

2.2 What Is a Conflict?

Two operations conflict if they satisfy all three:

  • They belong to different transactions
  • They access the same data item
  • At least one of them is a write

Conflicting pairs include:

  • Read – Write
  • Write – Read
  • Write – Write

Read – Read does not conflict.

3. Detecting Serializability Using the Graph

Once the graph is constructed:

  • If the graph contains no cycles, the schedule is conflict-serializable
  • If there is at least one cycle, the schedule is not serializable

Example

Schedule:

T1: R(A) 

T2: R(A) 

T1: W(A) 

T2: W(A)

  • Conflicting operations:
    • T1’s W(A) and T2’s W(A)

Precedence graph:

T1 → T2

No cycle exists ⇒ Serializable
Equivalent serial schedule: T1 followed by T2

Non-Serializable Example

Schedule:

T1: R(A) 

T2: W(A) 

T1: W(A)

Conflicts:

  • T1’s R(A) and T2’s W(A) ⇒ T1 → T2
  • T2’s W(A) and T1’s W(A) ⇒ T2 → T1

Graph:

T1 → T2 

T2 → T1

Cycle exists ⇒ Not serializable

This method is known as the Graph-Based Concurrency Control Protocol and is widely used to check the correctness of schedules.
(Reference: geeksforgeeks.org/dbms/graph-based-concurrency-control-protocol-in-dbms/)

4. Locking and Granularity

Concurrency control often uses locks to prevent conflicting access.
Locks can be applied at different levels of granularity — from entire tables to specific records.

5. Multiple Granularity Locking

Multiple Granularity Locking allows locks at various levels:

  • Database
  • Table
  • Page
  • Record

This improves performance by allowing transactions to lock only what they really need.

5.1 Intention Locks

When looking at higher levels (like the table), the system also needs to indicate intentions at lower levels (like the rows).

There are intention locks:

  • Intention Shared (IS)
  • Intention Exclusive (IX)

They indicate that a transaction intends to acquire finer-grained locks later.

5.2 Compatibility Table

Multiple granularity locking uses a compatibility matrix for locks at different levels.

Example:

  • A transaction holding an IX lock on a table can still allow another transaction to get an IS lock on the same table.
  • Butana X (exclusive) lock cannot be shared

The rule:

A transaction must obtain an intention lock on higher-level objects before locking lower-level objects.

This ensures that two transactions do not conflict when trying to lock overlapping data at different levels.

This approach reduces unnecessary blocking and improves performance in multi-level locking environments.

(Reference: geeksforgeeks.org/dbms/multiple-granularity-locking-in-dbms/)

6. Importance of Graph Protocols and Granularity

  • Graph-based testing determines whether a schedule is correct before execution
  • Multiple granularity locking allows efficient use of locks in large databases
  • Together, they help the DBMS enforce correctness without sacrificing performance

Summary

In this article, we discussed:

  • Serializability and why it is needed
  • Graph-Based Concurrency Control Protocol usinPrecedence Graphshs
  • How to construct the graph and detect cycles
  • Multiple Granularity Locking for efficient lock usage