Showing posts with label Serializability. Show all posts
Showing posts with label Serializability. Show all posts

Sunday, June 21, 2020

Serializable Schedules and Transactions - solved examples

Given schedule is conflict serializable or not exercise, view serializable schedules, serializability exercises, how to find whether a schedule is conflict serializable or view serializable? view serializability example, non-conflict serializability example

 

View Serializable Schedule - Solved Exercise


Question:

Is the following schedule S is serializable? If yes, is it conflict serializable or view serializable?

R1(C), W1(B), R2(B), W2(A), W1(A), W2(A)

 

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.

 

View serializable schedule: A schedule is view serializable if it is view equivalent to a serial schedule. A schedule is said to be view equivalent if all of the following conditions met by the schedule;

Consider two transactions T1 and T2 and two schedules S1 and S2. S1 and S2 are said to be view equivalent if the following conditions satisfied;

If T1 reads a data item Q initially in S1 then T1 must read Q initially in S2.

In S1, if T1 reads a data item Q which is resulted in the write operation of T2, then in S2 also T1 must read Q which is written by T2.

If T1 writes the final value of a data item Q in S1, then T1 must write the final value of Q in S2 also.

 

Is the schedule S a conflict serializable schedule?

NO. The precedence graph of S consists of a cycle.         

The cycle is formed due to the conflicting instructions {W1(B), R2(B)} (resulted in an edge T1 to T2), and {W2(A), W1(A)} (resulted in an edge T2 to T1).

Precedence graph for non-conflict serializable schedule
 

Is the schedule S a view serializable schedule?

YES.

For S, the possible serial schedules are <T1, T2> or <T2, T1>.

The conditions for view serializability are satisfied in the case of S for an equivalent schedule <T1, T2>. Let us consider the equivalent schedule as S’.

Schedule S

Schedule S’

T1

T2

T1

T2

R(C)

W(B)

 

 

W(A)

 

 

R(B)

W(A)

 

W(A)

R(C)

W(B)

W(A)

 

 

 

R(B)

W(A)

W(A)

 

Satisfaction of following conditions can be observed from the above table (refer the color code);

  • In schedule S and S’, T1 reads C first.
  • In schedule S and S’, T2 consumes B which is written by T1.
  • In schedule S and S’, T2 writes final A.

The schedule S is view equivalent to serial schedule S1. Hence, the schedule S is view serializable.


Note 1: A conflict serializable schedule is always a view serializable schedule. But a view serializable schedule need not be conflict serializable.

Note 2: The write operations in S (W(A), W(B) in T1 and T2) are called as Blind Writes because they have not read the values of data items A or B prior.

 


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

 



Conflict serializability solved exercise
view serializability solved exercise
conflict and view serializable schedule example
how to find whether a schedule is view serializable or not?
how to check a schedule is serializable or not?
use precedence graph for checking serializability
serializability solved exercise
concurrency and serializability



Saturday, June 20, 2020

Schedules that are conflict serializable - solved examples

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:

For the following schedule S, draw the precedence graph and decide if the schedule is conflict serializable.

r2(Y), w2(Y), r3(Y), r1(X), w1(X), w3(Y), r2(X), r1(Y), w1(Y)


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?

NO. The precedence graph of S consists of a cycle.

The precedence graph consists of the following edges (conflicting instructions) and a cycle;

  • T2 to T3 – W2(Y), and R3(Y) are the conflicting instructions causes this edge.
  • T1 to T2 – W1(X), and R2(X) are the conflicting instructions causes this edge.
  • T3 to T1 – W3(Y), and W1(Y) are the conflicting instructions causes this edge.

These three edges together formed a cycle. There is one more edge as follows;

  • T2 to T1 – W2(Y), and R1(Y) are the conflicting instructions causes this edge.

 

precedence graph of a non-conflict serializable schedule

As per the precedence graph, the schedule S has cycle in it. Hence, the schedule S is not 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...

All time most popular contents

data recovery