Calendario de transacciones de la base de datos

Se dice que dos acciones están en conflicto (par conflictivo) si y solo si se cumplen las tres condiciones siguientes:

1. Las acciones pertenecen a diferentes transacciones.
2. Al menos una de las acciones es una operación de escritura.
3. Las acciones acceden al mismo objeto (leer o escribir). ^{[ 4 ] [ 5 ]}

De forma equivalente, dos acciones se consideran conflictivas si y solo si no son conmutativas . De forma equivalente, dos acciones se consideran conflictivas si y solo si se trata de un conflicto de lectura-escritura , escritura-lectura o escritura-escritura .

El siguiente conjunto de acciones es contradictorio:

• R1(X), W2(X), W3(X) (3 pares conflictivos)

Si bien los siguientes conjuntos de acciones no son contradictorios:

• R1(X), R2(X), R3(X)
• R1(X), W2(Y), R3(X)

La reducción de conflictos, por ejemplo mediante la conmutatividad, mejora el rendimiento, ya que los conflictos son la causa fundamental de los retrasos y las interrupciones.

El conflicto se materializa si la operación conflictiva solicitada se ejecuta realmente: en muchos casos, una operación conflictiva solicitada/emitida por una transacción se retrasa e incluso nunca se ejecuta, normalmente debido a un bloqueo en el objeto de la operación, mantenido por otra transacción, o al escribir en el espacio de trabajo privado temporal de una transacción y materializarse, copiando a la propia base de datos, al confirmar la transacción; mientras una operación conflictiva solicitada/emitida no se ejecute en la propia base de datos, el conflicto no se materializa ; los conflictos no materializados no están representados por una arista en el grafo de precedencia.

Se dice que los anexos S1 y S2 son equivalentes en cuanto a conflictos si y solo si se cumplen las dos condiciones siguientes:

1. Tanto el Anexo S1 como el Anexo S2 implican el mismo conjunto de transacciones, de modo que cada transacción tiene las mismas acciones en el mismo orden.
2. Ambos cronogramas tienen el mismo conjunto de pares conflictivos (de modo que las acciones en cada par conflictivo están en el mismo orden). ^{[ 6 ]} Esto es equivalente a exigir que todas las operaciones conflictivas (es decir, las operaciones en cualquier par conflictivo) estén en el mismo orden en ambos cronogramas.

De forma equivalente, se dice que dos planificaciones son equivalentes en cuanto a conflictos si y solo si una puede transformarse en otra intercambiando pares de operaciones no conflictivas (sean adyacentes o no) manteniendo el orden de las acciones para cada transacción. ^{[ 4 ]}

De forma equivalente, se dice que dos planificaciones son equivalentes en cuanto a conflictos si y solo si una puede transformarse en otra intercambiando pares de operaciones adyacentes no conflictivas con transacciones diferentes. ^{[ 7 ]}

Se dice que una planificación es serializable por conflictos cuando dicha planificación es equivalente en términos de conflictos a una o más planificaciones seriales.

De forma equivalente, una planificación es serializable por conflictos si y solo si su grafo de precedencia es acíclico cuando solo se consideran las transacciones confirmadas. Cabe señalar que si el grafo se define para incluir también las transacciones no confirmadas, entonces pueden ocurrir ciclos que involucren transacciones no confirmadas sin que se produzca una violación de la serializabilidad por conflictos.

El plan K es equivalente en términos de conflicto al plan serial <T1,T2>, pero no a <T2,T1>.

La serializabilidad de conflictos se puede garantizar reiniciando cualquier transacción dentro del ciclo en el grafo de precedencia, o implementando bloqueo de dos fases , ordenación por marca de tiempo o aislamiento de instantáneas serializables . ^{[ 8 ]}

Se dice que dos tablas S1 y S2 son equivalentes en cuanto a su visualización cuando se cumplen las siguientes condiciones:

1. Si la transacción${\displaystyle T_{i}}$En S1 se lee un valor inicial para el objeto X, por lo que se realiza la misma transacción.${\displaystyle T_{i}}$en S2.
2. Si la transacción${\displaystyle T_{i}}$lee un valor (para un objeto X) escrito por la transacción${\displaystyle T_{j}}$En S1, debe hacerlo en S2.
3. Si la transacción${\displaystyle T_{i}}$En S1 se realiza la escritura final para el objeto X, por lo que se realiza la misma transacción.${\displaystyle T_{i}}$en S2.

Además, dos cronogramas equivalentes en cuanto a la vista deben involucrar el mismo conjunto de transacciones, de manera que cada transacción tenga las mismas acciones en el mismo orden.

En el ejemplo que se muestra a continuación, los planes S1 y S2 son visualmente equivalentes, pero ni S1 ni S2 son visualmente equivalentes al plan S3.

Las condiciones para que S3 sea visualmente equivalente a S1 y S2 no se cumplieron en los superíndices correspondientes por las siguientes razones:

1. No se cumplió la primera condición de equivalencia de vista porque T1 leyó el valor inicial de B en S1 y S2, pero T2 leyó el valor inicial de B en S3.
2. No se cumplió la segunda condición de equivalencia de vista porque T2 leyó el valor escrito por T1 para B en S1 y S2, pero T1 leyó el valor escrito por T2 para B en S3.
3. No se cumplió la tercera condición de equivalencia de vista porque T2 hizo la escritura final para B en S1 y S2, pero T1 hizo la escritura final para B en S3.

Para analizar rápidamente si dos planificaciones son equivalentes en cuanto a la vista, escriba ambas planificaciones como una lista donde el subíndice de cada acción represente la condición de equivalencia de vista que cumplen. Las planificaciones son equivalentes en cuanto a la vista si y solo si todas las acciones tienen el mismo subíndice (o carecen de él) en ambas planificaciones:

• S1: R1(A) _{lectura inicial} , W1(A), R1(B) _{lectura inicial} , W1(B), Com1, R2(A) _{escrito por T1} , W2(A) _{escritura final} , R2(B) _{escrito por T1} , W2(B) _{escritura final} , Com2
• S2: R1(A) _{lectura inicial} , W1(A), R2(A) _{escrito por T1} , W2(A) _{escritura final} , R1(B) _{lectura inicial} , W1(B), Com1, R2(B) _{escrito por T1} , W2(B) _{escritura final} , Com2
• S3: R1(A) _{lectura inicial} , W1(A), R2(A) _{escrito por T1} , W2(A) _{escritura final} , R2(B) _{lectura inicial} , W2(B), R1(B) _{escrito por T2} , W1(B) _{escritura final} , Com1, Com2

Una planificación es serializable por vista si es equivalente a alguna planificación serial. Cabe destacar que, por definición, todas las planificaciones serializables por conflicto son serializables por vista.

Nótese que el ejemplo anterior (que es el mismo que el ejemplo en la discusión sobre serialización de conflictos) es serializable por vista y serializable por conflicto al mismo tiempo. Sin embargo, existen planificaciones serializables por vista que no son serializables por conflicto: aquellas planificaciones con una transacción que realiza una escritura ciega :

El ejemplo anterior no es serializable por conflicto, pero sí es serializable por vista, ya que tiene una planificación serial equivalente a la de una vista <T1,|  T2,|  T3>.

Dado que determinar si una planificación es serializable por vista es un problema NP-completo , la serializabilidad por vista tiene poco interés práctico.

Las planificaciones sin cascada (también conocidas como "planificaciones para evitar abortos en cascada (ACA)") son planificaciones que evitan los abortos en cascada al no permitir lecturas sucias . Los abortos en cascada ocurren cuando el aborto de una transacción provoca el aborto de otra transacción porque esta última leyó y dependió de los cambios realizados por la primera transacción en un objeto. Una lectura sucia ocurre cuando una transacción lee datos de una escritura no confirmada en otra transacción. ^{[ 9 ]}

Los siguientes ejemplos son los mismos que los de la discusión sobre recuperabilidad:

En este ejemplo, aunque F2 es recuperable, no evita las interrupciones en cascada. Se observa que si T1 se interrumpe, T2 también deberá interrumpirse para mantener la corrección de la planificación, ya que T2 ya ha leído el valor no confirmado escrito por T1.

A continuación se muestra una planificación recuperable que evita la cancelación en cascada. Sin embargo, tenga en cuenta que la actualización de A por parte de T1 siempre se pierde (ya que T1 se cancela).

Tenga en cuenta que este cronograma no sería serializable si se confirmara la ejecución de T1. Evitar las interrupciones en cascada es suficiente, pero no necesario, para que un cronograma sea recuperable.

Una planificación es estricta si, para dos transacciones cualesquiera T1 y T2, si una operación de escritura de T1 precede a una operación conflictiva de T2 (ya sea de lectura o escritura), entonces el evento de confirmación o cancelación de T1 también precede a esa operación conflictiva de T2. Por ejemplo, la planificación F3 anterior es estricta.

Cualquier programación estricta no produce efectos en cascada, pero no al revés. La rigurosidad permite una recuperación eficiente de las bases de datos ante fallos.