Generalized Isolation Level Definitions

发表于 更新于 分类于 阅读次数：

Commercial databases support different isolation levels to allow programmers to trade off consistency for a poten- tial gain in performance. The isolation levels are defined in the current ANSI standard, but the definitions are ambigu- ous and revised definitions proposed to correct the problem are too constrained since they allow only pessimistic (lock- ing) implementations. This paper presents new specifica- tions for the ANSI levels. Our specifications are portable*; they apply not only to locking implementations, but also to optimistic and multi-version concurrency control schemes. Furthermore, unlike earlier definitions, our new specifica- tions handle predicates in a correct and flexible manner at all levels.*

商业数据库支持不同的隔离级别，使程序员可以牺牲一致性来获得潜在的性能提升。 隔离级别在当前的 ANSI 标准中进行了定义，但这些定义是不明确的，并且为纠正该问题而提出的修订定义过于受限，因为它们只允许悲观（锁定）实现。 本文提出了 ANSI 级别的新规范。 我们的规格是便携式的； 它们不仅适用于锁定实现，还适用于乐观和多版本并发控制方案。 此外，与早期的定义不同，我们的新规范在各个级别以正确且灵活的方式处理谓词。

1. Introduction

This paper gives new, precise definitions of the ANSI- SQL isolation levels [6]. Unlike previous proposals [13, 6, 8], the new definitions are both correct (they rule out all bad histories) and implementation-independent. Our spec- ifications allow a wide range of concurrency control tech- niques, including locking, optimistic techniques [20, 2, 5], and multi-version mechanisms [9, 24]. Thus, they meet the goals of ANSI-SQL and could be used as an isolation standard.

本文给出了 ANSI-SQL 隔离级别的新的、精确的定义 [6]。 与之前的提案 [13,6,8] 不同，新定义既正确（它们排除了所有不良历史）又独立于实现。 我们的规范允许广泛的并发控制技术，包括锁定、乐观技术[20,2,5]和多版本机制[9,24]。 因此，它们满足 ANSI-SQL 的目标，并且可以用作隔离标准。

The concept of isolation levels was first introduced in [13] under the name Degrees of Consistency. The goal of this work was to provide improved concurrency for workloads by sacrificing the guarantees of perfect isolation. The work in [13] and some refinements suggested by [11] set the stage for the ANSI/ISO SQL-92 definitions for isolation levels [6], where the goal was to develop a standard that was implementation-independent. However, a subsequent paper [8] showed that the definitions provided in [6] were ambiguous. That paper proposed different definitions that avoided the ambiguity problems, but, as stated in [8], these definitions were simply “disguised versions of locking” and therefore disallow optimistic and multi-version mech- anisms. Thus, these definitions fail to meet the goals of ANSI-SQL with respect to implementation-independence.

隔离级别的概念首次在[13]中以“一致性程度”的名称引入。 这项工作的目标是通过牺牲完美隔离的保证来提高工作负载的并发性。 [13] 中的工作和 [11] 建议的一些改进为隔离级别的 ANSI/ISO SQL-92 定义奠定了基础 [6]，其目标是开发一个独立于实现的标准。 然而，随后的论文[8]表明[6]中提供的定义是不明确的。 该论文提出了避免歧义问题的不同定义，但是，正如[8]中所述，这些定义只是“锁定的变相版本”，因此不允许乐观和多版本机制。 因此，这些定义无法满足 ANSI-SQL 在实现独立性方面的目标。

Thus, we have a problem: the standard is intended to be implementation-independent, but lacks a precise definition that meets this goal. Implementation-independence is im- portant since it provides flexibility to implementors, which can lead to better performance. Optimism can outperform locking in some environments, such as large scale, wide- area distributed systems [2, 15]; optimistic mechanisms are the schemes of choice for mobile environments; and Gem- stone [22] and Oracle [24] provide serializability and Snap- shot Isolation, respectively, using multi-version optimistic implementations. It is undesirable for the ANSI standard to rule out these implementations. For example, Gemstone provides serializability even though it does not meet the locking-based rules given in [8].

因此，我们遇到了一个问题：该标准旨在独立于实现，但缺乏满足此目标的精确定义。 实现独立性很重要，因为它为实现者提供了灵活性，从而可以带来更好的性能。 在某些环境中，乐观可以胜过锁定，例如大规模、广域分布式系统 [2, 15]； 乐观机制是移动环境的首选方案； Gemstone [22] 和 Oracle [24] 使用多版本乐观实现分别提供可序列化和快照隔离。 ANSI 标准排除这些实现是不可取的。 例如，Gemstone 提供了可序列化性，即使它不满足 [8] 中给出的基于锁定的规则。

This paper presents new implementation-independent specifications that correct the problems with the existing definitions. Our definitions cover the weaker isolation lev- els that are in everyday use: Most database vendors and database programmers take advantage of levels below se- rializability levels to achieve better performance; in fact, READ COMMITTED is the default for some database products and database vendors recommend using this level instead of serializability if high performance is desired. Our defi- nitions also enable database vendors to develop innovative implementations of the different levels using a wide variety of concurrency control mechanisms including locking, op- timistic and multi-version mechanisms. Furthermore, our specifications handle predicate-based operations correctly at all isolation levels.

本文提出了新的独立于实现的规范，纠正了现有定义的问题。 我们的定义涵盖了日常使用的较弱隔离级别：大多数数据库供应商和数据库程序员利用低于可串行性级别的级别来实现更好的性能； 事实上，READ COMMITTED 是某些数据库产品的默认设置，如果需要高性能，数据库供应商建议使用此级别而不是串行化。 我们的定义还使数据库供应商能够使用各种并发控制机制（包括锁定、乐观和多版本机制）开发不同级别的创新实现。 此外，我们的规范在所有隔离级别正确处理基于谓词的操作。

Thus, the paper makes the following contributions:

因此，本文做出以下贡献：

  • It specifies the existing ANSI isolation levels in an implementation-independent manner. The definitions are correct (they rule out all bad histories). They are also complete (they allow all good histories) for serializability; in particular, they provide conflict- serializability [9]. It is difficult to prove completeness for lower isolation levels, but we can easily show that our definitions are more permissive than those given in [8].

它以独立于实现的方式指定现有的 ANSI 隔离级别。 定义是正确的（它们排除了所有不好的历史）。 它们对于可序列化也是完整的（它们允许所有好的历史记录）； 特别是，它们提供冲突可串行化[9]。 很难证明较低隔离级别的完整性，但我们可以轻松证明我们的定义比[8]中给出的定义更宽松。

  • Our specifications also handle predicates correctly in a flexible manner; earlier definitions were either lock- based or incomplete [8].

    我们的规范还以灵活的方式正确处理谓词； 早期的定义要么是基于锁的，要么是不完整的[8]。

Our approach can be used to define additional levels as well, including commercial levels such as Cursor Stability [11], and Oracle’s Snapshot Isolation and Read Consistency [24], and new levels; for example, we have developed an ad- ditional isolation level called PL-2+, which is the weakest level that guarantees consistent reads and causal consistency with respect to transactions. Details can be found in [1].

我们的方法也可用于定义其他级别，包括商业级别，例如游标稳定性 [11]、Oracle 的快照隔离和读取一致性 [24]，以及新级别； 例如，我们开发了一个名为 PL-2+ 的附加隔离级别，这是保证事务一致性读取和因果一致性的最弱级别。 详细信息可以参见[1]。

Our definitions are given using a combination of con- straints on transaction histories and graphs; we proscribe different types of cycles in a serialization graph at each isolation level. Our graphs are similar to those that have been used before for specifying serializability [9, 19, 14], semantics-based correctness criterion [4], and for defining extended transaction models [10]. Our approach is the first that applies these techniques to defining ANSI and commer- cial isolation levels. Our specifications are different from the multi-version theory presented in [9] since that work only describes conditions for serializability whereas we specify all ANSI/SQL-92 and other commercial isolation levels for multi-version systems. Furthermore, unlike our specifica- tions, their definitions do not take predicates into account. Our work is also substantially different from the definitions presented in [8] since our specifications handle multi-version systems, optimistic systems and also deal with predicates in a correct and flexible manner at all isolation levels.

我们的定义是结合交易历史和图表的约束给出的； 我们在每个隔离级别的序列化图中禁止不同类型的循环。 我们的图与之前用于指定可序列化性 [9,19,14]、基于语义的正确性标准 [4] 以及定义扩展事务模型 [10] 的图类似。 我们的方法是第一个将这些技术应用于定义 ANSI 和商业隔离级别的方法。 我们的规范与 [9] 中提出的多版本理论不同，因为该工作仅描述了可串行性的条件，而我们为多版本系统指定了所有 ANSI/SQL-92 和其他商业隔离级别。 此外，与我们的规范不同，它们的定义没有考虑谓词。 我们的工作也与[8]中提出的定义有很大不同，因为我们的规范处理多版本系统、乐观系统，并且还在所有隔离级别以正确和灵活的方式处理谓词。

Relaxed correctness conditions based on semantics and extended transaction models have been suggested in the past [10, 4, 17, 7]. By contrast, our work focuses on specifying existing ANSI and commercial isolation levels that are being used by large numbers of application programmers.

过去已经提出了基于语义和扩展事务模型的宽松正确性条件[10,4,17,7]。 相比之下，我们的工作重点是指定大量应用程序员正在使用的现有 ANSI 和商业隔离级别。

The rest of this paper is organized as follows. Section 2 discusses prior work in more detail. Section 3 shows that the current definitions are inadequate and motivates the need for our work. Section 4 describes our database model. Section 5 provides our definitions for the existing ANSI isolation lev- els. We close in Section 6 with a discussion of what we have accomplished.

本文的其余部分安排如下。 第 2 节更详细地讨论了之前的工作。 第 3 节表明当前的定义是不充分的，并激发了我们工作的需要。 第 4 节描述了我们的数据库模型。 第 5 节提供了我们对现有 ANSI 隔离级别的定义。 我们在第 6 节结束时讨论了我们所取得的成就。

2. Previous Work

The original proposal for isolation levels [13] introduced four degrees of consistency, degrees 0, 1, 2 and 3, where de- gree 3 was the same as serializability. That paper, however, was concerned with locking schemes, and as a consequence the definitions were not implementation-independent.

隔离级别的最初提议[13]引入了四种一致性程度：0、1、2 和 3 度，其中 3 度与可串行性相同。 然而，该论文关注的是锁定方案，因此定义并不是独立于实现的。

However, that work, together with the refinement of the levels provided by Date [11], formed the basis for the ANSI/ISO SQL-92 isolation level definitions [6]. The ANSI standard had implementation-independence as a goal and the definitions were supposed to be less constraining than ear- lier ones. The approach taken was to proscribe certain types of bad behavior called phenomena; more restrictive consis- tency levels disallow more phenomena and serializability does not permit any phenomenon. The isolation levels were named READ UNCOMMITTED, READ COMMITTED, REPEAT- ABLE READ, and SERIALIZABLE; some of these levels were intended to correspond to the degrees of [13].

然而，这项工作与 Date [11] 提供的级别的细化一起，构成了 ANSI/ISO SQL-92 隔离级别定义 [6] 的基础。 ANSI 标准以实现独立性为目标，并且其定义应该比早期的定义更少限制。 采取的方法是禁止某些类型的不良行为，称为现象； 更严格的一致性级别不允许更多的现象，并且可串行化不允许任何现象。 隔离级别被命名为 READ UNCOMMITTED、READ COMMITTED、REPEATABLE READ 和 SERIALIZABLE； 其中一些级别旨在与[13]的程度相对应。

The work in [8] analyzed the ANSI-SQL standard and demonstrated several problems in its isolation level defini- tions: some phenomena were ambiguous, while others were missing entirely. It then provided new definitions. As with the ANSI-SQL standard, various isolation levels are defined by having them disallow various phenomena. The phenom- ena proposed by [8] are:

[8] 中的工作分析了 ANSI-SQL 标准并展示了其隔离级别定义中的几个问题：一些现象是不明确的，而另一些现象则完全缺失。 然后它提供了新的定义。 与 ANSI-SQL 标准一样，各种隔离级别是通过禁止各种现象来定义的。 [8]提出的现象是：

  1. P0: w1[x] … w2[x] … (c1 or a1)
  2. P1: w1[x] … r2[x] … (c1 or a1)
  3. P2: r1[x] … w2[x] … (c1 or a1)
  4. P3: r1[P] … w2[y in P] … (c1 or a1)

Proscribing P0 (which was missing in the ANSI-SQL defi- nitions) requires that a transaction T2 cannot write an object x if an uncommitted transaction T1 has already modified x. This is simply a disguised locking definition, requiring T1 and T2 to acquire long write-locks. (Long-term locks are held until the transaction taking them commits; short- term locks are released immediately after the transaction completes the read or write that triggered the lock attempt.) Similarly, proscribing P1 requires T1 to acquire a long write- lock and T2 to acquire (at least) a short-term read-lock, and proscribing P2 requires the use of long read and write locks.

禁止 P0（ANSI-SQL 定义中缺少）要求如果未提交的事务 T1 已经修改了 x，则事务 T2 不能写入对象 x。 这只是一个变相的锁定定义，要求T1和T2获取长写锁。 （长期锁会一直保持到获取它们的事务提交为止；短期锁会在事务完成触发锁尝试的读取或写入后立即释放。）类似地，禁止 P1 需要 T1 获取长写锁，并且 T2 获取（至少）短期读锁，而禁止 P2 需要使用长期读写锁。

Phenomenon P3 deals with the queries based on predi- cates. Proscribing P3 requires that a transaction T2 cannot modify a predicate P by inserting, updating, or deleting a row such that its modification changes the result of a query executed by an uncommitted transaction T1 based on pred- icate P; to avoid this situation, T1 acquires a long phantom read-lock [14] on predicate P.

现象 P3 处理基于谓词的查询。 禁止 P3 要求事务 T2 不能通过插入、更新或删除行来修改谓词 P，从而使其修改改变未提交事务 T1 基于谓词 P 执行的查询的结果； 为了避免这种情况，T1 在谓词 P 上获取长幻影读锁 [14]。

Thus, these definitions only allow histories that would occur in a system using long/short read/write item/predicate locks. Since locking serializes transactions by preventing certain situations (e.g., two concurrent transactions both modifying the same object), we refer to this approach as the preventative approach.

因此，这些定义仅允许使用长/短读/写项/谓词锁的系统中发生的历史记录。 由于锁定通过防止某些情况（例如，两个并发事务都修改同一对象）来序列化事务，因此我们将这种方法称为预防性方法。

Figure 1 summarizes the isolation levels as defined in [8] and relates them to a lock-based implementation. Thus the READ UNCOMMITTED level proscribes P0; READ COM- MITTED proscribes P0 and P1; the REPEATABLE READ level proscribes P0 - P2; and SERIALIZABLE proscribes P0 - P3.

图 1 总结了 [8] 中定义的隔离级别，并将它们与基于锁的实现相关联。 因此 READ UNCOMMITTED 级别禁止 P0； READ COMMITTED 禁止 P0 和 P1； 可重复读取级别规定 P0 - P2； 并且 SERIALIZABLE 禁止 P0 - P3。

Figure 1. Consistency Levels and Locking ANSI-92 Isolation Levels

Locking Isolation Level Proscribed Phenomena Read Locks on Data Items and Phantoms (same unless noted) Write Locks on Data Items and Phantoms (always the same)
Degree 0 none none Short write locks
Degree 1 = Locking READ UNCOMMITTED P0 none Long write locks
Degree 2 = Locking READ COMMITTED P0, P1 Short read locks Long write locks
Locking REPEATABLE READ P0, P1, P2 Long data-item read locks,Short phantom read locks Long write locks
Degree 3 = Locking SERIALIZABLE P0, P1, P2, P3 Long read locks Long write locks

3. Restrictiveness of Preventative Approach

预防方法的限制性

We now show that the preventative approach is overly restrictive since it rules out optimistic and multi-version implementations. As mentioned, this approach disallows all histories that would not occur in a locking scheme and prevents conflicting operations from executing concurrently.

我们现在表明，预防性方法过于严格，因为它排除了乐观和多版本的实现。 如前所述，此方法不允许在锁定方案中不会发生的所有历史记录，并防止同时执行冲突的操作。

The authors in [8] wanted to ensure that multi-object con- straints (e.g., constraints like x + y = 10) are not observed as violated by transactions that request an isolation level such as serializability. They showed that histories such as H1 and H2 are allowed by one interpretation of the ANSI standard (at the SERIALIZABLE isolation level) even though they are non-serializable:

[8] 中的作者希望确保请求隔离级别（例如可序列化性）的事务不会违反多对象约束（例如 x + y = 10 等约束）。 他们表明，诸如 H1 和 H2 之类的历史记录是 ANSI 标准的一种解释所允许的（在 SERIALIZABLE 隔离级别），即使它们是不可序列化的：

1
2
H1: r1(x, 5) w1(x, 1) r2(x, 1) r2(y, 5) c2 r1(y, 5) w1(y, 9) c1 
H2: r2(x, 5) r1(x, 5) w1(x, 1) r1(y, 5) w1(y, 9) c1 r2(y, 9) c2

In both cases, T2 observes an inconsistent state (it observes invariant x + y = 10 to be violated). These histories are not allowed by the preventative approach; H1 is ruled out by P1 and H2 is ruled out by P2.

在这两种情况下，T2 都会观察到不一致的状态（它观察到不变量 x + y = 10 被违反）。 预防性方法不允许出现这些历史； H1被P1排除，H2被P2排除。

Optimistic and multi-version mechanisms [2, 5, 9, 20, 22] that provide serializability also disallow non-serializable histories such as H1 and H2. However, they allow many legal histories that are not permitted by P0, P1, P2, and P3. Thus, the preventative approach disallows such implemen- tations. Furthermore, it rules out histories that really occur in practical implementations.

提供可序列化性的乐观和多版本机制 [2,5,9,20,22] 也不允许不可序列化的历史，例如 H1 和 H2。 然而，它们允许许多 P0、P1、P2 和 P3 不允许的法律历史记录。 因此，预防性方法不允许此类实施。 此外，它排除了实际实施中真正发生的历史。

Phenomenon P0 can occur in optimistic implementations since there can be many uncommitted transactions modify- ing local copies of the same object concurrently; if neces- sary, some of them will be forced to abort so that serializ- ability can be provided. Thus, disallowing P0 can rule out optimistic implementations.

现象 P0 可能发生在乐观实现中，因为可能有许多未提交的事务同时修改同一对象的本地副本； 如果有必要，其中一些将被迫中止，以便提供可串行性。 因此，禁止 P0 可以排除乐观的实现。

Condition P1 precludes transactions from reading up- dates by uncommitted transactions. Such reads are disal- lowed by many optimistic schemes, but they are desirable in mobile environments, where commits may take a long time if clients are disconnected from the servers [12, 16]; furthermore, reads from uncommitted transactions may be desirable in high traffic hotspots [23]. For example, in his- tory H1, if T2 reads T1’s values for both x and y, it can be serialized after T1 :

条件 P1 阻止事务读取未提交事务的更新。 许多乐观方案都不允许这种读取，但它们在移动环境中是可取的，如果客户端与服务器断开连接，提交可能需要很长时间[12, 16]； 此外，在高流量热点中可能需要读取未提交的事务[23]。 例如，在历史 H1 中，如果 T2 读取 T1 的 x 和 y 值，则可以在 T1 之后序列化：

1
H10 : r1(x, 5) w1(x, 1) r1(y, 5) w1(y, 9) r2(x, 1) r2(y, 9) c1 c2

The above history can occur in a mobile system, but P1 disallows it. In such a system, commits can be assumed to have happened “tentatively” at client machines [12, 16]; later transactions may observe modifications of those tentative transactions. When the client reconnects with the servers, its work is checked to determine if consistency has been violated and the relevant transactions are aborted. Of course, if dirty reads are allowed, cascading aborts can occur, e.g., in history H10 , T2 must abort if T1 aborts; this problem can be alleviated by using compensating actions [18, 26, 19].

上述历史可以在移动系统中发生，但P1不允许。 在这样的系统中，可以假设提交“暂时”发生在客户端计算机上 [12, 16]； 后续交易可能会观察到这些暂定交易的修改。 当客户端重新与服务器连接时，将检查其工作以确定是否违反了一致性并中止相关事务。 当然，如果允许脏读，则可能会发生级联中止，例如，在历史记录H10中，如果T1中止，则T2必须中止； 这个问题可以通过使用补偿措施来缓解[18,26,19]。

Proscribing phenomenon P2 disallows a modification to an object that has been read by an uncommitted transaction (P3 rules out a similar situation with respect to predicates). As with P0, uncommitted transactions may read/write the same object concurrently in an optimistic implementation. There is no harm in allowing phenomenon P2 if transactions commit in the right order. For example, in history H2 given above, if T2 reads the old values of x and y, the transactions can be serialized in the order T2; T1:

禁止现象 P2 不允许对已由未提交事务读取的对象进行修改（P3 排除了谓词方面的类似情况）。 与 P0 一样，未提交的事务可以在乐观实现中同时读/写同一对象。 如果事务以正确的顺序提交，那么允许 P2 现象并没有什么坏处。 例如，在上面给出的历史H2中，如果T2读取x和y的旧值，则交易可以按照T2的顺序序列化； T1：

1
H20 : r2(x, 5) r1(x, 5) w1(x, 1) r1(y, 5) r2(y, 5) w1(y, 9) c2 c1

The real problem with the preventative approach is that the phenomena are expressed in terms of single-object his- tories. However, the properties of interest are often multi- object constraints. To avoid problems with such constraints, the phenomena need to restrict what can be done with indi- vidual objects more than is necessary. Our approach avoids this difficulty by using specifications that capture constraints on multiple objects directly. Furthermore, the definitions in the preventative approach are not applicable to multi-version systems since they are described in terms of objects rather than in terms of versions. On the other hand, our specifica- tions deal with multi-version and single-version histories.

预防性方法的真正问题在于，这些现象是用单一对象历史来表达的。 然而，感兴趣的属性通常是多对象约束。 为了避免此类约束带来的问题，现象需要对单个对象所能做的事情进行超出必要的限制。 我们的方法通过使用直接捕获多个对象的约束的规范来避免这个困难。 此外，预防性方法中的定义不适用于多版本系统，因为它们是根据对象而不是版本来描述的。 另一方面，我们的规范涉及多版本和单版本历史。

The approach in [8] only allows schemes that provide the same guarantees for running and committed transac- tions (a lock-based implementation does indeed have this property). However, many optimistic mechanisms provide weak guarantees to transactions as they run while provid- ing strong guarantees such as serializability for committed transactions. Our definitions allow different isolation guar- antees for committed and running transactions; in this paper, we only present guarantees for committed transactions.

[8]中的方法只允许为运行和提交的事务提供相同保证的方案（基于锁的实现确实具有此属性）。 然而，许多乐观机制在事务运行时为事务提供弱保证，同时提供强保证，例如已提交事务的可串行性。 我们的定义允许对已提交和正在运行的事务提供不同的隔离保证； 在本文中，我们仅对已提交的交易提供担保。

4. Database Model and Transaction Histories

We now describe our database model, transaction histories, and serialization graphs. We use a multi-version model similar to the one presented in [9]. However, unlike [9], our model incorporates predicates also. Furthermore, we al- low predicate behavior that is possible in non-locking based systems.

我们现在描述我们的数据库模型、事务历史和序列化图。 我们使用类似于[9]中提出的多版本模型。 然而，与[9]不同的是，我们的模型也包含谓词。 此外，我们允许在基于非锁定的系统中可能出现的谓词行为。

4.1. Database Model

The database consists of objects that can be read or writ- ten by transactions; in a relational database system, each row or tuple is an object. Each transaction reads and writes objects and indicates a total order in which these operations occur.

数据库由可以通过事务读取或写入的对象组成； 在关系数据库系统中，每一行或元组都是一个对象。 每个事务读取和写入对象并指示这些操作发生的总顺序。

An object has one or more versions. However, trans- actions interact with the database only in terms of objects; the system maps each operation on an object to a specific version of that object. A transaction may read versions created by committed, uncommitted, or even aborted trans- actions; constraints imposed by some isolation levels will prevent certain types of reads, e.g., reading versions created by aborted transactions.

一个对象有一个或多个版本。 然而，事务仅以对象的形式与数据库进行交互。 系统将对象上的每个操作映射到该对象的特定版本。 事务可以读取由已提交、未提交甚至中止的事务创建的版本； 某些隔离级别施加的约束将阻止某些类型的读取，例如读取由中止事务创建的版本。

When a transaction writes an object x, it creates a new version of x. A transaction Ti can modify an object multiple times; its first modification of object x is denoted by xi:1, the second by xi:2, and so on. Version xi denotes the final modification of x performed by Ti before it commits or aborts. A transaction’s last operation, commit or abort, indicates whether its execution was successful or not; there is at most one commit or abort operation for each transaction.

当事务写入对象 x 时，它会创建 x 的新版本。 一个事务Ti可以多次修改一个对象； 它对对象 x 的第一次修改用 xi:1 表示，第二次用 xi:2 表示，依此类推。 版本 xi 表示 Ti 在提交或中止之前对 x 执行的最终修改。 事务的最后一个操作，提交或中止，表明其执行是否成功； 每个事务至多有一次提交或中止操作。

The committed state reflects the modifications of committed transactions. When transaction Ti commits, each version xi created by Ti becomes a part of the committed state and we say that Ti installs xi ; the system determines the ordering of xi relative to other committed version of x. If Ti aborts,x does not become part of the committed state.

提交状态反映了已提交事务的修改。 当事务 Ti 提交时，Ti 创建的每个版本 xi 都成为已提交状态的一部分，我们说 Ti 安装 xi ； 系统确定 xi 相对于其他已提交版本的 x 的顺序。 如果 Ti 中止，xi 不会成为提交状态的一部分。

Conceptually, the initial committed state comes into existence as a result of running a special initialization transaction, T(init). Transaction T(init) creates all objects that will ever exist in the database; at this point, each object x has an initial version, x(init) , called the unborn version. When an application transaction creates an object x (e.g., by in- serting a tuple in a relation), we model it as the creation of a visible version for x. Thus, a transaction that loads thedatabase creates the initial visible versions of the objects being inserted. When a transaction Ti deletes an object x (e.g., by deleting a tuple from some relation), we model it as the creation of a special dead version, i.e., in this case, xi is a dead version. Thus, object versions can be of three kinds — unborn, visible, and dead; the ordering relationship between these versions is discussed in Section 4.2.

从概念上讲，初始提交状态是由于运行特殊初始化事务 T(init) 而产生的。 事务 T(init) 创建数据库中存在的所有对象； 此时，每个对象 x 都有一个初始版本 x(init) ，称为 unborn 版本。 当应用程序事务创建对象x（例如，通过在关系中插入元组）时，我们将其建模为创建x的可见版本。 因此，加载数据库的事务创建所插入的对象的初始可见版本。 当事务 Ti 删除对象 x 时（例如，通过从某个关系中删除元组），我们将其建模为创建特殊的 dead 版本，即在这种情况下，xi 是一个dead 版本。 因此，对象版本可以分为三种：未出生的、可见的和死亡的。 这些版本之间的顺序关系将在 4.2 节中讨论。

If an object x is deleted from the committed database state and inserted later, we consider the two incarnations of x to be distinct objects. When a transaction Ti performs an insert operation, the system selects a unique object x that has never been selected for insertion before and Ti creates a visible version of x if it commits.

如果一个对象 x 从已提交的数据库状态中删除并稍后插入，我们认为 x 的两个化身是不同的对象。 当事务 Ti 执行插入操作时，系统会选择一个之前从未选择插入的唯一对象 x，如果提交，Ti 将创建 x 的可见版本。

We assume object versions exist forever in the committed state to simplify the handling of inserts and deletes, i.e., we simply treat inserts/deletes as write (update) operations. An implementation only needs to maintain visible versions of objects, and a single-version implementation can maintain just one visible version at a time. Furthermore, application transactions in a real system access only visible versions.

我们假设对象版本永远以提交状态存在，以简化插入和删除的处理，即我们简单地将插入/删除视为写（更新）操作。 一种实现只需要维护对象的可见版本，而单版本实现一次只能维护一个可见版本。 此外，真实系统中的应用程序事务仅访问可见版本。

4.2. Transaction Histories

We capture what happens in an execution of a database system by a history. A history H over a set of transactions consists of two parts — a partial order of events E that reflects the operations (e.g., read, write, abort, commit) of those transactions, and a version order, , that is a total order on committed versions of each object.

我们通过历史记录来捕获数据库系统执行过程中发生的情况。 一组事务的历史记录 H 由两部分组成：事件 E 的部分顺序，反映这些事务的操作（例如读、写、中止、提交），以及版本顺序 ，即全顺序 每个对象的提交版本。

Each event in a history corresponds to an operation of some transaction, i.e., read, write, commit, or abort. A write operation on object x by transaction Ti is denoted by wi (xi ) (or wi (xi:m )); if it is useful to indicate the value v being written into xi , we use the notation, wi (xi , v). When a transaction Tj reads a version of x that was created by Ti , we denote this as rj (xi ) (or rj (xi:a )). If it is useful to indicate the value v being read, we use the notation rj (xi , v).

历史记录中的每个事件对应于某个事务的操作，即读、写、提交或中止。 事务 Ti 对对象 x 的写操作记为 wi (xi ) （或 wi (xi:m )）； 如果需要指示将值 v 写入 xi ，我们使用符号 wi (xi , v)。 当事务 Tj 读取由 Ti 创建的 x 版本时，我们将其表示为 rj (xi ) （或 rj (xi:a )）。 如果指示正在读取的值 v 有用，我们使用符号 rj (xi , v)。

The partial order of events E in a history obeys the fol- lowing constraints:

历史中事件 E 的偏序遵循以下约束：

  • It preserves the order of all events within a transaction including the commit and abort events.

    它保留事务中所有事件的顺序，包括提交和中止事件。

  • If an event rj (xi:m ) exists in E, it is preceded by wi (xi:m ) in E, i.e., a transaction Tj cannot read ver- sion xi:m of object x before it has been produced by Ti . Note that the version read by Tj is not necessarily the most recently installed version in the committed database state; also, Ti may be uncommitted when rj (xi:m ) occurs.

    如果 E 中存在事件 rj (xi:m)，则 E 中的事件 rj (xi:m) 前面有 wi (xi:m)，即事务 Tj 在 Ti 生成对象 x 之前无法读取对象 x 的版本 xi:m。 注意，Tj读取的版本不一定是提交数据库状态下最近安装的版本； 另外，当 rj (xi:m ) 发生时，Ti 可能未提交。

  • If an event wi (xi:m ) is followed by ri (xj ) without an intervening event wi (xi:n ) in E, xj must be xi:m . This condition ensures that if a transaction modifies object x and later reads x, it will observe its last update to x.

    如果事件 wi (xi:m ) 后面跟着 ri (xj )，而 E 中没有中间事件 wi (xi:n )，则 xj 必须是 xi:m 。 此条件确保如果事务修改对象 x 并且稍后读取 x，它将观察其对 x 的最后更新。

  • The history must be complete: if E contains a read or write event that mentions a transaction Ti , E must contains a commit or abort event for Ti .

    历史记录必须完整：如果 E 包含提及事务 Ti 的读取或写入事件，则 E 必须包含 Ti 的提交或中止事件。

A history that is not complete can be completed by append- ing abort events for uncommitted transactions in E. Adding these events is intuitively correct since any implementation that allows a commit of a transaction that reads from an uncommitted transaction Ti can do so only if it is legal for Ti to abort later.

不完整的历史记录可以通过在 E 中附加未提交事务的中止事件来完成。添加这些事件直观上是正确的，因为任何允许提交从未提交事务 Ti 读取的事务的实现只有在以下情况下才可以这样做： Ti 稍后中止是合法的。

For convenience, we will present event histories in ex- amples as a total order (from left to right) that is consistent with the partial order.

为了方便起见，我们将在示例中将事件历史呈现为与部分顺序一致的全顺序（从左到右）。

The second part of a history H is the version order, , that specifies a total order on versions of each object created by committed transactions in H; there is no ordering of versions due to uncommitted or aborted transactions. We also refer to versions due to committed transactions in H as committed versions. We impose two constraints on a history’s version order for different kinds of committed versions:

历史记录 H 的第二部分是版本顺序 ，它指定由 H 中已提交事务创建的每个对象的版本的总顺序； 由于未提交或中止的事务，不会对版本进行排序。 我们还将 H 中已提交事务的版本称为已提交版本。 我们对不同类型的提交版本的历史版本顺序施加两个约束：

  • the version order of each object x contains exactly one initial version, xinit , and at most one committed dead version, xdead .

    每个对象 x 的版本顺序恰好包含一个初始版本 xinit 和至多一个已提交的死版本 xdead 。

  • xinit is x’s first version in its version order and xdead is its last version (if it exists); all committed visible versions are placed between xinit and xdead .

    xinit 是 x 按其版本顺序排列的第一个版本，xdead 是其最后一个版本（如果存在）； 所有提交的可见版本都放置在 xinit 和 xdead 之间。

We additionally constrain the system to allow reads only of visible versions:

我们还限制系统只允许读取可见版本：

  • if rj (xi ) occurs in a history, then xi is a visible version.

如果 rj (xi ) 出现在历史记录中，则 xi 是可见版本。

For convenience, we will only show the version order for visible versions in our example histories; in cases where unborn or dead versions help in illustrating an issue, we will show some of these versions as well.

为了方便起见，我们将仅在示例历史记录中显示可见版本的版本顺序； 如果未出生或已死亡的版本有助于说明问题，我们也会展示其中的一些版本。

The version order in a history H can be different from the order of write or commit events in H. This flexibility is needed to allow certain optimistic and multi-version imple- mentations where it is possible that a version xi is placed before version xj in the version order (xi xj ) even though xi is installed in the committed state after version xj was installed. For example, in history Hw r iteor der ,

历史记录 H 中的版本顺序可能与 H 中写入或提交事件的顺序不同。需要这种灵活性来允许某些乐观和多版本实现，其中版本 xi 可能放置在版本 xj 之前 版本顺序 (xi xj )，即使 xi 在安装版本 xj 之后以已提交状态安装。 例如，在历史 Hw r ite order 中，