Bases de Datos
Práctico 7: Teoría de la Serializabilidad

G. Saiz - N. Wolovick

  1. Demuestre que todo grafo dirigido que representa el orden parcial de una historia resulta acíclico ( $\ensuremath{\mathit{DAG}}$).

  2. Para los grafos de serialización $SG(H)$ demostrar o dar un contraejemplo de la siguiente propiedad:
    ``si existe un par de aristas $T_{i} \rightarrow T_{j}, T_{j} \rightarrow T_{k}$ entonces existe la arista $T_{i} \rightarrow T_{k}$''.

  3. Probar que si dos historias son equivalentes entonces sus grafos de serialización son idénticos.
    ¿Resulta válida la conversa?

  4. Demostrar que $\ensuremath{\mathit{ST}}\subset \ensuremath{\mathit{ACA}}\subset \ensuremath{\mathit{RC}}$ a través de los siguientes pasos:
    1. $H \in \ensuremath{\mathit{ST}}\Rightarrow H \in \ensuremath{\mathit{ACA}}$
    2. $H \in \ensuremath{\mathit{ACA}}\Rightarrow H \in \ensuremath{\mathit{RC}}$
    3. $(\exists H_{1} \cdot H_{1} \notin \ensuremath{\mathit{ST}}\wedge H_{1} \in \ensuremath{\mathit{ACA}})$
    4. $(\exists H_{2} \cdot H_{2} \notin \ensuremath{\mathit{ACA}}\wedge H_{2} \in \ensuremath{\mathit{RC}})$

  5. Demostrar que las propiedades $\ensuremath{\mathit{ST}}, \ensuremath{\mathit{ACA}}, \ensuremath{\mathit{RC}}$ son cerradas bajo prefijo finalizado (pcc).

  6. Decidir la equivalencia entre estas dos historias.

    \begin{displaymath}
H_{1} = \vcenter{\xymatrix @C-1.5pc @R-2pc {
& & *+{w_{1}[...
...r] \\
& *+{w_{2}[x]}\ar[uur]\ar[rrrr] & & & & *+{c_{2}}
}}
\end{displaymath}

  7. Para las siguientes transacciones, definir una historia $\ensuremath{\mathit{CSR}}$ no serial. Mostrar la(s) historia(s) serial(es) equivalentes.

    \begin{displaymath}T_{1} = \vcenter{\xymatrix @-1.7pc {
*+{w_{1}[x]}\ar[dr] & &...
...1pc {*+{inc_{2}[y]}\ar[r] & *+{dec_{2}[x]}\ar[r] & *+{c_{2}}}
\end{displaymath}


    \begin{displaymath}
T_{3} = \xymatrix @-1pc {*+{r_{3}[x]}\ar[r] & *+{inc_{3}[y]...
...r[r] & *+{w_{4}[x]}\ar[r] & *+{dec_{4}[y]}\ar[r] & *+{c_{4}}}
\end{displaymath}

  8. 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:
    $T_{1}$ $T_{2}$
    read(A)
    write(C)
    read(B)
    read(A)
    write(B)
    write(A)
    write(A)
     
    $T_{1}$ $T_{2}$ $T_{3}$
    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 $\ensuremath{\mathit{CSR}}$ y $\ensuremath{\mathit{VSR}}$.

  9. Para las dos transacciones que se muestran a continuación1:

    \begin{displaymath}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]
\end{displaymath}

    1. ¿Cuántas historias completas totalmente ordenadas hay?
    2. ¿Cuántas de estas historias son serializables?

  10. Mostrar que la historia $H=r_{1}[x]w_{2}[x]w_{1}[x]c_{1}c_{2}w_{3}[x]c_{3}$ cumple $H \in \ensuremath{\mathit{VSR}}$ y $H \notin \ensuremath{\mathit{CSR}}$.

  11. 2 Un write ciego es un Write sobre algún item de datos $x$ realizado por una transacción que previamente no leyó $x$. 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 $r_{i}[x],w_{i}[x] \in T_{i}$ entonces $r_{i}[x]<_{i}w_{i}[x] \vee
w_{i}[x]<_{i}r_{i}[x]$
    por la más fuerte:
    (4') Si $w_{i}[x] \in T_{i}$ entonces $r_{i}[x] \in T_{i} \wedge r_{i}[x]<_{i}w_{i}[x]$

    Demuestre que bajo esta definición de transacción, una historia es serializable en vistas sii es serializable en conflictos.

  12. 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 $H_{1}, \ldots, H_{12}$.

    \includegraphics[keepaspectratio=true, height=70mm]{p7f1.ps}



bdd@hal.famaf.unc.edu.ar