time stamp ordering protocol

Question

what is the meaning of TS(Ti) < WTS(Q) and TS(Ti) > WTS(Q)

Ti issuing read on data item Q.

please someone clear my doubt  i am very confuse in these terms.

Answer 1

In timestamp based protocol for concurrency control , the most important line being :

a ) The conflict pairs (R-W , W-R or W - W) are ensured to occur in the same order as the timestamp values of  the transaction are..Hence conflict equal serial schedule is given by timestamp values of the transactions of the schedule.

b) More is the value of timestamp , younger is the transaction .In other words , less is the value of timestamp older the transaction .  Actually timestamp is nothing but amount of time spent (say number of seconds) w.r.t a given start time(say 00:00:00 of 1st Jan 1980).. 

 Now here 2 variables are used for a data item Q : RTS(Q) and WTS(Q) :

RTS(Q) indicates the timestamp value of the youngest transaction that has read the data item Q successfully.So is the case for WTS(Q) which concerns for successful write instead. 

Now we have some  WTS(Q) and say a transaction T_i issues read operation on Q..As there is a read ,and possible conflict operation is "write" on that data item ,so we need to check the WTS(Q) against the timestamp value of T_i denoted by TS(T_i)..We have some value of WTS(Q) means some other instruction T_j  has already performed write and hence T_j --> T_i .. 

Hence same should be reflected by timestamp value as well..As T_i is younger hence it should have greater than or equal to timestamp value than T_j and hence greater timestamp value than WTS(Q)..

Hence the condition :  TS(T_i) >= WTS(Q) then only the read will be allowed and in that case we read and then set RTS(Q) to the  timestamp value of current transaction which is T_i..

Hence the condition : WTS(Q) > TS(T_i) leads to rollback of transaction T_i..

Similarly when a transaction issues write operation then conflict may occur due to read or write by other instruction on the same data item..

So for transaction T_i to run successfully , the condition is :

RTS(Q) <= TS(T_i)  and  WTS(Q) <= TS(T_i)  , then we write successfully and set WTS(Q) to the timestamp of current transaction i.e. T_i ..

However this is for basic timestamp protocol..

There is a slight modification  to this in one more protocol known as Thomas write protocol..

In this case , if we have write operation and WTS(A)  > TS(T) , then we do not rollback it but we simply ignore it as opposed to the case of basic timestamp protocol..

So Basic Timestamp protocol is similar to conflict serialisability and Thomas Write is similar to view serialisability..I hope this clears ur doubt..:) 

Comments

so basically you mean younger transaction can read but can not write and we need to roll back in case of write and restart to have schedule in serial order.

please do reply.