Please visit, subscribe and share 10 Minutes Lectures in Computer Science
Showing posts with label Transaction. Show all posts
Showing posts with label Transaction. Show all posts

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 the following schedule;

Schedule S: r1(X), r2(X), r3(X), r1(Y), w2(Z), r3(Y), w3(Z), w3(Y)

Here, r1(X) denotes that transaction 1 read data item X, w2(z) denotes that transaction 2 writes data item Z, and so on. Is the given schedule a conflict serializable schedule? If yes, what is the equivalent serial schedule?

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.

To find whether the given schedule is conflict serializable or not, we can draw precedence graph. 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.

Is the schedule a conflict serializable schedule?

YES. The precedence graph of this S does no consist of a cycle.

The precedence graph includes an edge from T2 to T3 due to the conflict between the instructions w2(Z) and w3(Z). There will be another edge from T1 to T3 due to the conflict between instructions r1(Y) and w3(Y).

The precedence graph for S is as follows;

What is the equivalent serial schedule?

Equivalent serial schedule to S is (T2, T1, T3). Another equivalent schedule is (T1, T2, T3)

*****************************

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

Conflict Serializable Schedule - Solved Exercise

Question:

For each of the schedules below, indicate whether they are conflict serializable. If you answer yes, then give the equivalent serial order of the transactions.

(i) Schedule S1: R1(A), R1(B), W1(A), R2(B), W2(D), R3(C), R3(B), R3(D), W2(B), W1(C), W3(D)

(ii) Schedule S2: R1(A), R1(B), W1(A), R2(B), W2(A), R3(C), R3(B), R3(D), W2(B), W1(C), W3(D)

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.

To find whether the given schedule is conflict serializable or not, we can draw precedence graph. 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.

(i) Schedule S1:

Schedule S1 is not conflict serializable because the precedence graph for S1 forms a cycle (refer the image below).

You could see two cycles here; T1 → T2 → T3 → T1 and T2 → T3 → T2. Second one is discussed below;

The conflicting instructions are highlighted in color below;

R1(A), R1(B), W1(A), R2(B), W2(D), R3(C), R3(B), R3(D), W2(B), W1(C), W3(D)

In the first conflict (green color), transaction T2 is writing D and T3 is reading D. In the second one, transaction T3 is reading B and T2 is writing B. And these two conflicts end up in creating a cycle. Hence, schedule S1 is not conflict-serializable.

(ii) Schedule S2:

Schedule S2 is conflict serializable because the precedence graph for S3 doesn’t have a cycle in it (refer the image below).

Serialization order for this schedule is T3, T1, T2. That is, the execution of this schedule will be same as executing transactions in the order T3, T1 and T2.

*****************************

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

Conflict Serializable Schedule - Solved Exercise

Question:
Consider a schedule S with five transactions T1, T2, T3 T4 and T5 as follows;
 Sl.No. T1 T2 T3 T4 T5 1 R(x) 2 W(x) 3 R(x) 4 R(y) 5 R(z) 6 W(y) 7 R(v) 8 W(v) 9 R(v) 10 W(y) 11 W(y) 12 W(z)

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.
To find whether the given schedule is conflict serializable or not, we can draw precedence graph. 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 instructions and the edge to be inserted Precedence graph Sl. No.: 1, 2 R1(x) and W2(x); T1 → T2 ➔ Sl. No.: 4, 6 R1(y) and W2(y); T1 → T2 ➔ Sl. No.: 7, 8 R1(v) and W3(v); T1 → T3 ➔ Sl. No.: 8, 9 W3(v) and R4(v); T3 → T4 ➔ Sl. No.: 6, 10 W2(y) and W4(y); T2 → T4 ➔ Sl. No.: 10, 11 W4(y) and W5(y); T4 → T5 ➔ Sl. No.: 5, 12 R4(z) and W5(z); T4 → T5 ➔ Sl. No.: 4, 11 R1(y) and W5(y); T1 → T5 ➔ Sl. No.: 6, 11 W2(y) and W5(y); T2 → T5 ➔ Sl. No.: 4, 10 R1(y) and W4(y); T1 → T4 ➔ Sl. No.: 2, 3 W2(x) and R3(x); T2 → T3 ➔
As per the complete (last one) precedence graph, there exists no cycles. Hence, the given schedule S is conflict serializable.

***********

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

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

data recovery