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
Answer my own question:

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