# Rollback and Timestamp Ordering in Database

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?

• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Jul 14 '16 at 6:10

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.

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.

• Welcome! Late isn't a problem, since we always hope that questions here will be useful to more people than just the person who originally asked them. You've formatted most of your answer as a quotation. If it is a quotation, please acknowledge its source (e.g., with a link to the original page). If it isn't, could you edit it, to remove the visual distraction? Thanks! – David Richerby Apr 15 '16 at 4:13