- Alan D. Fekete, University of Sydney, alan.fekete@sydney.edu.au
数据库管理系统添加价值的方式包括事务抽象，应用程序编码器可以将多个数据访问组合在一起，这些数据访问共同执行一个有意义的现实世界活动。该平台将提供“ACID”特性（原子性、一致性、隔离性和持久性），因此整个事务像单个事件一样发生。提供这些保证的机制包括崩溃恢复和回滚（通常基于日志条目）和并发控制（通常涉及锁）。
为了捕获并发控制的基本目标，我们考虑系统的执行是否为“可串行化”，这意味着存在另一种执行，其中事务之间根本没有相互交流，并且最终数据的最终状态和每个事务中观察到的值都相同。在可串行化执行中，即使平台没有显式强制任何完整性约束，只要每个程序单独运行时都能保持该完整性，结果仍然正确。理想情况下，平台的每个执行都将是可串行化的。
并发控制的早期机制是两阶段锁定（2PL），基于数据项的更新方法，采用排他锁（用于数据修改）或共享锁（用于读取），并将其保留到事务结束。相反，许多最近的平台采用多版本机制，多个访问可以看到数据项的较旧版本，而不是最新版本。这可以带来更好的性能，因为甚至在并发写操作完成之前就可以进行读取。
从数据库技术的早期开始，平台就在 API 中提供了命令，应用程序可以调用该命令将事务隔离级别设置为可串行化、可重复读或读已提交。Gray 等人[1]引入了读已提交隔离级别，作为锁定的变体，仅在读取访问期间持有共享锁，而不是像传统的可串行化两阶段锁定那样持有到事务结束。这样做可能会提高性能，但是数据完整性可能会面临风险。多版本并发控制也存在变体，其隔离性比可串行化弱，尽管给定级别允许的系统行为与传统的基于锁定的方式并不完全相同。
对弱隔离的期望是，应用程序开发者将根据对安全性的理解来决定每个事务应使用的隔离级别。Vandevoort、Ketsman 和 Neven 的工作以合理的方式（对于多版本隔离机制）做出了这一决定。此工作定义用于特定事务的分配（称为鲁棒分配）的方式是要求当每个事务都以所选隔离级别运行时，这些事务的每一次可能执行都是可串行化的。确定给定分配是否鲁棒会自然引出寻找最优分配的问题，这是困难的。
Vandevoort 等人的工作是以理论计算机科学风格完成的；关注精确的定义，并且知道特定的计算是否需要时间在输入大小或更糟的情况下是多项式的时间。一如既往的理论中有一些简化，可以使数学和符号易于管理。这项工作扩展了理论的悠久传统，适用于并发控制[2]。Vandevoort 等人的论文的显著贡献之一是捕获给定分配的可能执行。这很重要，因为隔离级别通常被描述为所有事务都有给定的隔离级别。了解执行方式如何进行混合隔离，需要仔细查看实现，然后将交互作用抽象以说明关键属性。该论文还提供了一个非常好的定理，它表明，如果分配允许交错的事务是不可串行化的，则存在一个特别简单的形式，作者将其称为“分式计划”。这使人们可以通过检查较少的交错来测试鲁棒性，并且是本文如何获得多项式时间算法的核心。
