Un gráfico de precedencia , también llamado gráfico de conflicto [1] y gráfico de serialización , se utiliza en el contexto del control de concurrencia en las bases de datos . [2]
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
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
Algoritmo para probar la serialización de conflictos de un Schedule S junto con un programa de ejemplo.
- o
- 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 1 , T 2 , T 3 .
- 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.
- 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 1 a T 2 (ya que T 1 tiene R (A) antes que T 2 tenga W (A) ).
- 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 2 a T 1 , T 2 a T 3 y T 1 a T 3 .
- El programa S es serializable si y solo si el gráfico de precedencia no tiene ciclos. Como T 1 y T 2 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.