Conflict Serializability in DBMS

A conflict serializable schedule is one that can be converted from a non-serial schedule to a serial schedule by swapping its non-conflicting operations.

Conflicting Operations

The two operations become conflicting if all conditions satisfy.

• Both operations are part of different transactions.
• Both operations are performed on the same data item.
• One of the two operations must be a write operation.

Conflicting Pair

Read [i] (x)   -    Read [j] (x) - non conflict    read-read operation.
Read [i] (x)   -    Write [j] (x) -  conflict           read-write operation.
Write [i] (x)   -    Read [j] (x) -  conflict            write-read operation.
Write [i] (x)   -    Write [j] (x) - conflict            write-write operation.

Where I and j denote two different transactions Ti and Tj.

Checking Whether a Schedule is Conflict Serializable Or Not

To determine whether a given non-serial schedule is conflict serializable, perform the following steps:

Step 1: We will find and list all of the operations that are in conflict.

Step 2: Then we will draw one node for each transaction in a precedence graph.

Step 3: After that, we will draw an edge from Ti to Tj for each conflict pair, so that if Xi (V) and Yj (V) form a conflict pair, draw an edge from Ti to Tj.
This ensured that Ti is executed before Tj.

Step 4: At the end, we will check the graph to see if any cycles have formed. If no cycles are found, the schedule is conflict serializable; otherwise, it is not.

Example to Check Whether the Schedule is Conflict Serialzabile or Not:

In this example we will check schedule is conflict serializable or not.

Step 1: We will find and list all of the operations that are in conflict.

Conflict Pair

1. Read [3] (x) – Write [1] (x)
2. Read [2] (y) – Write [3] (y)
3. Read [2] (z) – Write [1] (z)
4. Write [2] (z) – Read [1] (z)
5. Write [2] (z) – Write [1] (z)

Where I and j denote two different transactions Ti and Tj.

Step 2: We will create a precedence graph.
Here in this example, we have 3 transactions in this schedule. So we will create 3 nodes.

Step 3: We will draw an edge from Ti to Tj for each conflict pair.

1. Read [3] (x) – Write [1] (x)
   We will draw an edge from T[3] to T[1] for this conflict pair.

2. Read [2] (y) – Write [3] (y)
   We will draw an edge from T[2] to T[3] for this conflict pair.

3. Read [2] (z) – Write [1] (z)
   For this conflict pair, we will draw an edge from T[2] to T[1].

4. Write [2] (z) – Read [1] (z)
   For this conflict pair, we will draw an edge from T[2] to T[1]. But we already drew an edge from T[2] to T[1] in conflict pair 3. so we will not draw an edge again.

5. Write [2] (z) – Write [1] (z)
   For this conflict pair, we will draw an edge from T[2] to T[1]. But we already drew an edge from T[2] to T[1] in conflict pair 3. so we will not draw an edge again.

Step 4: Now we will check the graph to see if any cycles or loops have formed. Here in this example, we can not find out any cycles or loops. So this schedule is conflict serializable.

Conflict Equivalent

In the conflict equivalent, one can be transformed into another by swapping non-conflicting operations. In the given example, S2 is conflict equivalent to S1 (S1 can be converted to S2 by swapping non-conflicting operations).

Two schedules are said to be conflict equivalent if and only if they satisfy the following conditions:

1. They both have the same transaction set.
2. If each conflict operation pair is ordered in the same way.

Example of Conflict equivalent:
In the given example, S2 is conflict equivalent to S1 (S1 can be converted to S2 by swapping non-conflicting operations).

Step 1: We will make a list of all conflict pairs and non-conflict pairs.

Conflict pairs

R(A)        W(A)
W(A)        R(A)
W(A)        W(A)

Non-conflict pairs

R(A)        R(A)
R(B)        R(A)
W(B)        R(A)
R(B)        W(A)
W(A)        W(B)

Step 2: We will find the element in S1 which has no similar sequence order to S2. In this example, R(B) element in transaction 1 has no similar sequence.
So we will swape the adjacent non-conflict pair R(B)-W(A).

Adjacent non-conflict pair

After swapping of non-conflict operation

Step 3: Here still we have R(B) element which has no similar order to S2. So we will swape the adjacent non-conflict pair R(B)-R(A).

Adjacent non-conflict pair

After swapping of non-conflict operation

Now, S1 becomes conflict serializable.

Conflict Serializability – FAQs

1. How is View Serializability different from Conflict Serializability?
View serializability is a weaker form of serializability than conflict serializability. Conflict serializability requires that transactions do not have conflicting accesses to the same data item, while view serializability only requires that transactions produce the same final result as a serial schedule. As a result, some schedules that are viewed as serializable may not be conflict serializable.

2. How to test conflict serializability in DBMS?
Conflict serializability can be tested using a technique known as the precedence graph method. This method involves constructing a directed graph that represents the dependencies between transactions, and checking whether the graph contains any cycles. If the graph is acyclic, the schedule is conflict serializable.

3. What are the consequences of violating conflict serializability in DBMS?
If a schedule violates conflict serializability, it means that the order of the transactions affects the final outcome of the transactions. This can lead to inconsistent or incorrect results in the database, which can cause data integrity issues, incorrect query results, or even system failures.

4. How does the isolation level of a DBMS affect conflict serializability?
The isolation level of a DBMS determines the degree to which transactions can see the changes made by other transactions. Higher isolation levels can provide stronger guarantees of conflict serializability by preventing certain types of conflicts from occurring, but may also reduce concurrency and performance.

5. Can a conflict serializable schedule always be executed in parallel?
No, a conflict serializable schedule does not necessarily mean that the transactions can be executed in parallel. Even if a schedule is conflict serializable, other factors such as the locking protocol used by the DBMS and the resource requirements of the transactions can limit the degree of concurrency that is possible.