1
$\begingroup$

Serializability is the strongest consistency level with regard to the execution of two concurrent transactions T1 and T2. That is, if T1 and T2 independently change the application between consistent states, and a concurrent execution of T1 and T2 is equivalent to a serial execution of T1 and T2, then that concurrent execution results in a consistent state, after committing both transactions.

For example, the following concurrent execution (time advances to the right)

T1: w(a=1)         w(c=4)
T2:     w(a=2)w(b=3)

where W(x=v) sets (i.e., writes) x to the value v, is equivalent to the serial execution T1;T2, thus it is serializable and both transactions are committed.

However, it is clear that T2's write of a causes T1's write of a to be lost, i.e., we have a lost update despite serializability.

That is, serializability ensures consistent states in face of concurrency, though it does not prevent lost updates, which may have serious consequences (for example, imagine that T1 writes the correct delivery address of a VIP customer, and T2 writes the wrong address, T1 and T2 are run concurrently by different operators, who do not notice the mistake).

Is my statement correct about serializability and lost updates?

If it is correct then the table in "Isolation levels, read phenomena, and locks" in this wiki page can only be wrong with regard to serializability and lost updates.

If so, what other stronger consistency level ensures that there are no lost updates?

Thanks

Improve this question
$\endgroup$
18
  • $\begingroup$ I highly recommend Bailis et al's Highly Available Transactions: Virtues and Limitations for a concise but rather comprehensive overview of database isolation and data consistency models. Table 3 and Figure 2 provide an even more concise overview and clearly indicate that serializability and even weaker isolation levels prevent lost updates, so your statement is not correct. $\endgroup$
    – Derek Elkins left SE
    May 23, 2018 at 15:31
  • $\begingroup$ @DerekElkins I have read that article just before asking this question! The point is that the "Lost Update" case in the article (sec 5.2.1) is a different one, in which case there is no serializable execution. Now my point here is a different "Lost Update" situation, one in that the concurrent execution is serializable, though one of the updates is silently lost. $\endgroup$
    – mljrg
    May 23, 2018 at 15:38
  • $\begingroup$ @DerekElkins My point is that serializability does not prevent all situations of "lost update", like in the case of blind writes. $\endgroup$
    – mljrg
    May 23, 2018 at 15:40
  • $\begingroup$ If you want to use a different meaning of "lost update", I would recommend either making it clear that you are doing that or, preferably, finding a different way of saying that rather than reusing a technical term. I don't see why you describe the situation in your question as a "lost update". How is the scenario you describe any different from running all of T1 before all of T2? The end result is still a wrong address. Do we "lose an update" any time two transactions write to the same variable? $\endgroup$
    – Derek Elkins left SE
    May 23, 2018 at 15:59
  • $\begingroup$ @DerekElkins ok, now we are reaching to something that I was suspicious of. Unfortunately, I saw nowhere a clear statement of what is meant by "lost update" in the database world, and how does it distinguishes from "lost update" in real-world. If you have such reference, please tell me. So now it is a matter of what programmers want their applications to behave, that is, if they want to avoid inadvertent real-world "lost updates", in which case serializability is not enough, or does not care at all. Personally, I tend to the former. $\endgroup$
    – mljrg
    May 23, 2018 at 16:05

2 Answers 2

Reset to default
1
$\begingroup$

You say:

serializability ensures consistent states in face of concurrency, though it does not prevent lost updates

This is not true, since by definition the lost update is the phenomenon arising in presence of Write-write conflict, that is when a transaction B overwrites a value written by a transaction A before the commit of A. This operation can lead to a state which cannot arise from any serial execution of A and B.

Consider for instance, in your example, the case in which the transaction T2 is executed one hour after the transaction T1: this could happen in real life, the execution of the two transactions is serial, that is there is no interference between the two transactions, however the update is wrong since someone wrote a bad address. But this means bad data, not data base inconsistency in itself (in other words, you have a database inconsistent with the reality, but this has nothing to do with concurrency and transaction management, that are properties related to the execution of concurrent operations over the database).

Improve this answer
$\endgroup$
12
  • $\begingroup$ The link you give is a case of lost update that is detected as no concurrent execution is equivalent to a serial order of Ta and Tb. The case you give after "that this [sic] when a transaction B ..." is one of blind writes and is serializable (it is equivalent to Ta;Tb). And you did not understand my point: serializability ensures consistent application/database states, always, but it does not prevent situations when updates are silently ignored. However, there are "databases" that really prevent the kind of lost update I gave in my example, like version control tools. $\endgroup$
    – mljrg
    May 23, 2018 at 15:51
  • $\begingroup$ Version control has nothing to do with databases: the serializability theory is an old and well established theory that talks not about the consistency of the database with respect to the real world. If you don't want to lose any update, you can use version based-databases or historical databases, where no data is modified or deleted, but only added. Or you imagine that the application or the database know when an update is a correct update or is wrong? Under which bases? $\endgroup$
    – Renzo
    May 23, 2018 at 15:57
  • $\begingroup$ My example is a case of write-write conflict on variable a, as per the link you gave as it is "overwriting uncommitted data", though it is still serializable. $\endgroup$
    – mljrg
    May 23, 2018 at 15:58
  • $\begingroup$ The example given in the wikipedia page is not serializable, while your is, and if fact it is not prohibited by the theory (but note that real-life serializers of DBMS working with the Two-Strict Phase Protocol do not allow the concurrent execution of the two transactions, since T1 blocks a until it commits.) $\endgroup$
    – Renzo
    May 23, 2018 at 16:09
  • 1
    $\begingroup$ That is a interesting point of view! I think it could be explored somehow. $\endgroup$
    – Renzo
    May 23, 2018 at 16:31
0
$\begingroup$

The case above of transactions T1 and T2 is one of Dirty Writes, not of Lost Update. Let me explain what I have been learning regarding this phenomena (see paper A Critique of ANSI SQL Isolation Levels by Berenson et al, 1995).

I confounded these two phenomena because they are very similar when comparing the execution schedules of two concurrent transactions provoking each phenomenon. The trap is that both phenomena involve writes to the same data item in two transactions.

A Dirty Write happens when one transaction writes a data item, but does not finish (i.e., commit or abort) before another transaction writes the same data item in concurrency. Dirty writes are precluded in all databases, typically by putting a write (exclusive) lock as the data item is written, thus blocking other transactions trying to write the same data item until the one holding the lock finishes. This means that the schedule in this question (above) cannot happen in reality because T2 would block waiting for T1 to finish.

In contrast, a Lost Update happens when one transaction writes a data item and commits, then a second (concurrent) transaction writes the same data item based on a value of the data item read before the write of the first transaction, therefore if the second transaction commits the update of the first is lost. Lost Updates are avoided at isolation levels stronger than READ COMMITTED.

Improve this answer
$\endgroup$

Your Answer

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

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