# Coo: Rethink Data Anomalies In Databases

Haixiang Li∗, Xiaoyan Li†, Yuxing Chen∗, Xiaoyong Du‡, Wei Lu‡, Chang Liu∗,
Yuean Zhu∗, Anqun Pan∗ $\ast$ Tencent Inc. $\dagger$ Peking University
$\ddagger$ Renmin University of China
blueseali,axingguchen,williamcliu,anduinzhu,aaronpan<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Transaction processing technology has three important contents: data
anomalies, isolation levels, and concurrent control algorithms. Concurrent
control algorithms are used to eliminate some or all data anomalies at
different isolation levels to ensure data consistency. Isolation levels in the
current ANSI/ISO SQL standard are defined by disallowing certain kinds of data
anomalies. However, the definitions of data anomalies in the ANSI/ISO SQL
standard are controversial. On the one hand, the definitions lack a
mathematical formalization and cause ambiguous interpretations. On the other
hand, the definitions are made in a case-by-case manner, and lead to a
situation that even a senior DBA could not have infallible knowledge of data
anomalies, due to a lack of a complete understanding of its nature. While
revised definitions in existing literature propose various mathematical
formalizations to correct the former argument, how to address the latter
argument remains an open problem. In this paper, we present a general
framework called Coo with the capability to formally define all data anomalies
and quantitatively describe. Under this framework, we show that existing
reported data anomalies are only a small portion. While we theoretically prove
that Coo is complete to formalize data anomalies mathematically, we employ a
novel method to classify infinite data anomalies. In addition, we use this
framework to define new isolation levels and quantitatively describe the
proportion of data anomalies and the rollback rates of mainstream concurrency
control algorithms..These works show that the C and I of ACID can be
quantitatively analyzed based on all data anomalies.

Database, Data Anomalies, Isolation Levels, Concurrency Control

PVLDB Reference Format:
PVLDB, 14(1): XXX-XXX, 2021.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097.
doi:XX.XX/XXX.XX

##  1\. Introduction

The data anomalies are not recognized to the due height. In this section, we
discuss why we should define all data anomalies.

The ANSI/ISO SQL (16, 1992) specifies four data anomalies, including Dirty
Write, Dirty Read, Non-repeatable Read, and Phantom. Under the specifications
of data anomalies, four isolation levels, i.e., Read Uncommitted, Read
Committed, Repeatable Read and Serializable, are defined accordingly to
eliminate the different anomalies. For example, the Read Committed isolation
level is defined by disallowing Dirty Write and Dirty Read.

Table 1. A Thorough Survey on Data Anomalies in Existing Literature No | Anomaly, reference, year | Formal definition
---|---|---
1 |  |  Dirty Write (16, 1992) 1992
---
|  $W_{1}[x_{1}]...W_{2}[x_{2}]...$(($C_{1}$ or $A_{1}$) and ($C_{2}$ or
$A_{2}$) in any order)
---
2 |  |  Lost Update (Berenson et al., 1995b) 1995
---
$R_{1}[x_{0}]$…$W_{2}[x_{1}]$…$C_{2}$…$W_{1}[x_{2}]$
3 |  |  Dirty Read (16, 1992) 1992
---
$W_{1}[x]...R_{2}[x]$…($A_{1}$ and $C_{2}$ in either order)
4 |  |  Aborted Reads (Xie et al., 2015) 2015, (Adya et al., 2000) 2000
---
$W_{1}[x:i]...R_{2}[x:i]$…($A_{1}$ and $C_{2}$ in any order)
5 |  |  Fuzzy/Non-repeatable Read (16, 1992) 1992
---
$R_{1}[x]...W_{2}[x]...C_{2}...R_{1}[x]...C_{1}$
6 |  |  Phantom (16, 1992) 1992
---
$R_{1}[P]$…$W_{2}$[$y$ in $P$]…$C_{2}$…$R_{1}[P]$…$C_{1}$
7 |  |  Intermediate Reads (Xie et al., 2015) 2015, (Adya et al., 2000) 2000
---
$W_{1}[x:i]...R_{2}[x:i]...W_{1}[x:j]$…$C_{2}$
8 |  |  Read Skew (Berenson et al., 1995b) 1995
---
$R_{1}[x_{0}]...W_{2}[x_{1}]...W_{2}[y_{1}]...C_{2}...R_{1}[y_{1}]$
9 |  |  Unnamed Anomaly (Schenkel et al., 2000) 2000
---
|
$R_{1}[y]...R_{2}[x]...W_{2}[x]...R_{2}[y]...W_{2}[y]...C_{2}...R_{3}[x]...W_{3}[x]...R_{3}[z]...W_{3}[z]...C_{3}...R_{1}[z]...C_{1}$
---
10 |  |  Fractured Reads (Cerone et al., 2017) 2017, (Bailis et al., 2016) 2014
---
$R_{1}[x_{0}]...W_{2}[x_{1}]...W_{2}[y_{1}]...C_{2}...R_{1}[y_{1}]$
11 |  |  Serial-concurrent-phenomenon (Binnig et al., 2014) 2014
---
$R_{1}[x_{0}]...W_{2}[x_{1}]...W_{2}[y_{1}]...C_{2}...R_{1}[y_{1}]$
12 |  |  Cross-phenomenon (Binnig et al., 2014) 2014
---
|
$R_{1}[x_{0}]...R_{2}[y_{0}]...W_{3}[x_{1}]...C_{3}...W_{4}[y_{1}]...C_{4}...R_{2}[x_{1}]...R_{1}[y_{1}]$
---
13 |  |  Long Fork Anomaly (Cerone et al., 2017) 2017
---
|
$R_{1}[x_{0}]...R_{2}[y_{0}]...W_{3}[x_{1}]...C_{3}...W_{4}[y_{1}]...C_{4}...R_{2}[x_{1}]...R_{1}[y_{1}]$
---
14 |  |  Causality Violation Anomaly (Cerone et al., 2017) 2017
---
|
$R_{1}[x_{0}]...W_{2}[x_{1}]...C_{2}...R_{3}[x_{1}]...W_{3}[y_{1}]...C_{3}...R_{1}[y_{1}]$
---
15 |  |  Read-only Transaction Anomaly (Fekete et al., 2004; wikipedia, [n.d.]) 2004
---
|
$R_{1}[x_{0},0]...R_{1}[y_{0},0]...R_{2}[y_{0},0]...W_{2}[y_{1},20]...C_{2}...R_{3}[x_{0},0]...R_{3}[y_{1},20]...C_{3}...W_{1}[x_{2},-11]...C_{1}$
---
16 |  |  Write Skew (Berenson et al., 1995b) 1995
---
$R_{1}[x_{0}]...R_{2}[y_{0}]...W_{1}[y_{1}]...W_{2}[x_{1}]$
17 |  |  Predicate-based Write Skew (Fekete et al., 2005a) 2005
---
$R_{1}[P]...R_{2}[P]...W_{1}$ [$y_{1}$ in $P$]$...W_{2}$[$x_{1}$ in $P$]
18 |  |  Read Partial-committed (Xiaoyong, 2017) 2019
---
$R_{1}[x]\dot{W}_{2}[x]\dot{W}_{2}[y]\dot{C}_{2}\dot{R}_{1}[y]\dot{C}_{1}$

However, the definitions of data anomalies in the ANSI/ISO SQL standard are
controversial. On the one hand, the definitions lack a mathematical
formalization, and cause ambiguous interpretations. Let symbol “$W_{1}(x,k)$”
be a write by transaction $T_{1}$ on data item $x$ with value $k$, and
“$R_{2}(x,k)$” be a read on $x$ returned with value $k$ by transaction
$T_{2}$. Transaction $T_{1}$’s commit or abort are written as “$C_{1}$” or
“$A_{1}$”, respectively. For example in Dirty Read, it is specified as:
$T_{1}$ writes $x$; $T_{2}$ then reads $x$ before $T_{1}$ performs a commit or
abort; if $T_{1}$ then performs a abort, $T_{2}$ has read a data item that was
never committed and so never really existed (16, 1992; Berenson et al.,
1995b). One specification of the Dirty Read, which is still widely used in
exiting RDBMSs, is restated below:

$W_{1}(x,5)\dots R_{2}(x,5)\dots$ ($A_{1}$ and $C_{2}$ in any order)

Nevertheless, the above specification is single-variable based, and cannot be
extended to the multi-variable based Dirty Read. Assume there exists a
transfer operation from one account $x$ to another account $y$, where the
invariant is that $x+y=10$. Consider the following specification:

$R_{1}(x,5)W_{1}(x,2)R_{2}(x,2)R_{2}(y,5)C_{2}R_{1}(y,5)W_{1}(y,8)C_{1}$

As we can see, $T_{1}$ makes the transfer correctly, but $T_{2}$ observes an
intermediate state of the database, causing a Intermediate Reads (the total is
only 7). To avoid either Aborted Reads (Adya et al., 2000), or Intermediate
Reads (Adya et al., 2000), or Circular Information Flow (Adya et al., 2000),
or both, revised definitions are proposed with a more precise and complete
specification. For example, Jim Grey et. al (Berenson et al., 1995b) formally
define Dirty Read below:

$W_{1}(x,5)\dots R_{2}(x,5)\dots$ (($A_{1}$ or $C_{1}$) and ($C_{2}$ or
$A_{2}$) in any order)

Besides Dirty Read, the other three data anomalies are re-defined in
mathematical forms in order to avoid ambiguous interpretations (Berenson et
al., 1995b). Unfortunately, due to the re-definition of data anomalies,
although the meanings are more precise and complete, the interpretations
become more difficult because of the lack of uniform standards.

On the other hand, the definitions are made in a case-by-case manner, and lead
to a situation that even a senior DBA could not have infallible knowledge of
data anomalies, due to a lack of a complete understanding of its nature.
Except the four data anomalies defined in the ANSI/ISO SQL standard, typical
data anomalies are in different forms, such as Read skew (Berenson et al.,
1995b), Write Skew (Berenson et al., 1995b), Fractured Reads (Cerone et al.,
2017), Cross-phenomenon (Binnig et al., 2014). A thorough study on state-of-
the-art data anomalies will be conducted in Section 2. Apparently, without a
complete understanding of nature, it is rather challenging to know what they
are and what are the relationship among them. Even worse, the revised
definitions with the precise and complete specifications further deteriorate
the understanding of data anomalies.

While revised definitions in existing literature (16, 1992; Berenson et al.,
1995b; Adya et al., 2000) propose some mathematical formalization to correct
the former argument, how can we address the latter argument still remains an
open problem, we need a complete form to define data anomalies instead of case
by case.

In legacy database systems, ACID(Atomicity, Consistency, Isolation,
Durability) refers to a standard set of properties that guarantee database
transactions are processed reliably. Consistency and Isolation are two
important properties, the former ensures the correctness of data, and the
latter ensures the high performance of database systems. However, the latter
improves the performance of the database at the expense of the consistency of
the data. Weak isolation levels allow some data anomalies to occur.

(Berenson et al., 1995b) defines eight data anomalies such as Read Skew, Write
Skew. (Fekete et al., 2005a) defines some other data anomalies such as
Predicate-based Write Skew. In recent years, there still exist extensive
research works that focus on reporting new data anomalies, including
Intermediate Read (Adya et al., 2000; Xie et al., 2015), Serial-concurrency-
phenomenon and Cross-phenomenon (Binnig et al., 2014), Long Fork anomaly and
Causality Violation anomaly (Cerone et al., 2017). It seems that the conflict
graph can describe data anomalies, but Adya (Adya et al., 2000) defines
isolation levels with conflict graph and three specific data anomalies (Dirty
Writes, Dirty Reads, Intermediate Reads), his method is not unified and can
neither define what is data anomaly nor cover all data anomalies. So we wonder
how many data anomalies exist in the application? We analyze Read Skew is
similar with Serial-concurrency-phenomenon even though they are the same kind
of data anomalies with different names by their formal definition (Table 1).
But why do they have different names, and is there a unified standard to study
data anomalies? Further, we do not know whether there are some new coming data
anomalies that will affect the application. At the same time, we do not even
precisely know: what is the relationship between data anomalies and data
consistency or isolation levels?

For reference, we make a thorough survey on data anomalies reported in the
state-of-the-art literature and list them in Table 1. The table shows there
are some different data anomalies reported. Surprisingly, some are the same
anomalies but reported with different names, e.g., Long Fork and Cross-
phenomenon in Table 1. The reason is that, no formal definition to express
these anomalies. Worse, it is ambiguous which current isolation level can
eliminate these two data anomalies?

In this paper, We make the following contributions.

  * •

We propose a general framework, called Coo, which models data anomalies by
extending the conflicted relationship of the conflict graph. In our framework,
we can formally define all data anomalies(§2). At the same time, we report 20+
new entity-based data anomalies (Table 3) and all predicate-based data
anomalies (Table 2).

  * •

We, by Coo, can specify all simplified primitive data anomalies (§2.3) and
classify them. We also explore the similarity and difference between entity-
based data anomalies and predicate-based data anomalies (§2.5).

  * •

We quantitatively study the data anomalies(§3.2) and rollback rate(§3.3),
propose the new isolation levels (§4.1), and analyze the relationship between
data anomalies, isolation levels and concurrency control algorithms(§4.2). Our
new isolation levels can classify any types of anomalies, in contrast to the
current isolation levels which are defined based on limited known data
anomalies. To the best of our knowledge, this is the first paper to
systematically and quantitatively study data anomalies, rollback rates,
isolation levels and concurrent control algorithms.

The rest of this paper is organized as follows. Section 2 presents the Coo
framework. Section 3 discusses how to quantify data anomalies and rollback
rates. Section 4 shows the model application on databases, and discusses how
to define isolation levels and how to analyze concurrent control algorithms.
Section 5 discusses related work. Section 6 is a conclusion.

##  2\. Data anomalies Model

In this section, we first give the symbolizations, then define entity-based
and predicated-based partial order pairs, and finally present our Coo
framework to formulate data anomalies.

###  2.1. Abstract System Model

We consider storing objects $Obj=\\{x,y,...\\}$ in a concurrent system.
Transactions interact with the objects by issuing read and write operations,
grouped them together into transactions symbol $t_{i}$. We let
$Op_{i}=\\{R_{i}[x_{n}],W_{i}[x_{n}]|x\in Obj\\}$ describe the possible
operations invocations: reading the version $n$ from an object $x$ or writing
version $n$ to $x$ by the transaction $t_{i}$. The read operation is divided
into two categories. One type is a physical read $R_{i}[x_{n}]$, which
describes the transaction $t_{i}$ read the object $x$ with version $n$. The
other type is a predicate read operation $R_{i}^{P}[x_{n}]$, which describes
that the object $x$ with version $n$ was in the set of objects fitting
predicate logic $P$ by the transaction $t_{i}$, i.e, $R_{i}[x_{n}\in
Vset(P)]$. A predicate is a sentence that contains a finite number of
variables and becomes a statement when specific objects are substituted for
the variables. The domain of a predicate $Vset(P)$ is the set of all objects
that may be substituting in place of the variables (Epp, 2010). In logic,
predicates can be obtained by removing some or all of the nouns $x$ or $x,y$
from a statement and be symbolized as $P(x)$ or $P(x,y)$. Always predicate is
a predicate symbol together with suitable predicate variables referred to as
propositional functions or open sentences. Predicate logic includes first-
order logic, second-order logic and $n$-order logic. In first-order logic, a
predicate can only refer to a single subject. First-order logic is also known
as first-order predicate calculus or first-order functional calculus
(Smullyan, 1995). A sentence in first-order logic is written in the form
$P(x)$, where $P$ is the predicate and $x$ is the subject, represented as a
variable. Second-order logic is a predicate logic of two predicate variables
after simplie. The same definition method is for $n$-order logic. We define
that atomic formula for an $n$-tuple $P(x,y,\dots)$ where $P$ is any predicate
of degree $n$ and $x,y,\dots$ are $n$ cannot be divided symbols (or
variables).Smullyan and Raymond M (Janin and Walukiewicz, 1996)proved that a
$n$ order logic can containing only disjunction of sentence of the form:
$P(x,y,\dots)=\wedge(or\vee)P_{i}(x_{i})\wedge(or\vee)P_{j}(x_{j},y_{j})\dots\wedge(or\vee)P_{z}(x_{z},y_{z},\dots)$.
Besides, a physical read operation can be regarded as the predicate read
operation with the predicate variable happens to be the object ID.

Therefore, anomalies of a schedule can be detected just under the condition of
predicate logic of degree from one to $n$ in sequence.

In order to reflect the affection between writing and read operations and
predicate logic domain set, we extend senses of versions of the object which
adding insertion and deletion versions.

  * •

The object $x$ has an initial version $x_{init}$ called unborn version. When
transaction $t_{i}$ creates an object that will ever exist in the system
through writing operation, we denote $W_{i}[x_{0}]$. Of course, there is no
read operation $R_{i}[x_{init}]$.

  * •

The object $x$ has a visible version $x_{n}(n=0,1,2,\dots)$ when a transaction
updates an object to generate its new version. We use $R_{i}[x_{n}]$ to
describe a transaction read a version of an object that is in the set.

  * •

The object $x$ has a dead version $x_{dead}$ when the transaction deletes an
object $x$. We use $W_{i}[x_{dead}]$ to describe this situation. Also, there
is no read operation $R_{i}[x_{dead}]$.

Based on the definition of versions of an object, there are four cases of
reading and writing operations under the predicate logic.

  * •

The version of the object $x_{n}$ is in the predicate domain set $Vset(P)$ by
the predicated-based read operation, which denoted $R_{i}[x_{n}\in Vset(P)]$.

  * •

The version of the object $x_{n}$ is not in the predicate domain set $Vset(P)$
by the predicate-based read operation, which denoted $R_{i}[x_{n}\notin
Vset(P)]$.

  * •

The version of the object $x_{n}$ is in the predicate domain set $Vset(P)$ by
the predicate-based write operation, which denoted $W_{i}[x_{n}\in Vset(P)]$.

  * •

The version of the object $x_{n}$ is not in the predicate domain set $Vset(P)$
by the predicate-based write operation, which denoted $W_{i}[x_{n}\notin
Vset(P)]$.

We write $W_{i}[x_{n}]$ indicated writing a value $x_{n}$ that is irrelevant
to whether or not in the predicate domain set $Vset(P)$.

According to the extended definition of object versions, $W_{i}[x_{0}\in
Vset(P)]$ indicates that the transaction $t_{i}$ inserts the new object
exactly in the predicate set. And $W_{i}[x_{dead}\in Vset(P)]$ indicates that
the transaction $t_{i}$ deleted the object exactly in the predicate set.

###  2.2. Conflict Relations

We define the different types of predicate-based operation conflicts that can
occur to a concurrent system in this section. We define two types of conflict
relations and describe in detail different operations combination forms of
various categories of conflict relations.

###### Definition 2.1.

Let $t_{i},t_{j}$ be transactions in a schedule $s$, $t_{i}<_{s}t_{j}$. Two
operations $p\in t_{i}$ and $q\in t_{j}$ access the same object and at least
one of them is a write,
i.e.,$\\{W_{i}W_{j}[x],W_{i}R_{j}[x],R_{i}W_{j}[x]\\}$.

We separate the above relations to several cases by whether the object read of
predicate-based domain.

####  2.2.1. Write-Write Dependency

###### Definition 2.2.

Write-write conflicts $WW[x]$ occur when one transaction overwrites a version
written by another transaction.

Since predicate-based operations are queries objects sets. There is no notion
of predicate-based write-write conflicts.

####  2.2.2. Read-Write Dependency

###### Definition 2.3.

Read-write conflicts $RW[x]$ occur when one transaction reads or predicate-
based $P$ read a relevant object version by some other transaction.

There are four situations based on the relationship between the object version
and the predicate domain set $Vset(P)$.

  * 1

$R_{i}[x_{n}\in Vset(P)]W_{j}[x_{n+1}\in Vset(P)]$

  * 2

$R_{i}[x_{n}\in Vset(P)]W_{j}[x_{n+1}\notin Vset(P)]$

  * 3

$R_{i}[x_{n}\notin Vset(P)]W_{j}[x_{n+1}\in Vset(P)]$

  * 4

$R_{i}[x_{n}\notin Vset(P)]W_{j}[x_{n+1}\notin Vset(P)]$

Obviously, case 1 belongs to entity-based conflicts. Case 2 belongs to
predicate-based conflicts because after reading the object $x$, the write
operation gets $x$ out of the predicated domain. Case 3 belongs to predicate-
based conflicts, in which the write operation of transaction $t_{j}$ inserts
the object of the predicate set through the insert or update. In case 4, the
object is not visible read by transaction $t_{i}$, and the write operation of
transaction $t_{j}$ does not produce an intersection with the predicate set
$Vset(P)$, so there is no relationship between two operations.

We formally express the read-write conflicts as

$\displaystyle R_{i}W_{j}[x]=$ $\displaystyle\\{R_{i}[x_{n}\in
Vset(P)]W_{j}[x_{n+1}\in Vset(P)],$ $\displaystyle R_{i}[x_{n}\in
Vset(P)]W_{j}[x_{n+1}\notin Vset(P)],$ $\displaystyle R_{i}[x_{n}\notin
Vset(P)]W_{j}[x_{n+1}\in Vset(P)]\\}$

####  2.2.3. Write-Read Dependency

###### Definition 2.4.

Write-read conflicts $WR[x]$ occur when a transaction overwrites a version
observed or predicate-based $P$ observed by some other transaction.

There are two situations based on the relation between the object version and
the predicate domain set $Vset(P)$.

  * 1

$W_{i}[x_{n}\in Vset(P)]R_{j}[x_{n}\in Vset(P)]$

  * 2

$W_{i}[x_{n}\notin Vset(P)]R_{j}[x_{n}\notin Vset(P)]$

Thus the read-write conflicts can be expressed as:

$\displaystyle W_{i}R_{j}[x]=$ $\displaystyle\\{W_{i}[x_{n}\in
Vset(P)]R_{j}[x_{n}\in Vset(P)],$ $\displaystyle W_{i}[x_{n}\notin
Vset(P)]R_{j}[x_{n}\notin Vset(P)]\\}$

We divide the conflict relationship into entity conflicts and predicate
conflicts:

  * $\begin{aligned} \text{Entity Conflicts}=&\\{W_{i}[x_{n}]W_{j}[x_{n+1}],\\\ &R_{i}[x_{n}\in Vset(P)]W_{j}[x_{n+1}\in Vset(P)],\\\ &W_{i}[x_{n}\in Vset(P)]R_{j}[x_{n}\in Vset(P)]\\};\end{aligned}$

  * $\begin{aligned} \text{Predicate Conflicts}=&\\{R_{i}[x_{n}\in Vset(P)]W_{j}[x_{n+1}\notin Vset(P)],\\\ &R_{i}[x_{n}\in Vset(P)]W_{j}[x_{n+1}\notin Vset(P)],\\\ &W_{i}[x_{n}\notin Vset(P)]R_{j}[x_{n}\notin Vset(P)]\\}.\end{aligned}$

Based on the above discussion, We can still symbolize the conflict relations
as $conf=\\{W_{i}W_{j},W_{i}R_{j},R_{i}W_{j},\\}$.

###  2.3. Conflict Graphs

###### Definition 2.5.

(Conflict Equivalent) Let $s$ and $s^{\prime}$ be two schedules. $s$ and
$s^{\prime}$ are called conflict equivalent, denoted $s\thickapprox
s^{\prime}$, if they have the same conflict relations, including the entity-
based and the predicate-base, i.e., if the following holds:

  * 1

$Op(s)=Op(s^{\prime})$;

  * 2

$conf(s)=conf(s^{\prime})$.

Thus, two schedules are conflict equivalents if all conflicting pairs of steps
from distinct transactions occur in the same order in both schedules. The
conflict relations of a schedule can be described in terms of graphs (Weikum
and Vossen, 2002).

###### Definition 2.6.

(Conflict Graph) Let $s$ be a schedule and $T(s)$ be a set of transactions
belong to schedule $s$. A graph $G(s)=(V,E)$ is called conflict graph, if
vertices are transactions set and edges are operations with conflict
relations, i.e., if the following holds:

  * •

$V\subset T(s)$;

  * •

$(p_{i}q_{j})\in E\Leftrightarrow t_{i}\neq t_{j}\wedge(p_{i}q_{j})\in
conf(s)$.

We are now ready to introduce a notion of anomalies and consistency in
concurrency systems.

###### Definition 2.7.

(Data Anomalies) A schedule $s$ has anomalies if there exists a cycle in the
conflict graph.

###### Definition 2.8.

We call an anomaly as an entity-based if the anomaly cycle only has entity
conflicts. If there is at least one kind of predicate conflicts, we call it as
predicate-based anomaly.

###### Example 2.9.

If

$\displaystyle s=$ $\displaystyle W_{1}[x_{0}\in Vset(P)]W_{2}[x_{1}\notin
Vset(P)]W_{2}[y_{1}\in Vset(P)]$ $\displaystyle W_{3}[y_{2}\in
Vset(P)]R_{1}[x_{1}\notin Vset(P)]R_{1}[y_{2}\in Vset(P)]C_{1}C_{2}$

where $t_{1}$ and $t_{2}$ are committed, and $t_{3}$ still active.

The transaction $t_{1}$ inserts an object $x$ in predicate domain set
$Vset(P)$, but the transaction $t_{2}$ updates it and move it out. The
transaction $t_{3}$ updates the object $y$ and the transaction $t_{1}$ read
it.

We have

$\displaystyle\text{Entity conflicts}=$
$\displaystyle\\{W_{1}W_{2}[x],W_{2}W_{3}[y],$ $\displaystyle W_{3}[y_{2}\in
Vset(P)]R_{1}[y_{2}\in Vset(P)]\\}.$ $\text{Predicate
conflict}=\\{W_{2}[x_{1}\notin Vset(P)]R_{1}[x_{1}\notin Vset(P)]\\}.$

###### Example 2.10.

A schedule has two predicate logics and $Vset(P_{1})\bigcap Vset(P_{2})=\phi$,
i.e.,

$\displaystyle s=$ $\displaystyle W_{1}[x_{0}\in Vset(P_{1})]W_{2}[x_{1}\notin
Vset(P_{2})]W_{2}[y_{1}\in Vset(P_{2})]$ $\displaystyle W_{3}[y_{2}\in
Vset(P_{1})]R_{1}[x_{1}\notin Vset(P_{2})]R_{1}[y_{1}\in
Vset(P_{1})]C_{1}C_{2}.$

Firstly, we rewrite the schedule with visible read under non-predicate logic

$s_{1}=W_{1}[x_{0}]W_{2}[x_{1}]W_{2}[y_{1}]W_{3}[y_{2}]R_{1}[y_{1}].$

We have the entity conflicts set

$\text{Entity conflict}=\\{W_{1}W_{2}[x],W_{2}W_{3}[y],W_{3}R_{1}[y]\\}.$

The only invisible read operation is $R_{1}[x_{1}\notin Vset(P_{2})]$. We
choice operations with the predicate $P_{2}$

$\text{Predicate conflict}=\\{W_{2}[x_{1}\notin Vset(P_{2})]R_{1}[x_{1}\notin
Vset(P_{2})]\\}.$

So the conflict graph is shown as fig.1.

Figure 1. Conflict graphs of example 2.

According to the definition of consistency, there may be multiple cycles in a
conflict graph. Just one cycle can be a crucial disturbance in the system.
Therefore, we specify the earliest cycle that appeared in the conflict graph
to be studied. We prove that a conflict cycle constructed by an object at most
has two transactions, and a conflict cycle constructed by $n$ objects at most
has $2n$ transactions, and we use edges to classify them.

###### Definition 2.11.

(Data Anomalies Types) In the conflict graph formed by conflicts, we separate
into three types of anomalies based on the operations on the edges.

  * A1:

We defined a conflict graph with a cycle as Read Anomaly Type, RAT, if the
graph has a $WR$ edge at least, i.e., for a graph $G=\\{V,E\\}$ with $\exists
WR\in E$.

  * A2:

We defined a conflict graph with a cycle as Write Anomaly Type, WAT, if the
graph does not contain $WR$ edges, but contain at least a $WW$ edge, i.e.,for
a graph $G=\\{V,E\\}$ with $(\forall WR\notin E)\wedge(\exists WW\in E)$.

  * A3:

We defined a conflict graph with a cycle as Intersect Anomaly Type, IAT, if
the graph does not contain $WW$ edges, also does not contain $WR$ edges,
i.e.,for a graph $G=\\{V,E\\}$ with $(\forall WW\notin E)\wedge(\forall
WR\notin E)$.

Table 2. Combinations of bilateral cycles with predicate relations. Types of Anomalies | Edges Combanations | Anomalies | Partially ordered combination with predicate | Classification
---|---|---|---|---
SDA | $W-W-W[x]$ | Full-write | $W-W-W[x]$ | Entity-based
SDA | $W-W-R[x]$ | Lost Self Update | $W_{i}[x]-W_{j}[x\in Vset(P)]-R_{i}[x\in Vset(P)]$ | Entity-based
$W_{i}[x]-W_{j}[x\notin Vset(P)]-R_{i}[x\notin Vset(P)]$ | Predicate-based
SDA | $W-R-W[x]$ | Intermediate Read | $W_{i}[x\in Vset(P)]-R_{j}[x\in Vset(P)]-W_{i}[x\in Vset(P)]$ | Entity-based
$W_{i}[x\in Vset(P)]-R_{j}[x\in Vset(P)]-W_{i}[x\notin Vset(P)]$ | Predicate-based
$W_{i}[x\notin Vset(P)]-R_{j}[x\notin Vset(P)]-W_{i}[x\in Vset(P)]$ | Predicate-based
SDA | $R-W-W[x]$ | Lost Update | $R_{i}[x\in Vset(P)]-W_{j}[x\in Vset(P)]-W_{i}[x]$ | Entity-based
$R_{i}[x\in Vset(P)]-W_{j}[x\notin Vset(P)]-W_{i}[x]$ | Predicate-based
$R_{i}[x\notin Vset(P)]-W_{j}[x\in Vset(P)]-W_{i}[x]$ | Predicate-based
SDA | $R-W-R[x]$ | Non-repeatable Read | $R_{i}[x\in Vset(P)]-W_{j}[x\in Vset(P)]-R_{i}[x\in Vset(P)]$ | Entity-based
$R_{i}[x\notin Vset(P)]-W_{j}[x\in Vset(P)]-R_{i}[x\in Vset(P)]$ | Predicate-based
$R_{i}[x\in Vset(P)]-W_{j}[x\notin Vset(P)]-R_{i}[x\notin Vset(P)]$ | Predicate-based
DDA | $WW[x]-WW[y]$ | Full-write Skew | $WW[x]-WW[y]$ | Entity-based
DDA | $WW[x]-WR[y]$ | Double-write Skew 2 | $WW[x]-W[y\in Vset(P)]R[y\in Vset(P)]$ | Entity-based
$WW[x]-W[y\notin Vset(P)]R[y\notin Vset(P)]$ | Predicate-based
DDA | $WW[x]-RW[y]$ | Read-Write Skew 2 | $WW[x]-R[y\in Vset(P)]W[y\in Vset(P)]$ | Entity-based
$WW[x]-R[y\notin Vset(P)]W[y\in Vset(P)]$ | Predicate-based
$WW[x]-R[y\in Vset(P)]W[y\notin Vset(P)]$ | Predicate-based
DDA | $WR[x]-WW[y]$ | Double-Write Skew 1 | $W[x\in Vset(P)]R[x\in Vset(P)]-WW[y]$ | Entity-based
$W[x\notin Vset(P)]R[x\notin Vset(P)]-WW[y]$ | Predicate-based
DDA | $WR[x]-WR[y]$ | Write-Read Skew | $W[x\in Vset(P)]R[x\in Vset(P)]-W[y\in Vset(P)]R[y\in Vset(P)]$ | Entity-based
$W[x\in Vset(P)]R[x\in Vset(P)]-W[y\notin Vset(P)]R[y\notin Vset(P)]$ | Predicate-based
$W[x\notin Vset(P)]R[x\notin Vset(P)]-W[y\in Vset(P)]R[y\in Vset(P)]$ | Predicate-based
$W[x\notin Vset(P)]R[x\notin Vset(P)]-W[y\notin Vset(P)]R[y\notin Vset(P)]$ | Predicate-based
DDA | $WR[x]-RW[y]$ | Read Skew 2 | $W[x\in Vset(P)]R[x\in Vset(P)]-R[y\in Vset(P)]W[y\in Vset(P)]$ | Entity-based
$W[x\in Vset(P)]R[x\in Vset(P)]-R[y\in Vset(P)]W[y\notin Vset(P)]$ | Predicate-based
$W[x\in Vset(P)]R[x\in Vset(P)]-R[y\notin Vset(P)]W[y\in Vset(P)]$ | Predicate-based
$W[x\notin Vset(P)]R[x\notin Vset(P)]-R[y\in Vset(P)]W[y\in Vset(P)]$ | Predicate-based
$W[x\notin Vset(P)]R[x\notin Vset(P)]-R[y\in Vset(P)]W[y\notin Vset(P)]$ | Predicate-based
$W[x\notin Vset(P)]R[x\notin Vset(P)]-R[y\notin Vset(P)]W[y\in Vset(P)]$ | Predicate-based
DDA | $RW[x]-WW[y]$ | Read-Write Skew 1 | $R[x\in Vset(P)]W[x\in Vset(P)]-WW[y]$ | Entity-based
$R[x\in Vset(P)]W[x\notin Vset(P)]-WW[y]$ | Predicate-based
$R[x\notin Vset(P)]W[x\in Vset(P)]-WW[y]$ | Predicate-based
DDA | $RW[x]-WR[y]$ | Read Skew | $R[x\in Vset(P)]W[x\in Vset(P)]-W[y\in Vset(P)]R[y\in Vset(P)]$ | Entity-based
$R[x\in Vset(P)]W[x\notin Vset(P)]-W[y\in Vset(P)]R[y\in Vset(P)]$ | Predicate-based
$R[x\notin Vset(P)]W[x\in Vset(P)]-W[y\in Vset(P)]R[y\in Vset(P)]$ | Predicate-based
$R[x\in Vset(P)]W[x\in Vset(P)]-W[y\notin Vset(P)]R[y\notin Vset(P)]$ | Predicate-based
$R[x\in Vset(P)]W[x\notin Vset(P)]-W[y\notin Vset(P)]R[y\notin Vset(P)]$ | Predicate-based
$R[x\notin Vset(P)]W[x\in Vset(P)]-W[y\notin Vset(P)]R[y\notin Vset(P)]$ | Predicate-based
DDA | $RW[x]-RW[y]$ | Write Skew | $R[x\in Vset(P)]W[x\in Vset(P)]-R[y\in Vset(P)]W[y\in Vset(P)]$ | Entity-based
$R[x\in Vset(P)]W[x\notin Vset(P)]-R[y\in Vset(P)]W[y\in Vset(P)]$ | Predicate-based
$R[x\notin Vset(P)]W[x\in Vset(P)]-R[y\in Vset(P)]W[y\in Vset(P)]$ | Predicate-based
$R[x\in Vset(P)]W[x\in Vset(P)]-R[y\notin Vset(P)]W[y\in Vset(P)]$ | Predicate-based
$R[x\in Vset(P)]W[x\notin Vset(P)]-R[y\notin Vset(P)]W[y\in Vset(P)]$ | Predicate-based
$R[x\notin Vset(P)]W[x\in Vset(P)]-R[y\notin Vset(P)]W[y\in Vset(P)]$ | Predicate-based
$R[x\in Vset(P)]W[x\in Vset(P)]-R[y\in Vset(P)]W[y\notin Vset(P)]$ | Predicate-based
$R[x\in Vset(P)]W[x\notin Vset(P)]-R[y\in Vset(P)]W[y\notin Vset(P)]$ | Predicate-based
$R[x\notin Vset(P)]W[x\in Vset(P)]-R[y\in Vset(P)]W[y\notin Vset(P)]$ | Predicate-based

###  2.4. Simplify of Conflict cycles

###### Theorem 2.12.

If a single object from 3-transactions constitutes a cycle, the conflict graph
can be reduced to a cycle between two transactions.

###### Proof.

Suppose the conflict graph is
$G=\\{\\{t_{1},t_{2},t_{3}\\},\\{(p_{1}q_{2}[x]),\\\
(p_{2}q_{3}[x]),(p_{3}q_{1}[x])\\}\\}$ which $(pq)$ be one of
$\\{WW,WR,RW\\}$.

When $p_{1}=W$ in $(p_{1}q_{2}[x])$, no matter what operation $p_{2}$ (W or R)
is, there will be a conflict relationship $(p_{1}p_{2}[x])$ or
$(p_{2}p_{1}[x])$. If $(p_{2}p_{1}[x])$, there is a two transactions graph
$G^{\prime}=\\{\\{t_{1},t_{2}\\},\\{(p_{2}p_{1}[x]),\\\
(p_{1}q_{2}[x])\\}\\}$. If $(p_{1}p_{2}[x])$, because of existing the conflict
relationship $(p_{2}q_{3}[x])$, then we have $p_{1}<_{s}p_{2}<_{s}q_{3}$,
which means that it has the conflict relationship $(p_{1}q_{3})$. So we get
the two transaction graph
$G^{\prime}=\\{\\{t_{1},t_{3}\\},\\{(p_{1}q_{3}[x]),(p_{3}q_{1}[x])\\}\\}$

When $p_{1}=R$ in $(p_{1}q_{2}[x])$, $q_{2}$ can only be $W$ to constitute the
conflict. No matter what operation $p_{3}$ (W or R) in $(p_{3}q_{1}[x])$ is,
there will be a conflict relationship $(q_{2}p_{3}[x])$ or $(p_{3}q_{2}[x])$.
If $(q_{2}p_{3}[x])$, because of existing the conflict relationship
$(p_{3}q_{1}[x])$, then we have $q_{2}<_{s}p_{3}<_{s}q_{1}$, which means that
it has the conflict relationship $(q_{2}q_{1})$. So we get the two transaction
graph
$G^{\prime}=\\{\\{t_{1},t_{2}\\},\\{(p_{1}q_{2}[x]),(q_{2}q_{1}[x])\\}\\}$. If
$(p_{3}q_{2}[x])$, it exists the conflict relationship $(p_{2}q_{3}[x])$. So
we get the two transaction graph
$G^{\prime}=\\{\\{t_{2},t_{3}\\},\\{(p_{2}q_{3}[x]),(p_{3}q_{2}[x])\\}\\}$. ∎

###### Example 2.13.

The 3-transactions conflict cycle can be reduced to the 2-transactions ones,
and the reduction process is shown in Figure 2.

Figure 2. Reduction processes of 3-transactions conflict cycle.

###### Theorem 2.14.

The multi-transaction $(\geq 3)$ conflict cycle with a single object can be
reduced to a 2-transactions cycle.

###### Proof.

Suppose the conflict graph is $G=\\{\\{t_{1},t_{2},\dots t_{n}\\},\\\
\\{(p_{1}q_{2}[x]),(p_{2}q_{3}[x]),\dots,(p_{n}q_{1}[x])\\}\\}$ which $(pq)$
also be one of $\\{WW,WR,RW\\}$. We have proved $n=3$ in theorem 2.12.

Suppose when $N_{T}<n$ the theorem is true. When $N_{T}=n$, edges of the
conflict cycle is
$E(n)=(p_{1}q_{2}),(p_{2}q_{3}),\dots,(p_{n-1}q_{n}),(p_{n}q_{1})$.

When $p_{1}=W$ in $(p_{1}q_{2}[x])$, no matter what operation $p_{n-1}$ (W or
R) is, there will be a conflict relationship $(p_{1}p_{n-1}[x])$ or
$(p_{n-1}p_{1}[x])$.If $(p_{1}p_{n-1}[x])$, because of existing the conflict
relationship $(p_{n-1}q_{n}[x])$, then we get a 3-transaction conflict graph
$G^{\prime}=\\{\\{t_{1},t_{n-1},t_{n}\\},\\{(p_{1}p_{n-1}[x]),(p_{n-1}q_{n}[x]),(p_{n}q_{1}[x])\\}\\}$.
According to the theorem 2.12, $G^{\prime}$ can be reduced to a 2-transactions
conflict cycle.If $(p_{n-1}p_{1}[x])$, because of existing the conflict
relationship $(p_{n-2}q_{n-1}[x])$, then we get a $n-1$-transaction conflict
graph
$G^{\prime}=\\{\\{t_{1},t_{2},\dots,t_{n-1}\\},\\{(p_{1}q_{2}[x]),$$\dots,$$(p_{n-2}q_{n-1}[x]),$
$(p_{n-1}p_{1}[x])\\}\\}$. According to the assumption, the graph $G^{\prime}$
can be reduced to a 2-transaction conflict cycle.

When $p_{1}=R$ in $(p_{1}q_{2}[x])$, $q_{2}$ can only be $W$ to constitute the
conflict. No matter what operation $p_{n}$ (W or R) in $(p_{n}q_{1}[x])$ is,
there will be a conflict relationship $(q_{2}p_{n}[x])$ or $(p_{n}q_{2}[x])$.
If $(q_{2}p_{n}[x])$, because of existing conflict relationships
$(p_{1}q_{2}[x])$, then we have $p_{1}<_{s}q_{2}<_{s}p_{n}$, which means that
it has the conflict relationship $(p_{1}p_{n})$. So we get the two transaction
graph
$G^{\prime}=\\{\\{t_{1},t_{n}\\},\\{(p_{1}p_{n}[x]),(p_{n}q_{1}[x])\\}\\}$. If
$(p_{n}q_{2}[x])$, because of existing conflict relationships
$(p_{n}q_{1}[x])$, then we get a $n-1$-transaction conflict graph
$G^{\prime}=\\{\\{t_{2},t_{3},\dots,t_{n}\\},\\{(p_{2}q_{3}[x]),\dots,(p_{n-1}q_{n}[x]),\\\
(p_{n}q_{2}[x])\\}\\}$. According to the assumption, the graph $G^{\prime}$
can be reduced to a 2-transaction conflict cycle. ∎

###### Example 2.15.

The 5-transactions conflict cycle can be reduced to the 2-transactions
conflict cycle, and the reduction process is shown in Figure 3.

Figure 3. Reduction processes of 5-transactions conflict cycle.

According to Theorems 2.12 and 2.14, if only one object in the conflict cycle,
it can be reduced to a 2-transactions cycle. Therefore, a univariate circle
can easily detect a three-operation circle $O_{i}-O_{j}-O_{i}$.

###### Theorem 2.16.

If there are $n$ adjacent edges in conflict graph operation on the same
variable, it can be reduced to one or two adjacent edges, otherwise it will
form a 2-transactions conflicts cycle by itself.

###### Proof.

Suppose the conflict graph if $G={V,E}$, where $V$ is the set of transactions
have conflict relations $V={t_{1},t_{2},\dots,t_{n}}$, and $E$ is the set of
conflict relations
$E=\\{(p_{1}q_{2}),(p_{2}q_{3}),\dots,(p_{n-1}q_{n})\\}[x]$.

When $p_{1}=W$ in $(p_{1}q_{2})$, no matter what the operation $p_{n-1}$(W or
R) is, there is a conflict relationship$(p_{1}p_{n-1})$ or $(p_{n-1}p_{1})$.
If $(p_{1}p_{n-1})$, we have $p_{1}<_{s}p_{n-1}<_{s}q_{n}$ by the existing
conflict relation $(p_{n-1}q_{n})$. Thus these adjacent edges in the conflict
graph can be reduced to one adjacent edges $E=\\{(p_{1}q_{n})\\}$. If
$(p_{n-1}p_{1})$, it will be a cycle graph
$G^{\prime}=\\{V^{\prime},E^{\prime}\\}$ with
$E^{\prime}=\\{(p_{n-1}p_{1}),(p_{1}q_{2}),\dots,\\\ (p_{n-2}q_{n-1})\\}$.
Thus the graph $G^{\prime}$ can be reduced to a 2-transactions cycle which is
proved by theorem 2.14.

When $p_{1}=R$ in $(p_{1}q_{2})$, $q_{2}$ only can be $W$ to constitute the
conflict relation. no matter what the operation $p_{n-1}$(W or R) is, there is
a conflict relationship$(q_{2}p_{n-1})$ or $(p_{n-1}q_{2})$. If
$(q_{2}p_{n-1})$, we have $q_{2}<_{s}p_{n-1}<_{s}q_{n}$ by the existing
conflict relation $(q_{2}q_{n})$. Thus these adjacent edges in the conflict
graph can be reduced to two adjacent edges
$E=\\{(p_{1}q_{2}),(q_{2},p_{n})\\}$. If $(p_{n-1}q_{2})$, it will be a cycle
graph $G^{\prime}=\\{V^{\prime},E^{\prime}\\}$ with
$E^{\prime}=\\{(p_{n-1}q_{2}),(p_{2}q_{3}),\dots,\\\ (p_{n-2}q_{n-1})\\}$.
Thus the graph $G^{\prime}$ can be reduced to a 2-transactions cycle which is
proved by theorem 2.14. ∎

###### Example 2.17.

As is shown in Figure 4, there are $3$ adjacent edges acting on the same
object $x$ in the conflict graph. It can be reduced to two adjacent edges or a
2-transactions cycle graph.

Figure 4. Reduction processes of 5-transactions adjacent edges.

###### Theorem 2.18.

If there are $2$ edges of the same object with gaps in the conflict cycle, it
can be reduced to one or two adjacent edges in the cycle graph.

###### Proof.

Suppose the conflict cycle graph is $G=\\{V,E\\}$, where $V$ is the set of
transactions $V=\\{t_{1},t_{2},\dots,t_{n}\\}$, and $E$ is the set of conflict
relations
$E=\\{(p_{1}q_{2}[obj_{1}]),(p_{2}q_{3}[obj_{2}]),\dots,(p_{n}q_{1}[obj_{n}])\\}$.
If there are two partial edges with gaps on the same object
$(p_{i}q_{j}[obj])$ and $(p_{s}q_{t}[obj])$ for $j<s-1<s$.

When $p_{i}=W$ in $(p_{i}q_{j})$, no matter what the operation $p_{s}$(W or R)
is, there is a conflict relationship$(p_{i}p_{s})$ or $(p_{s}p_{i})$. If
$(p_{i}p_{s})$, we have $p_{i}<_{s}p_{s}<_{s}q_{t}$ by the existing conflict
relation $(p_{s}q_{t})$. Thus edges in the conflict graph can be reduced to
one adjacent edges $E=\\{\dots,(p_{i}q_{n})[obj],\dots\\}$. If $(p_{s}p_{i})$,
it will be a cycle graph $G^{\prime}=\\{V^{\prime},E^{\prime}\\}$ with
$E^{\prime}=\\{(p_{s}p_{i})[obj],(p_{i}q_{j})[obj],\dots,(p_{s-1}q_{s})[obj_{s-1}]\\}$.
Thus the two edges with gaps are merged together.

When $p_{i}=R$ in $(p_{i}q_{j})$, $q_{j}$ only can be $W$ to constitute the
conflict relation. no matter what the operation $p_{s}$(W or R) is, there is a
conflict relationship$(q_{2}p_{s})$ or $(p_{s}q_{2})$. If $(q_{2}p_{s})$, we
have $q_{2}<_{s}p_{s}<_{s}q_{t}$ by the existing conflict relation
$(q_{2}q_{t})$. Thus gaps edges in the conflict graph can be reduced to two
adjacent edges $E=\\{(p_{i}q_{j}),(q_{j},p_{t})\\}$. If $(p_{s}q_{j})$, it
will be a cycle graph $G^{\prime}=\\{V^{\prime},E^{\prime}\\}$ with
$E^{\prime}=\\{(p_{s}q_{2})[obj],(p_{2}q_{3})[obj_{2}],\dots,(p_{s-1}q_{s})[obj_{s-1}]\\}$.
Thus the two edges with gaps are merged together. ∎

###### Example 2.19.

We simplify the 3-objects and 5-transactions conflict cycle, and the
procession is shown in Figure 5. We reduce gaps about edges about object $x$.

Figure 5. Reduction processes of 5-transactions partially ordered cycle .

Based on the theorem 2.16 and the theorem 2.18, we can merge the operation on
the same objects and the longest operations are two edges as $RW[x]-WR[x]$ for
a conflict cycle graph. Therefore, the edges of the conflict cycle graph can
be sorted according to the order for appearance of the objects. And there are
only $2N_{obj}$ edge sets at most (figure6), where $N_{obj}$ is the number of
objects in a cycle.

Figure 6. The maximum conflict cycle graph of multi-transactions with
$N$-objects.

###### Example 2.20.

We summarize all possible forms of the one-object conflict cycle graph.
According to the theorem 2.12 and 2.14, there are 2 transactions in the cycle.
The possible combinations are as follows

$R_{1}W_{2}[x]-R_{2}W_{1}[x];\quad R_{1}W_{2}[x]-W_{2}R_{1}[x];\quad
R_{1}W_{2}[x]-W_{2}W_{1}[x];$ $W_{1}R_{2}[x]-R_{2}W_{1}[x];\quad
W_{1}R_{2}[x]-W_{2}R_{1}[x];\quad W_{1}R_{2}[x]-W_{2}W_{1}[x];$
$W_{1}W_{2}[x]-R_{2}W_{1}[x];\quad W_{1}W_{2}[x]-W_{2}R_{1}[x];\quad
W_{1}W_{2}[x]-W_{2}W_{1}[x].$

###### Example 2.21.

We summarize all possible forms of the two-objects conflict cycle graph.
Suppose that the two-objects conflict cycle graph is $G=\\{V,E\\}$, where $V$
is the set of transactions, $E$ is conflicts as $\\{WW,WR,RW\\}$, and the
objects is $\\{x,y\\}$. According to the theorem 2.16 and the theorem 2.18,
there are at most 4 transactions in the cycle, and the corresponding conflicts
is $R_{1}W_{2}[x]-W_{2}R_{3}[x]-R_{3}W_{4}[y]-W_{4}R_{1}[y]$.

If there are three transactions in the cycle, the possible combinations are as
follows.

$R_{1}W_{2}[x]-R_{2}W_{3}[y]-W_{3}R_{1}[y];\quad
R_{1}W_{2}[x]-W_{2}R_{3}[x]-R_{3}W_{1}[y];$
$W_{1}R_{2}[x]-R_{2}W_{3}[y]-W_{3}R_{1}[y];\quad
R_{1}W_{2}[x]-W_{2}R_{3}[x]-W_{3}R_{1}[y];$
$W_{1}W_{2}[x]-R_{2}W_{3}[y]-W_{3}R_{1}[y];\quad
R_{1}W_{2}[x]-W_{2}R_{3}[x]-W_{3}W_{1}[y].$

If there are two transactions in the cycle, the possible combinations are as
follows.

$R_{1}W_{2}[x]-R_{2}W_{1}[y];\quad R_{1}W_{2}[x]-W_{2}R_{1}[y];\quad
R_{1}W_{2}[x]-W_{2}W_{1}[y];$ $W_{1}R_{2}[x]-R_{2}W_{1}[y];\quad
W_{1}R_{2}[x]-W_{2}R_{1}[y];\quad W_{1}R_{2}[x]-W_{2}W_{1}[y];$
$W_{1}W_{2}[x]-R_{2}W_{1}[y];\quad W_{1}W_{2}[x]-W_{2}R_{1}[y];\quad
W_{1}W_{2}[x]-W_{2}W_{1}[y].$

We combine conflicting partial orders containing predicate relations
constructing a cycle. If the second type of conflict is contained in the
cycle, it is a predicate type data anomaly. Otherwise, it is an entity type
data anomaly. All the combinations of bilateral cycles are shown in Table 2.

Table 3. Data anomaly classification, formal expression, and their edges combinations in the conflict cycles. $N_{D}$ stands for the number of edges. Types of Anomalies | Anomalies | Mathematical Patterns | Edges Combinations
---|---|---|---
RAT | SDA | Dirty Read | $W_{i}[x_{m}]\dots R_{j}[x_{m}]\dots A_{i}$ | $W_{i}R_{j}[x]-R_{j}A_{i}[x]$
SDA | Non-repeatable Read | $R_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots R_{i}[x_{m+1}]$ | $R_{i}W_{j}[x]-W_{j}R_{i}[x]$
SDA | Intermediate Read | $W_{i}[x_{m}]\dots R_{j}[x_{m}]\dots(C_{j})\dots W_{i}[x_{m+1}]$ | $W_{i}R_{j}[x]-R_{j}W_{i}/R_{j}C_{j}W_{i}[x]$
DDA | Write-Read Skew Committed | $W_{i}[x_{m}]\dots R_{j}[x_{m}]\dots W_{j}[y_{n}]\dots C_{j}\dots R_{i}[y_{n}]$ | $W_{i}R_{j}[x]-W_{j}C_{j}R_{i}[y]$
DDA | Double-Write Skew 1 Committed | $W_{i}[x_{m}]\dots R_{j}[x_{m}]\dots W_{j}[y_{n}]\dots C_{j}\dots W_{i}[y_{n+1}]$ | $W_{i}R_{j}[x]-W_{j}C_{j}W_{i}[y]$
DDA | Write-Read Skew | $W_{i}[x_{m}]\dots R_{i}[x_{m}]\dots W_{j}[y_{n}]\dots R_{i}[y_{n}]$ | $W_{i}R_{j}[x]-W_{j}R_{i}[y]$
DDA | Read Skew | $R_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots W_{j}[y_{n}]\dots R_{i}[y_{n}]$ | $R_{i}W_{j}[x]-W_{j}R_{i}[y]$
DDA | Read Skew 2 | $W_{i}[x_{m}]\dots R_{j}[x_{m}]\dots R_{j}[y_{n}]\dots(C_{j})\dots W_{i}[y_{n+1}]$ | $W_{i}R_{j}[x]-R_{j}W_{i}[y]/C_{j}[y]$
MDA | Step RAT |  $\dots W_{i}[x_{m}]\dots R_{i}[x_{m}]\dots$, and $N_{D}\geq 3$ |
WAT | SDA | Dirty Write | $W_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots A_{i}/C_{i}$ | $W_{i}W_{j}[x]-W_{j}A_{i}/C_{i}[x]$
SDA | Lost Self Update Committed | $W_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots C_{j}\dots R_{i}[x_{m+1}]$ | $W_{i}W_{j}/W_{i}R_{j}[x]-W_{j}C_{j}R_{i}[x]/W_{i}[x]$
SDA | Full-Write Committed | $W_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots C_{j}\dots W_{i}[x_{m+2}]$ | $W_{i}W_{j}[x]-R_{j}C_{j}W_{i}[x]$
SDA | Full-Write | $W_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots W_{i}[x_{m+2}]$ |  |  $W_{i}W_{j}/W_{i}R_{j}[x]-W_{j}W_{i}[x]$ or
---
$W_{i}W_{j}[x]-R_{j}W_{i}[x]$
SDA | Lost Update | $R_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots W_{i}[x_{m+2}]$ | $R_{i}W_{j}[x]-W_{j}W_{i}/R_{j}W_{i}[x]$
SDA | Lost Self Update | $W_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots R_{i}[x_{m+1}]$ | $W_{i}W_{j}/W_{i}R_{j}[x]-W_{j}R_{i}[x]$
DDA | Double-Write Skew 2 Committed | $W_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots W_{j}[y_{n}]\dots C_{j}\dots R_{i}[y_{n}]$ | $W_{i}W_{j}[x]-W_{j}C_{j}R_{i}[y]$
DDA | Full-Write Skew Committed | $W_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots W_{j}[y_{n}]\dots C_{j}\dots W_{i}[y_{n+1}]$ | $W_{i}W_{j}[x]-W_{j}C_{j}W_{i}[y]$
DDA | Full-Write Skew | $W_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots W_{j}[y_{n}]\dots W_{i}[y_{n+1}]$ | $W_{i}W_{j}[x]-W_{j}W_{i}[y]$
DDA | Double-Write Skew 1 | $W_{i}[x_{m}]\dots R_{j}[x_{m}]\dots W_{j}[y_{n}]\dots W_{i}[y_{n+1}]$ | $W_{i}R_{j}[x]-W_{j}W_{i}[y]$
DDA | Double-Write Skew 2 | $W_{i}[x_{m}]\dots W_{j}[x_{m}]\dots W_{j}[y_{n}]\dots W_{i}[y_{n+1}]$ | $W_{i}W_{j}[x]-W_{j}R_{i}[y]$
DDA | Read-Write Skew 1 | $R_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots W_{j}[y_{n}]\dots W_{i}[y_{n+1}]$ | $R_{i}W_{j}[x]-W_{j}W_{i}[y]$
DDA | Read-Write Skew 2 | $W_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots R_{j}[y_{n}]\dots(C_{j})\dots W_{i}[y_{n+1}]$ |  |  $W_{i}W_{j}[x]-R_{j}(C_{j})W_{i}[y]$ or
---
$W_{i}W_{j}[x]-R_{j}C_{j}W_{i}[y]$
MDA | Step WAT |  $\dots W_{i}[x_{m}]\dots W_{i}[x_{m+1}]\dots$, and $N_{D}\geq 3$, |
and not include $(\dots W_{j}[x_{m}]\dots R_{j}[x_{m}]\dots)$ |
IAT | SDA | Non-repeatable Read Committed | $R_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots C_{j}\dots R_{i}[x_{m+1}]$ | $R_{i}W_{j}[x]-W_{j}C_{j}R_{i}[x]$
SDA | Lost Update Committed | $R_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots C_{j}\dots W_{i}[x_{m+2}]$ | $R_{i}W_{j}[x]-W_{j}C_{j}W_{i}/R_{j}C_{j}W_{i}[x]$
DDA | Read Skew Committed | $R_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots W_{j}[y_{n}]\dots C_{j}\dots R_{i}[y_{n}]$ | $R_{i}W_{j}[x]-W_{j}C_{j}R_{i}[y]$
DDA | Read-Write Skew 1 Committed | $R_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots W_{j}[y_{n}]\dots C_{j}\dots W_{i}[y_{n+1}]$ | $R_{i}W_{j}[x]-W_{j}C_{j}W_{i}[y]$
DDA | Write Skew | $R_{i}[x_{m}]\dots W_{j}[x_{m+1}]\dots R_{j}[y_{n}]\dots(C_{j})\dots W_{i}[y_{n+1}]$ | $R_{i}W_{j}[x]-R_{j}(C_{j})W_{i}[y]$
MDA | Step IAT |  Not include $(\dots W_{i}[x_{m}]\dots R_{i}[x_{m}]\dots$ |
and $\dots W_{j}[x_{m}]\dots W_{j}[x_{m+1}]\dots)$, $N_{D}\geq 3$ |

###  2.5. Conflict relations add Status

The impact of abort and commit in data consistency is also important
operations besides reading and writing. Therefore, we add these two operations
to the first type of conflict dependencies. Let $t_{i},t_{j}$ be transactions
in a schedule $s$, $t_{i}<_{s}t_{j}$. Two operations $p_{i}\in t_{i}$ and
$q_{j}\in t_{j}$ are conflicts. Let $U$ reflect the status of the transaction
still activates. Then conflicts can be extended to several situations below:

  * 1.

$p_{i}-C_{i}-q_{j}-A_{j}/C_{j}/U_{j}$: The transaction $t_{i}$ is committed
before the $t_{j}$ operations;

  * 2.

$p_{i}-A_{i}-q_{j}-A_{j}/C_{j}/U_{j}$: The transaction $t_{i}$ is aborted
before the $t_{j}$ operations;

  * 3.

$p_{i}-q_{j}-C_{i}-A_{j}/C_{j}/U_{j}$: The transaction $t_{i}$ is committed
after the $t_{j}$ operations;

  * 4.

$p_{i}-q_{j}-A_{i}-A_{j}/C_{j}/U_{j}$: The transaction $t_{i}$ is aborted
after the $t_{j}$ operations;

  * 5.

$p_{i}-q_{j}-C_{j}-A_{i}/C_{i}/U_{i}$: The transaction $t_{j}$ is committed
after the conflict operations;

  * 6.

$p_{i}-q_{j}-A_{j}-A_{i}/C_{i}/U_{i}$: The transaction $t_{j}$ is aborted
after the conflict operations.

  * 7.

$p_{i}-q_{j}=\\{p_{i}-U_{i}-q_{j}-U_{j},p_{i}-q_{j}-U_{i}-U_{j},p_{i}-q_{j}-U_{j}-U_{i}\\}$:
Both transactions $t_{i}$ and $t_{j}$ are still active.

Where situations $1-4$ are $t_{i}$ submitted or rolled back before $t_{j}$
operation, denoted as $(p_{i},A_{i}/C_{i},q_{j})$ or
$(p_{i},q_{j},A_{i}/C_{i})$. Situations $5-6$ are $t_{j}$ submitted or rolled
back before $t_{i}$ operation, denoted as $(p_{i},q_{j},A_{j}/C_{j})$;
situation $7$ describes that both transactions in scheduling $s$ are not
completed, denoted as $(p_{i},q_{j})$. i.e.,

$conf(s)=\\{(p_{i},A_{i}/C_{i},q_{j}),(p_{i},q_{j},A_{i}/C_{i}),(p_{i},q_{j},A_{j}/C_{j}),(p_{i},p_{j})\\}$

. In the situation $2$, due to the timely rollback of $t_{i}$, the operation
$p_{i}$ will not affect the operation $q_{j}$. So do the situation $6$.
Substituting the three conflict dependencies $pq\in\\{WW,WR,RW\\}$ into the
remaining 5 cases we can get 15 cases. Among them, $W_{i}W_{j}C_{j}$ indicate
the committed $t_{j}$ after the conflict operations which has the same meaning
of $W_{i}W_{j}$. So as $W_{i}R_{j}$ and $W_{i}R_{j}C_{j}$, and $R_{i}W_{j}$
and $R_{i}W_{j}C_{j}$. $W_{i}R_{j}C_{i}$ indicates the $t_{i}$ committed the
operation $W_{i}$ which is same as $W_{i}R_{j}$. $R_{i}W_{j}C_{i}$ and
$R_{i}W_{j}A_{i}$ indicates the $t_{i}$ committed or aborted the operation
$R_{i}$ which cannot disturb the $W_{j}$ of transaction $t_{j}$. So the two
cases are as the same mean as $R_{i}W_{j}$. Through the above discussion,
these fifteen cases are sorted into 9 categories that we calls partial order
pairs(POP).

  * 1.

$W_{i}C_{i}R_{j}=\\{W_{i}C_{i}R_{j}\\}$: The version written by $t_{i}$ and
confirmed to be valid is read by $t_{j}$.

  * 2.

$W_{i}C_{i}W_{j}=\\{W_{i}C_{i}W_{j}\\}$: The version written by $t_{i}$ is
overwritten by $t_{j}$ with a newer version, but legal overwriting will not
cause inconsistent data status;

  * 3.

$R_{i}C_{i}W_{j}=\\{R_{i}C_{i}W_{j}\\}$: The transaction $t_{i}$ committed the
operation $R_{i}$ and the $t_{j}$ rewrite the variable.

  * 4.

$W_{i}W_{j}=\\{W_{i}W_{j},W_{i}W_{j}C_{j}\\}$: The version written by $t_{i}$
is overwritten by $t_{j}$ with a newer version, so that there may be
inconsistent data status;

  * 5.

$W_{i}R_{j}=\\{W_{i}R_{j},W_{i}R_{j}C_{j},W_{i}R_{j}C_{i}\\}$: The version
written by $t_{i}$ read by $t_{j}$;

  * 6.

$R_{i}W_{j}=\\{R_{i}W_{j},R_{i}W_{j}C_{j},R_{i}W_{j}C_{i},R_{i}W_{j}A_{i}\\}$:
The version read by $t_{i}$, which is modified by $t_{j}$ to generate a new
version, which may affect $t_{i}$ to read or modify the same variables;

  * 7.

$W_{i}R_{j}A_{i}=\\{W_{i}R_{j}A_{i}\\}$: The version read by $t_{j}$ is
written by $t_{i}$. After being rolled back by $t_{i}$, $t_{j}$ may read a
non-existent version;

  * 8.

$W_{i}W_{j}C_{i}=\\{W_{i}W_{j}C_{i}\\}$: The version written by $t_{i}$ is
overwritten by the updated version of $t_{j}$, so that the value of the data
item written by $t_{j}$ cannot be read after the occurrence of $C_{i}$.

  * 9.

$W_{i}W_{j}A_{i}=\\{W_{i}W_{j}A_{i}\\}$: The version written by $t_{j}$ was
overwritten by $t_{i}$ with an older version due to rollback.

For the POP $1-6$, we can refine our conflict graph definition. That is to
say, based on (Weikum and Vossen, 2002), the conflict graph we define only
extends the traditional conflict relations types.

Table 4. The comparison between conflict serialization graph and conflict graph of this paper. |  Conflict serialization graph |  Extended conflict graph (We)
---|---|---
Purpose |  Model conflict serialization |  Model data anomalies
#Edge type |  3 (WW,WR,RW) |  9 (in §2.5)
Data structure |  Directed cycle graph |  Directed cycle graph
Expressive ness |  Limited to describe data anomalies, can not describe Dirty write, Dirty read, and Intermediate Reads |  Can express all the data anomalies including new reported and predicate-based anomalies in this paper
Added value |  Correlate to serializable schedule, but not to specific data anomalies |  Correlate directed graph, data anomalies, and consistency together

Obviously, the combination of the POP $7-9$ itself produces a cycle in
conflict graph.We will refine these three types in detail.

In category $7$, we can split ${W_{i}R_{j}A_{i}}$ into ${W_{i}R_{j}[x]}$ and
${R_{j}A_{i}[x]}$, that is, category $7$ and ${R_{j}A_{i}[x]}$ are in the same
variable The combination of operations under $x$, so the category $6$ can be
abbreviated as $R_{j}A_{i}$, which can be expressed as figure 7(a).

(a)

(b)

(c)

Figure 7. The partial order (a) $R_{j}A_{i}$, (b) $W_{j}C_{i}$ or (c)
$W_{j}A_{i}$ constitutes a cycle.

In category $8$, we can split ${W_{i}W_{j}C_{i}}$ into ${W_{i}W_{j}[x]}$ and
${W_{j}C_{i}[x]}$,so the category $8$ can be abbreviated as $W_{j}C_{i}$,
which can be expressed as figure 7(b).

According to Theorems 2.12 and 2.14, a single object can only be a partial
order cycle by $2$-transactions. At the same time, the bilateral cycle may be
at most two variables. We denote the Single-variable by Double-transactions
Anomalies as $SDA$, the Double-variables by Double-transactions Anomalies as
$DDA$, and others denoted $MDA$. Therefore, we show all the combined results
in Table 3 and classify them according to the definition 2.11. Bold fonts in
the table indicate 22 newly added anomalies. Therefore, we get all the data
anomalies types after classification in Table 3.

In Table 3, we did not distinguish conflicts relations with the predicates
domain set. Similarly, if there is a conflicting edge of the predicate-based
conflict in the anomaly cycle, it is a predicate-based anomaly. Otherwise, it
is an entity-based anomaly. The definition of anomalies is also based on the
conflict graph(Table 4), (Adya et al., 2000) only has three kinds of conflict
relations(e.g., can not include Dirty Writes, Dirty Reads and Intermediate
Reads), we have nine kinds of conflict relations, which makes all data
anomalies(e.g., including Dirty Reads) can be included in the extended
conflict graph. To the best of our knowledge, this is the first time to
completely establish a one-to-one mapping of all data anomalies and conflict
graphs.

###### Definition 2.22.

(Consistency) Consistency = Directed acyclic graph = No data anomalies. No
Consistency = Directed cyclic graph = Data anomalies.

##  3\. Quantitative Research

Mastering all data anomalies and being able to classify all data anomalies
mean that we have the opportunity to do some quantitative work. Based on data
anomalies classification, we quantify the probability of various data
anomalies. Then, we quantitatively study the rollback rates of various
concurrency control algorithms in different scenarios.

###  3.1. Setup

We evaluate the YCSB (Cooper et al., 2010) and TPC-C (Council, 2010) benchmark
in a unified transaction processing framework called
3TS111https://github.com/Tencent/3TS. 3TS is a open source research framework
of concurrent control (CC) protocols based on Deneva (Harding et al., 2017),
which carries out quantitative research on data anomalies and CC protocols.

We run all experiments on a single machine with 56 cores (Platinum 8276
<EMAIL_ADDRESS>hyper-threading to 112 threads) and 10 TB memory. The statistics
of workloads are shown in Table 5. The YCSB contention is controlled by the
skew factor of zip distribution access patterns. In our evaluation, low and
high contentions are with 0 and 0.9 values for the skew parameter,
representing uniform and extremely skew distributions, respectively. The Mix
workload consists of 50% Payment and 50% NewOrder workloads.

Table 5. Workload description. u/r/w/i stands for update rate/read/write/insert, sum of the read, read, and insert is 1. Low contention is with uniform distribution of data access while high contention is with zip distribution and extreme skewness of data access. Benchmark | No | Workload | u/r/w/i | Skew
---|---|---|---|---
YCSB | y1 | Main write | 0.9/0.1/0.9/0 | 0.5
y2 | Main read | 0.1/0.9/0.1/0 | 0.5
y3 | Low contention | 0.5/0.5/0.5/0 | 0.0
y4 | High contention | 0.5/0.5/0.5/0 | 0.9
TPCC | t1 | Payment | 1/0.2/0.6/0.2 | -
t2 | Neworder | 1/0.2/0.6/0.2 | -
t3 | Mix | 1/0.2/0.6/0.2 | -

###  3.2. Quantitative Data Anomalies

Understanding the statistics of all anomalies explains the current perspective
of defining anomalies and isolation levels. In this part, we analyze the
property of syntactic histories and analyze the anomaly statistics from these
histories. Internal comprehension of data anomalies is the foundation to
discuss isolation levels as well as the CC protocols. We later show that the
statistics summary is representative of real-life applications, as those
anomalies with higher occurrence probabilities in syntactic histories are also
well-known discovered ones in real-life. We first define the test set in the
following:

###### Definition 3.1.

History Testing Set

$\mathcal{H}(m,n,k)\overset{\text{def}}{\equiv\joinrel\equiv\joinrel\equiv}\\{H\
|\ H.variables=m\wedge H.transactions=n\wedge H.writes+H.reads<k\\}$.

where $H.variables$, $H.transactions$, $H.writes$, and $H.reads$ denote the
number of variables, transactions, write operations, and read operations in
history H, respectively. The history testing set $\mathcal{H}(m,n,k)$ is the
set of full permutation of all histories that have $m$ variables, $n$
transactions, and $k$ write/read operations. We infer that $\mathcal{H}$ has
the following two properties, where the function
$Mutex(\mathcal{H}_{1},\mathcal{H}_{2})$ represents $\mathcal{H}_{1}$ and
$\mathcal{H}_{2}$ are mutually exclusive.:

  * •

If $m_{1}\neq m_{2}$ or $n_{1}\neq n_{2}$ or $k_{1}\neq k_{2}$, then
$\mathcal{H}_{1}(m_{1},n_{1},k_{1})$ and $\mathcal{H}_{2}(m_{2},n_{2},k_{2})$
are mutually exclusive, i.e.,
$\forall m_{1},m_{2},n_{1},n_{2},k_{1},k_{2}\in\mathbb{N}\quad m_{1}\neq
m_{2}\vee n_{1}\neq n_{2}\vee k_{1}\neq k_{2}\Rightarrow
Mutex(\mathcal{H}_{1}(m_{1},n_{1},k_{1}),\mathcal{H}_{2}(m_{2},n_{2},k_{2}))$.

  * •

For any $m_{1},m_{2},n_{1},n_{2}$, if $k_{1}\leq k_{2}$, then
${H}_{1}(m_{1},n_{1},k_{1})$ is subset of ${H}_{2}(m_{2},n_{2},k_{2})$, i.e.,
$\forall m_{1},m_{2},n_{1},n_{2},k_{1},k_{2}\in\mathbb{N}\\\ k_{1}\leq
k_{2}\Rightarrow\mathcal{H}_{1}(m_{1},n_{1},k_{1})\subseteq{H}_{2}(m_{2},n_{2},k_{2})$.

For example, $H_{1}$:$W_{1}[X_{0}],R_{2}[X_{0}],A_{1}$ and $H_{2}$:
$W_{1}[X_{0}],W_{2}[X_{1}],A_{1}$ are example histories of Dirty Read and
Dirty Write anomalies (formally described in Table 3), respectively. They both
belong to $\mathcal{H}(1,2,3)$, as they have one variable, two transactions,
and three operations involved.

Table 6. Evaluation statistic of all data anomalies in static histories generated by by static method (Definition 3.1 with $\mathcal{H}(3,4,7)$). We compute the percentage of each anomaly as well as each category of RAT, WAT, and IAT. In each category, we rank the anomalies by the highest percentage. Class | Sub- | Anomaly name | Perc
---|---|---|---
RAT | SDA | Dirty Read | 16.68%
SDA | Intermediate Read | 5.86%
SDA | Non-repeatable Read | 5.34%
DDA | Read Skew 2 | 1.86%
DDA | Write-Read Skew | 1.59%
DDA | Read Skew | 1.53%
MDA | Step RAT | 0.41%
DDA | Write-Read Skew Committed | 0.26%
DDA | Double-Write Skew 1 Committed | 0.26%
WAT | SDA | Dirty Write | 36.13%
SDA | Full-Write | 11.28%
SDA | Lost Update | 5.31%
DDA | Read-Write Skew 2 | 1.76%
DDA | Double-Write Skew 1 | 1.58%
DDA | Read-Write Skew 1 | 1.53%
DDA | Full-Write Skew | 1.51%
DDA | Double-Write Skew 2 | 1.51%
SDA | Full-Write Committed | 0.74%
MDA | Step WAT | 0.35%
SDA | Lost Self Update | 0.23%
DDA | Full-Write Skew Committed | 0.23%
DDA | Double-Write Skew 2 Committed | 0.23%
SDA | Lost Self Update Committed | 0.04%
IAT | DDA | Write Skew | 1.79%
SDA | Non-repeatable Read Committed | 0.74%
SDA | Lost Update Committed | 0.74%
DDA | Read-Write Skew 1 Committed | 0.23%
DDA | Read Skew Committed | 0.23%
MDA | Step IAT | 0.02%
Table 7. Evaluation statistic of all data anomalies in static histories generated by by static method (Definition 3.1 with $\mathcal{H}(3,4,7)$). We summarize the statistics based on SDA, DDA, and MDA. | SDA | DDA | MDA | Sum
---|---|---|---|---
RAT | 27.88% | 5.51% | 0.41% | 33.79%
WAT | 53.74% | 8.36% | 0.35% | 62.45%
IAT | 1.48% | 2.25% | 0.02% | 3.76%
Sum | 83.10% | 16.12% | 0.78% |
Table 8. Evaluation statistic of all edges percentage by syntactic histories and cycles with $\mathcal{H}(3,2,6)$. Edge | RW | WR | WW | WA | RA | WC | WCR | WCW
---|---|---|---|---|---|---|---|---
History | 23.14% | 22.01% | 21.98% | 10.18% | 10.18% | 10.18% | 1.17% | 1.16%
Cycles | 18.90% | 25.88% | 32.45% | 6.52% | 6.10% | 7.23% | 1.50% | 1.41%

We first show the percentage of different edges in generated history with
parameter $\mathcal{H}(3,2,6)$ in Table 8. For all histories with or without
cycles, we generate them with equal probability. However, histories with
cycles have more WW (32.45%) edge, than WR (25.88%) and RW (18.9%) edges,
meaning WW is more sensitive in forming cycles. We then generate histories
with parameter $\mathcal{H}(3,4,7)$ and compute the percentage of each anomaly
in terms of all cycle histories. Table 6 depicts the statistics of these
syntactic cycle histories. Since a cycle may contain multiple anomalies, we
show the result collected by ranking the priority from RAT and WAT to IAT
based on Table 3. We also collected the statistics in different orders, but
the result shows minor changes. Among all anomalies, Dirty Write with
36.13$\%$ occurrences is the most one. Dirty Read with 16.68$\%$ is the most
one in RAT. We can tell that those with higher probabilities are very close to
known anomalies as they also occur frequently in real-life transaction
processing. Previous isolation levels are defined based on these known
anomalies, leading to solving practical application scenarios. Yet it is not
quantitatively defined, as a newly reported anomaly often can not be
categorized. WAT is more than 60$\%$, as the WW is usually the critical POP in
a cycle. We later also discussed that WW conflicts are unavoidable and tricky
to most CC protocols. IAT is a rare case, and this is where some commercial
databases often sacrifice serializability for performance.

We also summarize $\mathcal{H}(3,4,7)$ histories by SDA, DDA, and MDA in Table
7. The SDA is the most anomalies in RAT and WAT, and in total, it is more than
83$\%$ of all anomalies. SDA occurs more often as they are composed of fewer
operations, thus higher probabilities with a fixed number of read/write
operations. Again, the high probability of SDA occurrence is also revealed in
real-life scenarios, as they are usually known data anomalies. The total
probability of forming SDA and DDA data anomalies is as high as 99.22$\%$. We
show that the anomaly cycle of SDA and DDA has only two edges in Table 3.
Therefore, it should be low cost to detect these anomalies even by the cycle
detection method. The probability of forming MDA data anomalies is only
0.78$\%$. This part of data anomalies may have complicated and dynamic cycle
structures with several edges, which can be extremely expensive for cycle
detection.

For RAT and WAT, their probability is as high as 96.34$\%$. These two types of
data anomalies must be eliminated in order to ensure data consistency. The
probability of IAT is only 3.76$\%$, so solving this part of data anomalies at
a high cost will bring a certain degree of performance loss, this kind of data
anomalies usually depends on the cycle detection algorithm as (Weikum and
Vossen, 2001; Durner and Neumann, 2019). Identifying cycles of conflicts is
usually prohibitive, as the increasing concurrent transactions may produce
exponential overhead (Weikum and Vossen, 2001), however, after solving RAT and
WAT, we can avoid using cycle detection algorithm by eliminating RW conflict
as (Cahill et al., 2008; Yabandeh and Ferro, 2012).

Lesson learned: CC should eliminate SDA and DDA type data anomalies in a low-
cost way. CC also should eliminate RAT and WAT type data anomalies in a low-
cost way. For IAT type data anomalies, CC should trade-off between the cycle
detection algorithm and rolling back transactions.

In the following part, we use this syntactic test set as static histories to
evaluate the rollback rate of CC protocols.

###  3.3. Evaluation of Rollback Rates

Rollback rate is one of the most important factors affecting performance. Some
concurrency control algorithms focus on reducing the rollback rate to improve
performance. However, there is no clear specification on what aspects to
mitigate the rollback rate. To address this, we evaluate the rollback rate by
both static and dynamic methods. The static data is generated by the above
syntactic histories while the dynamic method uses the real-life benchmark,
i.e., TPC-C and YCSB. Observing these rollback rates helps to understand the
behaviors of CC protocols in dealing with anomalies or partial patterns of
these anomalies.

####  3.3.1. The Definition of Rollback Rate

Before comparing the rollback rate with CC protocols, we first introduce the
definition of rollback as well as the True and False rollback rate.

###### Definition 3.2.

Data Anomaly Rollback Forced to rollback due to a data anomaly in concurrent
transactions, i.e., True Rollback (TR).

###### Definition 3.3.

Non-Data Anomaly Rollback Forced to rollback in concurrent transactions
without a data anomaly. Also called False Rollback (FR).

###### Definition 3.4.

Algorithm Rollback Rollback due to CC algorithm’s decision (AR). It includes
TR and FR.

Calculation of Rollback Rate  First, we define some terminologies used in
formulas below.

  * •

Rollback Rate – The True Rollback Rate (TRR) is the percentage of histories
with cycles. The False Rollback Rate (FRR) is the percentage of histories are
not cycles but CC protocols still abort based on their rules. We denote
algorithm rollback rate as $R_{alg}$.

  * •

Number Of Transactions – We denote the total number of transactions as $N$,
number of transactions rolled back by concurrency control algorithm as
$N_{alg}$, number of transactions truly rolled back as $N_{true}$.

$None$ $R_{alg}=\cfrac{N_{alg}}{N}=TRR+FRR$ $None$ $TRR=\cfrac{N_{true}}{N}$
$None$ $FRR=R_{alg}-TRR$

Table 9. Evaluation result of static rollback rate. TRR and FRR stand for ture and false rollback rate, respectively. | ALL | OCC | MaaT | MVTO | TO | SSI | No$\\_$wait
---|---|---|---|---|---|---|---
| TRR | FRR | FRR | FRR | FRR | FRR | FRR
$\mathcal{H}$ (2,2,6) | 69.82% | 3.48% | 3.97% | 1.53% | 1.68% | 1.72% | 0.90%
$\mathcal{H}$ (3,2,6) | 72.91% | 3.36% | 3.94% | 0.75% | 0.87% | 1.41% | 6.88%
$\mathcal{H}$ (2,3,6) | 52.09% | 7.71% | 8.82% | 3.29% | 3.73% | 3.53% | 2.66%
$\mathcal{H}$ (2,4,6) | 42.13% | 9.83% | 11.37% | 4.16% | 4.80% | 4.31% | 30.19%
$\mathcal{H}$ (3,4,6) | 46.40% | 21.86% | 25.95% | 4.36% | 6.01% | 8.66% | 45.41%
$\mathcal{H}$ (3,4,7) | 58.36% | 20.17% | 23.22% | 5.28% | 6.45% | 8.92% | 38.26%
Table 10. Rollback rate evaluation result of benchmark Workloads. The workloads are described in Table 5 Workload | OCC | MaaT | MVTO | TO | SSI |  No$\\_$wait
---|---|---|---|---|---|---
y1 | 0.09% | 0.03% | 0.01% | 0.01% | 0.05% | 0.02%
y2 | 0.00% | 0.00% | 0.00% | 0.00% | 0.00% | 0.00%
y3 | 0.04% | 0.01% | 0.00% | 0.00% | 0.01% | 0.01%
y4 | 14.86% | 68.81% | 11.54% | 9.56% | 47.51% | 14.56%
t1 | 11.19% | 9.33% | 0.05% | 0.03% | 4.98% | 4.41%
t2 | 5.10% | 4.04% | 0.19% | 0.18% | 5.28% | 4.71%
t3 | 12.69% | 11.89% | 1.21% | 1.54% | 5.07% | 12.02%

####  3.3.2. Evaluation of Rollback Rates

TRR is not an indicator of CC protocols, as these aborts are necessary.
Instead, FRR is an indicator to measure the CC protocols. Without a full cycle
detection, all CC protocols have a false rollback, where non-anomaly
transactions will be aborted. Intuitively, the higher FRR the worse the
performance. So reducing the FRR has the potential to improve the performance.

We evaluates several CC protocols, such as, two-phase locking(2PL) (Eswaran et
al., 1976a) (includes No_wait and Wait_die), Timestamp Ordering (TO)
(Bernstein and Goodman, 1981), MVCC(Mutil-Version Concurrency Control) with TO
(MVTO) (Bernstein and Goodman, 1983), Optimistic Concurrency Control (OCC)
(Kung and Robinson, 1979), MaaT(Multi-access as a Transaction) (Mahmoud et
al., 2014), Serializable Snapshot Isolation(SSI) and Write-snapshot
Isolation(WSI) with 3TS. Table 9 and Table 10 show the evaluation result.

  * •

Table 9 is the evaluation result by a static method with multiple set of
static histories (Definition 3.1). The result shows the rate of false rollback
of CC protocols in scheduling with all permutations and combinations.

  * •

Table 10 is the evaluation result by a dynamic method with dynamic concurrent
transactions generated by YCSB and TPC-C workloads based on real-life
scenarios. Each schedule is dynamically formed during the execution of
concurrent transactions. We calculate the rollback rate of each CC algorithm.

Static Rollback Rates: For “ALL” column in Table 9, the number of data
anomalies contained in each group of history is determined, so the TRR is also
determined. The difference between different algorithms lies in the different
FRRs.

2PL (No$\\_$wait) algorithms have the highest FRR, as both read lock and write
lock will cause the concurrent write to abort. For all histories with RW, WR,
and WW, No$\\_$wait will abort them.

Both MVTO and TO are in the TO category with similar FRR. MVTO is an
improvement based on MVCC technology, which improves the concurrency of WW and
RW, and especially eliminates the occurrence of WR by reading specific
versions based on its start timestamp. SSI by using MVCC also has a relatively
low abort rate, as read does not block write and write does not block read.

Both OCC and MaaT belong to OCC algorithms with similar FRR. Both of them have
to detect RW and WW, so they will abort when they meet RW or WW conflict. In
contrast, MVTO and TO have some cases to wait WW conflict while SSI will abort
two consecutive RW instead of one.

Dynamic Rollback Rates: From the real run of benchmark data, MVTO and TO yield
lower abort rates as shown in Table 10. The reason is that they can allow some
WW conflicts to wait instead of the direct abort.

OCC and MaaT have higher abort rates in High contention (y4) and TPC-C
workloads (t1, t2, and t3). They suffer higher abort rates by more concurrent
transactions and higher concurrent threads in contented benchmark workloads.
When mixing with Payment and NewOrder workloads (t3), the contention
intensifies in reading/updating the warehouse information, leading to higher
abort rates for all CC protocols. Essentially, these CC protocols eliminate
the conflict edges of cycles, i.e., RW, WW, and WR conflicts. For No_wait,
since reads and writes are mutually blocked, it does not allow all conflicts,
resulting in the highest abort rates in both syntactic and benchmark
workloads. For TO and MVTO, it partially allows WW by queuing some
transactions, making it a very low abort rate in TPC-C workloads, where the
main aborts are from WW conflicts. Interestingly, (Durner and Neumann, 2019)
precisely avoids false rollback by means of the cycle detection. It claims to
have competitive throughput compared to the-state-of-art algorithms while
having lower abort rates. We will discuss more natural ideas on CC algorithms
dealing with these conflicts in §4.2.

Lesson learned: Different scenarios have different rollback rates. It is
necessary to model the rollback rates for different application scenarios.
This is our future work.

Next section, We will later design concise and easy-understanding isolation
levels based on our quantitative method in §4.1.2.

##  4\. Applications And Evaluation

This section shows how to use Coo framework (in §2) to, redefine isolation
levels (in §4.1.2), analyze the implementation process of mainstream algorithm
(in §4.2).

Table 11. Performance evaluation result (Transaction per second) of CC algorithms and their performance improvement (in percentage) comparing to READ COMMITTED(RC) and READ UNCOMMITTED(RU) isolation levels. The experiment is run with 64 server thread. Workload is described in Table 5 Workload | SSI | NRW | RC | RU | WAIT_DIE | RC | RU | NO_WAIT | RC | RU
---|---|---|---|---|---|---|---|---|---|---
y1 | 445552 | 6.16% | 6.63% | 16.04% | 510021 | 2.28% | 13.73% | 478832 | 10.92% | 11.75%
y2 | 586457 | 1.88% | 7.18% | 9.04% | 464146 | 17.28% | 26.44% | 485169 | 4.44% | 1.93%
y3 | 553605 | -2.29% | 3.10% | 10.25% | 543264 | -2.53% | 15.35% | 482065 | 0.59% | -1.16%
y4 | 140474 | 531.19% | 327.60% | 706.78% | 113114 | 347.01% | 436.43% | 117279 | 297.40% | 337.28%
t1 | 374208 | 0.65% | 2.98% | 51.78% | 406490 | 7.36% | 28.57% | 408835 | 4.20% | 28.90%
t2 | 254915 | 0.22% | 1.53% | 32.33% | 266444 | 4.17% | 17.17% | 279314 | 4.08% | 13.54%
t3 | 341092 | 0.86% | -1.47% | 37.75% | 151961 | 66.38% | 212.88% | 233255 | 60.04% | 173.88%

###  4.1. Isolation levels

In addition to data anomalies, isolation levels are another important content
in transaction processing technology. What is the relationship between them?
The previous knowledge system can not sufficiently reflect the relationship
between them. Limited data anomalies are used to define the isolation level
(16, 1992; Berenson et al., 1995b; Adya et al., 2000), indicating that there
is a relationship between them. However, the isolation levels are not
discussed based on all data anomalies, making their relationship unclear.
Therefore, this section discusses the relationship between data anomalies and
isolation levels.

####  4.1.1. Can isolation levels really improve performance?

(Gray et al., 1976a) discusses the motivation of the original definitions of
isolation levels of ANSI/ISO SQL (16, 1992). Early database systems used two-
phase locking(2PL) technology to ensure data consistency. The traditional view
is that a weak isolation level helps to improve performance. But is it really
true? Table 11 shows the performance of SSI (Cahill et al., 2008) and 2PL
(No$\\_$wait and Wait$\\_$die) (Eswaran et al., 1976a), and their performance
improvement (in percentage) comparing to Read Committed(RC) and Read
Uncommitted(RU) isolation levels. We see that the benefit to sacrifice
isolation level from serializable into RC (or NRW in our defined level) is not
significant (less than 5$\%$ in most cases) except in some cases with
extremely high contention between transactions (more than 100$\%$ for all
cases). Though the RU level has notable improvement, it does not suit most
practical applications.

####  4.1.2. The definition of Isolation Levels

There are two existing methods of isolation levels definition. The first is
based on limited data anomalies as (16, 1992; Berenson et al., 1995b),
however, this method cannot handle when more data anomalies are reported(Table
3). For example, Write-read Skew, which is a new data anomaly reported by this
paper, is not intuitively clear which isolation level can avoid it. The second
is based on conflict graph as (Adya et al., 2000), however, (Adya et al.,
2000) is not a pure method, (Adya et al., 2000) uses conflict graph and some
specific data anomalies to define isolation levels. We redefine isolation
levels based on the research results of this paper. We use a pure conflict
graph and do not narrow it to some special cases. Instead, we specify all
possible primitive data anomalies(Table 3). Therefore, we use a unified method
to define isolation levels. We think a good definition of isolation levels has
two features as follows.

  * •

_Maximize Concurrency_. A good definition of isolation levels helps to
maximize concurrent access control by using low-cost heuristic rules.

  * •

_Simplicity_. A simple definition of isolation levels help to simplify
implementation in engineering systems.

We define two isolation levels for all data anomalies in Table 12 as follows.

  * •

The first is the No Read and Write Data Anomalies(NRW) level, which forbid all
RAT and WAT data anomalies. RAT type data anomalies can be avoided by Read
committed heuristic rules. RAT type data anomalies can be avoided by applying
write locks, but with lower concurrency. It can also be eliminated by
detecting the cycle of WAT. The NRW isolation level is stronger than Read
Uncommitted, Read Committed and Repeatable Read isolation level of the
ANSI/ISO SQL (16, 1992).

  * •

The second also the strictest level is the No Data Anomalies(NA) level, which
allows no data anomaly. In other words, NA provides what is normally
considered as serializability. However, different CC algorithms have different
implementation enforcement to guarantee serializability. According to the
characteristics of IAT data anomalies, such data anomalies can only be
detected or avoided by eliminating RW and/or WCW and/or WCR edges.

  * •

From the NRW level to NA level, the degree of concurrency decreases, as the
constraints increases.

Table 12. Simplified isolation levels in practice and engineering. NP and P stands for Not Possible and Possible, respectively Types of Anomalies | Anomaly name | NRW | NA
---|---|---|---
| SDA | Dirty Read | NP | NP
| SDA | Non-repeatable Read | NP | NP
| SDA | Phantom | NP | NP
| SDA | Intermediate Read | NP | NP
| DDA | Write-read Skew Committed | NP | NP
| DDA | Double-write Skew 1 Committed | NP | NP
| DDA | Write-read Skew | NP | NP
| DDA | Read Skew | NP | NP
| DDA | Read Skew 2 | NP | NP
RAT | MDA | Step RAT | NP | NP
| SDA | Dirty Write | NP | NP
| SDA | Full-Write Committed | NP | NP
| SDA | Full-Write | NP | NP
| SDA | Lost Update | NP | NP
| SDA | Lost Self Update | NP | NP
| DDA | Double-write Skew 2 Committed | NP | NP
| DDA | Full-write Skew Committed | NP | NP
| DDA | Full-write Skew | NP | NP
| DDA | Double-write Skew 1 | NP | NP
| DDA | Double-write Skew 2 | NP | NP
| DDA | Read-write Skew 1 | NP | NP
| DDA | Read-write Skew 2 | NP | NP
WAT | MDA | Step WAT | NP | NP
| SDA | Non-repeatable Read Committed | P | NP
| SDA | Lost Update Committed | P | NP
| DDA | Read Skew Committed | P | NP
| DDA | Read-Write Skew 1 Committed | P | NP
| DDA | Write Skew | P | NP
| DDA | Predicate-based Write Skew | P | NP
IAT | MDA | Step IAT | P | NP

####  4.1.3. Isolation Levels and Data Anomalies

We define the isolation levels based on all data anomalies, which helps to
fully reflect the relationship between isolation levels and all data
anomalies. According to Table 12, isolation levels can also be considered as a
classification method of data anomalies, but this classification method is
from the perspective of the performance of concurrent control.

Lesson learned: The definition of isolation level is not a mystery. According
to the classification of data anomalies, it is a best practice to formulate
flexible isolation levels to meet the engineering implementation.

###  4.2. Concurrent Control Algorithms

We have divided data anomalies into three types of cycles, called RAT, WAT,
and IAT. Each cycle contains POPs like WR, WW, and RW. There are two ways to
eliminate data anomalies. The first is an algorithm based on a cycle detection
algorithm, which is an expensive method. The second is a rule-based algorithm,
which is a low-cost method. Most CC algorithms strive to eliminate one or some
of the data anomalies to avoid cycle detection.

Weak isolation levels can eliminate some data anomalies. For any isolation
levels defined by different methods, the strongest isolation level must
eliminate all data anomalies.

Table 13 shows the methods or rules used by CC algorithms to avoid different
POPs in different isolation levels. In the following, we discuss more detailed
rules on how to avoid different data anomalies.

Table 13. Analysis of CC algorithms in dealing with POPs to guarantee different isolation levels. RCR, RWA, and 2RWA, stands for Read Committed Rules, RW POP abort, and 2-continuous RW POPs abort, respectively Type of cycle | RAT | WAT | IAT
---|---|---|---
Target POP | WR | WW | RW | RW-WCR | RW-WCW
CC protocol | Levels |  |  |  |  |
2PL | RU | - | Lock | - | - | -
RC | RCR | Lock | - | - | -
RR | RCR+2PL | Lock | Lock+2PL | Lock+2PL | Lock+2PL
S | RCR+2PL | Lock | Lock+2PL | Lock+2PL | Lock+2PL
2PL+MVCC | RU | - | Lock | - | - | -
RC | MVCC | Lock | - | - | -
RR | MVCC+TO | Lock | Lock+2PL | MVCC+2PL | MVCC+2PL
S | MVCC+2PL | Lock | Lock+2PL | MVCC+2PL | MVCC+2PL
TO | RU | - | TO | - | - | -
RC | RCR | TO | - | - | -
RR | RCR+TO | TO | TO | RCR+TO | RCR+TO
S | RCR+TO | TO | TO | RCR+TO | RCR+TO
TO+MVCC | RU | - | TO | - | - | -
RC | MVCC | TO |  | - | -
RR | MVCC+TO | TO | TO | MVCC+TO | MVCC+TO
S | MVCC+TO | TO | MVCC+TO | MVCC+TO | MVCC+TO
OCC+ MVCC | RU | - | Lock | - | - | -
RC | MVCC | Lock | - | - | -
RR | MVCC+TO | Lock | RWA | RWA | RWA
S | MVCC+TO | Lock | RWA | RWA | RWA
SSI | RU | - | Lock | - | - | -
RC | SI | Lock | - | - | -
RR | SI | SI | - | SI | SI
S | SI+2RWA | SI | SI+2RWA | SI+2RWA | SI+2RWA
WSI | RU | - | Wait | - | - | -
RC | MVCC | Wait | - | - | -
RR | MVCC+TO | Wait | RWA | RWA | RWA
S | MVCC+TO | Wait | RWA | RWA | RWA

####  4.2.1. Avoidance of RAT(WR)

We first discuss the WR POP. Together with WCR, they have 23.18% in our
syntactic histories as shown in Table 8. And WR exists in RAT and WAT
anomalies while WCR exists in IAT anomalies. Based on our statistic in Table
6, Dirty Read with 16.68% is the most anomalies that are composited of the WR.

For ANSI/ISO SQL, Dirty Read often occurs with RU level enabled, as reading
uncommitted active writes is allowed. While for the RC level, each read
operation must read the committed version. This can be enforced by rules that
the only committed data can be read, where WR will be eliminated. For RR
level, this requirement is stronger than RC such that in RR, each read of a
transaction should be consistent(the same). The second read can not be
affected by the update or insert operation by other transactions.

Table 13 shows the solutions or rules used by CC algorithms to avoid different
POPs in different isolation levels. For example, in MVCC (Bernstein and
Goodman, 1983) or MVCC-based protocol like SSI and WSI, the RC level can be
obtained by reading the latest committed version via the versions of MVCC. RR
can be enforced by a transaction-life-time read lock on a data item or MVCC by
snapshot technique controlled by timestamps. Instead of reading the latest
committed version in RC where updates may affect two different reads, this
time, it should always read a fixed version, for example, the latest committed
version that is committed before the reading transaction starts. In purely TO
algorithm (Bernstein and Goodman, 1981), RR can be achieved such that the read
can not be a success if the data modified timestamp is greater than the start
timestamp of the read transaction. In our classification, the avoidance of WR
indicates RAT-free, as RATs always hold a WR POP in their cycles.

For this paper, in engineering implementation, RC and SI can be used as rules
to eliminate most data anomalies with NRW isolation level. For example, Read
Skew (RW-WR) anomaly includes one WR edge, it can be avoided by the RC rule.
But for Read Skew Committed (RW-WCR) anomaly, it has one WCR edge, which can
not be avoided by RC rule. But SI rule can avoid this anomaly via reading the
specific version instead of the new committed version by the technique of TO.

Lesson learned: The data anomalies of RAT can be eliminated by rule-based
methods. There is no need to use the cycle detection algorithm.

####  4.2.2. Avoidance of WAT(WW)

We next discuss the WW POP. Together with WCW, they have 23.14% in our
syntactic histories. And WW exists in WAT anomalies while WCW exists in RAT
and IAT anomalies. Based on our statistic in Table 6, Dirty Write with 36.13%
is the most anomalies that are composited of the WW. The WW is the most
annoying one, as we show most anomaly cases are composited of WW in Table 3,
and in Table 3 we show that from the full permutation of syntactic transaction
histories, more than 62$\%$ of the anomalies are types of WATs, which are with
WW conflict. Formally speaking, an anomaly is a cycle of several POPs. And WWs
are the most critical and often unavoidable ones, as these writes from WW can
easily form other POPs with other transactions.

For ANSI/ISO SQL, Dirty Writes often is not allowed even with the lowest RU
level enabled. So eliminating WW conflicts is required from the RU to the
highest serializable level. So to avoid the WAT anomalies in different
isolation levels, it needs to consider avoiding WR or RW in different levels.

We can summarize the WW conflict prevention techniques by two strategies, NO
WAIT and WAIT. We describe these two strategies in the following.

NO WAIT In this case, to avoid the WW conflict to form an anomaly cycle, the
CC algorithms abort one of the transactions once two transactions are intended
to write on the same data item concurrently. For example, 2PL (Eswaran et al.,
1976a), which belongs to a rule-based algorithm, implements this technique by
acquiring write lock by one transaction and aborting others who are also
acquiring write lock on the same record. Interestingly, other CC algorithms
may use implicit write locks. In TO algorithm (Bernstein and Goodman, 1981),
even though no specific write lock is set, the write operation will check the
write timestamp instead. The transactions with write operation abort when they
try to write on the records that have been modified after these transactions
started.

WAIT In this case, to avoid the WW conflict constructing an anomaly cycle, the
CC algorithms arrange transactions with the concurrent writes on the same item
to execute in sequence virtually. Here virtually means that a transaction may
be arranged earlier than its real execution. 2PL can also implement a WAIT
technique, which is to wait instead of aborting when the other transaction
holds the write lock. However, it may introduce deadlock in such cases, where
two transactions wait for each other by the write locks of different
records(We have proved a deadlock is a specific data anomaly (?)). Then either
wait die, which often waits in some pre-arranged orders, or deadlock
detection, which detects the above cases, is implemented to guarantee
proceeding and serializability. In MVTO (Bernstein and Goodman, 1983), a write
may be inserted as an earlier version if there exists no read between this
write to its next committed write. Allowing some writes to be committed
improves the concurrency as well as the performance. Likewise in MaaT (Mahmoud
et al., 2014), each transaction initially maintains the range from zero to
infinite, then dynamically adjust this range by other concurrent transaction.
If WW conflicts happen in MaaT, then one transaction range’s upper bound
should be smaller than the lower bound of the range of another transaction.

For this paper, the avoidance of both the RAT(WR) and WAT(WW) guarantees the
NRW isolation level.

Lesson learned: WAT data anomalies can be eliminated by cycle detection
algorithm or rule-based method(locking protocol), which can be divided into
WAIT DIE and NO WAIT. However, WAIT DIE may cause deadlock, which needs to be
eliminated through the deadlock detection method (cycle detection), in this
way, it is still the cycle detection algorithm.

####  4.2.3. Avoidance of IAT(RW and/or WCW)

Once the WW and WR are avoided, the percentage of IAT data anomalies is only
3.76%, as shown in Table 6. Table 8 also shows that in forming cycles, RW is
the least when compared to WW and WR. That is why most efforts of CC
algorithms do not focus on removing RW first.

For ANSI/ISO SQL and the definition of (16, 1992), only the serializable
isolation level can eliminate the data anomalies caused by RW, such as Write
Skewd(RW-RW) data anomaly.

In SSI, it allows a single RW to appear, while in WSI, the transaction will
abort as long as it meets the RW. For the serializable level, OCC and WSI need
to abort all RWs while SSI aborts only when two consecutive RWs constructed.

###### Lemma 4.1.

The avoidance of WR, WW, and RW conflicts guarantees serializability.

We can alternatively prove that an anomaly has at least one of WR, WW, or RW
POP in its conflict cycle. It can be easily proved by the contradictory. An
anomaly is a conflict cycle consisting of POPs. Assume the cycle is without
WW, WW, and WR, we can prove that POPs with only WCR, WCW, RCW can not form a
cycle. As the ”C” already determines the commit order between two
transactions. So POPs like $W_{0}C_{0}W1$ and $W_{1}C_{1}W_{0}$ can not happen
at the same time. Therefore, every two transactions of concurrent transactions
have a unique order. So it guarantees serializability with the absence of POPs
of WR, WW, and RW.

For this paper, in order to achieve the NA isolation level, we need to
eliminate IAT type data anomalies. But for Non-repeatable Read Committed(RW-
WCR) and Lost Updata Committed(RW-WCW) data anomalies, we can not use SSI to
eliminate them. Non-repeatable Read Committed(RW-WCR) can be eliminated by SI.
Lost Updata Committed(RW-WCW) can be eliminated by detecting whether a Write
operation and another write operation occur on the same item at the same time,
rather than whether there is a WW edge (WW and WCW POPs are different).

Lesson learned: IAT type data anomalies account for a small proportion.
Adopting rule-based methods as much as possible will help to improve the
performance of CC algorithms. The avoidance of IAT(RW and/or WCW) guarantees
the NA isolation level.

####  4.2.4. Discussion of SSI and WSI

Essentially, all algorithms guarantee serializability in a different way by
avoiding conflict cycles. In this part, we will discuss how SSI and WSI
algorithms avoid these cycles. Firstly in SSI (Cahill et al., 2008), the
algorithm is strongly based on the algorithm of Snapshot Isolation (SI)
(Berenson et al., 1995a), which isolation level is stronger than READ
COMMITTED. In SI, the first-updater-win or first-committer-win strategy is
applied for the avoidance of WW conflict to guarantee that only one active
write can be committed at a time. This corresponds to the above NO WAIT
strategy for WW conflicts. And it guarantees every read is to the committed
version by MVCC implementation. SI is not serializable and suffers read skew
and write skew anomalies (Berenson et al., 1995a). SSI algorithm (Cahill et
al., 2008) is serializable with the following steps on top of SI. (i) The
conflict types for the SSI cycle can be only RW and WCR, as WR is avoided by
reading the committed version while WW is avoided by aborting one of the
conflicting transactions. (ii) As SSI proves each cycle has two two-continuous
RWs (special case is read skew anomaly with only two RWs), it avoids a cycle
by destroying every two-continuous RWs structure. This for sure may abort some
non-cycle transactions with two-continuous RWs, but trading off the better
performance with less detection cost.

Interestingly, from our IAT anomalies in Table 3, it exists patterns like RW-
WCR (e.g., Non-repeatable Read Committed and Read Skew Committed) and RW-WCW
(Lost Update Committed and Read-write Skew 1 Committed), which seems that it
does not have WW pattern and-two continuous RWs. In fact in SSI, the second R
in RW-WCR did not read the new version since it started earlier than the new
committed version. Likewise, for RW-WCW, SSI considers a WCW conflict when the
last W is executed, as it writes on the version that already has a new version
after it started.

An interesting follow-up work, Write Snapshot Isolation (WSI) (Yabandeh and
Ferro, 2012) is proposed to prevent RW conflicts instead of WW conflicts. They
claim that unlike SSI blocks between writes, no interruption occurs by writes
between concurrent transactions. It is a bit confusing at first impression
whether WSI solves WW conflicts or not. In fact, they do solve WW conflicts
implicitly by enforcing the second strategy WAIT between concurrent writes.
The WSI is serializable by the following steps. (i) The conflict types for the
WSI cycle are with WWs and WRs but not RWs as it only detects RW conflicts.
(ii) WSI enforce all WWs and WRs become WCWs and WCRs by the centralized
commit technique (Junqueira et al., 2011) where writes operations allow to
write into the database only when no committed concurrent transactions have
modified these writes. The (ii) condition guarantees writing to the database
in sequential. The transaction aborts when occurring RWs. With only WCWs or
WCR, there will be no anomalies. The reason is that these WCW and WCR are not
possible to construct conflict cycles, as one of the POPs should be WR, WW, or
RW.

###  4.3. Relation between Data Anomalies, Isolation Levels, and Concurrency
Control algorithms

The purpose of CC algorithms is to ensure data consistency by eliminating all
data anomalies. By giving different levels of isolation, CC algorithms aim to
eliminate different edges of POP. Therefore by allowing some certain types of
edges or cycles, consistency can also be classified according to different
isolation levels (Gray et al., 1976b). We show the statistics in Table 6 that
some edges more frequently appear. In these cases, it is required to eliminate
by strict rules at first hand. In contrast, some edges are less anomaly-
sensitive, which can be dealt with by a post-processing method.

##  5\. Related Work

To the best of our knowledge, this is the first study about systematically
researching and defining data anomalies from the perspective of all anomalies.
In our previous work (Hai-Xiang et al., 2021), we systematically studied all
entity-based data anomalies. This paper not only includes predicate-based data
anomalies, but only makes a quantitative study on data anomalies, isolation
levels and CC algorithms.

Research history of data anomalies. Well-known data anomalies, including Dirty
Write, Dirty Read, Non-repeatable Read, Phantom, Lost update, Read Skew and
Write Skew, etc., proposed in (16, 1992; Berenson et al., 1995b; Adya et al.,
2000). These data anomalies were reported in the 1990s and before. In recent
years, there still exist extensive research works that focus on reporting new
data anomalies, including Aborted Reads (Xie et al., 2015), Intermediate Read
(Adya et al., 2000; Xie et al., 2015), Read-only Transaction Anomaly (Fekete
et al., 2004; wikipedia, [n.d.]), Serial-concurrency-phenomenon and Cross-
phenomenon (Binnig et al., 2014). (Cerone et al., 2017) reports Long Fork,
Fractured Reads, and Causality Violation. Even, an unnamed data anomaly was
reported in (Schenkel et al., 2000). For reference, we make a thorough survey
on data anomalies and show them in Table 1. This paper redefines known data
anomalies and defines the remaining 20+ new data anomalies in all data
anomalies formally, and shows them in Table 3.

Predicate-based data anomalies. We know Phantom is a predicate-based data
anomaly reported by (16, 1992; Berenson et al., 1995b; Adya et al., 2000),
Predicate-Based Write Skew is another predicate-based data anomaly reported by
(Fekete et al., 2005a), (Adya et al., 2000) discussed some data anomalies and
predicate related topics, but did not give how many kinds of predicate-based
data anomalies there are, nor did discuss the relationship between entity-
based data anomalies and predicate-based data anomalies. We integrate
predicates into POPs. We unify the relationship between predicates and entity
objects before formally defining data anomalies, so as to unify the expression
of predicate-based data anomalies and entity-based data anomalies.

Elements of data anomaly. Whether the number of variables and the number of
transactions are related to data anomalies has not been discussed. The early
reported data anomalies are single-variable or double-variables data
anomalies. For example, Dirty Write, Dirty Read, Non-repeatable Read, Phantom,
Lost Update, all are single-variable data anomalies. Only Read Skew and Write
Skew are double-variables data anomalies. But all of them involve only two
concurrent transactions. We found more new data anomalies from the perspective
of the number of variables and report them in this paper, for example, Step
RAT, Step WAT and Step IAT involve three variables, and we can extend four
variables or more variables data anomalies. In the conflict graph composed of
data anomalies, we not only classify the data anomalies according to the types
of edges in the conflict graph, but also classify the data anomalies carefully
according to the number of variables in the conflict graph. Table 6 shows that
this classification method is meaningful because the proportion of cycles
composed of three or more variables is small, for example, the probability of
Step RAT, Step WAT, and Step IAT are less than 1$\%$.

Definition of data anomalies. Although there are so many data anomalies, but
it seems that data anomalies are not explicitly defined. There is no
universally accepted definition of data anomalies in academia and industry,
and the understanding of data anomalies is only in the way of case-by-case.
What are data anomalies? (Cerone and Gotsman, 2018)‘s definition is: This
concurrency-control algorithm allows unserializable behaviours, called
anomalies. To our best knowledge, this is the first and only one to explicitly
define what is data anomalies. But it is no systematic research on data
anomalies, and it defines data anomalies with CC algorithms but each one CC
algorithm is only a method and it is not a root reason. Coo framework
explicitly defines what data anomalies is (Definition 2.7), studies some
characteristics of data anomalies and shows them with some lemmas(§4), and
classifies data anomalies(§2.3).

Research on quantification and classification of data anomalies. The existing
research shows that the work of quantifying and classifying data anomalies is
carried out within the known and limited range of data anomalies(only
including some anomalies in Table 1), using serializable and dependency graph
(Bernstein et al., 1987; Berenson et al., 1995b; Adya et al., 2000; Fekete et
al., 2005b; Elmasri and Navathe, 2006; Adya and Liskov, 1999) technology.
(Jorwekar et al., 2007) developed a set of tools and methods to automatically
detect data anomalies from applications under snapshot isolation technology.
(Zellag and Kemme, 2011; Zellag and Kemme, 2012b, 2014, a), use a middleware
layer that is embedded between the application and the database, according to
the serializable theory and dependency graph technology (Bernstein et al.,
1987; Berenson et al., 1995b; Adya et al., 2000; Fekete et al., 2005b; Elmasri
and Navathe, 2006; Adya and Liskov, 1999), the method quantifies and
classifies the data anomalies. However, this method detects data anomalies
based on applications such as TPCC (Council, 2010), and finds no new data
anomalies. (Fekete et al., 2009) quantitatively studied the integrity
violation rate of data anomalies in different isolation levels under snapshot
isolation technology, but did not propose new data anomaly. (Zellag and Kemme,
2012a) does similar work with us, but it does not make a quantitative
comparison of data anomalies for a variety of concurrent algorithms. To the
best of our knowledge, this is the first paper to quantify data anomalies
based on all data anomalies.

Data anomalies and Isolation Levels. (16, 1992; Berenson et al., 1995b; Adya
et al., 2000) try to define isolation levels with known and finite data
anomalies. Adya (Adya et al., 2000) defines isolation levels with conflict
graph and three specific data anomalies, but their methods are not unified. We
extend the definition of the edge of the conflict graph so that the conflict
graph can express all data anomalies, so we can completely and flexibly define
the isolation level based on all data anomalies.

Concurrent Control algorithms. There are many concurrent control algorithms,
include 2PL (Eswaran et al., 1976a), TO (Bernstein and Goodman, 1981), OCC
(Kung and Robinson, 1979; Schlageter, 1981; Bayertime1982Dynamic; Boksenbaum
et al., 1984; Binnig et al., 2014), MVCC (Bernstein and Goodman, 1983).
Locking-based approaches make a particular design on the lock types (e.g.,
read/write/predicate locks) as well as locking mechanism to disallow single-
variable data anomalies (Eswaran et al., 1976b; Gray et al., 1976b; Bernstein
et al., 1979; Garciamolina, 1999; Elmasri and Navathe, 2006). MVCC-based
approaches disallow a set of data anomalies based on snapshot isolation. To
disallow more data anomalies, (Cahill et al., 2008) proposes SSI and (Yabandeh
and Ferro, 2012) proposes WSI algorithm. Coo framework is potentially used for
detecting and reporting all data anomalies and we design the evaluation model
of mainstream concurrent control algorithms.

##  6\. Conclusion

We systematically define all data anomalies. Although the experimental data in
this paper is based on entity-based data anomalies, it is helpful to quantify
data anomalies, rollback rate and isolation levels in concurrent control
technology. This work also contributes to the in-depth analysis of various CC
algorithms, which brings opportunities to optimize existing CC algorithms and
find new CC algorithms. In the future, we will further carry out in-depth
quantitative research to better digitally reveal the internal laws of
transactions.

## References

  * (1)
  * 16 (1992) 1992\.  _Database Language – SQL_.  American National Standard for Information Systems.
  * Adya et al. (2000) A. Adya, B. Liskov, and P. O’Neil. 2000.  Generalized isolation level definitions. In _Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073)_. 67–78.
  * Adya et al. (2000) Atul Adya, Barbara Liskov, and Patrick O’Neil. 2000\.  Generalized isolation level definitions. In _Proceedings of 16th International Conference on Data Engineering (Cat. No. 00CB37073)_. IEEE, 67–78.
  * Adya and Liskov (1999) Atul Adya and Barbara H. Liskov. 1999.  Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions.  (1999).
  * Bailis et al. (2016) Peter Bailis, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. 2016\.  Scalable Atomic Visibility with RAMP Transactions.  _ACM Trans. Database Syst._ 41, 3, Article 15 (July 2016), 45 pages.  https://doi.org/10.1145/2909870
  * Berenson et al. (1995b) Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O’Neil, and Patrick O’Neil. 1995b.  A Critique of ANSI SQL Isolation Levels. In _Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data_ (San Jose, California, USA) _(SIGMOD ’95)_. Association for Computing Machinery, New York, NY, USA, 1–10.  https://doi.org/10.1145/223784.223785
  * Berenson et al. (1995a) Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O’Neil, and Patrick E. O’Neil. 1995a.  A Critique of ANSI SQL Isolation Levels. In _SIGMOD Conference_. ACM Press, 1–10.
  * Bernstein and Goodman (1981) Philip A. Bernstein and Nathan Goodman. 1981.  Concurrency Control in Distributed Database Systems.  _ACM Comput. Surv._ 13, 2 (1981), 185–221.
  * Bernstein and Goodman (1983) Philip A. Bernstein and Nathan Goodman. 1983.  Multiversion Concurrency Control - Theory and Algorithms.  _ACM Trans. Database Syst._ 8, 4 (1983), 465–483.
  * Bernstein et al. (1987) Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. 1987\.  _Concurrency Control and Recovery in Database Systems_.  Addison-Wesley.  http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx
  * Bernstein et al. (1979) P. A. Bernstein, D. W. Shipman, and W. S. Wong. 1979\.  Formal Aspects of Serializability in Database Concurrency Control.  _IEEE Transactions on Software Engineering_ SE-5, 3 (1979), 203–216.
  * Binnig et al. (2014) Carsten Binnig, Stefan Hildenbrand, Franz Farber, Donald Kossmann, Juchang Lee, and Norman May. 2014.  Distributed snapshot isolation: global transactions pay globally, local transactions pay locally.  23, 6 (2014), 987–1011.
  * Boksenbaum et al. (1984) Claude Boksenbaum, Michele Cart, Jean Ferrie, and Jeanfrancois Pons. 1984.  Certification by Intervals of Timestamps in Distributed Database Systems.  (1984), 377–387.
  * Cahill et al. (2008) Michael J. Cahill, Uwe Röhm, and Alan D. Fekete. 2008\.  Serializable isolation for snapshot databases. In _SIGMOD Conference_. ACM, 729–738.
  * Cerone and Gotsman (2018) Andrea Cerone and Alexey Gotsman. 2018.  Analysing Snapshot Isolation.  _J. ACM_ 65, 2 (2018), 11:1–11:41.
  * Cerone et al. (2017) Andrea Cerone, Alexey Gotsman, and Hongseok Yang. 2017\.  Algebraic Laws for Weak Consistency.  (2017), 26:1–26:18.
  * Cooper et al. (2010) Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010\.  Benchmarking cloud serving systems with YCSB. In _SoCC_. ACM, 143–154.
  * Council (2010) Transaction Processing Performance Council. 2010.  TPC Benchmark C (Revision 5.11). TPC.
  * Durner and Neumann (2019) Dominik Durner and Thomas Neumann. 2019.  No False Negatives: Accepting All Useful Schedules in a Fast Serializable Many-Core System. In _35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019_. IEEE, 734–745.  https://doi.org/10.1109/ICDE.2019.00071
  * Elmasri and Navathe (2006) Ramez Elmasri and Shamkant B. Navathe. 2006.  Fundamentals of Database Systems, 5/E.  (2006).
  * Epp (2010) Susanna S Epp. 2010\.  _Discrete mathematics with applications_.  Cengage learning.
  * Eswaran et al. (1976a) Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, and Irving L. Traiger. 1976a.  The Notions of Consistency and Predicate Locks in a Database System.  _Commun. ACM_ 19, 11 (1976), 624–633.
  * Eswaran et al. (1976b) Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, and Irving L. Traiger. 1976b.  The Notions of Consistency and Predicate Locks in a Database System.  _Communications of the Acm_ 19, 11 (1976), 624–633.
  * Fekete et al. (2009) Alan Fekete, Shirley N Goldrei, and Jorge Perez Asenjo. 2009\.  Quantifying isolation anomalies.  2, 1 (2009), 467–478.
  * Fekete et al. (2005b) Alan Fekete, Dimitrios Liarokapis, Elizabeth O’Neil, Patrick O’Neil, and Dennis Shasha. 2005b.  Making Snapshot Isolation Serializable.  _ACM Trans. Database Syst._ 30, 2 (June 2005), 492–528.  https://doi.org/10.1145/1071610.1071615
  * Fekete et al. (2004) Alan Fekete, Elizabeth O’Neil, and Patrick O’Neil. 2004\.  A Read-Only Transaction Anomaly under Snapshot Isolation.  _SIGMOD Rec._ 33, 3 (Sept. 2004), 12–14.  https://doi.org/10.1145/1031570.1031573
  * Fekete et al. (2005a) Alan D. Fekete, Dimitrios Liarokapis, Elizabeth J. O’Neil, Patrick E. O’Neil, and Dennis E. Shasha. 2005a.  Making snapshot isolation serializable.  _ACM Trans. Database Syst._ 30, 2 (2005), 492–528.  https://doi.org/10.1145/1071610.1071615
  * Garciamolina (1999) Hector Garciamolina. 1999\.  Review - The Notions of Consistency and Predicate Locks in a Database System.  _ACM Sigmod Digital Review_ 1 (1999).
  * Gray et al. (1976a) Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, and Irving L. Traiger. 1976a.  Granularity of Locks and Degrees of Consistency in a Shared Data Base. In _IFIP Working Conference on Modelling in Data Base Management Systems_. North-Holland, 365–394.
  * Gray et al. (1976b) Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, and Irving L. Traiger. 1976b.  Granularity of Locks and Degrees of Consistency in a Shared Data Base. In _Readings in database systems (3rd ed.)_. 365–394.
  * Hai-Xiang et al. (2021) Li Hai-Xiang, Li Xiao-Yan, Liu Chang, Du Xiao-Yong, Lu Wei, and Pan An-Qun. 2021\.  Systematic definition and classification of data anomalies in DBMS (English Version).  arXiv:2110.14230 [cs.DB]
  * Harding et al. (2017) Rachael Harding, Dana Van Aken, Andrew Pavlo, and Michael Stonebraker. 2017.  An Evaluation of Distributed Concurrency Control.  _Proc. VLDB Endow._ 10, 5 (2017), 553–564.
  * Janin and Walukiewicz (1996) David Janin and Igor Walukiewicz. 1996.  On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic. In _International Conference on Concurrency Theory_. Springer, 263–277.
  * Jorwekar et al. (2007) Sudhir Jorwekar, Alan Fekete, Krithi Ramamritham, and S Sudarshan. 2007.  Automating the detection of snapshot isolation anomalies.  (2007), 1263–1274.
  * Junqueira et al. (2011) Flavio Junqueira, Benjamin Reed, and Maysam Yabandeh. 2011\.  Lock-free transactional support for large-scale storage systems. In _DSN Workshops_. IEEE Computer Society, 176–181.
  * Kung and Robinson (1979) H. T. Kung and John T. Robinson. 1979.  On Optimistic Methods for Concurrency Control. In _VLDB_. IEEE Computer Society, 351.
  * Mahmoud et al. (2014) Hatem A. Mahmoud, Vaibhav Arora, Faisal Nawab, Divyakant Agrawal, and Amr El Abbadi. 2014.  MaaT: Effective and scalable coordination of distributed transactions in the cloud.  _Proc. VLDB Endow._ 7, 5 (2014), 329–340.
  * Schenkel et al. (2000) Ralf Schenkel, Gerhard Weikum, N Weissenberg, and Xuequn Wu. 2000\.  Federated transaction management with snapshot isolation.  _Lecture Notes in Computer Science_ (2000), 1–25.
  * Schlageter (1981) Gunter Schlageter. 1981\.  Optimistic Methods for Concurrency Control in Distributed Database Systems. In _Proceedings of the Seventh International Conference on Very Large Data Bases - Volume 7_ (Cannes, France) _(VLDB ’81)_. VLDB Endowment, 125–130.
  * Smullyan (1995) Raymond M Smullyan. 1995\.  _First-order logic_.  Courier Corporation.
  * Weikum and Vossen (2001) Gerhard Weikum and Gottfried Vossen. 2001.  _Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery_.  Elsevier.
  * Weikum and Vossen (2002) G. Weikum and G. Vossen. 2002.  Concurrency Control: Notions of Correctness for the Page Model.  _Transactional Information Systems_ (2002), 61–123.
  * wikipedia ([n.d.]) wikipedia. [n.d.].  Read$\\_$Only$\\_$Transactions.  Website.  https://wiki.postgresql.org/wiki/SSI#Read_Only_Transactions
  * Xiaoyong (2017) Du el at. Xiaoyong. 2017\.  Big data management.  (2017).
  * Xie et al. (2015) Chao Xie, Chunzhi Su, Cody Littley, Lorenzo Alvisi, Manos Kapritsos, and Yang Wang. 2015\.  High-performance ACID via modular concurrency control. In _Proceedings of the 25th Symposium on Operating Systems Principles_. 279–294.
  * Yabandeh and Ferro (2012) Maysam Yabandeh and Daniel Gómez Ferro. 2012.  A critique of snapshot isolation. In _EuroSys_. ACM, 155–168.
  * Zellag and Kemme (2011) K. Zellag and B. Kemme. 2011.  Real-time quantification and classification of consistency anomalies in multi-tier architectures. In _2011 IEEE 27th International Conference on Data Engineering_. 613–624.
  * Zellag and Kemme (2012a) Kamal Zellag and Bettina Kemme. 2012a.  ConsAD: A Real-Time Consistency Anomalies Detector. In _Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data_ (Scottsdale, Arizona, USA) _(SIGMOD ’12)_. Association for Computing Machinery, New York, NY, USA, 641–644.  https://doi.org/10.1145/2213836.2213920
  * Zellag and Kemme (2012b) Kamal Zellag and Bettina Kemme. 2012b.  How Consistent is Your Cloud Application?. In _Proceedings of the Third ACM Symposium on Cloud Computing_ (San Jose, California) _(SoCC ’12)_. Association for Computing Machinery, New York, NY, USA, Article 6, 14 pages.  https://doi.org/10.1145/2391229.2391235
  * Zellag and Kemme (2014) Kamal Zellag and Bettina Kemme. 2014.  Consistency anomalies in multi-tier architectures: automatic detection and prevention.  23, 1 (2014), 147–172.