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

Physical records, Physical Records These are the records that are store...

Physical Records These are the records that are stored in the secondary storage devices. For the database relation, physical records are the group of fields kept in adjacent me

What is trigger, What is Trigger? Trigger: A database trigger is proced...

What is Trigger? Trigger: A database trigger is procedural code which is automatically executed in response to specific events on a particular table in a database. Triggers can

State the design of associations, State the Design of Associations Bef...

State the Design of Associations Before designing associations, it is essential to know the way they are used. For this, analysis of association traversals is required. It is

Can you scan double-sided documents and remove blank pages, Can you scan do...

Can you scan double-sided documents - and remove blank pages? Our software and imaging systems supports duplex scanning, at the same time scanning both sides of a page. Program

Improved performance, Improved performance: As the data is located near the...

Improved performance: As the data is located near the site of its demand, and given the inherent parallelism because of multiple copies, speed of database access may be good for di

Explain the data access protocol, (a) Explain the three types of potentia...

(a) Explain the three types of potential mistake which could occur if concurrency control is not properly enforced in the database system. Support your answer with appropriate ex

Define weak and strong entity sets, Define weak and strong entity sets?  ...

Define weak and strong entity sets?  Weak entity  set:  entity  set  that  do not  have  key  attribute  of  their  own are  known as weak entity sets.  Strong entity set

What is aggregate function, What is aggregate function? Briefly describe it...

What is aggregate function? Briefly describe it? Aggregate functions are functions that take a collection of values as input and return a one value. SQL offers 5 built-in aggre

Explain the term- event, Event Occurrence of a process is called event...

Event Occurrence of a process is called event. In other words, the object can receive many input instructions. The changes which occur due to these instructions are known as e

Oracle fusion middleware, Oracle Fusion Middleware: Key Skills: Consul...

Oracle Fusion Middleware: Key Skills: Consulting,Architect, Oracle Fusion Middleware,ECM, UCM, Stellent,Identity Management, SOA Suites, BPEL, ESB,OAM,OIM,J2ee, Java, Livelink

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