Computer Science Engineering (CSE)  >  Database Management System (DBMS)  >  Graph Based Concurrency Control Protocol

Graph Based Concurrency Control Protocol Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE)

Document Description: Graph Based Concurrency Control Protocol for Computer Science Engineering (CSE) 2022 is part of Database Management System (DBMS) preparation. The notes and questions for Graph Based Concurrency Control Protocol have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Graph Based Concurrency Control Protocol covers topics like Graph Based Concurrency Control Protocol in DBMS and Graph Based Concurrency Control Protocol Example, for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Graph Based Concurrency Control Protocol.

Introduction of Graph Based Concurrency Control Protocol in English is available as part of our Database Management System (DBMS) for Computer Science Engineering (CSE) & Graph Based Concurrency Control Protocol in Hindi for Database Management System (DBMS) course. Download more important topics related with notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Computer Science Engineering (CSE): Graph Based Concurrency Control Protocol Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE)
Table of contents
Graph Based Concurrency Control Protocol in DBMS
1 Crore+ students have signed up on EduRev. Have you?

Graph Based Concurrency Control Protocol in DBMS

As we know the prime problems with Lock Based Protocol has been avoiding Deadlocks and ensuring a Strict Schedule. We’ve seen that Strict Schedules are possible with following Strict or Rigorous 2-PL. We’ve even seen that Deadlocks can be avoided if we follow Conservative 2-PL but the problem with this protocol is it cannot be used practically. Graph Based Protocols are used as an alternative to 2-PL. Tree Based Protocols is a simple implementation of Graph Based Protocol.
A prerequisite of this protocol is that we know the order to access a Database Item. For this we implement a Partial Ordering on a set of the Database Items (D) {d1, d2, d3, ….., dn} . The protocol following the implementation of Partial Ordering is stated as-

  • If di → dj then any transaction accessing both di and dj must access di before accessing dj.
  • Implies that the set D may now be viewed as a directed acyclic graph (DAG), called a database graph.

Tree Based Protocol

  • Partial Order on Database items determines a tree like structure.
  • Only Exclusive Locks are allowed.
  • The first lock by Ti may be on any data item. Subsequently, a data Q can be locked by Ti only if the parent of Q is currently locked by Ti.
  • Data items can be unlocked at any time.

Following the Tree based Protocol ensures Conflict Serializablity and Deadlock Free schedule. We need not wait for unlocking a Data item as we did in 2-PL protocol, thus increasing the concurrency.
Now, let us see an Example, following is a Database Graph which will be used as a reference for locking the items subsequently.

Database GraphDatabase Graph

Let’s look at an example based on the above Database Graph. We have three Transactions in this schedule and this is a skeleton example, i.e, we will only see how Locking and Unlocking works, let’s keep this simple and not make this complex by adding operations on data.

Graph Based Concurrency Control Protocol Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE)

From the above example, first see that the schedule is Conflict Serializable. Serializablity for Locks can be written as T2 → T1 → T3.
Data items Locked and Unlocked are following the same rule as given above and follows the Database Graph.
Thus, let’s revise once more what are the key points of Graph Based Protocols.

Advantage

  • Ensures Conflict Serializable Schedule.
  • Ensures Deadlock Free Schedule
  • Unlocking can be done anytime
  • With some advantages comes some Disadvantages also.

Disadvantage

  • Unnecessary locking overheads may happen sometimes, like if we want both D and E, then at least we have to lock B to follow the protocol.
  • Cascading Rollbacks is still a problem. We don’t follow a rule of when Unlock operation may occur so this problem persists for this protocol.

Overall this protocol is mostly known and used for its unique way of implementing Deadlock Freedom.

The document Graph Based Concurrency Control Protocol Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Database Management System (DBMS).
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Related Searches

Exam

,

ppt

,

Semester Notes

,

past year papers

,

shortcuts and tricks

,

Summary

,

study material

,

Objective type Questions

,

Graph Based Concurrency Control Protocol Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE)

,

video lectures

,

Sample Paper

,

Important questions

,

Graph Based Concurrency Control Protocol Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE)

,

mock tests for examination

,

Graph Based Concurrency Control Protocol Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE)

,

MCQs

,

Extra Questions

,

Viva Questions

,

practice quizzes

,

pdf

,

Previous Year Questions with Solutions

,

Free

;