$3.$ Transaction Processing

Consider schedules S$1$ and S$2$ below.

S$1$: r$2($X$),$ r$2($Z$),$ r$3($Y$),$ w$2($X$),$ w$2($Z$),$ w$3($Y$),$ r$1($Z$),$ r$3($X$),$ w$3($X$),$ r$1($X$),$ r$3($Z$),$ w$1($X$),$ w$3($Z$),$ w$1($Z$)$

S$2$: r$1($X$),$ r$1($Z$),$ r$2($Y$),$ w$2($Y$),$ w$1($X$),$ r$3($Y$),$ w$1($Z$),$ r$2($X$),$ r$3($X$),$ r$2($Z$),$ w$2($Z$),$ r$3($Z$),$ w$3($Y$),$ w$3($Z$)$

$($a$)$ Apply the basic timestamp ordering $($BTO$)$ algorithm to schedules S$1$ and S$2.$ Determine whether or not the algorithm allows the execution of the schedules, and discuss cascading rollback $($if any$).$

Hints: each operation takes one time unit, and timestamp of each transaction is the time associated to its first operation. For example, timestamps of transactions T$1,$ T$2,$ and T$3$ in schedule S$1$ are $7,1,$ and $3($respectively$).$

$($b$)$ Testing the serializability of S$1$ and S$2$ by serialization graph technique to prove that the successful execution of a schedule under BTO will ensure the serializability of the schedule.

$($c$)$ Examine the recoverable characteristic of S$1$ and S$2.$ What schedule $($S$1$ or S$2)$ can be executed under the strict timestamp ordering $($STO$)$ algorithm and write an equivalent strict schedule for it$?$ We assume that a transaction will be be committed or aborted right after its last operation.