Can deadlocks occur in graph-based protocols?

No, the graph-based protocol completely avoids the deadlocks.

Dirty Read is not permitted, which means that reading data written by an uncommitted operation is prohibited. It's possible that you'll have an issue with a lost update. Because there is always the possibility that the uncommitted transaction will be rolled back later, it is referred to as a dirty read. As a result, uncommitted transactions may cause other transactions to read values that do not exist. As a result, the database becomes inconsistent.

Graph-based protocol - Naukri Code 360

Introduction

The article aims to explain to you the Graph-based protocol. First, we will learn about protocol. Then we will learn briefly about different types of Graph-based protocols. After that, we will look into the advantages and drawbacks of the protocols.

Must Recommended Topic, Generalization in DBMS.

Recommended Topic, Schema in DBMS,Lock based protocol in DBMS

Graph-based protocol

As we all know, one of the most challenging aspects of the Lock Based Protocol has been preventing deadlocks and maintaining a strict schedule. Strict Schedules are possible while following Strict or Rigorous 2-PL. We've even observed that following Conservative 2-PL can prevent deadlocks, however, the problem with this protocol is that it can't be employed in practice. As an alternative to 2-PL, Graph-Based Protocols are utilized. A basic implementation of Graph-Based Protocol is Tree-Based Protocols.

Two-phase locking can be replaced using graph-based methods.

Apply a partial ordering to the A = a1 set. and a2 …., ah, in all of the data elements

If ai, aj, then any transaction involving both ai and aj will fail. also, ai must gain access to before using aj

Infers that set A may now be considered a directed acyclic set is known as a database graph.

Tree protocol

The tree protocol is a type of graph-based protocol.

A tree-like structure is determined by partial ordering on database elements.
Exclusive Locks are the only ones that can be used.
ai's initial lock might be on any data object. As a result, ai can lock a data Q only if the parent of Q is now locked by ai.
At any point, data items can be unlocked.
The Tree-based Protocol enables conflict serialization and deadlock-free scheduling. We don't have to wait for a Data item to be unlocked, as we did in the 2-PL protocol, which increases concurrency.
shortened wait times and increased concurrency
The protocol is deadlock-free; thus, no rollbacks are necessary.

Drawbacks

However, the protocol has the drawback of requiring a transaction to lock data items that it does not access in some instances. A transaction, for example, that wants to access data items A and F in the database graph must lock not just A and F but also data items B. This additional locking increases locking overhead, the chance of extra waiting time, and the risk of decreased concurrency. Furthermore, without previous knowledge of which data items would need to be locked, transactions will be forced to lock the tree's root, which can significantly restrict concurrency.

However, the protocol does not ensure recoverability or cascade freedom! To enable recoverability, commit dependencies must be introduced.
Transactions may be required to lock data items that they do not use. increased locking overhead, as well as extra waiting time, a possible reduction in concurrency
Schedules that are not conceivable with two-phase locking are possible with tree protocol and vice versa.

Advantages

The tree-locking protocol offers an advantage over the two-phase locking protocol in that, unlike two-phase locking, it is deadlock-free, which eliminates the need for rollbacks. Another advantage of the tree-locking protocol over the two-phase locking approach is that unlocking can happen sooner. Early unlocking may result in lower wait times and increased concurrency.

A method for ensuring recoverability and cascadelessness

To ensure recoverability and cascadelessness, the protocol might be adjusted to prohibit the release of exclusive locks until the transaction is completed. Keeping exclusive locks until the transaction is complete limits concurrency. Here's an approach that boosts concurrency while ensuring just recoverability: We record which transaction executed the last write to the data item for each data item with an uncommitted write. When a transaction Ti reads an uncommitted data item, we record Ti's commit dependence on the transaction last written to the data item. Transaction Ti is then not allowed to commit until all transactions on which it is dependent have been committed. Ti must be aborted if any of these transactions fail.

You can also read about the Log based recovery and Checkpoint in DBMS.

Frequently asked questions

What are the applications of graph-based protocols?
As an alternative to 2-PL, Graph-Based Protocols are utilized.
Can deadlocks occur in graph-based protocols?
No, the graph-based protocol completely avoids the deadlocks.
What are cascades?
Dirty Read is not permitted, which means that reading data written by an uncommitted operation is prohibited. It's possible that you'll have an issue with a lost update. Because there is always the possibility that the uncommitted transaction will be rolled back later, it is referred to as a dirty read. As a result, uncommitted transactions may cause other transactions to read values that do not exist. As a result, the database becomes inconsistent.

Key takeaways

The article taught you about Graph-based Protocols, their Potential problems, and their advantages. Then we saw different protocol types where we learned in detail about their advantages over 2-phase locking and drawbacks.

Check out this article - File System Vs DBMS and Recursive Relationship in DBMS

Ninjas! You have taken the first yet most crucial step in learning about Concurrency Control Protocols.

Ninja, don't stop here; check out the Top 100 SQL Problems to get hands-on experience with frequently asked interview questions and land your dream job. Also, try Coding Ninjas Studio to practice programming problems for your complete interview preparation.