Two transactions $T_1$ and $T_2$ are given as $$T_1: r_1(X)w_1(X)r_1(Y)w_1(Y)$$ $$T_2: r_2(Y)w_2(Y)r_2(Z)w_2(Z)$$ where $r_i(V)$ denotes a read operation by transaction $T_i$ on a variable $V$ and $w_i(V)$ denotes a write operation by transaction $T_i$ on a variable $V$. The total number of conflict serializable schedules that can be formed by $T_1$ and $T_2$ is ________.

Each transaction contains $4$ operations, so the total number of interleaved schedules of $T_1$ and $T_2$ is:

Conflicting operations only occur on variable $Y$:

• Operations of $T_1$ on $Y$: $r_1(Y)$ (3rd operation of $T_1$) and $w_1(Y)$ (4th operation of $T_1$).

• Operations of $T_2$ on $Y$: $r_2(Y)$ (1st operation of $T_2$) and $w_2(Y)$ (2nd operation of $T_2$).

A schedule is conflict serializable if its precedence graph has no cycle, which means either:

1. $T_1 \to T_2$: All operations of $T_1$ on $Y$ occur before any operation of $T_2$ on $Y$, i.e., $w_1(Y)$ occurs before $r_2(Y)$. Since $w_1(Y)$ is the last operation of $T_1$ and $r_2(Y)$ is the first operation of $T_2$, all $4$ operations of $T_1$ must precede all $4$ operations of $T_2$. There is only $1$ such schedule: $T_1 T_2$.

2. $T_2 \to T_1$: All operations of $T_2$ on $Y$ occur before any operation of $T_1$ on $Y$, i.e., $w_2(Y)$ occurs before $r_1(Y)$.

A schedule is not conflict serializable if and only if it produces a cycle, which happens when:

• $r_1(Y)$ appears before $w_2(Y)$, and

• $r_2(Y)$ appears before $w_1(Y)$.

Let us count the number of non-serializable schedules:

• Among the $8$ positions in the schedule, let $T_1$ occupy $4$ positions and $T_2$ occupy the other $4$.

• The non-serializable condition means $r_1(Y)$ (the 3rd op of $T_1$) appears before $w_2(Y)$ (the 2nd op of $T_2$), while $r_2(Y)$ (1st op of $T_2$) appears before $w_1(Y)$ (4th op of $T_1$).

• Counting the combinations of positions where this holds yields exactly $16$ non-serializable schedules.

Thus, the total number of conflict serializable schedules is: