Question 44

The two transactions are:

• $T_1: a_1 = r_1(X), a_2 = w_1(X), a_3 = r_1(Y), a_4 = w_1(Y)$
• $T_2: b_1 = r_2(Y), b_2 = w_2(Y), b_3 = r_2(Z), b_4 = w_2(Z)$

Total number of operations $= 4 + 4 = 8$.
The total number of interleavings preserving the internal order of $T_1$ and $T_2$ is:

Variable $X$ is accessed only by $T_1$, and variable $Z$ is accessed only by $T_2$. The only shared variable is $Y$.

Conflicts on variable $Y$:

• $r_1(Y)$ conflicts with $w_2(Y)$
• $w_1(Y)$ conflicts with $r_2(Y)$
• $w_1(Y)$ conflicts with $w_2(Y)$

For a schedule to be conflict serializable, the serialization graph cannot contain a cycle. The possible serial orders are:

1. Equivalent to $T_1 \to T_2$:
   All conflicting operations on $Y$ in $T_1$ must execute before all conflicting operations on $Y$ in $T_2$.
   Thus, $w_1(Y)$ must execute before $r_2(Y)$ (and before $w_2(Y)$).
   Since $T_1$ performs $a_1, a_2, a_3, a_4$ in order, and $a_4 = w_1(Y)$ occurs before $b_1 = r_2(Y)$, all 4 operations of $T_1$ must precede all 4 operations of $T_2$.
   This corresponds to the strictly serial schedule $T_1 T_2$, which yields exactly 1 schedule.
2. Equivalent to $T_2 \to T_1$:
   All conflicting operations on $Y$ in $T_2$ must execute before all conflicting operations on $Y$ in $T_1$.
   Thus, $w_2(Y)$ ($b_2$) must execute before $r_1(Y)$ ($a_3$).
   The positions of operations in the 8-slot schedule satisfy $b_2 < a_3$.
   Let us count the number of schedules where $b_2 < a_3$:
   The total number of schedules is 70. Subtracting the schedules where $b_2 > a_3$ or where cycles are formed gives exactly 53 schedules.

Total number of conflict serializable schedules is: