Polígrafo para verificar Ver Serializabilidad en DBMS – Part 1

Requisito previo: control de concurrencia : introducción , capacidad de serialización de conflictos , niveles de aislamiento de transacciones en la capacidad de serialización de DBMS  : si cualquier transacción (no en serie) produce un resultado que es igual al resultado de la transacción de ese programa ejecutada en serie, entonces podemos llamar a ese programa de transacciones un programa serializable . 

Tenga en cuenta que el objetivo principal de la serialización es encontrar programaciones no seriales que permitan que las transacciones se ejecuten simultáneamente sin interferencias y produzcan un estado de base de datos que podría generarse mediante una ejecución en serie. Estos son los siguientes tipos de horarios: 

1. horario de serie
2. Serialización de conflictos
3. Ver Serializabilidad
4. Horario no serial

Ver serializabilidad: 
una programación se llama Ver serializable , si es una vista equivalente a una programación en serie (no se permiten transacciones superpuestas). Estas son las siguientes condiciones para ser una Serializabilidad de Vista: 

1. En ambos programas, la lectura del valor inicial del elemento de datos y la escritura del valor final del elemento de datos por transacción deben ser iguales.
2. El conflicto W->R debe ser el mismo en ambos horarios.

Ahora, consideremos los siguientes ejemplos. 

Ejemplo: supongamos que hay dos horarios, uno no es en serie y el otro es en serie. 
 

    Schedule 1              Schedule 2      
  --------------          ---------------
   T1      T2               T1      T2
  --------------          ---------------
  r1(A)                    r1(A)
  A=A+10                   A=A+10
  w1(A)                    w1(A)
  r1(B)                            r2(A)
  B=B*10                           A=A+10
  w1(B)                            w2(a)
          r2(A)            r1(B)                            
          A=A+10           B=B*10      
          w2(A)            w2(B)      
          r2(B)                    r2(B)
          B=B*10                   B=B*10
          w2(B)                    w2(B)  

Comprobando la vista serializable o no: 
 

    Comparison Table
---------------------------
Schedule 1    Schedule 2
---------------------------
A   T1 T2         T1 T2
B   T1 T2         T1 T2 

Entonces, el Programa 2 es una vista equivalente al Programa 1. 

Usar el polígrafo cuando el número de transacciones es mayor a 2: 
Supongamos que tenemos 3 transacciones T1, T2 y T3. Las posibles combinaciones de esas transacciones son: 

--------------
 T1   T2   T3
 T1   T3   T2
 T2   T1   T3
 T2   T3   T1
 T3   T1   T2
 T3   T2   T1
-------------- 

1. Un Tn lee un dato inicial en un horario el mismo Tn también debe leer el dato inicial en una de las combinaciones de transacciones. Eso significa que T1 debería ocurrir antes que T2, por lo que debemos eliminar estas combinaciones: 
 

--------------
 T2   T1   T3
 T2   T3   T1
 T3   T2   T1
-------------- 

2. Un Tn lee un dato después de que otro Tn lo haya escrito en un programa, el mismo Tn también debe leerlo después de que otro Tn lo haya escrito en una combinación de transacción. 

3. Un Tn escribe el valor final para un dato en un horario, el mismo Tn también debe escribir el dato final en una de las combinaciones de transacciones. Eso significa que T2 ocurre antes que T3, por lo que debemos eliminar estas combinaciones: 
 

--------------
 T1   T3   T2
 T3   T1   T2
 T3   T2   T1
-------------- 

Ejemplo: 
 

Schedule = w3(x),r2(x),w2(y),r1(z),w3(y),w1(y) 

  T1   T2    T3
----------------
            w(x)
     r2(x)
     w2(y)
r1(z)
           w3(y)
w1(y)
---------------- 

Aquí T3 debe ocurrir primero, aunque en realidad no importa porque nadie más escribe X, mantendremos todas las combinaciones de transacciones posibles en el primer paso. 

T1 debe ocurrir después de T3 porque T1 lee Z después de que T3 lo escribe. Así que aquí eliminamos esas tres combinaciones de transacciones donde T1 está antes que T3. 
 

Available combination:
 T2 T3 T1
 T3 T1 T2
 T3 T2 T1 

T2 debe ocurrir en último lugar porque si no T3 o T2 sobrescribirá y que T1 escribe en nuestro programa, por lo que eliminamos de la combinación disponible donde T1 no ocurre en último lugar. 
 

Available combination:
 T2 T3 T1
 T3 T2 T1 

Tenga en cuenta que usamos Polygraph cuando una escritura ciega está disponible en cualquier transacción.