0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\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
    Commented Jan 21, 2018 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
    Commented Jan 21, 2018 at 9:59
  • $\begingroup$ In this case I think the assumption does not hold. $\endgroup$
    – Renzo
    Commented Jan 21, 2018 at 10:09
  • $\begingroup$ So the given schedule is not allowed basically? $\endgroup$
    – newbie
    Commented Jan 21, 2018 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
    Commented Jan 21, 2018 at 10:50

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jan 21, 2018 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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