Explain the rules for creating a labelled precedence graph, Database Management System

Assignment Help:

Explain the rules for creating a labelled precedence graph for testing view serializability.          

 Ans: A schedule S is view serializable if it is view equivalent to a serial schedule 

  • Each conflict serializable schedule is also view serializable
  • A schedule that is view serializable but not conflict serializable:

Testing for Serializability 

  • Refer some schedule of a set of transactions T1, T2... Tn
  • Precedence graph is a direct graph in which the vertices denote the transactions
  • We illustrate an arc from Ti to Tj if the two transaction conflict and Ti accessed the data item earlier on which the conflict arose
  • We may label the arc through the item on which the conflict arose. A schedule is conflict serializable if and only if its precedence graph is acyclic
  • If precedence graph is acyclic, the serializability order can be acquired by a topological sorting of the graph.
  • The trouble of checking if a schedule is view serializable falls in the class of NP-complete problems
  • Though practical algorithms that just check few sufficient conditions for view serializability can still be employed.

Related Discussions:- Explain the rules for creating a labelled precedence graph

Data warehouse, XYZ is a large chain of home entertainment rental over 100 ...

XYZ is a large chain of home entertainment rental over 100 stores distributed over all states in Australia. XYZ lends entertainment products such as movies, TV shows and games on v

The file based system in dbms, The File Based System File based systems...

The File Based System File based systems are an early attempt to computerise the manual filing system. For example, a manual file can be set up to hold all the correspondence r

Difference between left outer join and right outer join, Difference between...

Difference between LEFT OUTER JOIN and RIGHT OUTER JOIN In left outer join tuples from the left-hand-side relation which do not match any tuple in the right-hand-side relation

ERD DIAGRAM, Law Associates is a large legal practice based in Sydney. You...

Law Associates is a large legal practice based in Sydney. You have been asked to design a data model for the practice based upon the following specification: The practice employs

Database incident table, The Incident table, with an auto-incrementing in...

The Incident table, with an auto-incrementing incident number, etc, looks like: incident_num reporter date time incide

Function module and a normal abap/4 subroutine, What is the difference betw...

What is the difference between the function module and a normal ABAP/4 subroutine? In contrast to normal subroutines function modules have uniquely exact interface.  Declaring da

Prove that a relation which is 4nf must be bcnf, Prove that a relation whic...

Prove that a relation which is 4NF must be BCNF.   Ans Let R be in 4NF.  Suppose it is not in BCNF.  Hence, there exists an FD X→Y in R such that x is not a super key. Although

What are advantages of object models, What are advantages of object models?...

What are advantages of object models? Object models are efficient for communicating with the application experts and reaching a consensus about the significant aspects of the p

Objectives of database manangement system, OBJECTIVES After going thro...

OBJECTIVES After going through this unit you should be capable to: Explain the File Based system and its limitations; Explain the structure of DBMS; Explain the

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