$[$Question $1]$ Consider the following relational schema:

Student $($S#$,$ Sname, Dept$)$ Prof $($P#$,$ Pname, Dept, Salary$)$

Course $($C#$,$ Cname, Text$)$ St$-$Course $($S#$,$ C#$)$ Prof$-$Course $($P#$,$ C#$)$

For the following SQL query

SELECT Sname

FROM Student, Prof, St$-$Course, Prof$-$Course

WHERE $($Student$.$Dept $=$ Prof. Dept OR

$($Prof$.$Salary $>100$ AND Student.Dept $=$ Prof. Dept$))$

AND Prof. P# $=$ Prof.Course.P#

AND Prof$-$Course.C# $=$ St$-$Course.C#

AND St$-$Course.S# $=$ Student.S#

$(1-$a$)$ Write the initial query tree corresponding to the above SQL query.

$(1-$b$)$ Apply query optimization heuristics on the tree to produce the most efficient

query tree.

$(1-$c$)$ Write the Relational Algebra query corresponding to the most efficient tree.

$2$

$[$Question $2]$ Find out if the following schedules are conflict serializable or not? If

a schedule is conflict serializable, get its corresponding serial schedule: $[$Hint:

assuming all transactions are committed at the end of the schedule$]$

a$.$ R$1($x$),$ R$2($x$),$ W$1($x$),$ R$3($x$),$ W$3($x$)$

b$.$ R$1($x$),$ R$2($x$),$ W$2($x$),$ W$1($x$),$ R$3($x$)$

c$.$ R$3($x$),$ R$1($x$),$ W$3($x$),$ R$2($x$),$ W$1($x$)$

d$.$ R$3($x$),$ R$1($x$),$ R$2($x$),$ W$3($x$),$ W$1($x$)$

e$.$ R$1($x$),$ R$2($z$),$ R$3($z$),$ R$3($x$),$ R$3($y$),$ W$1($x$),$ W$3($y$),$ R$2($y$),$ W$2($z$),$ W$2($y$)$

f$.$ R$1($x$),$ R$2($z$),$ R$3($x$),$ R$1($z$),$ R$2($x$),$ R$3($y$),$ W$1($x$),$ W$2($z$),$ W$3($y$),$ W$2($y$)$

$[$Question $3]$ Consider the following three transactions:

T$1$: R$1($x$),$ R$1($z$),$ W$1($x$),$ C$1$

T$2$: R$2($z$),$ R$2($x$),$ W$2($z$),$ W$2($y$)$ C$2$

T$3$: R$3($x$),$ R$3($y$),$ W$3($y$),$ C$3$

$(3-$a$)$ Add Locks and Unlocks to each transaction such that the transaction follows

the $2$PL protocol.

$(3-$b$)$ Add Locks and Unlocks to each transaction such that the transaction follows

the Strict $2$PL protocol $($S$2$PL$).$

$(3-$c$)$ Add Locks and Unlocks to each transaction such that the transaction follows

the Rigours $2$PL protocol $($R$2$PL$).$

$(3-$d$)$ Write a possible schedule that may be produced by each locking protocol

$2$PL$,$ S$2$PL$,$ R$2$PL$.$

$(3-$e$)$ Show whether the schedule is deadlock free or not.

$3$

$[$Question $4]$ Consider the following schedule where, for clarity, we have included

all the operations that will appear in the log$,$ plus additional helpful detail.

Operation Column $2$

T$1$ STARTS

T$1$ reads item B

T$1$ writes item B with old value $11,$ new value $12$

T$2$ STARTS

T$2$ reads item B

T$2$ writes item B with old value $12,$ new value $13$

T$3$ STARTS

T$3$ reads item A

T$3$ writes item A with old value $29,$ new value $30$

T$2$ reads item A

T$2$ writes item A with old value $30,$ new value $31$

T$2$ COMMITS

T$1$ reads item D

T$1$ writes item D with old value $44,$ new value $45***$

T$3$ COMMITS

T$1$ COMMITS

$[4-$a$]$ What serial schedule is this equivalent to$?$ If none, then explain why.

$[4-$c$]$ Is this schedule consistent with two phase locking? If your answer is yes,

then in column $2,$ insert into the schedule a minimal set of additional operations

that will make the schedule no longer consistent with two phase locking. Do not

introduce any new transactions. Make sure to show exactly where your new

operations should be inserted in the original schedule. If your answer is no$,$ then

in column $2,$ remove from the schedule a minimal set of operations, so that the

revised schedule is consistent with two phase locking.

$[4-$d$]$ Consider the version of the schedule that is consistent with two phase

locking $($either the original one or your revised version, depending on your

answer to the previous part$).$ Is that version consistent with strict two phase

locking? Why or why not?

$4$

$[4-$c$]$ Now consider an undo log corresponding to the original schedule. Suppose

that a crash occurs right after the log record with asterisks next to it is written to

disk, and the recovery procedure is then run.

$($i$)$ What transactions get rolled back?

$($ii$)$ Does cascading rollback take place? Why or why not?

$($iii$)$ Which operations in the log get undone?

$($iv$)$ At the time of the crash, which of the five data write

operations are guaranteed to have taken place on disk?

$($v$)$ At the time of the crash, which of the five data write

operations are guaranteed to not have taken place on disk