1
721views
Draw the serializable graphs for the schedule S1 and S2 and state whether each schedule is...

Draw the serializable graphs for the schedule S1 and S2 and state whether each schedule is (i)conflict serializable or not (ii)view serializable or not. If a schedule is conflict/view serializable , write down equivalent serial schedule(s) S1:r1(X);r2(Z);r1(Z);r3(X);r3(Y);w1(X);w3(Y);r2(Y);w2(Z);w2(Y); S2:r1(X);r2(Z);r3(X);r1(Z);r2(Y);r3(Y);w1(X);w2(Z);w3(Y);w2(Y);

1 Answer
3
82views

Serializability in DBMS

  • Serializability helps to identify which non-serial schedules are correct and will maintain the consistency of the database.

  • Serializable Schedules - If a given non-serial schedule of ‘n’ transactions is equivalent to some serial schedule of ‘n’ transactions, then it is called a Serializable Schedule.

  • There are two types of Serializability in the database as follows:

    • Conflict Serializability
    • View Serializability

Basic Rules for Conflict Serializability to identify Schedule is Conflict Serializable or not -

  • Step 1 - Identify a Conflicting Operations.

    • Rule 1 - At least one of the two operations is a write operation

    • Rule 2 - Both the operations are on the same data item

    • Rule 3 - Both the operations belong to different transactions

  • Step 2 - Draw a Precedence Graph by drawing one node for each transaction.

  • Step 3 - Check whether any cycle is present in the graph or not.

  • Step 4 - If there is no cycle found, then the schedule is Conflict Serializable otherwise NOT.

Basic Rules for View Serializability to identify Schedule is View Serializable or not -

  • Step 1 - Check whether the given schedule is Conflict Serializable or not.

    • Rule 1 - All Conflict Serializable schedules are View Serializable.

    • Rule 2 - But, all View Serializable schedules may or may not be conflict serializable.

  • Step 2 - Check if there exists any blind write operation or not.

    • Rule 3 - No blind write means not a View Serializable Schedule.
  • Step 3 - If the below three conditions hold true then the schedule is View Serializable.

    • Condition 1 - Initial readers must be the same for all the data items

    • Condition 2 - Write-read sequence must be the same

    • Condition 3 - Final writers must be the same for all the data items.

  • Step 4 - By using the above three conditions, write all the dependencies.

  • Step 5 - Draw a Precedence Graph by using dependencies find in the above step 4.

  • Step 6 - Check whether any cycle is present in the graph or not.

  • Step 7 - If there is no cycle found, then the schedule is View Serializable otherwise NOT.


Let's check Serializability for each schedule S1 and S2.

1] Serializability for Schedule S1

The given schedule S1: r1(X); r2(Z); r1(Z); r3(X); r3(Y); w1(X); w3(Y); r2(Y); w2(Z); w2(Y);

Step 1 -

For a better understanding purpose represent the given schedule S1 in the transaction table format as follows:

T1 T2 T3
R(X)
R(Z)
R(Z)
R(X)
R(Y)
W(X)
W(Y)
R(Y)
W(Z)
W(Y)

Step 2 -

List all the conflicting operations and determine the dependency between the transactions.

Therefore,

Conflicting Operations Dependencies between the Transactions
R1(Z), W2(Z) T1 → T2
R3(X), W1(X) T3 → T1
R3(Y), W2(Y) T3 → T2
W3(Y), W2(Y) T3 → T2

Step 3 -

Draw the Precedence Graph for schedule S1 based on the above transaction dependencies.

Therefore,

Precedence Graph for schedule S1

Step 4 -

Check whether any cycle is present in the graph or not.

  • Clearly, there exists no cycle in the precedence graph.
  • Therefore, the given schedule S1 is Conflict Serializable.
  • Based on the View Serializability Rule 1 - All Conflict Serializable schedules are View Serializable.
  • Therefore, the given schedule S1 is also a View Serializable.

Schedule S1 is Conflict as well as View Serializable.

Step 5 -

Now, schedule S1 is conflict/view serializable, therefore find out the equivalent serial schedule.

  • All the possible topological orderings of the above precedence graph will be the possible equivalent serialized schedules.
  • Therefore, the topological orderings can be found by performing the Topological Sort of the above precedence graph as follows:

Topological Sorting for Precedence graph of Schedule S1

After performing the topological sort,

The possible Equivalent Serialized Schedule for S1 got is T3 → T1 → T2


2] Serializability for Schedule S2

The given schedule S2: r1(X); r2(Z); r3(X); r1(Z); r2(Y); r3(Y); w1(X); w2(Z); w3(Y); w2(Y);

Step 1 -

For a better understanding purpose represent the given schedule S2 in the transaction table format as follows:

T1 T2 T3
R(X)
R(Z)
R(X)
R(Z)
R(Y)
R(Y)
W(X)
W(Z)
W(Y)
W(Y)

Step 2 -

List all the conflicting operations and determine the dependency between the transactions.

Therefore,

Conflicting Operations Dependencies between the Transactions
R3(X), W1(X) T3 → T1
R1(Z), W2(Z) T1 → T2
R2(Y), W3(Y) T2 → T3
R3(Y), W2(Y) T3 → T2
W3(Y), W2(Y) T3 → T2

Step 3 -

Draw the Precedence Graph for schedule S2 based on the above transaction dependencies.

Therefore,

Precedence Graph for schedule S2

Step 4 -

Check whether any cycle is present in the graph or not.

  • Clearly, there exists a cycle in the precedence graph.
  • Therefore, the given schedule S2 is NOT Conflict Serializable.
  • Since, the given schedule S2 is NOT Conflict Serializable. But, it may or may not be View Serializable according to Rule 2 for the View Serializability.
  • To check whether S2 is View Serializable or not, let us use another Step 2. (Blind Writes)

Step 5 -

  • Writing without reading is called as a Blind Write.
  • Every write operation is performed after the read operation in each transaction.
  • Therefore, there exists no blind write in the given schedule S2.
  • Therefore, schedule S2 is surely not View Serializable.

Step 6 -

As the given Scheule S2 is neither Conflict Serializable nor View Serializable.

Therefore, there are No Equivalent Serialized Schedules Possible.


Answer -

1] Schedule S1 is Conflict as well as View Serializable, with Equivalent Serialized Schedule T3 → T1 → T2

2] Scheule S2 is neither Conflict Serializable nor View Serializable, therefore, No Equivalent Serialized Schedules are Possible.

Please log in to add an answer.