Question

presedence graph

Answer 1

`Hey,

Note: If you have any queries related to the answer please do comment. I would be very happy to resolve all your queries.

Precedence Graph or Serialization Graph is used commonly to test Conflict Serializability of a schedule.
It is a directed Graph (V, E) consisting of a set of nodes V = {T₁, T₂, T₃……….T_n} and a set of directed edges E = {e₁, e₂, e₃………………e_m}.
The graph contains one node for each Transaction T_i. An edge e_i is of the form T_j –> T_k where T_j is the starting node of e_i and T_k is the ending node of e_i. An edge e_i is constructed between nodes T_j to T_k if one of the operations in T_j appears in the schedule before some conflicting operation in T_k .

The Algorithm can be written as:

1. Create a node T in the graph for each participating transaction in the schedule.
2. For the conflicting operation read_item(X) and write_item(X) – If a Transaction T_j executes a read_item (X) after T_i executes a write_item (X), draw an edge from T_i to T_j in the graph.
3. For the conflicting operation write_item(X) and read_item(X) – If a Transaction T_j executes a write_item (X) after T_i executes a read_item (X), draw an edge from T_i to T_j in the graph.
4. For the conflicting operation write_item(X) and write_item(X) – If a Transaction T_j executes a write_item (X) after T_i executes a write_item (X), draw an edge from T_i to T_j in the graph.
5. The Schedule S is serializable if there is no cycle in the precedence graph.

If there is no cycle in the precedence graph, it means we can construct a serial schedule S’ which is conflict equivalent to the schedule S.

Kindly revert for any queries

Thanks.