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

Set of FDs are equivalent or not Exercise 11

How to prove that two sets of functional dependencies are equal or not - Proving equality of two sets of functional dependencies - How to find whether two sets of functional dependencies are equal or not? - Equivalent sets of functional dependencies

Exercise:

Let F = {A → C, AC → D, E → AD}, and let G = {A → CD, E → AHE}. Are they equivalent?

Solution:

To check whether two sets of functional dependency are equivalent, we have to verify every functional dependency (FD) of F is in G⁺ and every FD of G is in F⁺.

Theorem: If F ⊆ G⁺ and G ⊆ F⁺, then F and G are equivalent.

To check for F ⊆ G⁺

Let us take the first FD of F, A → C and find the closure using FDs from G as follows;

• A⁺ = ACD through the FD A → CD of G. The result includes the RHS attribute of FD A → C. Hence, A → C is in G⁺.

Let us do the same for other FDs of F;

• AC⁺ = ACD through the FD A → CD of G. The result includes the RHS attribute of FD AC → D. Hence, AC → D is in G⁺.

• E⁺ = AHECD through the FDs E → AHE and A → CD of G. The result includes the RHS attribute of FD E → AD. Hence, E → AD is in G⁺.

As all the FDs of F can be derived using G, F ⊆ G⁺ is true.

To check for G ⊆ F⁺

• A⁺ = ACD through the FDs A → C and AC → D of F. The result includes the RHS attribute of FD A → CD. Hence, A → CD is in F⁺.

• E⁺ = ACDE through the FDs E → AD, A → C and AC → D of F. The result does not include the RHS attribute of FD E → AHE. Hence, E → AHE is in F⁺.

As all the FDs of G cannot be derived using F, G ⊆ F⁺ is false.

Result:

We found that F ⊆ G⁺ is true but not G ⊆ F⁺. Hence, the given set of functional dependencies F and G are not equivalent (F ≠ G).  

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

How to find closure of set of functional dependencies?

How to find closure of attributes?

How to find canonical cover for a set of functional dependencies?

How to find extraneous attribute?

Go back to Question/QUIZ page

Go back to Online Quizzes home page

Transaction Management in DBMS solved exercise on Transaction Isolation Level concept

Transaction Management Exercise – Transaction Isolation Level

Question:

Assume that the following schedules are allowed by the database system with a particular isolation level. Indicate which of the three phenomena, as defined by ANSI-SQL, are occurring in these schedules. What are the locking-isolation levels for the two transaction schedules?

(a) Schedule S₁

Instruction No.	T1	T2
1 2 3 4 5 6	R(A) W(A) Abort	R(A) W(A) Commit

(b) Schedule S₂.

Instruction No.	T1	T2
1 2 3 4 5 6 7 8	R(A) R(A) Commit	R(A) W(A) R(B) W(B) Commit

Answer:

Three phenomena that either permitted or not at a given isolation level are;

Dirty read – You're permitted to read uncommitted, or dirty, data.

Non-repeatable read – Reading a row at time t₁ and t₂ may show different values due to deletion or update that happened between time t₁ and t₂.

Phantom read – Reading rows at time t₁ and t₂ may show additional rows that may have been added between time t₁ and t₂. More records resulted in the query that is executed at time t₂ than the result of execution at t₁.
Refer for more here - Facts about database transactions.

(a) Schedule S₁:

Phenomena happened in S₁: Dirty read – You're permitted to read the data that are uncommitted, or dirty.

T₂ has a dirty read. Transaction T₂ reads A (refer instruction 3) which was written by T₁ (refer instruction 2). Later, T₁ aborted.

Isolation level for S₁: READ UNCOMMITTED

Only READ UNCOMMITTED isolation level can permit this transaction. The basic goal of a READ UNCOMMITTED isolation level is to provide a standards-based definition that allows for non-blocking reads.

Read Uncommitted isolation level is implemented by requiring no read locks for reads and requiring long duration write locks for all writes; thus R₂(A) is possible because no read lock is required, even though we have W₁(A) before it.

(b) Schedule S₂:

Phenomena happened in S₂: Non-repeatable read – What you are seeing as a result of second read is different from the first one.

T₁ has a non-repeatable read. Transaction T₁ reads data item A (refer instruction 1). T₂ then modified data item A (refer instruction 3). Later, T₁ reads a new value for A (refer instruction 4).

Isolation level for S₂: READ COMMITTED

READ COMMITTED isolation level permits non-repeatable read and phantom read phenomena. It does not permit dirty read. It states that a transaction may read only data that has been committed in the database.

READ COMMITTED isolation Level will allow the above schedule; this isolation Level is implemented by requiring short duration read locks for all reads and long duration write locks for all writes. Thus, W2(A) is possible after R1(A) because R1(A) can be a short duration read lock.

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

Related links:

• Go to Transaction management in DBMS page

• Go to Important keywords in DBMS page

• Go to Why do we need recoverable schedules page 

• Go to SOLVED EXERCISES in Transaction management

Solved exercise in transaction management of dbms

Database transaction solved exercise on isolation levels

Find whether the schedules permit different transaction isolation levels given the phenomena dirty read, nonrepeatable read, and phantom read

Exercise with solution on transaction isolation levels