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);

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:

Step 2 -

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

Therefore,

Step 3 -

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

Therefore,

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:

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:

Step 2 -

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

Therefore,

Step 3 -

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

Therefore,

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.