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 ejecuciones en 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 sistema no determina el orden en el tiempo entre determinadas operaciones, 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 se incluye un subconjunto de los tipos de operaciones de transacción en una programación.
Los cronogramas 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 programas recuperables estrictos y serializables por conflictos.
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.
El siguiente es un ejemplo de cronograma:
En este ejemplo, las columnas representan las diferentes transacciones en el cronograma D. El cronograma D consta de tres transacciones T1, T2, T3. Primero T1 lee y escribe en el objeto X y luego se confirma. Luego, T2 lee y escribe en el objeto Y y se confirma, y finalmente, T3 lee y escribe en el objeto Z y se confirma.
El programa D anterior se puede representar como una lista de la siguiente manera:
D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3
Por lo general, para razonar sobre el control de concurrencia en bases de datos, una operación se modela como atómica , que ocurre en un momento determinado, sin duración. Las operaciones reales ejecutadas siempre tienen una duración determinada.
Las operaciones de transacciones en un cronograma pueden intercalarse (es decir, las transacciones se pueden ejecutar simultáneamente ), pero las órdenes de tiempo entre operaciones en cada transacción deben permanecer sin cambios. La programación está en orden parcial cuando las operaciones de las transacciones en una programación se intercalan (es decir, cuando la programación es serializable por conflicto 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).
Una programación completa es aquella que contiene una acción de cancelación (también conocida como reversión ) o de 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 aborta.
Una programación es en serie si las transacciones ejecutadas no están entrelazadas (es decir, una programación en serie es aquella en la que no comienza ninguna transacción hasta que finaliza una transacción en ejecución).
El Anexo D es un ejemplo de un programa en serie:
Un cronograma es serializable si es equivalente (en su resultado) a un cronograma en serie.
En el cronograma E, el orden en el 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 consistente. Es el criterio principal para la exactitud del cronograma de transacciones concurrentes y, por lo tanto, se admite en todos los sistemas de bases de datos de propósito general. Es probable que los cronogramas que no sean serializables generen resultados erróneos; lo cual puede ser extremadamente dañino (por ejemplo, cuando se trata de dinero dentro de los bancos). [1] [2] [3]
Si una aplicación solicita algún orden específico entre algunas transacciones, se aplica independientemente de los mecanismos de serialización subyacentes. Estos mecanismos suelen ser indiferentes a cualquier orden específica y generan un orden parcial impredecible que suele ser compatible con múltiples órdenes en serie de estas transacciones.
Se dice que dos acciones están en conflicto (par en conflicto) si y sólo si se cumplen las 3 condiciones siguientes:
De manera equivalente, dos acciones se consideran conflictivas si y sólo 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 contradictorio:
Si bien los siguientes conjuntos de acciones no están en conflicto:
La reducción de los 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 realmente se ejecuta: 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, retenido por otra transacción o cuando se escribe en el espacio de trabajo privado temporal de una transacción y materializándose, copiándose a la propia base de datos, al momento de la confirmación; mientras no se ejecute una operación conflictiva solicitada/emitida en la propia base de datos, el conflicto no se materializa ; Los conflictos no materializados no están representados por un borde en el gráfico de precedencia.
Se dice que los programas S1 y S2 son equivalentes a conflictos si y sólo si se cumplen las dos condiciones siguientes:
De manera equivalente, se dice que dos programas son equivalentes en conflicto si y sólo si uno puede transformarse en otro intercambiando pares de operaciones no conflictivas (ya sean adyacentes o no) mientras se mantiene el orden de acciones para cada transacción. [4]
De manera equivalente, se dice que dos programas son equivalentes en conflicto si y sólo si uno puede transformarse en otro intercambiando pares de operaciones adyacentes no conflictivas con diferentes transacciones. [7]
Se dice que una programación es serializable por conflicto cuando la programación es equivalente en conflicto a una o más programaciones seriales.
De manera equivalente, una programación es serializable por conflictos si y solo si su gráfico de precedencia es acíclico cuando solo se consideran las transacciones comprometidas. Tenga en cuenta que si el gráfico se define para incluir también transacciones no confirmadas, entonces pueden ocurrir ciclos que involucran transacciones no confirmadas sin violación de serialización de conflicto.
El programa K es equivalente en conflicto al programa en serie <T1,T2>, pero no <T2,T1>.
La serialización de conflictos se puede imponer 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 programas S1 y S2 son equivalentes en vista cuando se cumplen las siguientes condiciones:
Además, dos programaciones equivalentes a vistas 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 programas S1 y S2 son equivalentes en vista, pero ni S1 ni S2 son equivalentes en vista al programa S3.
Las condiciones para que S3 sea equivalente en vista a S1 y S2 no se cumplieron en los superíndices correspondientes por las siguientes razones:
Para analizar rápidamente si dos programas son equivalentes en vista, escriba ambos programas como una lista con el subíndice de cada acción que represente con qué condición de equivalencia de vista coinciden. Los cronogramas son equivalentes en vista si y solo si todas las acciones tienen el mismo subíndice (o la falta del mismo) en ambos cronogramas:
Una programación es serializable en vista si es equivalente en vista a alguna programación en serie. Tenga en cuenta que, por definición, todas las programaciones serializables por conflictos son serializables por vista.
Observe que el ejemplo anterior (que es el mismo que el ejemplo en la discusión sobre serializable por conflicto) es serializable por vista y por conflicto al mismo tiempo. Sin embargo, hay programaciones serializables por vista que no son serializables por conflictos: aquellas programaciones con una transacción que realiza una escritura ciega :
El ejemplo anterior no es serializable por conflicto, pero sí por vista, ya que tiene una programación serial equivalente a 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 necesaria ]
En un cronograma recuperable , las transacciones solo se confirman después de que se hayan confirmado todas las transacciones cuyos cambios leyeron. Una programación se vuelve irrecuperable si una transacción lee y se basa en los cambios de otra transacción , y luego se confirma y aborta.
Estos horarios son recuperables. El cronograma F es recuperable porque T1 se confirma antes que T2, lo que hace que el valor leído por T2 sea correcto. Entonces T2 puede comprometerse. En el programa F2, si T1 abortó, T2 tiene que abortar porque el valor de A que leyó es incorrecto. En ambos casos, la base de datos se deja en un estado consistente.
La transacción J es irrecuperable porque T2 se comprometió antes que T1 a pesar de haber leído previamente el valor escrito por T1. Debido a que T1 canceló después de que T2 se comprometió, el valor leído por T2 es incorrecto. Debido a que una transacción no se puede revertir después de confirmarse, la programación 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 la cancelación de una transacción hace que otra transacción se cancele porque leyó y se basó en los cambios de la primera transacción en un objeto. Una lectura sucia ocurre cuando una transacción lee datos de escrituras no confirmadas en otra transacción. [9]
Los siguientes ejemplos son los mismos que los de la discusión sobre recuperables:
En este ejemplo, aunque F2 es recuperable, no evita abortos en cascada. Se puede ver que si T1 aborta, T2 también tendrá que abortar para mantener la exactitud del cronograma, ya que T2 ya leyó el valor no confirmado escrito por T1.
El siguiente es un programa recuperable que evita el aborto en cascada. Sin embargo, tenga en cuenta que la actualización de A por T1 siempre se pierde (ya que T1 se cancela).
Tenga en cuenta que este programa no sería serializable si se confirmara T1. La evitación de abortos en cascada es suficiente, pero no necesaria, para que un programa sea recuperable.
Una programación es estricta si para dos transacciones cualesquiera T1, T2, si una operación de escritura de T1 precede a una operación conflictiva de T2 (ya sea lectura o escritura), entonces el evento de confirmación o cancelación de T1 también precede a esa operación conflictiva de T2.
Cualquier cronograma estricto no tiene cascadas, pero no al revés. La rigurosidad permite la recuperación eficiente de bases de datos en caso de falla.
Las siguientes expresiones ilustran las relaciones jerárquicas (de contención) entre las clases de serialización y recuperabilidad :
El diagrama de Venn (a continuación) ilustra gráficamente las cláusulas anteriores.
