# Conflict Serializability | Practice Problems

## Conflict Serializability-

Before you go through this article, make sure that you have gone through the previous article on Conflict Serializability.

We have discussed-

• The concept of serializability helps to identify the correct non-serial schedules that will maintain the consistency of the database.
• There are two types of serializability-

In this article, we will discuss practice problems based on conflict serializability.

## Problem-01:

Check whether the given schedule S is conflict serializable or not-

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

## Solution-

### Step-01:

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

• R2(A) , W1(A)              (T2 → T1)
• R1(B) , W2(B)              (T1 → T2)
• R3(B) , W2(B)              (T3 → T2)

### Step-02:

Draw the precedence graph-

• Clearly, there exists a cycle in the precedence graph.
• Therefore, the given schedule S is not conflict serializable.

## Problem-02:

Check whether the given schedule S is conflict serializable and recoverable or not-

## Solution-

### Step-01:

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

• R2(X) , W3(X)              (T2 → T3)
• R2(X) , W1(X)              (T2 → T1)
• W3(X) , W1(X)             (T3 → T1)
• W3(X) , R4(X)              (T3 → T4)
• W1(X) , R4(X)              (T1 → T4)
• W2(Y) , R4(Y)              (T2 → T4)

### Step-02:

Draw the precedence graph-

• Clearly, there exists no cycle in the precedence graph.
• Therefore, the given schedule S is conflict serializable.

### Checking Whether S is Recoverable Or Not-

• Conflict serializable schedules are always recoverable.
• Therefore, the given schedule S is recoverable.

Alternatively,

• There exists no dirty read operation.
• This is because all the transactions which update the values commits immediately.
• Therefore, the given schedule S is recoverable.
• Also, S is a Cascadeless Schedule.

## Problem-03:

Check whether the given schedule S is conflict serializable or not. If yes, then determine all the possible serialized schedules-

## Solution-

### Step-01:

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

• R4(A) , W2(A)              (T4 → T2)
• R3(A) , W2(A)              (T3 → T2)
• W1(B) , R3(B)              (T1 → T3)
• W1(B) , W2(B)             (T1 → T2)
• R3(B) , W2(B)              (T3 → T2)

### Step-02:

Draw the precedence graph-

• Clearly, there exists no cycle in the precedence graph.
• Therefore, the given schedule S is conflict serializable.

## Finding the Serialized Schedules-

• All the possible topological orderings of the above precedence graph will be the possible serialized schedules.
• The topological orderings can be found by performing the Topological Sort of the above precedence graph.

After performing the topological sort, the possible serialized schedules are-

1. T1 → T3 → T4 → T2
2. T1 → T4 → T3 → T2
3. T4 → T1 → T3 → T2

## Problem-04:

Determine all the possible serialized schedules for the given schedule-

## Solution-

The given schedule S can be rewritten as-

This is because we are only concerned about the read and write operations taking place on the database.

### Step-01:

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

• R1(A) , W2(A)              (T1 → T2)
• R2(A) , W1(A)              (T2 → T1)
• W2(A) , W1(A)             (T2 → T1)
• R2(B) , W1(B)              (T2 → T1)
• R1(B) , W2(B)              (T1 → T2)
• W1(B) , W2(B)             (T1 → T2)

### Step-02:

Draw the precedence graph-

• Clearly, there exists a cycle in the precedence graph.
• Therefore, the given schedule S is not conflict serializable.
• Thus, Number of possible serialized schedules = 0.

Next Article- View Serializability in DBMS

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Article Name
Conflict Serializability | Practice Problems
Description
Practice Problems based on Conflict Serializability and How to check whether a given schedule is conflict serializable or not. Serializability in DBMS is a concept that helps to identify the correct non-serial schedules that will maintain the consistency of the database.
Author
Publisher Name
Gate Vidyalay
Publisher Logo