Bases de Datos
Práctico 7: Teoría de la Serializabilidad
G. Saiz - N. Wolovick
Demuestre que todo grafo dirigido que representa el orden parcial de una historia
resulta acíclico (
).
Para los grafos de serialización demostrar o dar un contraejemplo de la siguiente
propiedad:
``si existe un par de aristas
entonces existe la arista
''.
Probar que si dos historias son equivalentes entonces sus grafos de serialización
son idénticos.
¿Resulta válida la conversa?
Demostrar que
a través de los siguientes pasos:
Demostrar que las propiedades
son
cerradas bajo prefijo finalizado (pcc).
Decidir la equivalencia entre estas dos historias.
Para las siguientes transacciones, definir una historia
no serial.
Mostrar la(s) historia(s) serial(es) equivalentes.
Una forma alternativa para denotar historias con órden total es mostrar como se
produce el interleaving entre las transacciones sin mezclar las operaciones
como en:
read(A)
write(C)
read(B)
read(A)
write(B)
write(A)
write(A)
read(A)
read(C)
write(C)
write(A)
write(A)
read(C)
read(A)
write(C)
write(A)
Decidir para cada una de las historias la pertenencia a las clases
y
.
Para las dos transacciones que se muestran a continuación1:
2 Un write ciego es un Write sobre algún item de datos realizado por una
transacción que previamente no leyó .
Suponga que las transacciones no tienen writes ciegos.
Formalmente esto lo definimos reemplazando la condición en la definición de
transacción:
(4) Si
entonces
por la más fuerte:
(4') Si
entonces
Demuestre que bajo esta definición de transacción, una historia es serializable en
vistas sii es serializable en conflictos.
3Este
diagrama de Venn resume las relaciones entre las clases de historias definidas.
Pruebe que toda región del diagrama es un conjunto no vacío, dando ejemplos
de historias
.