Precedence Graph Construction
The steps of constructing a precedence graph are:
- Create a node for every transaction in the schedule.
- Find the precedence relationships in conflicting operations. Conflicting operations are (read-write) or (write-read) or (write-write) on the same data item in two different transactions.
- For a transaction Ti which reads an item A, find a transaction Tj that writes A later in the schedule. If such a transaction is found, draw an edge from Ti to Tj.
- For a transaction Ti which has written an item A, find a transaction Tj later in the schedule that reads A. If such a transaction is found, draw an edge from Ti to Tj.
- For a transaction Ti which has written an item A, find a transaction Tj that writes A later. If such a transaction is found, draw an edge from Ti to Tj.
- If there is any cycle in the graph, the schedule is not serialisable, otherwise, find the equivalent serial schedule of the transaction by traversing the transaction nodes starting with the node that has no input edge.