Tipos de Horarios en DBMS – Part 1

La programación, como sugiere el nombre, es un proceso de alinear las transacciones y ejecutarlas una por una. Cuando hay múltiples transacciones que se ejecutan de manera simultánea y es necesario establecer el orden de la operación para que las operaciones no se superpongan entre sí, se pone en juego la programación y las transacciones se cronometran en consecuencia. Los aspectos básicos de las transacciones y los cronogramas se analizan en los artículos Control de concurrencia (Introducción) y Niveles de aislamiento de transacciones en DBMS . Aquí discutiremos varios tipos de horarios.

1. Programaciones en serie:
   Las programaciones en las que las transacciones se ejecutan sin intercalar, es decir, una programación en serie es aquella en la que ninguna transacción comienza hasta que finaliza una transacción en curso, se denominan programaciones en serie.

   Ejemplo: Considere el siguiente cronograma que involucra dos transacciones T ₁ y T ₂ .

   T 1	T 2
   REAL ACADEMIA DE BELLAS ARTES)
   WASHINGTON)
   R(B)
   W (B)
   REAL ACADEMIA DE BELLAS ARTES)
   R(B)

   donde R(A) denota que se realiza una operación de lectura en algún elemento de datos ‘A’
   Este es un programa en serie ya que las transacciones se realizan en serie en el orden T ₁ —> T ₂

2. Programación No Serial:
   Este es un tipo de Programación donde se intercalan las operaciones de múltiples transacciones. Esto podría conducir a un aumento en el problema de concurrencia. Las transacciones se ejecutan de manera no serial, manteniendo el resultado final correcto y el mismo que el programa serial. A diferencia del cronograma serial donde una transacción debe esperar a que otra complete toda su operación, en el cronograma no serial, la otra transacción continúa sin esperar a que se complete la transacción anterior. Este tipo de horario no proporciona ningún beneficio de la transacción concurrente. Puede ser de dos tipos, a saber, programación serializable y no serializable.

   El programa no serializado se puede dividir en serializable y no serializable.

   1. Serializable:
      Esto se utiliza para mantener la consistencia de la base de datos. Se utiliza principalmente en la programación no serial para verificar si la programación dará lugar a alguna inconsistencia o no. Por otro lado, un programa en serie no necesita la serialización porque sigue a una transacción solo cuando la transacción anterior está completa. Se dice que el programa no serial está en un programa serializable solo cuando es equivalente a los programas seriales, para un número n de transacciones. Dado que en este caso se permite la concurrencia, se pueden ejecutar varias transacciones al mismo tiempo. Un programa serializable ayuda a mejorar tanto la utilización de recursos como el rendimiento de la CPU. Estos son de dos tipos:
      1. Serializable en conflicto:
         un programa se denomina serializable en conflicto si se puede transformar en un programa en serie intercambiando operaciones que no están en conflicto. Se dice que dos operaciones son contradictorias si se cumplen todas las condiciones:
         • Pertenecen a diferentes transacciones.
         • Operan en el mismo elemento de datos.
         • Al menos uno de ellos es una operación de escritura.
      2. Ver serializable:
         un programa se llama vista serializable si es igual a una vista serial (sin transacciones superpuestas). Un cronograma de conflicto es una vista serializable, pero si la serializabilidad contiene escrituras ocultas, entonces la vista serializable no entra en conflicto con la serializable.
   2. No serializable:
      El programa no serializable se divide en dos tipos, Programa recuperable y No recuperable.
      1. Calendario recuperable:
         los calendarios en los que las transacciones se confirman solo después de que se confirmen todas las transacciones cuyos cambios leen se denominan calendarios recuperables. En otras palabras, si alguna transacción _Tj está leyendo el valor actualizado o escrito por alguna otra transacción _Ti , entonces la confirmación de _Tj debe ocurrir después de la confirmación de _Ti .

         Ejemplo: considere el siguiente cronograma que involucra dos transacciones T ₁ y T ₂ .

         T 1	T 2
         REAL ACADEMIA DE BELLAS ARTES)
         WASHINGTON)
         WASHINGTON)
         REAL ACADEMIA DE BELLAS ARTES)
         comprometerse
         comprometerse

         Este es un programa recuperable ya que T ₁ se compromete antes que T ₂ , lo que hace que el valor leído por T ₂ sea correcto.

         Puede haber tres tipos de programa recuperable:

         1. Horario en cascada:

            También llamado Evita anulaciones/retrocesos en cascada (ACA). Cuando hay una falla en una transacción y esto conduce a la reversión o cancelación de otras transacciones dependientes, dicha programación se denomina reversión en cascada o cancelación en cascada. Ejemplo:
            

         2. Programación sin cascada:
            las programaciones en las que las transacciones leen valores solo después de que se confirmen todas las transacciones cuyos cambios van a leer se denominan programaciones sin cascada. Evita que un solo aborto de transacción conduzca a una serie de reversiones de transacciones. Una estrategia para evitar abortos en cascada es prohibir que una transacción lea cambios no confirmados de otra transacción en el mismo cronograma.

            En otras palabras, si alguna transacción T _j quiere leer el valor actualizado o escrito por alguna otra transacción T _i , entonces la confirmación de T _j debe leerlo después de la confirmación de T _i .

            Ejemplo: Considere el siguiente cronograma que involucra dos transacciones T ₁ y T ₂ .

            T 1	T 2
            REAL ACADEMIA DE BELLAS ARTES)
            WASHINGTON)
            WASHINGTON)
            comprometerse
            REAL ACADEMIA DE BELLAS ARTES)
            comprometerse

            Este horario no tiene cascada. Dado que el valor actualizado de A es leído por T ₂ solo después de la transacción de actualización, es decir, T ₁ se compromete.

            Ejemplo: Considere el siguiente cronograma que involucra dos transacciones T ₁ y T ₂ .

            T 1	T 2
            REAL ACADEMIA DE BELLAS ARTES)
            WASHINGTON)
            REAL ACADEMIA DE BELLAS ARTES)
            WASHINGTON)
            abortar
            abortar

            Es un programa recuperable pero no evita los abortos en cascada. Se puede ver que si T ₁ aborta, T ₂ también tendrá que abortar para mantener la corrección del programa ya que T ₂ ya ha leído el valor no comprometido escrito por T ₁ .

         3. Cronograma estricto:
            un cronograma es estricto si para dos transacciones _Ti , _Tj , si una operación de escritura de _Ti precede a una operación conflictiva de _Tj (ya sea lectura o escritura), entonces el evento de compromiso o cancelación de _Ti también precede esa operación conflictiva de T _j .
            En otras palabras, _Tj puede leer o escribir el valor actualizado o escrito de _Ti solo después de _{que Ti} se compromete/aborta.

            Ejemplo: Considere el siguiente cronograma que involucra dos transacciones T ₁ y T ₂ .

            T 1	T 2
            REAL ACADEMIA DE BELLAS ARTES)
            REAL ACADEMIA DE BELLAS ARTES)
            WASHINGTON)
            comprometerse
            WASHINGTON)
            REAL ACADEMIA DE BELLAS ARTES)
            comprometerse

            Este es un programa estricto ya que T ₂ lee y escribe A que está escrito por T ₁ solo después de la confirmación de T ₁ .

   3. Cronograma no recuperable:
      Ejemplo: Considere el siguiente cronograma que involucra dos transacciones T ₁ y T ₂ .
      

      T 1	T 2
      REAL ACADEMIA DE BELLAS ARTES)
      WASHINGTON)
      WASHINGTON)
      REAL ACADEMIA DE BELLAS ARTES)
      comprometerse
      abortar

      T ₂ lee el valor de A escrito por T ₁ y comprometido. T ₁ luego abortó, por lo tanto, el valor leído por T ₂ es incorrecto, pero dado que T ₂ se comprometió, este programa no es recuperable .

Nota – Se puede ver que:

1. Los programas sin cascada son más estrictos que los programas recuperables o son un subconjunto de los programas recuperables.
2. Los horarios estrictos son más estrictos que los horarios sin cascada o son un subconjunto de los horarios sin cascada.
3. Los programas en serie satisfacen las restricciones de todos los programas recuperables, sin cascada y estrictos y, por lo tanto, son un subconjunto de los programas estrictos.

La relación entre varios tipos de horarios se puede representar como:

Ejemplo: Considere el siguiente horario:

S:R1(A), W2(A), Commit2, W1(A), W3(A), Commit3, Commit1 

¿Cual de los siguientes es verdadero?
(A) El cronograma es un cronograma serializable de vista y un cronograma recuperable estricto
(B) El cronograma es un cronograma no serializable y un cronograma recuperable estricto
(C) El cronograma es un cronograma no serializable y no es un cronograma recuperable estricto.
(D) El Cronograma es un cronograma serializable y no es un cronograma recuperable estricto

Solución: El horario se puede reescribir como:-

T 1	T 2	T 3
REAL ACADEMIA DE BELLAS ARTES)
WASHINGTON)
Comprometerse
WASHINGTON)
WASHINGTON)
Comprometerse
Comprometerse

En primer lugar, es una programación serializable de vista, ya que tiene una programación serial igual a la vista T ₁ —> T ₂ —> T ₃ que satisface las lecturas iniciales y actualizadas y la escritura final en la variable A que se requiere para la serialización de la vista. Ahora podemos ver que hay un par de escritura – escritura realizado por las transacciones T ₁ seguidas por T ₃ que viola la condición mencionada anteriormente de horarios estrictos, ya que se supone que T ₃ debe realizar la operación de escritura solo después de que T ₁ se compromete, lo cual se viola en el dado calendario. Por lo tanto, el cronograma dado es serializable pero no estrictamente recuperable.
Entonces, la opción (D) es correcta.