Please visit, subscribe and share 10 Minutes Lectures in Computer Science
Showing posts with label Solved Exercises. Show all posts
Showing posts with label Solved Exercises. Show all posts

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; T1 → T2 → T3 → T1 and T2 → T3 → T2. 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 T2 is writing D and T3 is reading D. In the second one, transaction T3 is reading B and T2 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 T3, T1, T2. That is, the execution of this schedule will be same as executing transactions in the order T3, T1 and T2.

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

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

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 extraneous attribute?

Go back to Question/QUIZ page

Go back to

Tuesday, May 5, 2020

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 S1
 Instruction No. T1 T2 1 2 3 4 5 6 R(A) W(A) Abort R(A) W(A) Commit

(b) Schedule S2.
 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

Three phenomena that either permitted or not at a given isolation level are;
Non-repeatable read – Reading a row at time t1 and t2 may show different values due to deletion or update that happened between time t1 and t2.
Phantom read – Reading rows at time t1 and t2 may show additional rows that may have been added between time t1 and t2. More records resulted in the query that is executed at time t2 than the result of execution at t1.
Refer for more here - Facts about database transactions.

(a) Schedule S1:
Phenomena happened in S1: Dirty read – You're permitted to read the data that are uncommitted, or dirty.
T2 has a dirty read. Transaction T2 reads A (refer instruction 3) which was written by T1 (refer instruction 2). Later, T1 aborted.
Isolation level for S1: 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 R2(A) is possible because no read lock is required, even though we have W1(A) before it.

(b) Schedule S2:
Phenomena happened in S2: Non-repeatable read – What you are seeing as a result of second read is different from the first one.
T1 has a non-repeatable read. Transaction T1 reads data item A (refer instruction 1). T2 then modified data item A (refer instruction 3). Later, T1 reads a new value for A (refer instruction 4).
Isolation level for S2: 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.

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

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

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

data recovery