MindStudy - MindStudy

Question:

Published on: 23 February, 2025

Let T1, T2, T3 be transactions that operate on the same data items A, B, C. Let r1(A) means that T1 reads A, w1(A) means that T1 writes A and so on for T2 and T3. Consider the following schedule: S1: r2(C), r2(B), w2(B), r3(C), r1(A), w1(A), w3(B), w3(C), r2(A), r1(B), w1(B), w2(A). Is the schedule serializable and why?

Answer:

A precedence graph, also named conflict graph and serializability graph, is used in the context of concurrency control in databases.

The precedence graph for a schedule S contains:
A node for each committed transaction in S.

An arc from T_i to T_j if an action of T_i precedes and conflicts with one of T_j's actions.

The drawing sequence for the precedence graph:-

For each transaction T_i participating in schedule S, create a node labeled T_i in the precedence graph. So the precedence graph contains T₁, T₂, T₃
For each case in S where T_i executes a write_item(X) then T_j executes a read_item(X), create an edge (T_i --> T_j) in the precedence graph. This occurs nowhere in the above example, as there is no read after write.
For each case in S where T_i executes a read_item(X) then T_j executes a write_item(X), create an edge (T_i --> T_j) in the precedence graph. This will bring to front a directed graph from T₁ to T₂.
For each case in S where T_i executes a write_item(X) then T_j executes a write_item(X), create an edge (T_i --> T_j) in the precedence graph. It creates a directed graph from T₂ to T₁, T₁ to T₃, and T₂ to T₃.

The schedule S is serializable if the precedence graph has no cycles. As T₁ and T₂ constitute a cycle, then we cannot declare S as serializable.

The Precedence Graph is cyclic, so, this is not serializable.

Subjects

C Programming and Practices Software Engineering Computer Graphics and Multimedia Data Structures & Algorithm Design and Analysis of Algorithm Mobile computing

Trending

Write the rules of DBA.

23 February, 2025

What do you mean by ‘Ternary Relationship’? Define the concept of aggregation with suitable example.

23 February, 2025

Explain how to reduce a relationship set of an E-R diagram into relational schema.

23 January, 2022

With suitable examples, show how recovery in a database system can be done using Log Files with