<p><em>Answer my own question:</em></p>

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

<hr>

<p>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.</p>

<p><em>The SR in [Lin et al@TODS'2009]:</em></p>

<p>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 <a href="http://dl.acm.org/citation.cfm?id=319998" rel="nofollow">[Bernstein et al@TODS'1983]</a>. </p>

<p>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 <em>multiversion serialization graph</em> $MVSR(H, \ll)$ can be constructed. As a consequence, we have</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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$.</p>

<p><em>The SR in [Berenson et al@MSR-TR'1995]:</em></p>

<p>The $\textrm{SR}$ adopted in [Berenson et al@MSR-TR'1995] is defined by avoiding <em>phenomena</em> ($P$) and <em>anomalies</em> ($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$.</p>

<p>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 <em>might</em> in the future. Although $r_2(x_1)$ reads-x-from $w_1(x_1)$ that is committed <em>later on</em>, it is still a "dirty read". In this way, it does not satisfy $\textrm{SR}$.</p>

<hr>

<p><em>The perspective of computational complexity:</em></p>

<p>[Bernstein et al@TODS'1983] also shows that </p>

<blockquote>
  <p>It is $\textrm{NP}$-complete to decide whether an MV history is 1-$\textrm{SR}$.</p>
</blockquote>

<p>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 <a href="http://dl.acm.org/citation.cfm?id=1376690" rel="nofollow">[Cahill et al@SIGMOD'2008]</a>.</p>

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

<blockquote>
  <p><em>A guess:</em> 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].</p>
</blockquote>

<hr>

<p><em>References:</em></p>

<p>([Bernstein et al@TODS'1983]) <a href="http://dl.acm.org/citation.cfm?id=319998" rel="nofollow">Multiversion Concurrency Control — Theory and Algorithms</a></p>

<p>([Cahill et al@SIGMOD'08]) <a href="http://dl.acm.org/citation.cfm?id=1376690" rel="nofollow">Serializable Isolation for Snapshot Databases</a></p>

CC BY-SA 3.0
2014-10-16T06:31:19.780Z
2014-10-16T06:36:25.877Z
2014-10-16T06:36:25.877Z
hengxin
<p>In <a href="http://history.acm.org/pictures/tods/tods.acm.org/accepted/2009/LiSnapshot.pdf" rel="nofollow noreferrer">[Lin et al@TODS'2009] (Page 5)</a>, a history of concurrent transactions <strong>satisfying "serializability" ($\textrm{SR}$) but not "snapshot isolation" ($\textrm{SI}$)</strong> is given as follows:</p>

<blockquote>
  <p>$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$</p>
</blockquote>

<p>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$.</p>

<p>Pictorially (horizontal axis is time),</p>

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

<hr>

<p><strong>My Confusion:</strong></p>

<p>However, as my basic understanding, <code>Serializability is strictly stronger than snapshot isolation</code>. In particular, we have a hierarchy of isolation levels as shown in the following figure copied from <a href="http://research.microsoft.com/pubs/69541/tr-95-51.pdf" rel="nofollow noreferrer">[Berenson et al@MSR-TR'1995]</a>.</p>

<p><img src="https://i.sstatic.net/OLdXn.png" alt="ANSI Isolation Levels"></p>

<hr>

<p><strong>My question:</strong></p>

<blockquote>
  <p>What is wrong with my understanding and what is going on here?</p>
  
  <p>Any comprehensive references on the relationships among $\textrm{SI}$, $\textrm{SR}$, and maybe other isolation levels are appreciated.</p>
</blockquote>

<hr>

<p><strong>References:</strong></p>

<p>([Lin et al@TODS'2009]) <a href="http://history.acm.org/pictures/tods/tods.acm.org/accepted/2009/LiSnapshot.pdf" rel="nofollow noreferrer">Snapshot Isolation and Integrity Constraints in Replicated Databases</a></p>

<p>(Berenson et al@MSR-TR'1995) <a href="http://research.microsoft.com/pubs/69541/tr-95-51.pdf" rel="nofollow noreferrer">A Critique of ANSI SQL Isolation Levels</a></p>

CC BY-SA 3.0
2014-10-15T07:50:28.713Z
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
CC BY-SA 3.0
2014-10-15T13:02:03.360Z
@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
CC BY-SA 3.0
2014-10-15T13:14:49.650Z
@MarzioDeBiasi Of course, there are problems involving computational complexity :). One of the most classic papers is [Papadimitriou@JACM'1979](https://www.cs.purdue.edu/homes/bb/cs542-11Spr/SCDU-Papa-79.pdf), 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
CC BY-SA 3.0
2014-10-15T13:17:33.973Z
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
CC BY-SA 3.0
2014-10-15T13:30:55.977Z
@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](http://dl.acm.org/citation.cfm?id=1071615) may be useful. As said in Abstract, it develops a theory that characterizes when non-serializable executions of applications can occur under SI.
hengxin
CC BY-SA 3.0
2014-10-15T13:43:46.233Z
@MarzioDeBiasi I realized that SI is a *multiversion* concurrency control algorithm. Under the multiversion mechanism, $H_{example}$ may be a valid history. In particular, $r_3(x_1)$ is valid, even though it is after $w_2(x_2)$. I will think over this point of view.
hengxin
CC BY-SA 3.0
2014-10-15T13:45:02.283Z
But $r_2(x_1)$ is still wrong for a SI system, it should be $r_2(x_0)$
Marzio De Biasi
CC BY-SA 3.0
2014-10-15T13:52:42.373Z
@MarzioDeBiasi Yes. That ($r_2(x_1)$) means $H$ is not SI. However, the history itself may be valid, being a possible execution of a set ($T_1 \sim T_4$) of transactions that run under serializability (SR).
hengxin
CC BY-SA 3.0
2014-10-16T06:39:06.243Z
@MarzioDeBiasi I have written a tentative answer to my own question. Please check it out and let me know your comments. Thanks.
hengxin
<db.databases><concurrency>
Concurrent transactions satisfying "serializability" but not "snapshot isolation"
hengxin
# Concurrent transactions satisfying "serializability" but not "snapshot isolation"

(Asked by: username_0 on 2014-10-15)

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

**Tags:** db.databases, concurrency
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_0**: @MarzioDeBiasi Of course, there are problems involving computational complexity :). One of the most classic papers is [Papadimitriou@JACM'1979](https://www.cs.purdue.edu/homes/bb/cs542-11Spr/SCDU-Papa-79.pdf), 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`.  
> **username_1**: 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.  
> **username_0**: @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](http://dl.acm.org/citation.cfm?id=1071615) may be useful. As said in Abstract, it develops a theory that characterizes when non-serializable executions of applications can occur under SI.  
> **username_0**: @MarzioDeBiasi I realized that SI is a *multiversion* concurrency control algorithm. Under the multiversion mechanism, $H_{example}$ may be a valid history. In particular, $r_3(x_1)$ is valid, even though it is after $w_2(x_2)$. I will think over this point of view.  
> **username_1**: But $r_2(x_1)$ is still wrong for a SI system, it should be $r_2(x_0)$  
> **username_0**: @MarzioDeBiasi Yes. That ($r_2(x_1)$) means $H$ is not SI. However, the history itself may be valid, being a possible execution of a set ($T_1 \sim T_4$) of transactions that run under serializability (SR).  
> **username_0**: @MarzioDeBiasi I have written a tentative answer to my own question. Please check it out and let me know your comments. Thanks.  

---

## 1 answers

### Answer by username_0 on 2014-10-16. Score: 1 | Accepted answer

*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]](http://dl.acm.org/citation.cfm?id=319998).

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]](http://dl.acm.org/citation.cfm?id=1376690).

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](http://dl.acm.org/citation.cfm?id=319998)

([Cahill et al@SIGMOD'08]) [Serializable Isolation for Snapshot Databases](http://dl.acm.org/citation.cfm?id=1376690)


---

