test series

Question

Consider the following orders of transactions:

T2:R(x); T3:W(x); T3:commit; T1:W(x); T1:commit; T2:R(y); T2:W(z); T2:commit; T4:R(x); T4:R(y); T4:commit.

If S is serializable, then how many conflict serial orderings of S is possible?

(A)10

(B)11

(C)8

(D)13

Comments

srestha mam

conflict serializable should be more

but conflict equivalent such a less number I think

what I know that  both  conflict equivalent and conflict  serializable are the same thing ??? 

correct me if I'm wrong

 

---

@Magma

if those are same things, why my page-2 answer not match with page-1 answer ( in the images of answer.)

 ( you already know it just recall from  https://gateoverflow.in/96108/schedules )

Moreover mam, written that statement wrongly,

actual sentence is

conflict serializable schedules ≤ conflict equivalent schedules

---

hmmm thanks Shaik Masthan

Answer 1

for clarity images https://drive.google.com/open?id=1C3NO8gDGdRzUn5JHY6bj3ptQLHEruUi4

Comments

But as you said the there's no conflict in T4

T3 ----> T4

T1----->T4

there's a conflict nah ??

Or

T4 reads after the commit of T3 and T1 that's why  there is no conflict arises ???

---

Ooh now I understood properly thank you  Shaik Masthan

---

Awesome explanation @Shaik Masthan Sir ...

Thank you....!!

---

But @Shaik

T4->T2->T1->T3 is not a valid conflict serializable schedule

---

why mam?

note that, it is serial schedules.

T4 completes, T2 completes, T1 completes and T2 completes

---

Can u check this?

https://gateoverflow.in/118640/gate2017-2-44

---

Commit or not T4 cannot go first

It always need to be appear last

---

and plz draw polygraph

---

Can u check this?

https://gateoverflow.in/118640/gate2017-2-44

i checked.... i am also getting 52 only.

 

Commit or not T4 cannot go first

It always need to be appear last

it is not asked for view equal, it is asked for conflict equivalent.

 

and plz draw polygraph

poly graph for view serializable schedules, precedence graph is sufficient for conflict equivalent serial schedules.

---

@shaik, Please confirm if T4 first operation is w(x) then t4 can come only two position (first and last)?

---

if T₄ first operation is W(X), then T₂ → T₄ should be there in precedence graph.

therefore 3 ! possibles only

---

but why? T4 is starting after T2 commits.

---

@Shubhgupta

yes, you are correct, but note that you are interested in serial schedules, replacing W(X) in T4 doesn't create any problem. answer is 8 only.

T₂ → T₄ → T₁ → T₃ ====> it means after T₂ completes T₄ completes, then T₁ after that T₃, there is no problem. ( As per our schedule, T₁ and T₃ should be after T₂ )

---

but @shaik, silly question, if t2 already completes(commits) before t1 and t3 then how can this be conflict serial schedule. I mean there is no conflict between any transaction.

---

in serial schedules, there is no chance for conflicts.

But as per given schedules we have to maintain T2->T1  and T2->T3 property.

if you are saying, no need to satisfy these properties, then for any question = no.of serial schedules, is answer.

---

no, you took me wrong please correct if my understanding right or not..

In question they are asking about conflict serial ordering of s. means T2->T1 and T2->T3, we know that there is conflict between them that's why we need to perform T2 first and then T3 and T1.

in question because t4 first operation is R(x) that's why t4 can come at any 4 places because there will be no conflict.

but if t4 first operation will be w(x) then it will come only 2 position first and last.

But you are saying that T2-T4-T3-T1 is also possible. If this is possible then it will be a serial schedule not a conflict ordering of S. because in S T2 read operation is having conflict with t3 write and t1 write but in that sequence there is no conflict between read of t2 with write of t3 and t1.

And thanks for helping... :)

---

let go with you...

T2 -> T3 -> T1 -> T4 is one of the schedule as per you.

then how T2 read operation is having conflict with t3 write and t1 write, in this sequence?

 

and one more thing is T1 and T3 can come in any order, why?

because of there is no conflicting btw them, right?

as in the same way T2 and T4 also can come in any way

---

T2 -> T3 -> T1 -> T4 is one of the schedule as per you.

then how T2 read operation is having conflict with t3 write and t1 write, in this sequence?

This ordering is given in question.

@Shaik, I am little bit confused here why are you taking ordering at their finish time means we generally take ordering with their conflict operation.

T2:R(x); T3:W(x); T3:commit; T4:R(x); T4:R(y); T4:commit; T1:W(x); T1:commit; T2:R(y); T2:W(z); T2:commit;

can you tell me the ordering of above schedule and is it conflict serial ordering of s?

---

getting 61 ways

Any mistake I have done?

---

@Shaik Masthan ,why are you not ignoring commit operations from each transactions?? Look at this https://gateoverflow.in/218388/aborted-transactions-determining-conflict-serializability

---

@Prateek Raghuvanshi

why are you not ignoring commit operations from each transactions??

i didn't get, why to ignore commit operations from each transactions ( after reading the answer provided by the link also. )

---

@ Shaik Masthan ,

 all operations in the transactions must appear in the complete schedule. Since every transaction has either committed or aborted, a complete schedule will not contain any active transactions at the end of the schedule.

 In general, it is difficult to encounter complete schedules in a transaction processing system because new transactions are continually being submitted to the system. Hence, it is useful to define the concept of the committed projection C(S) of a schedule S.

 Committed Projection of a Schedule :

Committed Projection C(S) of a schedule S includes only the operations in S that belong to committed transactions—that is, transactions Ti whose commit operation Ci is in S. 

---

Now, as according to Navathe,

We can theoretically define a schedule S to be serializable if its committed projection C(S) is equivalent to some serial schedule, since only committed transactions are guaranteed by the DBMS.

And It applies to both Conflict and View Serializability.

 Ignoring  commit operation is nothing but taking committed projection of schedule S.

---

Brother,

if you really ignore the commit operation, then T3---> T1 and T1---->T4 are come into picture, but those are not implied by my original schedule.

---

but those are not implied by my original schedule.

I am not getting this.what do you mean?? 

---

T3---> T1 and T1---->T4

are not produced by the original ( question ) schedule.

---

if commit operations of each transaction is ignored then T3---> T1 and T1---->T4 will produced .why not we get them??

---

yes, if you ignore them, then only you get it, otherwise you didn't get it.... So clearly we can sense that there is a difference between ignoring commit operation and having commit operation !

---

yeah right ,if we ignore them then only one serial order is possible.

---

@Shaik Masthan

here it its little contradicting

https://gateoverflow.in/112238/self-doubt

https://gateoverflow.in/81125/conflict-serializability-when-schedule-contains-commit

---

For all who read this answer,

yes, commit operation makes no difference while calculating the Serializability.

So, remove the commit operations and do the process.

In this question T4 must be at last !

why ?

otherwise if T4 go first, then it read the value which is not updated by T1.

( i am very sorry to deliver wrong information. )

---

@Shaik Masthan  Sir,

So answer to this question will be 1 & Not 8 as per your last comment  ??

$T_{2}$$\rightarrow$$T_{3}$$\rightarrow$$T_{1}$$\rightarrow$$T_{4}$

---

@Kushagra गुप्ता

yes, but note that there are 14 more conflict equivalent schedules which are conflict equivalent to other schedules.

---

What about the 2nd part of the ans  @Shaik Masthan?

Answer 2

$T_{1}$	$T_{2}$	$T_{3}$	$T_{4}$
$1.$
$2.$	$r(x)$
$3.$
$4.$		$w(x)$
$5.$
$6.$		$Commit$
$7.$
$8.$ $w(x)$
$9.$
$10.$ $Commit$
$11.$
$12.$	$r(y)$
$13.$
$14.$	$w(z)$
$15.$
$16.$	$Commit$
$17.$
$18.$			$r(y)$
$19.$
$20.$			$Commit$

Now, See for $T_{2}$ $r(y)$ , $w(z)$ , $Commit$ has no conflict with $T_{1}$ or $T_{3}$. So, $T_{2}$ can be placed in $3,5,7,9,11$ th places. Now all 3 of them can be placed in 1 place , or 2 place in one among these 5 places and 3rd one in another place , or all 3 can place in different place

So, $\binom{5}{1}+\binom{5}{2}+\binom{5}{3}=25$ arrangement are possible

-------------------------------------------------------------------------------------------------------------------------

Now, Similarly $T_{4}$ can arrange in 8 places. Now, $T_{4}$ transaction can place $\binom{8}{1}+\binom{8}{2}=36$ ways

So, total arrangement $25+36=61$ ways

Comments

check this question https://gateoverflow.in/96108

to understand between the terms conflict serializable schedule and conflict serializable serial schedule

---

conflict serializable schedule can't be greater than n! (n is no. of transaction)

no.of  conflict serializable schedule can be greater than n! (n is no. of transaction)

ex:- T1 have R(A),W(A) and T2 have R(B),W(B)

serial schedules are = 2! = 2 ===> 1) T1 ---> T2 and 2) T2 ---> T1

conflict serializable schedules = $\frac{4!}{2!\;.\;2!} = 6$, in this 6 schedules, 3 are conflict serializable to the serial schedule T1 ---> T2 and remaining 3 are conflict serializable to the serial schedule T2 ---> T1.

---

@ Shaik Masthan  yeah you are right ,CSS can be greater than n!,i did mistake.thank you.