Question

Q5: In DBMS, a graph precedence is used to test whether a schedule of concurrent transactions is conflict serializable or not. Given the following schedule S with three transactions Ti T read(A) T; read(B) write(A) write(B) read(A) write(A) read(B) write(B) 1. Draw the precedence graph for the schedule S (5 points) 2. Check whether the schedule S conflict serializable or not (5 points) 3. Is it possible to construct a serial schedule S' which is conflict equivalent to the schedule S? How? (5 points) 4. Check whether the following schedule recoverable or not (5 points) T T: T: read(A) read(B) write(A) read(A) write(B) write(A) commit read(B) write(B) commit

Answer 1

Q5.

1.

A precedence for transactions of schedule can be drawn by including the Transactions T1,T2,T3 as nodes of the graph and drawing a directed edge from one transaction to other i.e. Ti ->Tj, if an operation on an object is performed in transaction Ti before a conflicting operation on same object in transaction Tj.

In the given schedule S Transaction T1 performs write operation on B before Transaction T2 performs write operation on B (write-write conflict), so there will be a directed edge from T1 to T2, (T1->T2).

Transaction T2 performs write operation on A before Transaction T3 performs conflicting write operation on A (write-write conflict), so there will be a directed edge from T2 to T3,( T2->T3).

Resultant precedence graph:

Т2 Tз Т1

2.

For finding weather a Schedule is conflict serializable or not, its precedence graph is drawn , if there is cycle present in the precedence graph then the schedule is not conflict serializable.

From the precedence graph in part 1, there is no cycle present in it, so the schedule S is conflict serializable.

3.

Yes, it is possible to construct serial schedule S' that is conflict equivalent to S.

First all the operations of T1 should be performed, then all the operations of T2 should be performed, at the end all the operations of T3 should be performed.

T1	T2	T3
read(B) write(B)	read(A) write(A) read(B) write(B)	read(A) write(A)

4.

A recoverable schedule is one in which if a transaction reads value written by other transaction the it should commit only after the other transaction has committed.

In the given schedule in part 4 the transaction T3 reads value of A which is written by T2 and T2 is not committed, and T3 commits before T2, so it is not recoverable schedule.