Serializabilidad de transacciones: equivalencia por conflicto y por vistas en bases de datos

Serializabilidad de Transacciones en Bases de Datos

La serializabilidad (o secuencialidad) es un concepto fundamental en la gestión de bases de datos. El sistema debe controlar la ejecución concurrente de las transacciones para asegurar que el estado de la base de datos sigue siendo consistente.

Para determinar qué planificaciones aseguran la consistencia y cuáles no, se consideran solo dos operaciones básicas sobre un elemento de dato $Q$:

• leer(Q)
• escribir(Q)

Entre estas dos operaciones, una transacción puede realizar una secuencia arbitraria de operaciones con la copia de $Q$ que reside en la memoria intermedia.

Formas de Equivalencia de Planificación

Existen dos formas principales de equivalencia de planificación que definen la serializabilidad:

1. Serializabilidad en Cuanto a Conflicto

Una planificación $P$ implica dos instrucciones consecutivas $I_i$ e $I_j$, pertenecientes a las transacciones $T_i$ y $T_j$ respectivamente ($i eq j$).

• Si $I_i$ e $I_j$ se refieren a distintos elementos de datos, se pueden intercambiar $I_i$ e $I_j$ sin afectar el resultado de cualquier instrucción de la planificación.
• Si $I_i$ e $I_j$ se refieren al mismo elemento $Q$, el orden de los dos pasos puede ser importante.

Casos de Conflicto Potencial (Mismo Elemento Q)

1. $I_i = leer(Q)$, $I_j = leer(Q)$: El orden de $I_i$ e $I_j$ no importa, puesto que $T_i$ y $T_j$ leen el mismo valor de $Q$, independientemente del orden.
2. $I_i = leer(Q)$, $I_j = escribir(Q)$: El orden de $I_i$ e $I_j$ es importante. Si $I_i$ está antes que $I_j$, $T_i$ no lee el valor de $Q$ que escribe $I_j$ de $T_j$. Si $I_j$ está antes que $I_i$, $T_i$ lee el valor de $Q$ escrito por $T_j$. Por tanto, el orden de $I_i$ e $I_j$ es importante.
3. $I_i = escribir(Q)$, $I_j = leer(Q)$: Ídem al anterior. El orden de $I_i$ e $I_j$ es importante.
4. $I_i = escribir(Q)$, $I_j = escribir(Q)$: El orden afecta al valor final de $Q$ en la base de datos. Puesto que ambas son operaciones de escritura, el orden no afecta ni a $T_i$ ni a $T_j$ en su ejecución inmediata. Sin embargo, el valor que obtendrá la siguiente instrucción leer(Q) de $P$ sí se ve afectado, ya que se conserva en la DB la última instrucción de escritura. Si no hay ninguna otra instrucción escribir(Q) después de $I_i$ e $I_j$ en $P$, el orden de $I_i$ e $I_j$ afecta directamente al valor final de $Q$ en el estado de la DB que se obtiene con la planificación $P$.

Definiciones Clave de Conflicto

• Se dice que $I_i$ e $I_j$ están en conflicto si son operaciones de diferentes transacciones sobre el mismo elemento de datos, y al menos una de esas instrucciones es una operación escribir.
• Si una planificación $P$ se puede transformar en otra $P'$ por medio de una serie de intercambios de instrucciones no conflictivas, se dice que $P$ y $P'$ son equivalentes en cuanto a conflictos.
• Se dice que una planificación $P$ es serializable en cuanto a conflictos si es equivalente en cuanto a conflictos a una planificación secuencial.

2. Serializabilidad en Cuanto a Vistas

Considérense dos planificaciones, $P$ y $P'$, en las cuales participa el mismo conjunto de transacciones. Son equivalentes en cuanto a vistas si se cumplen las tres condiciones siguientes:

1. Si la transacción $T_i$ lee el valor inicial de $Q$ en $P$, también debe leer el valor inicial de $Q$ en $P'$.
2. Si $T_i$ ejecuta leer(Q) en $P$ y el valor lo ha producido $T_j$, entonces $T_i$ debe leer también el valor de $Q$ que produjo $T_j$ en $P'$.
3. Para todo elemento de datos $Q$, la transacción que realice la última operación escribir(Q) en $P$ debe realizar la misma operación escribir(Q) en $P'$.

Las condiciones 1 y 2 aseguran que cada transacción lee los mismos valores en ambas planificaciones y, por tanto, realizan los mismos cálculos. La condición 3, junto con las condiciones 1 y 2, asegura que ambas planificaciones dan como resultado el mismo estado final del sistema.

Se dice que la planificación $P$ es serializable en cuanto a vistas si es equivalente en cuanto a vistas a una planificación secuencial.

Relación entre Tipos de Serializabilidad y Escrituras a Ciegas

Toda planificación serializable en cuanto a conflictos es siempre serializable en cuanto a vistas. Sin embargo, una planificación serializable en cuanto a vistas puede que no sea serializable en cuanto a conflictos.

La escritura a ciegas (blind write) se denomina cuando hay transacciones que realizan operaciones de escribir(Q) sin haber realizado ninguna operación leer(Q) previamente.

Las escrituras a ciegas aparecen en toda planificación serializable en cuanto a vistas que no sea serializable en cuanto a conflictos.