|
|
Para realizar dos o mas transacciones, no damos cuenta de que pueden existir varias formas de ejecutar esas transacciones. Si estamos hablando de que las transacciones se ejecutaran de forma serial, y tenemos dos transacciones que queremos ejecutar, T1 y T2, podemos tener en este caso 2 formas de ordenar las transacciones. Estas son: que se ejecute primero la transacción T1 y después la transacción T2, y la segunda , es primero la T2 y después la T1. Esto es en el caso serie, pero si queremos ejecutar las transacciones de forma concurrente, la situación cambia, ya que al intentar convertirla, se pueden cometer errores y el resultado puede no ser el esperado.
En base a lo anterior es necesario saber si el plan que se va a ejecutar es correcto y si se puede ver de forma serial.
T1
T2
T1
T2
read_item(X)
Read_item(X);
X:X-N;
X:=X-N;
Read_item(X)
Write_item(X);
X:X+M;
Read_item(X);
write_item(X);
X:=X+M;
Read_item(Y);
Write_item(X);
Write_item(X);
Read_item(Y)
Y:=Y+N;
Y:=Y+M;
Write_item(Y);
Write_item(Y);
Plan A
Plan B
En los planes anteriores, las transacciones no son seriales, ya que ambas intercalan operaciones de las dos transacciones..
En terminos generales, un plan es serial si por cada transacción T que participa en el plan, todas las transacciones de T se ejecutan consecutivamente en el plan, de lo contrario el plan es no serie.
Si tenemos ahora un plan que es concurrente, necesitamos saber si este es correcto, entonces, veremos si es seriable.
Un plan de P transacciones es seriable si es equivalente a algún plan en serie de las mismas n transacciones. Existen (n)! Posibles planes en serie de n transacciones y muchos más planes no serie posibles. Podemos formar dos grupos de planes, los que son equivalentes a uno o mas de los planes en serie, y que por tanto son seriables; y los que no son equivalentes a ningun plan serie, y que por tanto no son seriables.
Decir que un plan no serie es seriable, equivale a decir que es correcto.
Existen dos definiciones de equivalencia de planes: equivalencia
por conflictos y equivalencia de vistas.
EQUIVALENCIA POR CONFLICTOS
Se dice que dos planes son equivalentes por conflictos si el orden de cualesquier dos operaciones en conflicto es el mimo en ambos planes., recordando que dos operaciones de diferentes transacciones están en conflicto si tienen acceso al mismo elemento de la B.D., y si una de las operaciones es escribir_elemento. Si dos operaciones en conflicto se aplican en diferente orden en dos planes, el efecto de los planes puede ser diferente, ya sea sobre las transacciones o sobre la B.D., de modo que los planes no son equivalentes por conflictos.
Con la notación de equivalencia por conflictos, definiremos que un plan P es seriable por conflictos si es equivalente a algún plan en seria P’ . En tal caso, se pueden reordenar las operaciones de P que no están en conflicto hasta formar el plan equivalente en P’. De acuerdo a esto, los dos planes siguientes, son equivalentes. Por ejemplo, en ambos casos, la operación leer elemento X de la transacción T2 lee el valor de X que T1 escribio. Además T1, es la ultima transacción que escribe el elemento Y y T2 es la ultima transacción que escribe el elemento X en ambos planes. Entonces, como el plan A es un plan serie y el plan B es un plan equivalente a A, B es un plan seriable.
T1
T2
T1
T2
read_item(X)
Read_item(X);
X:X-N;
X:=X-N;
Write_item(X);
Write_item(X);
Read_item(Y);
Read_item(X);
Y:=Y+N;
X:=X+M;
Write_item(Y);
Write_item(X);
Read_item(X);
Read_item(Y)
X:=X+M;
Y:=Y+M;
Write_item(X);
Write_item(Y);
Plan A
Plan B
EQUIVALENCIA DE VISTAS
Otra definición menos restrictiva de la equivalencia entre planes que la equivalencia por conflictos, se denomina equivalencia por vistas. Lo que conduce a otra definición de seriabilidad llamada seriabilidad por vistas. Se dice que dos planes son equivalentes por vistas si se cumplen las siguientes tres condiciones:
1. El mismo conjunto de transacciones participa en P y en P’, y P y
P’ incluyen las mismas operaciones de estas transacciones.
2. Para cualquier operación li(X) de Ti en P, si el valor de
X que lee la operación fue escrito por una operación ej(X)
de Tj (o si es el valor original de X antes de comenzar el plan), debe
cumplirse la misma condición para el valor de X que lee la
operación li(X) de Ti en P’.
3. Si la operación ek(Y) de Tk es la última operación
que escribe el elemento Y en P, entonces ek(Y) de Tk debe ser también
la última operación que escribe Y en P’.
La equivalencia de vistas se basa en la idea de que, en tanto cada operación
de lectura de una transacción lea el resultado de la misma operación
de escritura en ambos planes, las operaciones de escritura de ambas transacciones
producirán los mismos resultados. Asi pues, se dice que las operaciones
de lectura perciben la misma vista en ambos planes. La condicion 3 garantiza
que la operación de escritura final, de cada elemento de información,
sea la misma en ambos planes, con lo que el estado de la base de datos
deberá ser el mismo al final de lo dos. Se dice que un plan P es
seriable por vistas si es equivalente por vistas a un plan en serie.