Prerequisite : Conflict Serializability

**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_{1}, T_{2}, T_{3}……….T_{n}} and a set of directed edges E = {e_{1}, e_{2}, e_{3}………………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:

- Create a node T in the graph for each participating transaction in the schedule.
- 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. - 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. - 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. -
**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.

The serial schedule S’ can be found by Topological Sorting of the acyclic precedence graph. Such schedules can be more than 1.

For example,

Consider the schedule S :

S : r1(x) r1(y) w2(x) w1(x) r2(y)

**Creating Precedence graph:**

- Make two nodes corresponding to Transaction T
_{1}and T_{2}.

- For the conflicting pair r1(x) w2(x), where r1(x) happens before w2(x), draw an edge from T
_{1}to T_{2}.

- For the conflicting pair w2(x) w1(x), where w2(x) happens before w1(x), draw an edge from T
_{2}to T_{1}.

Since the graph is cyclic, we can conclude that it is **not conflict serializable** to any schedule serial schedule.

Let us try to infer a serial schedule from this graph using topological ordering.

The edge T_{1}–>T_{2} tells that T_{1} should come before T_{2} in the linear ordering.

The edge T_{2} –> T_{1} tells that T_{2} should come before T_{1} in the linear ordering.

So, we can not predict any particular order (when the graph is cyclic). Therefore, no serial schedule can be obtained from this graph.

Consider the another schedule S1 :

S1: r1(x) r3(y) w1(x) w2(y) r3(x) w2(x)

The graph for this schedule is :

Since the graph is acyclic, the schedule is conflict serializable. Performing Topological Sort on this graph would give us a possible serial schedule which is conflict equivalent to schedule S1.

In Topological Sort, we first select the node with indegree 0, which is T1. This would be followed by T3 and T2.

So, **S1 is conflict serializable** since it is **conflict equivalent** to the **serial schedule T1 T3 T2. **

Source: Operating Systems book, Silberschatz, Galvin and Gagne

## leave a comment

## 0 Comments