Conflict Serializability and Types of Schedules

Conflict Serializability in DBMS is an important concept in Transaction Processing System. Serializability and different types of serializability like view serializability and conflict serializabilty along with different types of schedule in DBMS are explained in this tutorial with suitable example.

The Schedule is an important topic, especially for students preparing for the GATE(CS/IT) and UGC NET Exam. Generally, two types of problem are asked on serializability in GATE exam. These problems are as follow –

Type 1

(1)  Four Schedules will be given in the options and it will be ask that which Schedule is View Serializable among the given schedule.

(2) Four Schedules will be given in the options and it will be ask that which which Schedule is Conflict Serializable.

Type 2

(1) Check whether the given schedule S is view serializable or not. If yes, then among the four given options, we have to find the corresponding serial Schedule for the given Schedule

(2) Check whether the given schedule S is conflict serializable or not. If yes, then among the four given options, we have to find the corresponding serial Schedule.

This tutorial discussion and explanation is going to be more important for GATE Exam Aspirants, So  they are requested to prepare this topic very well.

Let’s start to learn about the Schedule in DBMS.

Prerequisite

Students should have the knowledge of basics concepts of transactions like Read, Write, Commit and Rollback operations of a transaction, different ACID Properties of transaction and transactions states before study the serializability in DBMS.

Students can learn and understand some basic concepts of DBMS in the Following tutorial. The Link is given below

Transaction Processing – Basics Concepts

Frequently Asked Questions

After reading this tutorial students will be able to answer the following frequently asked questions  on Serializability in DBMS .

• What is  Schedule in DBMS?
• What are the types od schedule in DBMS ?
• What is a Serial and Serializable schedule ?
• What do you understand by View SerialiSchedule?
• What is Conflict and View serializability in DBMS ?
• What is a Conflict Serializable Schedule?
• What are Conflicting Operations?
• What are Non-Conflicting Operations?
• How to check View Serializability and Conflict Serializability in DBMS?

What is Schedule in DBMS ?

• When several transactions are executing concurrently, if all it’s operations are performed in a chronological order, the process is known as a schedule.
• The Schedule generally represents the order or execution of its transactions.
• In simpler words, a bundle of transactions executing together is called a schedule.
• Hence we can say that a schedule ‘S’ is a set of transactions, where all the transactions follow a definite order.
• Whenever multiple transactions are operating, every transaction has got a particular set of actions to be done. Each operation will get executed in a separate instance of time, and that will be mapped following some order.

For example, we have a set of two transactions, where some particular operation are to be executed, as shown below.

So, if both these two transactions are carried away simultaneously, it will be called a schedule. The Schedule will decide and order in which the operations are to be executed.

Example of Schedule

Below two example schedules are shown based on.

Both the schedules S1 and S2 represents two different orders of operations for it’s Transactions T1 and T2.

This shows a sequence of operations by a set of concurrent transactions that preserves the order of the operations in each of the individual transactions.

Types of Schedules in DBMS

Different Types of Schedules in DBMS are –

• Serial Schedule.
• Non Serial Scahedule.

Non Serial Schedule is further classified in Two types

• Serializable Schedule
• Non Serializable Schedule

Serializable schedule is of two types

• View Serializable
• Conflict Serializable

Non Serial schedule are of two types

• Coverable Schedule
• Non Coverable Schedule

Coverable Schedules are of three types

• Cascading Schedule
• Cascadeless Schedule
• Strict Schedule

 

 

shown in following picture.

Let’s start with serial schedule.

Key Point to Remember – Here I would like to remind the students that when you will search on internet about different types of schedule in DBMS then it may be possible that there will not all these in same article. But this is the proper classification of all types of schedule in DBMS.

In this tutorial  we have explained Serial and Non Serial Schedule. We have covered View and Conflict Serializable schedule in more detail.

1. Serial Schedule

• A schedule where the operations of each transaction are executed concurrently without any interleaved operations from other operations.
• It means Transactions in the serial schedule  executes sequentially one after the other.

Just see the schedule S2 given below-

In this case, after completion of all the operations of transaction T1, Transaction T2 starts executing. They are concurrent transactions but there is no overlapping of execution span or interleaving of operations. Hence this is an example of serial schedule.

Key Point – The main advantage of serial schedule is, it always guarantee a consistent state. The main disadvantage of serial schedule is there is no concurrency; only after a transaction is executed, another transaction starts executing.

2. Non-Serial Schedule

In non serial schedule, the operations from a set of concurrent transactions are interleaved. Here the concurrent transactions are overlapping. Focus on the example below.

• Transaction T1 is initiating instant t1, and it is getting terminated at time instant t 6. Transaction T2 is getting initiated at time instant t3 and getting terminated at t8.
• The time spans are overlapping, and after interleaving the operations of the transaction T1, the operations of the transaction T2 are executed. Hence this is an example of a non-serial schedule.

Key Point – The main advantage of a non-serial schedule is the concurrency of executing the transactions. The source utilization and execution time will be less and will have a faster response time.

The main disadvantage of a non-serial schedule is that there is a potential risk that the system may go into an inconsistent state.

Non-Serial Schedule is further divided into Two Main Categories.

• Serializable Schedule 
• Non Serializable Schedule

Here in this tutorial, we will discuss Serializable Schedule, and It’s Types.

Serializable Schedule

• The objective of serializability is to find a non-serial schedule that allows transactions to execute concurrently without interfering with one another and producing a database state that a serial execution could produce.
• That means a non-serial schedule is serializable and correct if it produces the same results as some serial execution.
• Example of a serial schedule and a non-serial schedule is shown above figure. A schedule is called serializable if both the serial and non-serial schedule gives the same output.
• If  we are able to get a serial schedule by performing some swapping among the operations of non serial schedule then such non serial schedule is known as Serializable schedule.

1.Conflict Serializability in DBMS or Conflict Serializable Schedule

It is discussed before that a non-serial schedule may lead to inconsistency sometimes. Here, in the conflict schedule, we will discuss how, with a non-serial Schedule, we can ensure consistency in the system.

To ensure a consistent system, we first need to confirm whether a non-serial schedule will produce a compatible system or not.

As we have already discussed that the serial schedules are consistent, we can compare the output of the serial Schedule to the non-serial Schedule. If both the outputs are just equivalent, we can ensure that the non-serial Schedule will produce a consistent system.

Let’s consider two schedules (non-serial) and (serial).

If we try to convert a non-serial schedule to a serial schedule, we need to swap operations between the non-serial Schedule.

But sometimes, the swapping of operations ( Read/Write) may cause conflicts and lead us to a non-consistent system.

So there are some conditions for swapping the operations –

• The operations of the same transaction can not be swapped. So there is no conflict between the operations of the same transaction.
• The Operations can be conflict only when they belong to different transactions.
• Operations must operate on the same data Item value to have conflicting operations.
• There may be a conflict if any of the swapping operations is a write operation.

So after swapping non-conflicting operations, if we can convert a non-serial schedule into a serial one, that Schedule is called conflict serializable. The non-serial Schedule is proved to be a consistent one.

To check that the Schedule is Conflict Serializable or not, We should know What are Conflict Operations and Non-Conflict Operation.

Conflict Operations

Two operations are said to be conflict operations if they satisfy the following three conditions. Conflicts operations are necessary conditions of Conflict Serializability in DBMS.

(1) Both operations should belong to different transactions

(2) Both operations should use the Same data Item.

(3) There should be at least one Write operation between this two operation.

Example of Conflict Operations

Following operations are Conflict Operations

• R1(A), W2(A) satisfy conditions of conflicting operations
• W1(A), R2(A) satisfy conditions of conflicting operations.
• W1(A), W2(A) satisfy conditions of conflicting operations.

Non Conflicting Operations

Two operations are said to be non-conflicting operations if they satisfy any one of the following properties

(1) Both Operations use different data item.

(2) If both operations are read operations, in this case, it does not matter whether they are on the same data or different.

Example of Non-Conflicting Operations

• R1(A), R2(A) – Both operations are Read Operations, so these are non-conflicting operations
• W1(A), R2(B) – Both use different data item A and B, respectively, so these are non-conflicting operations

Example of Conflict Serializable Schedule

Consider a Schedule Given Below

S: R1(A) , W1(A) , R2(A) , W2(A),R1(B), W1(B),R2(B),W2(B)

Let’s see whether this Schedule is conflict serializable or not ?

So W2(A) and R1(B) are non-conflicting operations to swap them. After Swapping the order of Schedule will be

S: R1(A) , W1(A),R2(A),R1(B),W2(A),W1(B),R2(B),W2(B)

R2(A) and R1(B) are non-conflicting operations so that we can swap them. After swapping, the sequence will be like given below.

S: R1(A),W1(A),R1(B),R2(A),W2(A),W1(B),R2(B),W2(B)

R2(A) and W1(B) are non-conflicting operations because they are performed on a different data item to swap these operations. After Swapping, the sequence will be like given below.

S: R1(A),W1(A),R1(B),R2(A), W1(B),W2(A),R2(B),W2(B)

R2(A) and W1(B) are non-conflicting operations, so we can swap them after swapping the sequence will be like given below.

S: R1(A),W1(A),R1(B),W1(B),R2(A),W2(A),R2(B),W2(B)

This resultant Schedule is a serial schedule, so here we can convert the given non-serial Schedule to a serial schedule by swapping the non-conflicting operations, so this verifies that the given Schedule is Conflict Serializable.

Important Note – Another Method to check whether the given Schedule is conflict serializable or not is to make a precedence graph. If there is a cycle in the graph, then the given Schedule is conflicting.

 Draw a precedence graph to figure out a schedule is conflict serializable or not:

Consider the Schedule below-

Now let’s check whether we can swap operations among or not.

• Among all these operations, R(X) can not be swapped with W(X). Hence can’t be executed before.
• Secondly, R(Y) can’t be swapped with W(Y). Hence can’t be executed before.
• Thirdly W(Z) can’t be swapped with W(Z) of. Hence can’t be executed before.

We use the following steps to draw the graph-

• Create a node for each transaction.
• Draw a directed edge to a transaction if there is a conflict in swapping.

This is showing a cycle. Hence this is not conflict serializable. If the graph does not produce a cycle, the non-serial schedule is proved to be conflict serializable.

2.View Serializable Schedule

We have discussed that if a schedule is conflict serializable then the output must be consistent. But even if the schedule is not conflict serializable there may be a chance that the schedule is consistent. There comes the concept of view serializability.

Two schedules  and  are view serializable if following conditions are fulfilled:

1. For each data item Q, if T1 reads an initial value of Q in schedule, then T1  must be in   also reads an initial value of Q in second schedule.
2. If T2 executes reads Q in S, and that value of Q was produced by write operation of T1 (if any), then  same situation must be in second schedule it means in second schedule  transaction T2 also reads the value of Q that was produced by transaction T1.
3. For each data item Q, the transaction that perform the final write(Q) operation in schedule  must also the final write(Q) in the schedule  .

Key Points – Students are requested to remember the following points

1. A schedule is view serializable if it is view equivalent to a serial schedule.
2. Every conflict serializable schedule is view serializable, but not every view serializable schedule is conflict serializable.

An example of view serializable schedules is shown below-

Conclusion and Summary

In this Conflict Serializability in DBMS tutorial we have learned about schedules in dbms and different types of schedules. We have also discussed the types of serializability like view serializability and conflict serializability with suitable example.

I hope this Conflict Serializability in DBMS and types of schedule tutorial will be helpful for the computer science student in understanding the concept of schedule in DBMS and schedule’s types.

I kindly request to readers please give your feedback and suggestion. If you find any mistake in this tutorial then comment.

Don’t stop learning and practice.

Previous Tutorial – ACID Properties of Transaction

Next Tutorial – Database Recovery Techniques in DBMS