Consider three data items D1, D2 and D3 and the following execution schedule…

2003

Consider three data items D1, D2 and D3 and the following execution schedule of transactions T1, T2 and T3. In the diagram, R(D) and W(D) denote the actions reading and writing the data item D respectively.

GATECS2003Q87

Which of the following statements is correct?

  1. A.

    The schedule is serializable as T2; T3; T1

  2. B.

    The schedule is serializable as T2; T1; T3

  3. C.

    The schedule is serializable as T3; T2; T1

  4. D.

    The schedule is not serializable

Attempted by 52 students.

Show answer & explanation

Correct answer: D

To determine whether the schedule is serializable, we construct the precedence graph.

A schedule is serializable only if the precedence graph is acyclic.

Conflicting operations:

  • T1 and T2 on D1:
    T1 writes D1 before T2 writes D1
    ⇒ T1 → T2

  • T2 and T3 on D2:
    T2 writes D2 before T3 writes D2
    ⇒ T2 → T3

  • T3 and T1 on D2:
    T3 writes D2 before T1 reads/writes D2
    ⇒ T3 → T1

Now the precedence graph contains:

T1 → T2
T2 → T3
T3 → T1

This forms a cycle:

T1 → T2 → T3 → T1

Since the precedence graph contains a cycle, the schedule is not conflict serializable.

Hence, the correct answer is Option D.

Also different cycle can be present.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir