Como se explica en Control de simultaneidad , las programaciones en serie tienen una menor utilización de recursos y un bajo rendimiento. Para mejorarlo, dos o más transacciones se ejecutan simultáneamente. Pero la concurrencia de transacciones puede generar inconsistencias en la base de datos. Para evitar esto, debemos verificar si estos horarios concurrentes son serializables o no.
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.
Operaciones conflictivas: Se dice que dos operaciones son conflictivas si todas las condiciones satisfacen:
- Pertenecen a diferentes transacciones.
- Operan en el mismo elemento de datos.
- Al menos uno de ellos es una operación de escritura.
Ejemplo: –
- Par de operaciones en conflicto (R 1 (A), W 2 (A)) porque pertenecen a dos transacciones diferentes en el mismo elemento de datos A y una de ellas es la operación de escritura.
- Del mismo modo, los pares (W 1 (A), W 2 (A)) y (W 1 (A), R 2 (A)) también están en conflicto .
- Por otro lado, el par (R 1 (A), W 2 (B)) no está en conflicto porque operan en elementos de datos diferentes.
- De manera similar, el par ((W 1 (A), W 2 (B)) no está en conflicto.
Considere el siguiente horario:
S1: R1(A), W1(A), R2(A), W2(A), R1(B), W1(B), R2(B), W2(B)
Si O i y O j son dos operaciones en una transacción y O i < O j (O i se ejecuta antes que O j ), también seguirá el mismo orden en el cronograma. Usando esta propiedad, podemos obtener dos transacciones del programa S1 como:
T1: R1(A), W1(A), R1(B), W1(B) T2: R2(A), W2(A), R2(B), W2(B)
-> Intercambiando la operación no conflictiva s R 2 (A) y R 1 (B) en S1, el programa se convierte en,
S11: R1(A), W1(A), R1(B), W2(A), R2(A), W1(B), R2(B), W2(B)
-> De manera similar, intercambiando operaciones no conflictivas W 2 (A) y W 1 (B) en S11, el programa se convierte en,
S12: R1(A), W1(A), R1(B), W1(B), R2(A), W2(A), R2(B), W2(B)
S12 es un horario en serie en el que todas las operaciones de T1 se realizan antes de iniciar cualquier operación de T2. Dado que S se ha transformado en un programa de serie S12 mediante el intercambio de operaciones no conflictivas de S1, S1 es un conflicto serializable.
Tomemos otro Horario:
S2: R2(A), W2(A), R1(A), W1(A), R1(B), W1(B), R2(B), W2(B)
Dos transacciones serán:
T1: R1(A), W1(A), R1(B), W1(B) T2: R2(A), W2(A), R2(B), W2(B)
El horario original es:
S2: R2(A), W2(A), R1(A), W1(A), R1(B), W1(B), R2(B), W2(B)
Intercambiando operaciones no conflictivas R 1 (A) y R 2 (B) en S2, el programa se convierte en,
S21: R2(A), W2(A), R2(B), W1(A), R1(B), W1(B), R1(A), W2(B)
De manera similar, intercambiando operaciones no conflictivas W 1 (A) y W 2 (B) en S21, el programa se convierte en,
S22: R2(A), W2(A), R2(B), W2(B), R1(B), W1(B), R1(A), W1(A)
En el programa S22, todas las operaciones de T2 se realizan primero, pero las operaciones de T1 no están en orden (el orden debe ser R 1 (A), W 1 (A), R 1 (B), W 1 (B)). Entonces S2 no es un conflicto serializable.
Equivalente en conflicto: se dice que dos horarios son equivalentes en conflicto cuando uno se puede transformar en otro intercambiando operaciones que no están en conflicto. En el ejemplo discutido anteriormente, S11 es un conflicto equivalente a S1 (S1 se puede convertir a S11 intercambiando operaciones que no están en conflicto). De manera similar, S11 es un conflicto equivalente a S12 y así sucesivamente.
Nota 1: aunque S2 no es un conflicto serializable, sigue siendo un conflicto equivalente a S21 y S21 porque S2 se puede convertir en S21 y S22 intercambiando operaciones que no están en conflicto.
Nota 2: El horario que es serializable en conflicto siempre es equivalente en conflicto a uno de los horarios en serie. El cronograma S1 discutido anteriormente (que es un conflicto serializable) es equivalente al cronograma en serie (T1->T2).
Pregunta: Considere los siguientes programas que involucran dos transacciones. ¿Cuál de las siguientes afirmaciones es verdadera?
S1: R 1 (X) R 1 (Y) R 2 (X) R 2 (Y) W 2 (Y) W 1 (X)
S2: R 1 (X) R 2 (X) R 2 (Y) W 2 (Y) R 1 (Y) W 1 (X)
- Tanto S1 como S2 son serializables en conflicto
- Solo S1 es serializable en conflicto
- Solo S2 es serializable en conflicto
- Ninguna
[Puerta 2007]
Solución: Dos transacciones de calendarios dados son:
T1: R1(X) R1(Y) W1(X) T2: R2(X) R2(Y) W2(Y)
Primero verifiquemos la serialización de S1:
S1: R1(X) R1(Y) R2(X) R2(Y) W2(Y) W1(X)
Para convertirlo en un horario en serie, tenemos que intercambiar operaciones que no entren en conflicto para que S1 sea equivalente al horario en serie T1->T2 o T2->T1. En este caso, para convertirlo a un horario en serie, debemos intercambiar R 2 (X) y W 1 (X) pero están en conflicto. Por lo tanto, S1 no se puede convertir en un horario en serie.
Ahora, verifiquemos la serialización de S2:
S2: R1(X) R2(X) R2(Y) W2(Y) R1(Y) W1(X)
Intercambiando operaciones no conflictivas R 1 (X) y R 2 (X) de S2, obtenemos
S2’: R2(X) R1(X) R2(Y) W2(Y) R1(Y) W1(X)
Nuevamente, intercambiando operaciones no conflictivas R 1 (X) y R 2 (Y) de S2′, obtenemos
S2’’: R2(X) R2(Y) R1(X) W2(Y) R1(Y) W1(X)
Nuevamente, intercambiando operaciones no conflictivas R 1 (X) y W 2 (Y) de S2», obtenemos
S2’’’: R2(X) R2(Y) W2(Y) R1(X) R1(Y) W1(X)
que es equivalente a un horario serial T2->T1.
Entonces, la opción correcta es C . Solo S2 es serializable en conflicto.
Artículo relacionado:
Ver
gráfico de precedencia de serializabilidad para probar la serializabilidad de conflictos
Artículo aportado por Sonal Tuteja. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA