**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.

**PRACTICE PROBLEMS BASED ON CONFLICT SERIALIZABILITY-**

**Problem-01:**

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

**S : R _{1}(A) , R_{2}(A) , R_{1}(B) , R_{2}(B) , R_{3}(B) , W_{1}(A) , W_{2}(B)**

**Solution-**

**Step-01:**

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

- R
_{2}(A) , W_{1}(A) (T_{2}→ T_{1}) - R
_{1}(B) , W_{2}(B) (T_{1}→ T_{2}) - R
_{3}(B) , W_{2}(B) (T_{3}→ T_{2})

**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-**

**Checking Whether S is Conflict Serializable Or Not-**

**Step-01:**

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

- R
_{2}(X) , W_{3}(X) (T_{2}→ T_{3}) - R
_{2}(X) , W_{1}(X) (T_{2}→ T_{1}) - W
_{3}(X) , W_{1}(X) (T_{3}→ T_{1}) - W
_{3}(X) , R_{4}(X) (T_{3}→ T_{4}) - W
_{1}(X) , R_{4}(X) (T_{1}→ T_{4}) - W
_{2}(Y) , R_{4}(Y) (T_{2}→ T_{4})

**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-**

**Checking Whether S is Conflict Serializable Or Not-**

**Step-01:**

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

- R
_{4}(A) , W_{2}(A) (T_{4}→ T_{2}) - R
_{3}(A) , W_{2}(A) (T_{3}→ T_{2}) - W
_{1}(B) , R_{3}(B) (T_{1}→ T_{3}) - W
_{1}(B) , W_{2}(B) (T_{1}→ T_{2}) - R
_{3}(B) , W_{2}(B) (T_{3}→ T_{2})

**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-

- T
_{1}→ T_{3}→ T_{4}→ T_{2} - T
_{1}→ T_{4}→ T_{3}→ T_{2} - T
_{4}→ T_{1}→ T_{3}→ T_{2}

**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.

**Checking Whether S is Conflict Serializable Or Not-**

**Step-01:**

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

- R
_{1}(A) , W_{2}(A) (T_{1}→ T_{2}) - R
_{2}(A) , W_{1}(A) (T_{2}→ T_{1}) - W
_{2}(A) , W_{1}(A) (T_{2}→ T_{1}) - R
_{2}(B) , W_{1}(B) (T_{2}→ T_{1}) - R
_{1}(B) , W_{2}(B) (T_{1}→ T_{2}) - W
_{1}(B) , W_{2}(B) (T_{1}→ T_{2})

**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**.