What are wait-for-graphs, Database Management System

Assignment Help:

What are wait-for-graphs?Give the algorithm to construct a wait-for-graph from a given schedule of transactions? How can deadlocks be detected from wait-for-graphs? 

 Ans:  The wait-for-graph is a directed graph and consists of nodes and directed arcs; the nodes of the graph are active transactions. An arc of the graph is inserted among two nodes if there is a data-item is needed by the node at the tail of the arc that is being held by the node at the head of the arc. 

  Algorithm to construct wait-for-graph is as follows:

1.  For every transaction Ti active at the time of deadlock detection, make a node labeled Ti in the wait-for-graph.

2.  For every case, if there is a transaction Ti, waiting for a data-item that is at present allocated and held by transaction Tj, then there is a directed arc from the node for transaction Ti, to the node for transaction Tj.

3.  For every case, if there is a directed arc from the node for transaction Ti, to the node for transaction Tj and transaction Tj released the lock, after that remove the arc between them.

4.  There no deadlock if the wait-for-graph is acyclic.  

The wait-for-graph is employed for detection of deadlock in the system. If there is any cycle exits in the wait-for-graph, all the active transaction (denoted as nodes) are in deadlock that are in the cycle.


Related Discussions:- What are wait-for-graphs

ERD, A student entity type has the following attributes,name..

A student entity type has the following attributes,name..

Define canonical cover, Define canonical cover? A canonical cover Fc fo...

Define canonical cover? A canonical cover Fc for F is a set of dependencies like F logically implies all dependencies in FC and Fc logically shows all dependencies in F.

Define deadlock avoidance, Define Deadlock avoidance These protocols a...

Define Deadlock avoidance These protocols as well ensure that the system will never enter a deadlock state although the way it is done is different from deadlock prevention. I

What is nested relational model, What is nested relational model? The n...

What is nested relational model? The nested relational model is an extension of relational model in which domains might be either atomic or relation valued.

Entity set that does not have sufficient attributes known as, An entity set...

An entity set that does not have sufficient attributes to form a primary key is called? An entity set that doesn't have sufficient attribute to form a primary key is known as w

Explain the exec statement in sql, Explain the EXEC statement in SQL  A...

Explain the EXEC statement in SQL  Ans: All statements which start with EXEC SQL are embedded SQL database statements. High level languages such as C can be employed to write a

What is gathering information and producing erd, What is Gathering informat...

What is Gathering information and Producing ERD Gathering information: This could be a written document that explains the system in question with reasonable quantity of detai

Define the division operation of relational algebra, Define the Division Op...

Define the Division Operation of Relational Algebra Let R be a relation comprising attributes (A1,...Ap,Ap+1,...An) and S comprising attributes (Ap+1,...An)  DEF: Division

Find a 3nf decomposition , Find a 3NF decomposition of the following relati...

Find a 3NF decomposition of the following relation scheme: University (Faculty, Dean, Department, Chair, Professor, Rank, Student}. The University relation satisfies the following

System Analysis and design, Using the questions found at the end of Chapter...

Using the questions found at the end of Chapter 9 in your textbook, complete this homework activity. Students will submit a Word document answering questions 2, 3, and 4.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd