Given schedule is conflict serializable or not - exercise

Given schedule is conflict serializable or not exercise, Conflict serializability exercise, how to find whether a schedule is conflict serializable? conflict serializability example

 

Conflict Serializable Schedule - Solved Exercise

Question:

Consider a schedule S with two transactions T₁, T₂, T₃ and T₄ as follows;

S: R₂(x); W₃(x); W₁(x); W₂(y); R₂(y); R₄(x); R₄(y);

Is the schedule S conflict serializable?

Solution:

Conflict serializable schedule: A schedule is conflict serializable if it can be transformed into an equivalent serial schedule by swapping pairs of non-conflicting instructions. Two instructions conflict if they involve the same data item and at least one of them is a WRITE.

The schedule S given in questions is as follows;

Instruction	T1	T2	T3	T4
1 2 3 4 5 6 7	W(x)	R(x) W(y) R(Z)	W(x)	R(x) R(y)

We can construct a precedence graph to decide whether the given schedule is conflict serializable or not.

Precedence graph can be constructed by carefully analyzing the conflicting instructions. For every conflicting instruction, an edge can be inserted into the precedence graph. At the end, if the graph has not formed a cycle, then we would say that the schedule S is conflict serializable, otherwise not.

Conflicting instruction and the edge to be inserted		Precedence graph
R2(x) and W3(x); T2 → T3	➔
R2(X) and W1(X); T2 → T1	➔
W3(X) and W1(X); T3 → T1	➔
W3(X) and R4(X); T3 → T4	➔
W1(X) and R4(X); T1 → T4	➔
W2(Y) and R4(Y); T2 → T4	➔

From the precedence graph, it is clear that no cycle has been formed through the conflicting instructions. Hence, the schedule is a conflict serializable schedule.

***********

Go to Define Serializability page

Go to Conflict Serializability explained with example page

Go to Solved exercises in DBMS page

Conflict serializability solved exercise

conflict serializable schedule example

how to find whether a schedule is conflict serializable or not?

how to check a schedule is serializable or not?

use precedence graph for checking serializability

serializability solved exercise

concurrency and serializability

Check for conflict serializability solved example in dbms

Check for conflict serializability solved example in dbms

Question:

Consider a schedule S with two transactions T₁ and T₂ as follows;

S: R₁(x);W₂(x);R₁(x);W₁(y);commit1;commit2;

Is the schedule S conflict serializable?

Solution:

The given schedule S is as follows;

Instruction	T1	T2
1 2 3 4 5 6	R(x) R(x) W(y) Commit	W(x) Commit

Conflict serializable schedule: A schedule is conflict serializable if it can be transformed into an equivalent serial schedule by swapping pairs of non-conflicting instructions. Two instructions conflict if they involve the same data item and at least one of them is a WRITE.

Let us construct a precedence graph;

Ins. 1 and 2: Transaction T₂ executes w(x) after T₁ executed r(x). [These two instructions are conflict]. We insert an edge from T₁ to T₂ as follows;

Ins. 2 and 3: Transaction T₁ executes a r(x) after T₂ executed w(x). [These two are conflicting instructions.] We insert an edge from T₂ to T₁ as follows;

Insertion of new edge forms a cycle. If there is a cycle in the precedence graph, then the schedule cannot be a conflict serializable schedule.

In other words, if you observe the schedule S carefully you can find that neither of the following can occur;

• Instruction 1 cannot be swapped with instruction 2 due to conflict (Read-Write conflict).

• Instruction 2 cannot be swapped with instruction 3 due to conflict (Write-Read conflict)

Hence, the schedule S cannot be serialized.

Schedule S is not conflict serializable schedule.

***********

Go to Define Serializability page

Go to Conflict Serializability explained with example page

Go to Solved exercises in DBMS page

Conflict serializability solved exercise

conflict serializable schedule example

how to find whether a schedule is conflict serializable or not?

how to check a schedule is serializable or not?

use precedence graph for checking serializability

serializability solved exercise

concurrency and serializability