Gráfico de precedencia

${\displaystyle S={\begin{bmatrix}T1&T2\\R(A)&R(A)\\A=A*5&R(B)\\W(A)&B=B+A\\R(B)&W(B)\\B=B*10&\\W(B)&\\\end{bmatrix}}}$

${\displaystyle D=R1(A)}$${\displaystyle R2(B)}$${\displaystyle W2(A)}$${\displaystyle Com.2}$${\displaystyle W1(A)}$${\displaystyle Com.1}$${\displaystyle W3(A)}$${\displaystyle Com.3}$

Un grafo de precedencia del cronograma D, con 3 transacciones. Dado que existe un ciclo (de longitud 2; con dos aristas) a través de las transacciones confirmadas T1 y T2, este cronograma (historial) no es serializable por conflictos . Nótese que la confirmación de la transacción 2 no tiene ninguna relevancia para la creación de un grafo de precedencia.

Algoritmo para probar la serializabilidad de conflictos de una planificación S, junto con un ejemplo de planificación.

${\displaystyle S={\begin{bmatrix}T1&T2&T3\\R(A)&&\\&W(A)&\\&Com.&\\W(A)&&\\Com.&&\\&&W(A)\\&&Com.\\\end{bmatrix}}}$

o

${\displaystyle S=R1(A)}$${\displaystyle W2(A)}$${\displaystyle Com.2}$${\displaystyle W1(A)}$${\displaystyle Com.1}$${\displaystyle W3(A)}$${\displaystyle Com.3}$

1. Para cada transacción T _x que participe en el cronograma S, cree un nodo etiquetado como T _i en el grafo de precedencia. Por lo tanto, el grafo de precedencia contiene T ₁ , T ₂ , T ₃ .
2. Para cada caso en S donde T _j ejecuta una lectura de elemento (X) después de que T _i ejecuta una escritura de elemento (X), cree una arista (T _i → T _j ) en el grafo de precedencia. Esto no ocurre en ningún lugar del ejemplo anterior, ya que no hay lectura después de escritura.
3. Para cada caso en S donde T _j ejecuta un write_item (X) después de que T _i ejecuta un read_item (X), crea una arista (T _i → T _j ) en el grafo de precedencia. Esto da como resultado una arista dirigida de T ₁ a T ₂ (ya que T ₁ tiene R(A) antes de que T ₂ tenga W(A) ).
4. Para cada caso en S donde T _j ejecuta un write_item (X) después de que T _i ejecuta un write_item (X), crea una arista (T _i → T _j ) en el grafo de precedencia. Esto da como resultado aristas dirigidas de T ₂ a T ₁ , de T ₂ a T ₃ y de T ₁ a T ₃ .
5. La planificación S es serializable si y solo si el grafo de precedencia no tiene ciclos. Como T1 _y T2 _constituyen un ciclo, el ejemplo anterior no es serializable (por conflicto).