Gráfico de precedencia - Precedence graph

Un grafo de precedencia , también llamado gráfico de conflicto y seriabilidad gráfica , se utiliza en el contexto de control de concurrencia en las bases de datos .

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

• Un nodo para cada transacción comprometida 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 diferentes transacciones, al menos una de las acciones es una operación de escritura y las acciones acceden al mismo objeto (lectura o escritura).

Ejemplos de gráficos de precedencia

Ejemplo 1

Ejemplo 2

${\ 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 horario D, con 3 transacciones. Como hay un ciclo (de longitud 2; con dos aristas) a través de las transacciones comprometidas T1 y T2, este programa (historial) no es serializable por conflictos . Tenga en cuenta que la confirmación de la Transacción 2 no tiene ningún significado con respecto a la creación de un gráfico de precedencia.

Prueba de serialización con gráfico de precedencia

Ejemplo de prueba de serialización

Algoritmo para probar la serialización de conflictos de un Schedule 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} participa en el programa S, cree un nodo etiquetado como T _i en el gráfico de precedencia. Por 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), cree una arista (T _i → T _j ) en el gráfico de precedencia. Esto no ocurre en ninguna parte del ejemplo anterior, ya que no hay lectura tras 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), cree un borde (T _i → T _j ) en el gráfico de precedencia. Esto da como resultado un borde dirigido de T ₁ a T ₂ (ya que T ₁ tiene R (A) antes que T ₂ tenga W (A) ).
4. Para cada caso en S donde T _j ejecuta un elemento_escritura (X) después de que T _i ejecuta un elemento_escritura (X), cree una arista (T _i → T _j ) en el gráfico de precedencia. Esto da como resultado bordes dirigidos de T ₂ a T ₁ , T ₂ a T ₃ y 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 (conflicto) serializable.

Referencias

enlaces externos

• The Fundamentals of Database Systems, 5th Edition, el uso de gráficos de precedencia se analiza en el capítulo 17, ya que se relacionan con 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.