# GATE2014-1-29

5k views

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by $r(x)$ and $w(x)$ respectively. Which one of them is conflict serializable?

1. $r_1(x)$; $r_2(x)$; $w_1(x)$; $r_3(x)$; $w_2(x)$;
2. $r_2(x)$; $r_1(x)$; $w_2(x)$; $r_3(x)$; $w_1(x)$;
3. $r_3(x)$; $r_2(x)$; $r_1(x)$; $w_2(x)$; $w_1(x)$;
4. $r_2(x)$; $w_2(x)$; $r_3(x)$; $r_1(x)$; $w_1(x)$;

(D)  make precedence graph for all the options, for option (D) only graph will be acyclic, hence (D) is CSS.

edited by
0
Is R - W a conflict ??
0
yup. only R -R is not conflict.
0
R=-W is conflict only when one more read is performed . It is called unrepeatable read. Is it NOt ?
0
Here there is No unrepeatable read in any of the 4 options . Then How can one get cycles in all the graphs . Could some one explain it in a nice manner .
6

take node for evry transaction

procedure is simple scan left to right for

take first element => scan from 2nd elemnt to right for every r-w . w-w or w-r  conflict in diffrent transaction thier is a edge

take 2nd element => scan from 3rd elemnt to right for every r-w . w-w or w-r  conflict in diffrent transaction thier is a edge

do like this skip left side one elemnt evry time.

if u found cycle then not css otherwise css.

0
@ Arjun Sir,

I wrote D which was given wrong saying correct ans is 4 (GO Full length test). Can you please tell me what to write if similar situation arises in gate exam.
0
@amolagrawal same happened with mebut don't worry this will not happen in gate.
In option D, there is no interleaving of operations. The option D has first all operations of transaction 2, then 3 and finally 1 There can not be any conflict as it is a serial schedule with sequence 2 --> 3 -- > 1
0
when we make precedence graph  for option C ,D  only graph will be acyclic, then why option C is not correct ?
0
In option C there is a conflict in r1(x) -> w2(x) and w2(x) -> w1(x) which makes cycle!
3
only  option D is correct as there is no cycle in precedence graph, but in C there is cycle as there are  conflicts in r1(x) -> w2(x) and w2(x) -> w1(x) which makes cycle!
–1 vote

## Related questions

1
6.5k views
Given the following schema: employees(emp-id, first-name, last-name, hire-date, dept-id, salary) departments(dept-id, dept-name, manager-id, location-id) You want to display the last names and hire dates of all latest hires in their respective departments in the ... because of pairwise comparison. It generates an error because of the GROUP BY clause cannot be used with table joins in a sub-query.
Given the following two statements: S1: Every table with two single-valued attributes is in 1NF, 2NF, 3NF and BCNF. S2: $AB \to C$, $D \to E$, $E \to C$ is a minimal cover for the set of functional dependencies $AB \to C$, $D \to E$, $AB \to E$, $E \to C$. ... one of the following is CORRECT? S1 is TRUE and S2 is FALSE. Both S1 and S2 are TRUE. S1 is FALSE and S2 is TRUE. Both S1 and S2 are FALSE.
Given the following statements: S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL. S2: Given the table $R(a,b,c)$ where $a$ and $b$ together form the primary key, the following is a valid table definition. CREATE TABLE S ( a INTEGER, d ... is CORRECT? S1 is TRUE and S2 is FALSE Both S1 and S2 are TRUE S1 is FALSE and S2 is TRUE Both S1 and S2 are FALSE
Consider the relation scheme $R = (E, F, G, H, I, J, K, L, M, N)$ and the set of functional dependencies $\left\{ \{E, F \} \to \{G\}, \{F\} \to \{I, J\}, \{E, H\} \to \{K, L\}, \\ \{K\} \to \{M\}, \{L\} \to \{N\}\right\}$ on $R$. What is the key for $R$? $\{E, F\}$ $\{E, F, H\}$ $\{E, F, H, K, L\}$ $\{E\}$