Precedence graph algorithm can be used to find out whether the given concurrent schedule is conflict serializable or not.
Algorithm:
- Create the number of node in the graph equal to the number of transactions in the given schedule.
- 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.
- Check if the precedence graph has either a cycle or a loop.
- If the cycle or loop does exist, then the given schedule is not conflict serializable.
- Else the schedule is conflict serializable.
- In case the schedule is conflict serializable then apply the Topological ordering in the graph to find out the equivalent serial schedule.
