search
Log In
19 votes
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.

in Databases 2.9k views
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.

6 Answers

25 votes
 
Best answer

For $S1$ : it is not conflict serializable 

for $S2$ : it is conflict serializable

Answer is option C.


edited by
8 votes
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. 

4 votes
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
–5 votes
OPTION IS A
–5 votes
OPTION IS B IS APPROPIATE ONE
Answer:

Related questions

62 votes
11 answers
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
asked Oct 4, 2014 in Databases Aravind 7.2k views
32 votes
6 answers
2
11k views
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$
asked Sep 22, 2014 in Databases Kathleen 11k views
47 votes
5 answers
3
7.3k views
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
asked Sep 22, 2014 in Databases Kathleen 7.3k views
49 votes
4 answers
4
9k views
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
asked Sep 22, 2014 in Databases Kathleen 9k views
...