explain the rules for creating a labelled

Question

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 T_i to T_j 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.