Describe the algorithm to draw the dependency graph?
Ans: Algorithm to draw Precedence Graph is like this:
a. For every transaction T_{i} participating in schedule S, make a node labeled T_{i} in the precedence graph.
b. For every case in S where T_{j} executes a read_item(X) after Ti executes a write_item(X), create an edge (T_{i}→T_{j}) in the precedence graph.
c. For every case in S where T_{j} executes a write_item(X) after T_{i} executes a read_item(X), create an edge (T_{i}→T_{j}) in the precedence graph.
d. For every case in S where T_{j} executes a write_item(X) after Ti executes a write_item(X), create an edge (T_{i}→T_{j}) in the precedence graph.
e. The schedule S is serializable if and only if the precedence graph has no cycles.