3
$\begingroup$

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 _______________

I have tried finding the total number of schedules – nonconflict serializable schedules, but I think there is a higher possibility in committing mistakes in the exam for that method. Please suggest a better way to solve this.

$\endgroup$
  • $\begingroup$ Is the answer $16$? $\endgroup$ – Mr. Sigma. Jan 3 '18 at 14:37
  • $\begingroup$ @Tamas the answer is 54 $\endgroup$ – venkat Jan 3 '18 at 16:18
1
$\begingroup$

While checking for conflict serializable schedules, we should be sure to avoid RW, WW, WR conflicts. Also the relative order of operations internal to each transaction also needs to be maintained. For example T1's operations on $X$should come before T1's operations on $Y$. Also since $Y$ is the common datum here, therefore either all of T1's operation on $Y$ occur before T2's $Y$ operations or they may occur later, but they shouldn't be interleaved.

So let's try to see the number of such serializable schedules: Here is $T_1$:

(a) $r_1(X)$ (b) $w_1(X)$ (c) $r_1(Y)$ (d) $w_1(Y)$ (e)

Since $Y$ is the common datum so I pick it first from $T_2$. put $w_2(Y)$ at position (a)

(a1) $w_2(Y)$ (a2) $r_1(X)$ (b) $w_1(X)$ (c) $r_1(Y)$ (d) $w_1(Y)$ (e)

We now have two new positions (a1) and (a2). Now, see that $r_2(Y)$ can come only at (a1) since it cannot come after $w_2(Y)$. Now The $Z$ operations of $T_2$ remain. See that they can come at any of the 5 postions starting from (a2) till (e). So for this case, we get total schedules as

$1 *( \binom{5}{1} + \binom{5}{2}) = 15$

$\binom{5}{1}$ is the case when both $r_2(Z)$ and $w_2(Z)$ come together. $\binom{5}{2}$ is the case when they are separated. Note that $r_2(Z)$ and $w_2(Z)$ have not been permuted to maintain their relative order. Similarly, you can move $w_2(Y)$ through positions (b) (c) and (e) (note that (d) is an excluded possibility since interleaving is not allowed) to get $20, 18, 1$ as the answer respectively for each individual case. They sum up to $54$.

In case you need the explanation for all cases, you can look up here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.