Schedules that are conflict serializable - solved examples

Given schedule is conflict serializable or not exercise, Conflict serializability exercise, how to find whether a schedule is conflict serializable? conflict serializability example

 

Conflict Serializable Schedule - Solved Exercise

Question:

Consider the following schedule;

Schedule S: r1(X), r2(X), r3(X), r1(Y), w2(Z), r3(Y), w3(Z), w3(Y)

Here, r1(X) denotes that transaction 1 read data item X, w2(z) denotes that transaction 2 writes data item Z, and so on. Is the given schedule a conflict serializable schedule? If yes, what is the equivalent serial schedule?

 

Solution:

Conflict serializable schedule: A schedule is conflict serializable if it can be transformed into an equivalent serial schedule by swapping pairs of non-conflicting instructions. Two instructions conflict if they involve the same data item and at least one of them is a WRITE.

 

To find whether the given schedule is conflict serializable or not, we can draw precedence graph. Precedence graph can be constructed by carefully analyzing the conflicting instructions. For every conflicting instruction, an edge can be inserted into the precedence graph. At the end, if the graph has not formed a cycle, then we would say that the schedule S is conflict serializable, otherwise not.

 

Is the schedule a conflict serializable schedule?

YES. The precedence graph of this S does no consist of a cycle.

The precedence graph includes an edge from T2 to T3 due to the conflict between the instructions w2(Z) and w3(Z). There will be another edge from T1 to T3 due to the conflict between instructions r1(Y) and w3(Y).

The precedence graph for S is as follows;

 

What is the equivalent serial schedule?

Equivalent serial schedule to S is (T2, T1, T3). Another equivalent schedule is (T1, T2, T3)

 

*****************************

 

Go to Define Serializability page

Go to Conflict Serializability explained with example page

Go to Solved exercises in DBMS page

Conflict serializability solved exercise

conflict serializable schedule example

how to find whether a schedule is conflict serializable or not?

how to check a schedule is serializable or not?

use precedence graph for checking serializability

serializability solved exercise

concurrency and serializability

 

Conflict serializable schedules - one more solved exercise

Given schedule is conflict serializable or not exercise, Conflict serializability exercise, how to find whether a schedule is conflict serializable? conflict serializability example

 

Conflict Serializable Schedule - Solved Exercise

Question:

For each of the schedules below, indicate whether they are conflict serializable. If you answer yes, then give the equivalent serial order of the transactions.

(i) Schedule S1: R1(A), R1(B), W1(A), R2(B), W2(D), R3(C), R3(B), R3(D), W2(B), W1(C), W3(D)

(ii) Schedule S2: R1(A), R1(B), W1(A), R2(B), W2(A), R3(C), R3(B), R3(D), W2(B), W1(C), W3(D)

 

Solution:

Conflict serializable schedule: A schedule is conflict serializable if it can be transformed into an equivalent serial schedule by swapping pairs of non-conflicting instructions. Two instructions conflict if they involve the same data item and at least one of them is a WRITE.

 

To find whether the given schedule is conflict serializable or not, we can draw precedence graph. Precedence graph can be constructed by carefully analyzing the conflicting instructions. For every conflicting instruction, an edge can be inserted into the precedence graph. At the end, if the graph has not formed a cycle, then we would say that the schedule S is conflict serializable, otherwise not.

(i) Schedule S1:

Schedule S1 is not conflict serializable because the precedence graph for S1 forms a cycle (refer the image below).

You could see two cycles here; T₁ → T₂ → T₃ → T₁ and T₂ → T₃ → T₂. Second one is discussed below;

The conflicting instructions are highlighted in color below;

R1(A), R1(B), W1(A), R2(B), W2(D), R3(C), R3(B), R3(D), W2(B), W1(C), W3(D)

In the first conflict (green color), transaction T₂ is writing D and T₃ is reading D. In the second one, transaction T₃ is reading B and T₂ is writing B. And these two conflicts end up in creating a cycle. Hence, schedule S1 is not conflict-serializable.

 

(ii) Schedule S2:

Schedule S2 is conflict serializable because the precedence graph for S3 doesn’t have a cycle in it (refer the image below).

Serialization order for this schedule is T₃, T₁, T₂. That is, the execution of this schedule will be same as executing transactions in the order T₃, T₁ and T₂.

*****************************

 

Go to Define Serializability page

Go to Conflict Serializability explained with example page

Go to Solved exercises in DBMS page

Conflict serializability solved exercise

conflict serializable schedule example

how to find whether a schedule is conflict serializable or not?

how to check a schedule is serializable or not?

use precedence graph for checking serializability

serializability solved exercise

concurrency and serializability

Need for Concurrency Control in Executing Database Transactions

Why do we need concurrency control mechanisms in DBMS? Problems with concurrent execution of transactions

Need for Concurrency Control in Executing Database Transactions

Concurrency or concurrent execution of transactions is about executing multiple transactions simultaneously. This is done by executing few instructions of one transaction then the next and so on. This way will increase the Transaction throughput (number of transactions that can be executed in a unit of time) of the system is increased. All the advantages are discussed here.

When you execute multiple transactions simultaneously, extra care should be taken to avoid inconsistency in the results that the transactions produce. This care is mandatory especially when two or more transactions are working (reading or writing) on the same database items (data objects). 

For example, one transaction is transferring money from account A to account B while the other transaction is withdrawing money from account A. these two transactions should not be permitted to execute in interleaved fashion like the transaction that are working on different data items. We need to serially execute (one after the other) such transactions.

If we do not take care about concurrent transactions that are dealing with same data items, that would end up in following problems;

• Lost Update Problem

• Reading Uncommitted Data / Temporary Update / Dirty Read Problem

• Incorrect Summary / Inconsistent Analysis problem

********************

Go to Transaction Management in DBMS home page

Define lost update problem
What is dirty read problem?
define inconsistent analysis problem
what is the role of lost update problem, dirty read problem and phantom read in concurrency control 
what is the role of lost update problem, dirty read problem and phantom read in transaction management