Made Easy Test

Question

Consider the following schedule for transaction T1,T2,T3

r1(x),r2(y),r3(y),w1(x),w3(x),r2(z),w1(x)

Also assume that the timestamp for the three transaction is{30,10,20} which of the following statement is true with respect to the above schedule?

ANS will be Thomas Write Time Stamp Protocol but not basic time stamp protocol HOW?

Answer 1

	T2	T3	T1
Timestamps	10	20	30
			R(X)
	R(Y)
		R(Y)
			W(X)
		W(X)
	R(Z)
			W(X)

Basic Timestamp Protocol (BTSP) states that a schedule is allowed only if it is conflict serializable in the increasing order of the timestamp.Here, R1(X) clearly conflicts with W3(X), hence, given schedule does not comply with BTSP, and T3 must be rolled back.

Similarly, as Thomas Write Rule (TWR) saves us from aborting a transaction only in the case of an obsolete write in a WW conflict pair, the schedule again does not comply with TWR due to the presence of a R1(X)...W3(X) conflict. Note that Thomas Write rule could only save us a roll back in the case of T1(X)...T3(X) conflict, but not R1(X)...W3(X).

Hence, no matter the given answer, the given schedule does not follow both BTSP and TWR :)

Comments

yes you're correct, X is read by an younger transaction and older transaction T2 wants to write it. T2 will be rolled back even under TW TSP. This even won't be allowed under multiversion TSP.

---

I wonder how people are able to score full Marks in test series,given if answers to 1-2 questions are not correct.:)

Answer 2

Time stamp is value attached by sytsem to a transaction to indicate when that transaction was arrived in the system  

Or in other word you give a time to transaction when it was enterd in to system

note that here in transaction 1 (T1) has time stamp 30 , T2  has 10 and T3 has 20 Hence from the above given timestamp we can make out T2 is first one to come followed by T3 and T2

In a basic Time stamp protocol : A early arriving Timestamp(older ) must complete its all operation as compared to late arriving transaction (younger ). Here in this above T3 is older as comapred to T1 so all operation of T3 must happen before T1. but T1 is writing on a date item (X) before T3 write . SO the basic timestamp rule is violated

Hence this doesnt come under basic time stamp .

Now thomas  Write Timestamp : This can happen between WW pair . here it say all opertaion of older must happen before younger . except the write of older and write of younger . the reason why this pair is allowed beacuse anyways the final data item would be always of younger transaction . so older one write on a data item can be neglected .

Here if you see such WW pair happen between T1 and T3

Here T3 inspite of been older , T1 is writing before that . So the above come under thomas basic timestamp :)

Comments

Dexter, in thomas write rule W-W pairs are allowed. I agree to that but there is a R-W conflict present too. i.e R1(X) is happening before W3(X). Hence how can the thomas write rule can be applicable?

---

@pratiksha yes you're correct, X is read by an younger transaction and older transaction T2 wants to write it. T2 will be rolled back even under TW TSP. This even won't be allowed under mutiversion TSP.