Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Graph-based protocol
Tree protocol 
 The tree protocol is a type of graph-based protocol.  
Frequently asked questions
Key takeaways
Last Updated: Mar 27, 2024

Graph-based protocol

Author Ankit Kumar
1 upvote
Master Python: Predicting weather forecasts
Ashwin Goyal
Product Manager @


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. 

Recommended Topic - Specialization and Generalization in DBMS, Multiple Granularity in DBMS

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.  


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. 


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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job

Frequently asked questions

  1. What are the applications of graph-based protocols?
    As an alternative to 2-PL, Graph-Based Protocols are utilized.
  2. Can deadlocks occur in graph-based protocols?
    No, the graph-based protocol completely avoids the deadlocks.
  3. 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.

Previous article
Implementation of Locking
Next article
Two-Phase Locking
Live masterclass