\begin{frame} \frametitle{Checking Conflict-Serializability} \begin{block}{} If the precedence graph has no cycles, then an equivalent serial schedule is obtained by a \emph{topological sort} of the precedence graph. \end{block} \pause \begin{exampleblock}{} {\def\scheduleWidth{1cm} \begin{tcenter} \begin{tikzpicture}[node distance=15mm] \schedule{}{3}{2rV|1wY|3wV|2rY|2wZ} \node (t1) at (6.5cm,-\scheduleHeight) {$T_1$}; \node (t3) [below right of=t1] {$T_3$}; \node (t2) [above right of=t3] {$T_2$}; \draw [very thick,->] (t1) -- (t2); \draw [very thick,->] (t2) -- (t3); \end{tikzpicture} \end{tcenter} }\vspace{-2ex} \begin{itemize} \pause \item There is an edge from $T_1$ to $T_2$ thus $T_1$ must be before $T_2$. \pause \item There is an edge from $T_2$ to $T_3$ thus $T_2$ must be before $T_3$. \end{itemize} \pause The sorting which fulfils these criteria is: $T_1,T_2,T_3$. \pause\smallskip This yields the equivalent serial schedule: {\def\scheduleWidth{1cm} \begin{tcenter} \begin{tikzpicture} \schedule{}{3}{1wY|2rV|2rY|2wZ|3wV} \end{tikzpicture} \end{tcenter} } \end{exampleblock} \end{frame}