Data Science, Machine Learning & Artificial Intelligence

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.

Read more