Bases de Datos
Práctico 8: Buenas Prácticas para la Serializabilidad

G. Saiz - N. Wolovick

1. Sean las transacciones
   
   $$T_{1}: r_{1}[x]w_{1}[x]c_{1} \hspace{.5in} T_{2}: w_{2}[x]r_... ... T_{3}: r_{3}[y]r_{3}[z]w_{3}[y]r_{3}[x]w_{3}[z]w_{3}[x]c_{3}$$
   
   
   Dar planificaciones $\ensuremath{\mathit{2PL}}$ no necesariamente estrictas, mostrando locks y unlocks, para lograr:
   1. Una planificación SR.
   2. Un deadlock.

2. Vimos como a través de las propiedades $P_{1}, P_{2}, P_{3}$ se caracterizaban las transacciones e historias $\ensuremath{\mathit{2PL}}$. Una transacción se dice bien formada cuando cumple con $P_{1}$, y es dos fases si cumple con $P_{3}$, mientras que una historia que cumple con $P_{2}$ se dice que respeta locks.
   1. Dar una transacción bien formada pero no en dos fases y otra que no esté bien formada, pero si sea de dos fases.
   2. Demuestre que si $H$ no está bien formada o no es dos fases, entonces es posible escribir una transacción bien formada y en dos fases que produzca una planificación no serializable. Siempre supondremos que se cumple con la propiedad $P_{2}$.

3. Para las dos transacciones que se muestran a continuación¹:
   
   $$T_{1}=r_{1}[x]w_{1}[x]r_{1}[y]w_{1}[y] \hspace{.5in} T_{2}=r_{2}[y]w_{2}[y]r_{2}[x]w_{2}[x]$$
   
   
   ¿Cuántos historias $\ensuremath{\mathit{2PL}}$ totalmente ordenadas hay?

4. Demuestre $\ensuremath{\mathit{2PL}}\subsetneq CSR$

5. En tipos de lock $\{r,w,ir,iw,riw\}$ del $\ensuremath{\mathit{MGL}}$ se dice que $q$ ``es más fuerte que'' $p$ cuando:
   
   $$p \ll q \equiv (\forall o \cdot \ensuremath{\mathit{conflict}}(o,q) \Rightarrow \ensuremath{\mathit{conflict}}(o,p))$$
   
   
   La relación $\ll$ define un orden parcial entre los tipos de locks. Obtenga el reticulado asociado a $\ll$ y la tabla de conversión de locks de doble entrada, donde cada celda es el valor de la función $sup(p,q) = p \vee q$.

6. Dado el protocolo $\ensuremath{\mathit{MGL}}$ para grafos de instancia que son árboles, suponga que ahora se permite a una transacción liberar un lock sobre un item de datos $x$ antes de liberar un lock sobre un hijo de $x$. Asumiendo que el planificador es $\ensuremath{\mathit{2PL}}$, obtenga una ejecución incorrecta que pueda surgir a partir de esta modificación.

7. Sea $S \subseteq P$ un subconjunto de procesos y $\rightarrow$ la relación espera-a, entonces decimos que $S$ está en deadlock cuando $(\forall x \cdot x \in S \cdot (\exists y \cdot y \in S \wedge x \neq y \cdot x \rightarrow y))$. Bajo esta definición, demostrar que $\{T_{1}, \ldots, T_{n}\}$ está en deadlock sii $\ensuremath{\mathit{WFG}}$ contiene un ciclo.

8. Demostrar que en D2PL un deadlock fantasma sólo puede ocurrir debido a abortos espontáneos².

9. En el esquema de prevención de deadlocks para $\ensuremath{\mathit{D2PL}}$ cambiamos la definición de Wait-Die a:
   if $ts(T_{i})>ts(T_{j})$ then $T_{i}$ espera else $T_{i}$ aborta
   ¿Este método sufre de deadlock? ¿Y de livelock? Respalde su respuesta con pruebas o contraejemplos.

10. Para la historia
    
    $$H : r_{2}[x]r_{3}[x]w_{2}[y]w_{3}[x]r_{1}[y]r_{4}[y]r_{1}[x]w_{1}[z]w_{4}[x]$$
    
    
    decidir cuando y cuales de las cuatro transacciones aborta (si es que alguna lo hace) teniendo en cuenta que el planificador es $\ensuremath{\mathit{TO}}$ y las estampillas de tiempo son:
    1. $ts(T_{1})=300, ts(T_{2})=310, ts(T_{3})=320, ts(T_{4})=330$
    2. $ts(T_{1})=250, ts(T_{2})=200, ts(T_{3})=210, ts(T_{4})=275$
    Indique en cada caso el valor final del arrgelo maxSch para todos los items de datos y operaciones.

11. Demuestre que y son incomparables ( $\ensuremath{\mathit{TO}}\nsubseteq \ensuremath{\mathit{2PL}}\wedge \ensuremath{\mathit{2PL}}\nsubseteq \ensuremath{\mathit{TO}}$). Para esto encuentre historias $H_{1}$ y $H_{2}$ tales que $H_{1} \in \ensuremath{\mathit{TO}}\wedge H_{1} \notin \ensuremath{\mathit{2PL}}$ y $H_{2} \in \ensuremath{\mathit{2PL}}\wedge H_{2} \notin \ensuremath{\mathit{TO}}$.

12. Demuestre que $\ensuremath{\mathit{TO}}$ es una propiedad $\ensuremath{\mathit{pcc}}$.

13. Para la planificación H:

    $T_{1}$	$T_{2}$	$T_{3}$
    read(A)
    	write(A)
    write(A)
    		write(A)

    decidir si $H \in \ensuremath{\mathit{2PL}}$, $H \in \ensuremath{\mathit{TO}}$, $H \in \ensuremath{\mathit{TO\!+\!TWR}}$

14. Proponga una modificación en el algoritmo del planificador $\ensuremath{\mathit{TO}}$ básico para lograr que las historias resultantes sean $\ensuremath{\mathit{ACA}}$.

15. ³Caracterización de las historias $\ensuremath{\mathit{2PL}}$ y $\ensuremath{\mathit{TO}}$ respecto a sus equivalentes seriales.
    1. En una historia $\ensuremath{\mathit{2PL}}$, se define el punto de lock de $T_{i}$ cuando se han tomado todos los locks y no se ha soltado ninguno. Demuestre que si $H \in \ensuremath{\mathit{2PL}}$ entonces $H \equiv_{C} H_{S}$ donde el orden de $H_{S}$ es el de los locked points.

    2. Demuestre que $H \in \ensuremath{\mathit{TO}}\Rightarrow H\equiv_{C}H_{S}$ donde el orden de $H_{S}$ está dado por $ts(T_{i})$.

16. ⁴Sea $T_{1} \rightarrow \ldots \rightarrow T_{n} \rightarrow T_{1}$ un ciclo en un $\ensuremath{\mathit{WFG}}$. Una arista $T_{i} \rightarrow T_{j}$ es una cuerda de un ciclo si $T_{i},T_{j}$ están en el ciclo pero $T_{i} \rightarrow T_{j}$ no es arista del ciclo. Un ciclo es elemental si no tiene cuerdas.

    Suponga que usamos un detector de deadlocks que encuentra todos los ciclos elementales del $\ensuremath{\mathit{WFG}}$ y rompe cada uno de esos deadlocks parciales abortando una víctima en el ciclo. Demuestre que esto rompe todos los ciclos del $\ensuremath{\mathit{WFG}}$.