MindStudy - MindStudy

Question:

Published on: 3 December, 2024

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

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

Trending

What is the need for normalization? Explain 2nd and 3rd normal form with example.

Consider the following relation:

EMP_PROJ { SSn, Pnumber, Hours, Ename, Pname, Plocation}

Assume { SSn, Pnumber} as primary key.

The dependencies are {SSn, Pnumber}→ Hours; SSn →Ename; Pnumber → {Pname, Plocation}.

Normalize the above relation into 2NF.

23 January, 2022

State the advantages of using database system over file-based information system.

3 December, 2024