Multiple Granularity in DBMS

In the context of database systems, "granularity" refers to the size or extent of a data item that can be locked by a transaction. The idea behind multiple granularity is to provide a hierarchical structure that allows locks at various levels, ranging from coarse-grained (like an entire table) to fine-grained (like a single row or even a single field). This hierarchy offers flexibility in achieving the right balance between concurrency and data integrity.

The concept of multiple granularity can be visualized as a tree. Consider a database system where:

• The entire database can be locked.
• Within the database, individual tables can be locked.
• Within a table, individual pages or rows can be locked.
• Even within a row, individual fields can be locked.

Lock Modes in multiple granularity

To ensure the consistency and correctness of a system that allows multiple granularity, it's crucial to introduce the concept of "intention locks." These locks indicate a transaction's intention to acquire a finer-grained lock in the future.

There are three main types of intention locks:

1. Intention Shared (IS): When a Transaction needs S lock on a node "K", the transaction would need to apply IS lock on all the precedent nodes of "K", starting from the root node. So, when a node is found locked in IS mode, it indicates that some of its descendent nodes must be locked in S mode.

Example: Suppose a transaction wants to read a few records from a table but not the whole table. It might set an IS lock on the table, and then set individual S locks on the specific rows it reads.

2. Intention Exclusive (IX): When a Transaction needs X lock on a node "K", the transation would need apply IX lock on all the precedent nodes of "K", starting from the root node. So, when a node is found locked in IX mode, it indicates that some of its descendent nodes must be locked in X mode.

Example: If a transaction aims to update certain records within a table, it may set an IX lock on the table and subsequently set X locks on specific rows it updates.

3. Shared Intention Exclusive (SIX): When a node is locked in SIX mode; it indicates that the node is explicitly locked in S mode and Ix mode. So, the entire tree rooted by that node is locked in S mode and some nodes in that are locked in X mode. This mode is compatible only with IS mode.

Example: Suppose a transaction wants to read an entire table but also update certain rows. It would set a SIX lock on the table. This tells other transactions they can read the table but cannot update it until the SIX lock is released. Meanwhile, the original transaction can set X locks on specific rows it wishes to update.

Compatibility Matrix with Lock Modes in multiple granularity

A compatibility matrix defines which types of locks can be held simultaneously on a database object. Here's a simplified matrix:

|       |   NL  |   IS   |   IX  |   S    |  SIX  |   X    |
|:-----:|:-----:|:------:|:-----:|:------:|:-----:|:------:|
|   NL  |   ✓   |   ✓   |   ✓   |   ✓   |   ✓   |   ✓   |
|   IS  |   ✓   |   ✓   |   ✓   |   ✓   |   ✓   |   ✗   |
|   IX  |   ✓   |   ✓   |   ✓   |   ✗   |   ✗   |   ✗   |
|   S   |   ✓   |   ✓   |   ✗   |   ✓   |   ✗   |   ✗   |
|  SIX  |   ✓   |   ✓   |   ✗   |   ✗   |   ✗   |   ✗   |
|   X   |   ✓   |   ✗   |   ✗   |   ✗   |   ✗   |   ✗   |

(NL = No Lock, S = Shared, X = Exclusive)

The Scheme operates as follows:-

1. A Transaction must first lock the Root Node and it can be locked in any mode.
2. Locks are granted as per the Compatibility Matrix indicated above.
3. A Transaction can lock a node in S or IS mode if it has already locked all the predecessor nodes in IS or IX mode.
4. A Transaction can lock a node in X or IX or SIX mode if it has already locked all the predecessor nodes in SIX or IX mode.
5. A transaction must follow two-phase locking. It can lock a node, only if it has not previously unlocked a node. Thus, schedules will always be conflict-serializable.
6. Before it unlocks a node, a Transaction has to first unlock all the children nodes of that node. Thus, locking will proceed in top-down manner and unlocking will proceed in bottom-up manner. This will ensure the resulting schedules to be deadlock-free.

Benefits of using multiple granularity

• Flexibility: Offers flexibility to transactions in deciding the appropriate level of locking, which can lead to improved concurrency.
• Performance: Reduces contention by allowing transactions to lock only those parts of the data that they need.

Challenges in multiple granularity

• Complexity: Managing multiple granularity adds complexity to the lock management system.
• Overhead: The lock manager needs to handle not just individual locks but also the hierarchy and compatibility of these locks.