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

Domains, Every simple attribute of an entity type have a possible set of va...

Every simple attribute of an entity type have a possible set of values that can be attached to it. This is known as the domain of an attribute. An attribute cannot have a value out

Define query language, Define query language?   A query is a statement ...

Define query language?   A query is a statement requesting the retrieval of information. The portion of DML that includes information retrieval is known as a query language.

Explain the two types of participation constraint, Explain the two types of...

Explain the two types of participation constraint.  Total: The participation of an entity set E in a relationship set R is said to be total if each entity in E participates i

Perform an exploratory analysis on the entire dataset, Australian Bureau of...

Australian Bureau of Statistics (ABS) provides retail data for different groups and different states as well as the aggregate numbers. Table 11 " Retail Turnover, State by Industry

Explain the term- periodic recomputation, Explain the term- Periodic recomp...

Explain the term- Periodic recomputation Periodic recomputation:  Base values are often updated in bunches. Sometimes, it is possible to just recompute all derived attributes p

Explain mechanism of nested queries, Explain mechanism of nested queries? ...

Explain mechanism of nested queries? SQL gives a mechanism for nesting subqueries. A subquery is a select from where expression that is nested within one more query. A common u

Write short notes on schema diagram, Write short notes on Schema diagram.  ...

Write short notes on Schema diagram.  A database schema along with primary key and foreign key dependencies can be depicted pictorially by schema  diagram. Every relation appea

Data model, data models are being replaced over years. Reasons and why does...

data models are being replaced over years. Reasons and why does that happen?

Explain interfaces for parametric users, Explain Interfaces for parametric ...

Explain Interfaces for parametric Users? Interfaces for Parametric Users - Parametric users, such as bank tellers, frequent have a little set of operations in which they must p

What is serialization and where it is used, What is serialization? Where it...

What is serialization? Where it is used and why?  Serialization is a basic term used for mechanisms which enable objects and object structures to be converted into portable for

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