# Concurrent transactions satisfying “serializability” but not “snapshot isolation”

In [Lin et al@TODS'2009] (Page 5), a history of concurrent transactions satisfying "serializability" ($\textrm{SR}$) but not "snapshot isolation" ($\textrm{SI}$) is given as follows:

$H_{example}: s_1 \; s_2 \; w_1(x_1) \; r_2(x_1) \; w_2(x_2) \; w_2(y_2) \; c_1 \; c_2 \; s_3 \; r_3(x_1) \; c_3 \; s_4 \; w_4(y_4) \; a_4$

where, $s_1$ denotes the start of transaction $T_1$; $w_1(x_1)$ denotes the write of $T_1$ of version $v_1$ to data item $x$; $c_1$ denotes the commit of $T_1$; and $a_4$ denotes the abort of transaction $T_4$.

Pictorially (horizontal axis is time),

T1: s1    w1(x1)                      c1
T2:    s2        r2(x1) w2(x2) w2(y2)    c2
T3:                                         s3 r3(x1) c3
T4:                                                      s4 w4(y4) a4


My Confusion:

However, as my basic understanding, Serializability is strictly stronger than snapshot isolation. In particular, we have a hierarchy of isolation levels as shown in the following figure copied from [Berenson et al@MSR-TR'1995].

My question:

What is wrong with my understanding and what is going on here?

Any comprehensive references on the relationships among $\textrm{SI}$, $\textrm{SR}$, and maybe other isolation levels are appreciated.

References:

([Lin et al@TODS'2009]) Snapshot Isolation and Integrity Constraints in Replicated Databases

(Berenson et al@MSR-TR'1995) A Critique of ANSI SQL Isolation Levels

• I'm not an expert, but perhaps the history H would not be serializable if you replace c1 with a1. But that particular H is serializable because the reading r2(x1) before c1 leads to the same final state as if the transactions were executed serially: T1 T3 T2 T4. My understanding: Snapshot isolation is weaker because it doesn't guarantee serializability, and H cannot occur on a system that offers snapshot isolation; but on a system that implements serializability, the schedule H would also never occur. And all valid history sequences generated on a serializable system satisfy SI. – Marzio De Biasi Oct 15 '14 at 7:50
• @MarzioDeBiasi Thanks. I think you have mentioned two similar but yet fundamentally distinct concepts: the serializability as a correctness criterion and the serializability that is implementable. Are they the same? If not, what is the relationship between them? Is this claim Serializability is strictly stronger than snapshot isolation valid on both concepts. There are many other related concepts such as state-serializability, view-serializability, and conflict-serializability. Some references dealing with all the intricate relationships among them would be of great help. – hengxin Oct 15 '14 at 13:02
• @MarzioDeBiasi Of course, there are problems involving computational complexity :). One of the most classic papers is Papadimitriou@JACM'1979, which has left an open problem (Section 4.4; I am not sure whether it is still open now) that whether the class SSR (one of the stricter variants of serializability) is efficiently recognizable. – hengxin Oct 15 '14 at 13:14
• I think that the difference is "Transactions that run under Serializable Isolation Level or under Snapshot Isolation Level" versus "Execution (histories) of one ore more transactions under some isolation level that can be serializable or not". A set of transactions that run under SI level may not be serializable. The H in your example cannot be the execution history of neither a set of transactions that run under Serializable level nor under transactions that run under SI. Now I'll give a look to see if I find some references. – Marzio De Biasi Oct 15 '14 at 13:17
• @MarzioDeBiasi For the latter "Execution (histories) of one ore more transactions under some isolation level that can be serializable or not", the paper Making Snapshot Isolation Serializable@TODS'2005 may be useful. As said in Abstract, it develops a theory that characterizes when non-serializable executions of applications can occur under SI. – hengxin Oct 15 '14 at 13:30

I am not sure with the ideas below. Both comments and answers from experts are highly appreciated. Any references are also welcome.

I think the confusion arises from the fact that the two definitions of serializability ($\textrm{SR}$, for short) adopted in [Lin et al@TODS'2009] and [Berenson et al@MSR-TR'1995] are different.

The SR in [Lin et al@TODS'2009]:

In [Lin et al@TODS'2009] (at least in the test of $H_{example}$), the serializability is the classic One-Copy Serializability (or, $\textrm{1-SR}$) introduced in [Bernstein et al@TODS'1983].

To tell if an multiversion (or MV) history is $\textrm{1-SR}$, we should first decide on a version order $\ll$ (which is a total order) for each data item. Given a history $H$ and a version order $\ll$, an multiversion serialization graph $MVSR(H, \ll)$ can be constructed. As a consequence, we have

1-SR Theorem: An MV history $H$ is $\textrm{1-SR}$ iff there exists a version order $\ll$ such that $MVSG(H, \ll)$ is acyclic.

Back to the history $H_{example}$, the version order for $x$ can be chosen as $x_1 \ll x_2$. It is easy to show, according to the above theorem, that $H_{example}$ is $\textrm{1-SR}$ because it is equivalent to the serial history of $T_1 \; T_3 \; T_2$.

The SR in [Berenson et al@MSR-TR'1995]:

The $\textrm{SR}$ adopted in [Berenson et al@MSR-TR'1995] is defined by avoiding phenomena ($P$) and anomalies ($A$). In this sense, Snapshot Isolation (or $\textrm{SI}$) avoids $P_0, P_1, A_3, A5A, P4$. The $\textrm{SR}$ here is thus strictly stronger than $\textrm{SI}$ because it further avoids $A5B$.

Back to the history $H_{example}$, it even does not avoid $P_1$ which indicates a "dirty read". Notice that $P_1$ (instead of $A_1$) prohibits an execution sequence if something anomalous might in the future. Although $r_2(x_1)$ reads-x-from $w_1(x_1)$ that is committed later on, it is still a "dirty read". In this way, it does not satisfy $\textrm{SR}$.

The perspective of computational complexity:

[Bernstein et al@TODS'1983] also shows that

It is $\textrm{NP}$-complete to decide whether an MV history is 1-$\textrm{SR}$.

However, if we know that $H$ is $\textrm{SI}$ in advance, we can decide efficiently whether it is 1-$\textrm{SR}$. The key here is that the version order $\ll$ has been determined by $\textrm{SI}$. See [Cahill et al@SIGMOD'2008].

Furthermore, I guess that, for an $\textrm{SI}$ history, the above two different definitions of serializability coincide. More precisely,

A guess: With $\textrm{SI}$, a history $H$ is 1-$\textrm{SR}$ in [Bernstein et al@TODS'1983] iff it is $\textrm{SR}$ in [Berenson et al@MSR-TR'1995].

References:

([Bernstein et al@TODS'1983]) Multiversion Concurrency Control — Theory and Algorithms

([Cahill et al@SIGMOD'08]) Serializable Isolation for Snapshot Databases