MindStudy - MindStudy

Question:

Published on: 22 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

Computer Graphics and Multimedia Software Engineering Design and Analysis of Algorithm Database Management System Data Structures & Algorithm Mobile computing

Trending

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

Immediate updation
Deferred updation

22 December, 2024

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

23 January, 2022

Consider the following tables:

DEPT (DCODE, DNAME)

EMP (ECODE, ENAME, BASIC, DCODE, DT_JN)

Write down the SQL statements for the following:

For each department, show DNAME and total basic of the employee in the department.
Find out the names of the department where no person is working.
Find out the names of the employees who are working in the department named as ‘ABC’.
Find out the maximum basic among the employees who have joined after year 2000.

22 December, 2024

22 December, 2024

Explain two-phase locking protocol.

22 December, 2024

Compression of GIF images