Gráfico de precedencia

Un gráfico de precedencia , también llamado gráfico de conflictos ^[1] y gráfico de serializabilidad , se utiliza en el contexto del control de concurrencia en bases de datos . ^[2] Es el gráfico dirigido que representa la precedencia de las transacciones en el cronograma, como se refleja en la precedencia de las operaciones en conflicto en las transacciones. Un cronograma es serializable por conflictos si y solo si su gráfico de precedencia de transacciones confirmadas es acíclico .

El gráfico de precedencia para un cronograma S contiene:

• Un nodo para cada transacción confirmada en S
• Un arco de T _i a T _j si una acción de T _i precede y entra en conflicto con una de las acciones de T _j . Es decir, las acciones pertenecen a transacciones diferentes, al menos una de las acciones es una operación de escritura y las acciones acceden al mismo objeto (lectura o escritura).

Los ciclos de transacciones comprometidas se pueden evitar abortando una transacción no decidida (ni comprometida ni abortada) en cada ciclo en el gráfico de precedencia de todas las transacciones, que de otra manera puede convertirse en un ciclo de transacciones comprometidas (y una transacción comprometida no se puede abortar). Se requiere y es suficiente abortar una transacción por ciclo para romper y eliminar el ciclo (es posible que haya más abortamiento y esto puede suceder con algunos mecanismos, pero no es necesario para la serialización). La probabilidad de generación de ciclos es típicamente baja, pero, no obstante, tal situación se maneja con cuidado, generalmente con una cantidad considerable de sobrecarga, ya que está involucrada la corrección. Las transacciones abortadas debido a la prevención de violación de serialización se reinician y se ejecutan nuevamente de inmediato.

Ejemplos de gráficos de precedencia

Ejemplo 1

${\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}}}$

Ejemplo 2

${\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 gráfico de precedencia del cronograma D, con 3 transacciones. Como hay 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 conflicto . Nótese que la confirmación de la transacción 2 no tiene ningún significado en cuanto a la creación de un gráfico de precedencia.

Ejemplo 3

Ejemplo de prueba de serialización

Algoritmo para probar la serialización de conflictos de un programa S junto con un programa de ejemplo.

${\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 programa S, cree un nodo etiquetado como T _i en el gráfico de precedencia. Por lo tanto, el gráfico de precedencia contiene T ₁ , T ₂ , T ₃ .
2. Para cada caso en S donde T _j ejecuta un read_item (X) después de que T _i ejecuta un write_item (X), crea una arista (T _i → T _j ) en el gráfico 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 gráfico 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 gráfico de precedencia. Esto da como resultado aristas dirigidas de T ₂ a T ₁ , de T ₂ a T ₃ y de T ₁ a T ₃ .
5. El programa S es serializable si y solo si el gráfico de precedencia no tiene ciclos. Como T ₁ y T ₂ constituyen un ciclo, el ejemplo anterior no es serializable (por conflicto).

Referencias

1. "21-110: Gráficos de conflicto".
2. "Prueba de gráfico de precedencia para serialización de conflictos".

Enlaces externos

• En el capítulo 17 se analiza el uso de gráficos de precedencia en lo que respecta a las pruebas de serialización de conflictos .
• Abraham Silberschatz , Henry Korth y S. Sudarshan. 2005. Conceptos de sistemas de bases de datos (5 ed.), PP. 628–630. McGraw-Hill, Inc., Nueva York, NY, EE. UU.