Rollback and Timestamp Ordering in Database

Question

If we use the Timestamp Ordering for concurrency control in the following scheduling:

My TA says $T_2,T_3,T_5$ is Run and $T_4,T_5$ is Rollback. I think it's false. Is there any expert who could help us?

Answer 1

Timestamp Ordering ensures serializability by serializing transactions in order of their timestamps.

The transaction that starts earlier is assigned smaller timestamp than a transaction started later. Assuming the given schedule shows each transaction's start. $T_{5}$ will have smallest timestamp.

So to ensure serializability the given schedule must be conflict serializable. In other words it must be conflict equivalent to a serial schedule(It is a schedule in which transactions are aligned in such a way that one transaction is executed first. When the first transaction completes its cycle, then the next transaction is executed) whose first transaction is $T_{5}$ because of smallest timestamp.

Because $Write(y)$ of $T_{5}$ conflicts with $Write(y)$ of $T_{3}$, $T_{5}$ is rolled back. Now considering $T_{1}$ , $T_{2}$, $T_{3}$ , $T_{4}$, their execution is already serial with respect to each other , the order being $T_{2}$ followed by $T_{1}$, followed by $T_{3}$, followed by $T_{4}$.

Hence only transaction $T_{5}$ is rolled back.

Answer 2

I know its a little too late, but here's my take:

All the read and writes by t1,t2,t3,t4 are sucessfully run, since there are just 1 instructions until that point. And assuming the systems assigns the timestamp just before each transaction's first instruction.

The last write(y) instruction by t5 is rejected, since the TS(T5) < W-TStamp and R-TStamp. Hence its restarted with a new time stamp.