加锁协议

以下几种加锁协议结合特定的规则来保证调度是冲突可串行化的：

1. 共享锁 (Shared Lock) 和排他锁 (Exclusive Lock) 与两阶段锁协议 (2PL)

   • 协议规则： 这是标准的关系数据库管理系统中最常用的 2PL 版本。
     • 良好形式的事务: 事务 Ti 在读取数据项 A 之前，必须获得 A 的共享锁 l-Si(A)；在写入数据项 A 之前，必须获得 A 的排他锁 l-Xi(A)。所有锁最终都需要释放 [51]。事务如果先读后写同一数据项，可能需要将共享锁升级为排他锁 [53]。
     • 合法的调度器: 调度器必须根据 锁的兼容矩阵 来授予锁 [54, 55]。共享锁 (S) 与其他共享锁 (S) 兼容，但不与排他锁 (X) 兼容。排他锁 (X) 与任何其他锁 (S 或 X) 都不兼容 [55]。只有当事务请求的锁模式与数据项上当前所有已持有的锁模式都兼容时，才能授予锁 [66]。
   • 保证冲突可串行化的机制： 教材中明确指出，遵循 Shared/Exclusive 锁规则和两阶段锁协议的调度，其结果是冲突可串行化的 [56]。证明思路与基本排他锁的 2PL 类似 [57]，核心仍然是 2PL 特性确保了基于锁释放顺序的前趋关系是无环的，从而保证了优先图无环。共享锁的引入提高了并发度（多个事务可以同时读取同一数据项），但冲突的定义和 2PL 保证无环的原理保持不变。

2. 树协议 (Tree Protocol)

   • 协议规则 (教材主要描述排他锁版本): 假设数据库中的数据项组织成一个树形结构。
     • 事务 Ti 获得的第一个锁可以是树中的任何数据项。
     • 之后，事务 Ti 只能锁定节点 Q 当且仅当 Ti 已经持有了 Q 的父节点 parent(Q) 的锁。这意味着加锁操作是沿着树结构向下进行的。
     • 事务可以随时释放锁。注意： 与 2PL 不同，树协议不强制存在一个只释放锁的收缩阶段。
     • 事务释放某个数据项的锁后，不能再次锁定该数据项。
   • 保证冲突可串行化的机制：
     • 教材提出树协议可以保证 冲突可串行化。尽管树协议不遵循 2PL，允许在增长阶段释放锁，但其通过限制加锁的方式（必须先锁父节点才能锁子节点）来防止优先图中出现环。如果事务 Ti 和 Tj 冲突，它们必然在某个共同祖先节点（可能就是冲突数据项 A 本身）上产生了依赖。树协议强制事务从根（或某个入口点）向下加锁，这种结构化的加锁顺序本身就足以防止形成依赖环。
     • 例如，如果 Ti 锁定了 A 之前锁定了 parent(A)，而 Tj 后来也需要锁定 A，Tj 必须等待 Ti 释放 A。如果在 Tj 释放 A 后 Ti 又想锁定 A，它必须重新从根开始向下加锁（或从某个已锁定的祖先节点），但根据规则 4，它不能再次锁定 A。这种规则组合起来，确保了事务之间的冲突依赖不会形成循环。

3. 验证并发控制（Validation concurrency control），也称为乐观并发控制（optimistic concurrency control），是一种用于管理数据库事务并发执行的机制。

   • 它的核心思想是将事务的执行分为三个阶段:
     1. 读阶段 (Read Phase)：事务读取数据库需要的数据，并将所有写操作记录在临时存储中，而不是直接修改数据库。在这个阶段通常不使用锁。
     2. 验证阶段 (Validate Phase)：这是一个原子操作阶段。系统检查当前事务到目前为止的执行是否与已提交事务的调度可串行化。验证的顺序（例如 T1, T2, T3…）决定了最终等价的串行执行顺序。
     3. 写阶段 (Write Phase)：如果验证成功，系统将临时存储中的写操作应用到数据库中。如果验证失败，事务将被中止并回滚。
   • Validation 并发控制的主要优点在于其乐观性，即假设冲突很少发生。它允许事务在读阶段自由地执行，只在验证阶段才检查冲突。这种方法适用于冲突率较低、系统资源充足或有实时性要求的场景 。
   • 它的规则旨在防止并发事务之间的读写冲突，例如一个事务在验证时，会检查它读取的数据是否被在此之前已验证成功的其他事务修改过，或者它修改的数据是否会与之前已验证成功但尚未完成写操作的事务发生冲突。