So, the task is to prove the following:

If S is a schedule containing at most one write action, then S is conflict-serializable.

The answer is yes, but I disagree, because the following schedule contains at most one write action, and is not conflict-serializable:

R1(A), R2(A), W2(A), R1(A).

Am I completely wrong? Or is the answer wrong?

  • $\begingroup$ The statement is true if in a transaction there is only one read on a datum (no repeated reads). And this a reasonable assumption when discussing schedules (and also in practice). $\endgroup$ – Renzo Jan 21 '18 at 9:49
  • $\begingroup$ But let´s say repeated reads are allowed. If we just look at this in theory and not practical, does the assumption hold? $\endgroup$ – newbie Jan 21 '18 at 9:59
  • $\begingroup$ In this case I think the assumption does not hold. $\endgroup$ – Renzo Jan 21 '18 at 10:09
  • $\begingroup$ So the given schedule is not allowed basically? $\endgroup$ – newbie Jan 21 '18 at 10:17
  • $\begingroup$ I think the statement to prove should be interpreted in this way (no duplicate operations on data). However, I looked in several well-known books on databases and didn't find an explicit prohibition of replication of operations on the same data in the definition of a schedule. So, it is not clear to me if this is just a case of underspecification or something else. $\endgroup$ – Renzo Jan 21 '18 at 10:50

The resulting precedence graph for your example will contain a cycle due to $R1(A) W2(A) R1(A)$. Hence its not conflict serializable. Since one example is sufficient to disprove the statement, therefore I agree with you. The answer might be wrong.

  • $\begingroup$ @Renzo Not allowing duplicate reads combined with the condition of having at most one write operation essentially leaves us with the choice of operations like $R1(A) W2(A)$ or $R2(A) W1(A)$. This becomes too simple to be seen as serializable. Whats's to prove here then? or have I misunderstood something? $\endgroup$ – virmis_007 Jan 21 '18 at 13:18

In transaction theory, it's usually assumed that a transaction reads or writes a same data item at most once. So your schedule is not valid since the transaction 1 reads A twice.

Unfortunately, text books do not always make it very easy to find. Here are some quotes I can find.

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman "Concurrency Control and Recovery in Database Systems" P.21 Section 2.1

To keep this notation unambiguous, we assume that no transaction reads or writes a data item more than once.

Gerhard Weikum, Gottfried Vossen "Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery" P.47 Section 2.3

To exclude redundancies of this kind, we henceforth make the following assumptions: in each transaction each data item is read or written at most once

New contributor
Ryoji is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.