Programación de transacciones de la base de datos

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Database transaction schedule" – news · newspapers · books · scholar · JSTOR (November 2012) (Learn how and when to remove this message)

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:

• Columnas: Las diferentes transacciones en el cronograma.
• Filas: El orden temporal de las operaciones (también conocidas como acciones).

Operaciones (también conocidas como acciones):

• R(X): La transacción correspondiente "lee" el objeto X (es decir, recupera los datos almacenados en X). Esto se hace para poder modificar los datos (por ejemplo, X=X+4) durante una operación de "escritura" en lugar de simplemente sobrescribirlos. Cuando el cronograma se representa como una lista en lugar de una cuadrícula, la acción se representa como donde es un número correspondiente a una transacción específica.${\displaystyle Ri(X)}$${\displaystyle i}$
• W(X): La transacción correspondiente "escribe" en el objeto X (es decir, modifica los datos almacenados en X). Cuando el cronograma se representa como una lista en lugar de una cuadrícula, la acción se representa como donde es un número que corresponde a una transacción específica.${\displaystyle Wi(X)}$${\displaystyle i}$
• Com.: Representa una operación de "confirmación" en la que la transacción correspondiente ha completado con éxito sus acciones anteriores y ha hecho que todos sus cambios sean permanentes en la base de datos.

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:

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

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:

• R1(X), W2(X), W3(X) (3 pares en conflicto)

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 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:

1. Ambos programas S1 y S2 involucran el mismo conjunto de transacciones, de modo que cada transacción tiene las mismas acciones en el mismo orden.
2. Ambos programas tienen el mismo conjunto de pares en conflicto (de modo que las acciones en cada par en conflicto están en el mismo orden). ^[6] Esto es equivalente a requerir que todas las operaciones en conflicto (es decir, las operaciones en cualquier par en conflicto) estén en el mismo orden en ambos programas.

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:

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

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:

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 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:

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

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.${\displaystyle T_{i}}$${\displaystyle T_{j}}$${\displaystyle T_{i}}$${\displaystyle T_{j}}$

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 :

• Serial ⊂ serializable por conflicto ⊂ serializable por vista ⊂ todas las programaciones
• Serie ⊂ estricta ⊂ sin cascada (ACA) ⊂ recuperable ⊂ todas las programaciones

El diagrama de Venn (abajo) ilustra gráficamente las cláusulas anteriores.

• Cronograma (gestión de proyectos)
• Bloqueo estricto de dos fases fuerte (SS2PL o Rigor).
• Hacer que el aislamiento de instantáneas sea serializable ^[8] en Aislamiento de instantáneas .
• Serializabilidad global , donde se describe el problema de serializabilidad global y sus soluciones propuestas.
• Linealizabilidad , un concepto más general en computación concurrente .