Serialization Graph

Wooo, this is one of the super useful applications of Graph Theory.

Learned in CS348.

Serialization Graph

A serialization graph $SG(N,E)$ for a schedule $S$ is a directed graph with

1. nodes $T_i\in N$, corresponding to the transactions of $S$, and
2. edges $T_i\to T_j\in E$ whenever an operation $o_i[x]$ for transaction $T_i$ occurs prior to an operation $o_j[x]$ for transaction $T_j$ in $S$, where $o_i[x]$ and $o_j[x]$ are conflicting operations.

Ahh yess I get it, it is VERY easy

• Video: https://www.youtube.com/watch?v=WtlbLA0pfCI&list=PL3TE2CsKK478JNAXYLD_hzQFx5JE360KO&index=60&ab_channel=TheoreticalComputerScience