GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 17

Question

Consider the following schedule
$$\textbf{Schedule}$$$$\begin{array}{|c|c|c|c|c|c|} \hline T_{1} & T_{2} & T_{3} & T_{4} \\\hline  R(x) & & & \\ & R(x) & & \\ & & R(x) & \\ & & & R(x) \\ W(y) & & & \\ & W(y) & & \\ & & W(y) & \\ & & & W(y) \\\hline \end{array}$$
If the number of view equivalent serial schedules is equal to $a,$ the value of $2^a = $ ________

Answer 1

$\text{View Equivalence:}$ Lets learn how to check whether the two schedules are view equivalent.

Two schedules $S_{1}$ and $S_{2}$ are said to be view equivalent, if they satisfy the following three conditions:

1. Initial Read: Initial read of each data item in transactions must match in both schedules. For example, if transaction $T_{1}$ reads the initial value of data item $X$ first in schedule $S_{1}$ then in schedule $S_{2}$ also $T_{1}$ should read the same value of $X.$

2. Final Write: Final write operations on each data item must match in both the schedules. For example, a data item $X$ is last written by Transaction $T_1$ in schedule $S_1$ then in $S_2$ also the last write operation on $X$ must be performed by transaction $T_{1}.$

3. Update Read: If in schedule $S_{1},$ the transaction $T_{1}$ is reading a data item updated by another transaction $T_{2}$ then in schedule $S_{2}$ also $T_{1}$ must read the value updated by $T_{2}.$ For example, if in schedule $S_{1}, T_{1}$ performs a read operation on $X$ after the write operation on $X$ by $T_{2}$ then in $S_{2}, T_{1}$ should read the $X$ last updated by $T_{2}.$

In the given schedule Read and Writes are to different data items and so requirements $1$ and $3$ are always satisfied for any schedule. For the second requirement, we need to ensure that transaction $T_4$ is the last one in any view equivalent schedule. The remaining 3 transactions can occur in $3!=6$ order giving $6$ view equivalent schedules.

• $T_{1}\; T_{2}\; T_{3}\; T_{4}$
• $T_{2}\; T_{1}\; T_{3}\; T_{4}$
• $T_{1}\; T_{3}\; T_{2}\; T_{4}$
• $T_{2}\; T_{3}\; T_{1}\; T_{4}$
• $T_{3\;} T_{1}\; T_{2}\; T_{4}$
• $T_{3}\; T_{2}\; T_{1}\; T_{4}$

$\therefore a = 6$

So, $2^6=64.$

If we are asked just view serializable schedules (not necessarily serial, meaning operations among the transactions can interleave) we’ll get $\dfrac{7!}{2!2!2!} = 630.$

Reference: https://beginnersbook.com/2018/12/dbms-view-serializability/

Comments

Sir , please look into my doubt.

---

Initial read – is for value read : “

“should read the same value of X.”

---

Thank you, sir.

Now I know there is a difference between reading the initial value vs being the first to read a value.