# GATE2007-64

2.9k views

Consider the following schedules involving two transactions. Which one of the following statements is TRUE?

• $S_1 :r_1(X); r_1(Y); r_2(X); r_2(Y); w_2(Y); w_1(X)$
• $S_2 :r_1(X); r_2(X); r_2(Y); w_2(Y); r_1(Y); w_1(X)$
1. Both $S_1$ and $S_2$ are conflict serializable.

2. $S_1$ is conflict serializable and $S_2$ is not conflict serializable.

3. $S_1$ is not conflict serializable and $S_2$ is conflict serializable.

4. Both $S_1$ and $S_2$ are not conflict serializable.

1
Also S1: not a view serializable as no blind write present
0
How to check? (to minimize chances of silly error during exams)

1st instruction is read on X from T1, so look for W. We get w2(Y), see if it for same variable and then if its from different transaction. Here its not so ignore and move ahead. w1(X), same transaction so ignore.

2nd instruction is read on Y from T2, so look for W. We get w2(Y), see if it for same variable and then if its from different transaction. Here it is both, so draw a directed edge from T1 -> T2. As there are only 2 transaction and we already have an edge from T1->T2, so no need to check for subsequent instructions.

3rd instruction is read on X from T2, so look for W. We get w2(Y), see if it for same variable and then if its from different transaction. Here it is both, so draw a directed edge from T2 -> T1.

As there is a cycle so its not CS.

For $S1$ : it is not conflict serializable

for $S2$ : it is conflict serializable

edited
You can make a Precedence graph for the two schedules.And check for the conflicts pairs making a Cycle.

S1 makes a cycle. T1-->T2 and T2-->T1. And hence is not Conflict Serializable.

S2 does not makes cycle and has transition from T2-->T1 only. And hence is Conflict Serializable.

Conflict Pairs: RW, WR, WW.
0

These WR RW WW are adjacent in the transactions T1 and T2 or any where (in cross or different) in the transaction. please mention.

Ans - Option C

In S1: RW conflict from 1-2 and 2-1 so It is not C.S.

In S2: RW conflict AND WR conflict from 2-1 only so it is C.S.
1 vote
As per the precedence graph there is a cycle in schedule S1 T1--->T2 and T2---->T1
so that's why it is not conflict serializable.

Schedule S1
T1            T2
---------------------
r1(X)
r1(Y)
r2(X)
r2(Y)
w2(Y)
w1(X)

Schedule S2
T1            T2
---------------------
r1(X)
r2(X)
r2(Y)
w2(Y)
r1(Y)
w1(X)
In precedence graph for S2 there is only one edge that is T2--->T1(no cycle) so S2 is conflict serializable

OPTION IS A
OPTION IS B IS APPROPIATE ONE

## Related questions

1
7.2k views
Information about a collection of students is given by the relation $\text{studInfo(}\underline{\text{studId}},\text{ name, sex)}$. The relation $\text{enroll(}{\text{studId}},{\text{ courseId}})$ gives which student has enrolled for (or taken) what ... enrolled. Courses in which a proper subset of female students are enrolled. Courses in which only male students are enrolled. None of the above
The order of a leaf node in a B$^+$ - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is $1K$ $bytes$, data record pointer is $7$ $bytes$ long, the value field is $9$ $bytes$ long and a block pointer is $6$ $bytes$ long, what is the order of the leaf node? $63$ $64$ $67$ $68$
Which one of the following statements is $\text{FALSE}$? Any relation with two attributes is in $\text{BCNF}$ A relation in which every key has only one attribute is in $2NF$ A prime attribute can be transitively dependent on a key in a $3NF$ relation A prime attribute can be transitively dependent on a key in a $\text{BCNF}$ relation
Consider the table employee(empId, name, department, salary) and the two queries $Q_1, \, Q_2$ below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements ... $Q_2$ is the correct query Both $Q_1$ and $Q_2$ produce the same answer Neither $Q_1$ nor $Q_2$ is the correct query