“A Critique of ANSI SQL Isolation Levels,” Proc. ACM SIGMOD 95, pp. 1-10, San Jose, CA, June 1995, © ACM. -2-
2. Isolation Definitions
2.1 Serializability Concepts
Transactional and locking concepts are well documented
in the literature [BHG, PAP, PON, GR]. The next few
paragraphs review the terminology used here.
A transaction groups a set of actions that transform the
database from one consistent state to another. A history
models the interleaved execution of a set of transactions as
a linear ordering of their actions, such as Reads and Writes
(i.e., inserts, updates, and deletes) of specific data items.
Two actions in a history are said to conflict if they are
performed by distinct transactions on the same data item
and at least one of is a Write action. Following [EGLT],
this definition takes a broad interpretation of “data item”:
it could be a table row, a page, an entire table, or a
message on a queue. Conflicting actions can also occur on
a set of data items, covered by a predicate lock, as well as
on a single data item.
A particular history gives rise to a dependency graph
defining the temporal data flow among transactions. The
actions of committed transactions in the history are repre-
sented as graph nodes. If action op1 of transaction T1
conflicts with and precedes action op2 of transaction T2 in
the history, then the pair <op1, op2> becomes an edge in
the dependency graph. Two histories are equivalent if they
have the same committed transactions and the same depen-
dency graph. A history is serializable if it is equivalent to
a serial history — that is, if it has the same dependency
graph (inter-transaction temporal data flow) as some
history that executes transactions one at a time in se-
quence.
2.2 ANSI SQL Isolation Levels
ANSI SQL Isolation designers sought a definition that
would admit many different implementations, not just
locking. They defined isolation with the following three
phenomena:
P1 (Dirty Read): Transaction T1 modifies a data item.
Another transaction T2 then reads that data item before T1
performs a COMMIT or ROLLBACK. If T1 then performs a
ROLLBACK, T2 has read a data item that was never
committed and so never really existed.
P2 (Non-repeatable or Fuzzy Read): Transaction T1
reads a data item. Another transaction T2 then modifies or
deletes that data item and commits. If T1 then attempts to
reread the data item, it receives a modified value or
discovers that the data item has been deleted.
P3 (Phantom): Transaction T1 reads a set of data items
satisfying some <search condition>. Transaction T2
then creates data items that satisfy T1’s <search condi-
tion> and commits. If T1 then repeats its read with the
same <search condition>, it gets a set of data items
different from the first read.
None of these phenomena could occur in a serial history.
Therefore by the Serializability Theorem they cannot occur
in a serializable history [EGLT, BHG Theorem 3.6, GR
Section 7.5.8.2, PON Theorem 9.4.2].
Histories consisting of reads, writes, commits, and aborts
can be written in a shorthand notation: “w1[x]” means a
write by transaction 1 on data item x (which is how a data
item is “modified’), and “r2[x]” represents a read of x by
transaction 2. Transaction 1 reading and writing a set of
records satisfying predicate P is denoted by r1[P] and
w1[P] respectively. Transaction 1’s commit and abort
(ROLLBACK) are written “c1” and “a1”, respectively.
Phenomenon P1 might be restated as disallowing the fol-
lowing scenario:
(2.1) w1[x] . . . r2[x] . . . (a1 and c2 in either order)
The English statement of P1 is ambiguous. It does not ac-
tually insist that T1 abort; it simply states that if this hap-
pens something unfortunate might occur. Some people
reading P1 interpret it to mean:
(2.2) w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order)
Forbidding the (2.2) variant of P1 disallows any history
where T1 modifies a data item x, then T2 reads the data
item before T1 commits or aborts. It does not insist that T1
aborts or that T2 commits.
Definition (2.2) is a much broader interpretation of P1
than (2.1), since it prohibits all four possible commit-abort
pairs by transactions T1 and T2, while (2.1) only prohibits
two of the four. Interpreting (2.2) as the meaning of P1
prohibits an execution sequence if something anomalous
might in the future. We call (2.2) the broad interpretation
of P1, and (2.1) the strict interpretation of P1.
Interpretation (2.2) specifies a phenomenon that might
lead to an anomaly, while (2.1) specifies an actual
anomaly. Denote them as P1 and A1 respectively. Thus:
P1: w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order)
A1: w1[x]...r2[x]...(a1 and c2 in any order)
Similarly, the English language phenomena P2 and P3
have strict and broad interpretations, and are denoted P2
and P3 for broad, and A2 and A3 for strict:
P2: r1[x]...w2[x]...((c1 or a1) and (c2 or a2) in any order)