En los campos de las bases de datos y el procesamiento de transacciones (gestión de transacciones), un cronograma (o historial ) de un sistema es un modelo abstracto para describir el orden de ejecución de un conjunto de transacciones que se ejecutan en el sistema. A menudo, es una lista de operaciones (acciones) ordenadas por tiempo, realizadas por un conjunto de transacciones que se ejecutan juntas en el sistema. Si el orden en el tiempo entre ciertas operaciones no está determinado por el sistema, entonces se utiliza un orden parcial . Ejemplos de tales operaciones son solicitar una operación de lectura, leer, escribir, abortar, confirmar , solicitar un bloqueo , bloquear, etc. A menudo, solo un subconjunto de los tipos de operaciones de transacción se incluyen en un cronograma.
Las programaciones son conceptos fundamentales en la teoría del control de concurrencia de bases de datos . En la práctica, la mayoría de los sistemas de bases de datos de propósito general emplean programaciones serializables ante conflictos y estrictamente recuperables.
Notación de cuadrícula:
Operaciones (también conocidas como acciones):
Alternativamente, un cronograma se puede representar con un gráfico acíclico dirigido (o DAG) en el que hay un arco (es decir, un borde dirigido ) entre cada par ordenado de operaciones.
A continuación se muestra un ejemplo de un cronograma:
En este ejemplo, las columnas representan las diferentes transacciones en el cronograma D. El cronograma D consta de tres transacciones: T1, T2 y T3. Primero, T1 lee y escribe en el objeto X y, a continuación, confirma. Luego, T2 lee y escribe en el objeto Y y confirma y, por último, T3 lee y escribe en el objeto Z y confirma.
El anexo D anterior se puede representar como lista de la siguiente manera:
D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3
Por lo general, a los efectos de razonar sobre el control de concurrencia en bases de datos, una operación se modela como atómica , que ocurre en un punto en el tiempo, sin duración. Las operaciones ejecutadas realmente siempre tienen cierta duración.
Las operaciones de las transacciones en un cronograma pueden intercalarse (es decir, las transacciones pueden ejecutarse simultáneamente ), pero los órdenes de tiempo entre las operaciones en cada transacción deben permanecer inalterados. El cronograma está en orden parcial cuando las operaciones de las transacciones en un cronograma se intercalan (es decir, cuando el cronograma es serializable por conflictos pero no serial). El cronograma está en orden total cuando las operaciones de las transacciones en un cronograma no se intercalan (es decir, cuando el cronograma es serial).
Un cronograma completo es aquel que contiene una acción de cancelación (también conocida como reversión ) o confirmación para cada una de sus transacciones. La última acción de una transacción es confirmar o cancelar. Para mantener la atomicidad , una transacción debe deshacer todas sus acciones si se cancela.
Un programa es serial si las transacciones ejecutadas no están intercaladas (es decir, un programa serial es uno en el que ninguna transacción comienza hasta que una transacción en ejecución ha finalizado).
El Anexo D es un ejemplo de un anexo serial:
Una programación es serializable si es equivalente (en su resultado) a una programación serial.
En el anexo E, el orden en que se ejecutan las acciones de las transacciones no es el mismo que en D, pero al final, E da el mismo resultado que D.
La serialización se utiliza para mantener los datos del elemento de datos en un estado coherente. Es el criterio principal para la corrección de la programación de transacciones concurrentes y, por lo tanto, es compatible con todos los sistemas de bases de datos de propósito general. Las programaciones que no son serializables pueden generar resultados erróneos, lo que puede ser extremadamente perjudicial (por ejemplo, cuando se trata de dinero dentro de los bancos). [1] [2] [3]
Si una aplicación solicita un orden específico entre algunas transacciones, este se aplica independientemente de los mecanismos de serialización subyacentes. Estos mecanismos suelen ser indiferentes a cualquier orden específico y generan un orden parcial impredecible que suele ser compatible con múltiples órdenes seriales de estas transacciones.
Se dice que dos acciones están en conflicto (par en conflicto) si y solo si se cumplen las tres condiciones siguientes:
De manera equivalente, dos acciones se consideran conflictivas si y solo si son no conmutativas . De manera equivalente, dos acciones se consideran conflictivas si y solo si son un conflicto de lectura-escritura , escritura-lectura o escritura-escritura .
El siguiente conjunto de acciones es conflictivo:
Si bien los siguientes conjuntos de acciones no son contradictorios:
La reducción de conflictos, por ejemplo mediante la conmutatividad, mejora el rendimiento porque los conflictos son la causa fundamental de los retrasos y los abortos.
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 por un bloqueo en el objeto de la operación, mantenido por otra transacción, o cuando se escribe en el espacio de trabajo privado temporal de una transacción y se materializa, copiando a la base de datos misma, al confirmar; siempre que una operación conflictiva solicitada/emitida no se ejecute en la base de datos misma, el conflicto no se materializa ; los conflictos no materializados no se representan mediante un borde en el gráfico de precedencia.
Se dice que los horarios S1 y S2 son equivalentes en cuanto a conflictos si y solo si se cumplen las dos condiciones siguientes:
De manera equivalente, se dice que dos programaciones son equivalentes en conflicto si y solo si una puede transformarse en otra intercambiando pares de operaciones no conflictivas (sean adyacentes o no) mientras se mantiene el orden de las acciones para cada transacción. [4]
De manera equivalente, se dice que dos programaciones son equivalentes en conflicto si y solo si una puede transformarse en otra intercambiando pares de operaciones adyacentes no conflictivas con transacciones diferentes. [7]
Se dice que una programación es serializable en caso de conflicto cuando es equivalente en caso de conflicto a una o más programaciones seriales.
De manera equivalente, una programación es serializable por conflicto si y solo si su gráfico de precedencia es acíclico cuando solo se consideran las transacciones confirmadas. Tenga en cuenta que si el gráfico está definido para incluir también transacciones no confirmadas, entonces los ciclos que involucran transacciones no confirmadas pueden ocurrir sin violación de la serialización por conflicto.
El programa K es equivalente en cuanto a conflictos al programa serial <T1,T2>, pero no a <T2,T1>.
La serialización de conflictos se puede hacer cumplir reiniciando cualquier transacción dentro del ciclo en el gráfico de precedencia, o implementando bloqueo de dos fases , orden de marca de tiempo o aislamiento de instantáneas serializables . [8]
Se dice que dos programaciones S1 y S2 son equivalentes en cuanto a la vista cuando se cumplen las siguientes condiciones:
Además, dos programaciones equivalentes en cuanto a la vista deben involucrar el mismo conjunto de transacciones, de modo que cada transacción tenga las mismas acciones en el mismo orden.
En el siguiente ejemplo, los cronogramas S1 y S2 son equivalentes en cuanto a la vista, pero ni S1 ni S2 son equivalentes en cuanto a la vista del cronograma S3.
Las condiciones para que S3 sea equivalente a S1 y S2 no se cumplieron en los superíndices correspondientes por las siguientes razones:
Para analizar rápidamente si dos programaciones son equivalentes en cuanto a la vista, escriba ambas programaciones como una lista con el subíndice de cada acción que represente la condición de equivalencia de vista con la que coinciden. Las programaciones son equivalentes en cuanto a la vista si y solo si todas las acciones tienen el mismo subíndice (o la falta de él) en ambas programaciones:
Una programación es serializable en vista si es equivalente en vista a alguna programación serial. Tenga en cuenta que, por definición, todas las programaciones serializables en caso de conflicto son serializables en vista.
Tenga en cuenta que el ejemplo anterior (que es el mismo que el ejemplo en la discusión sobre serializable por conflicto) es serializable por vista y serializable por conflicto al mismo tiempo. Sin embargo, existen programaciones serializables por vista que no son serializables por conflicto: aquellas programaciones con una transacción que realiza una escritura a ciegas :
El ejemplo anterior no se puede serializar por conflictos, pero sí por vistas, ya que tiene un programa serial equivalente a la vista <T1,| T2,| T3>.
Dado que determinar si una programación es serializable en vista es NP-completo , la serialización en vista tiene poco interés práctico. [ cita requerida ]
En un cronograma recuperable , las transacciones solo se confirman después de que se hayan confirmado todas las transacciones cuyos cambios leyeron. Un cronograma se vuelve irrecuperable si una transacción lee y depende de los cambios de otra transacción y luego se confirma y se cancela.
Estas programaciones son recuperables. La programacion F es recuperable porque T1 confirma antes que T2, lo que hace que el valor leído por T2 sea correcto. Entonces T2 puede confirmarse a sí mismo. En la programacion F2, si T1 cancela, T2 tiene que cancelar porque el valor de A que leyó es incorrecto. En ambos casos, la base de datos se deja en un estado consistente.
El cronograma J no se puede recuperar porque T2 se comprometió antes que T1 a pesar de haber leído previamente el valor escrito por T1. Debido a que T1 se canceló después de que T2 se comprometiera, el valor leído por T2 es incorrecto. Debido a que una transacción no se puede revertir después de que se compromete, el cronograma es irrecuperable.
Las programaciones sin cascada (también conocidas como "programaciones para evitar abortos en cascada (ACA)") son programaciones que evitan los abortos en cascada al no permitir lecturas sucias . Los abortos en cascada ocurren cuando el aborto de una transacción hace que otra transacción se anule porque leyó y dependió de los cambios de 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 que se mencionan en la discusión sobre recuperables:
En este ejemplo, aunque F2 es recuperable, no evita los abortos en cascada. Se puede ver que si T1 aborta, T2 también tendrá que abortarse para mantener la corrección de la programación, ya que T2 ya ha leído el valor no confirmado escrito por T1.
A continuación se muestra un programa recuperable que evita la interrupció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 esta programación no se podría serializar si se confirmara T1. Evitar abortos en cascada es suficiente, pero no necesario, para que una programación sea recuperable.
Un cronograma es estricto si, para dos transacciones T1 y T2, una operación de escritura de T1 precede a una operación conflictiva de T2 (ya sea de lectura o de escritura), entonces el evento de confirmación o cancelación de T1 también precede a esa operación conflictiva de T2. Por ejemplo, el cronograma F3 anterior es estricto.
Cualquier programación estricta no tiene cascada, pero no a la inversa. La rigurosidad permite una recuperación eficiente de las bases de datos en caso de fallo.
Las siguientes expresiones ilustran las relaciones jerárquicas (de contención) entre las clases de serialización y recuperabilidad :
El diagrama de Venn (abajo) ilustra gráficamente las cláusulas anteriores.
