Precedence Graph to check Conflict Serializable Schedule

Precedence graph algorithm can be used to find out whether the given concurrent schedule is conflict serializable or not.

Algorithm:

1. Create the number of node in the graph equal to the number of transactions in the given schedule.
2. Starting with each and every transaction identify all the existing conflicting operations and represent them in the graph in the form of edges following the direction of the conflicting operation.
3. Check if the precedence graph has either a cycle or a loop.
4. If the cycle or loop does exist, then the given schedule is not conflict serializable.
5. Else the schedule is conflict serializable.
6. In case the schedule is conflict serializable then apply the Topological ordering in the graph to find out the equivalent serial schedule.

Before going to take the example, let us first understand what is the Topological ordering.

Topological Ordering: The process of selecting the nodes with in-degree zero always, is known as topological ordering.

while applying this process, after selecting the node with in-degree zero, we shall ignore that node further and also we should ignore the edges that were emerging from that selected node.

From the remaining graph we should continue finding the next node with in-degree zero until all the nodes of graph gets selected.

Example: (Topological Ordering)

Example (Check for Conflict Serializablity using Precedence Graph)

For now signing off until next post. In case you have any doubts, please do not hesitate to ask using the comment section below. I will be happy to clear them.

Also please give your feedback as comment and share your thoughts.

You may connect with me on  LinkedIn

Thanks for reading.

Take care!