Precedence Graph Algorithm

Using the notion of precedence graph, an algorithm can be devised to determine whether an interleaved schedule is serialisable or not. In this graph, the transactions of the schedule are represented as the nodes and the graph also has directed edges. An edge from the node representing transactions Ti to node Tj means that there exists a conflicting operation between Ti and Tj and Ti precedes Tj in some conflicting operations. It has been proved that a serialisable schedule is the one that contains no cycle in the graph.