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