事务调度

每个事务像一条保持自身字序的句子，调度把多条句子的字交织成一行。交织不能颠倒任何一句内部的字，却可能让一个事务在另一个提交前读到它的写。正是这条总记录，使“谁影响了谁”可以落成边与公式。

调度不先判好坏。它忠实记录一次可能正确、可能不可恢复、也可能不可串行化的执行。后续性质在同一个对象上逐层提问：冲突图是否有环，读者是否早于写者提交，崩溃时哪些事务已作出决定。

初值 $x=5,y=7$。事务 $T_1$ 把一单位从 $x$ 移到 $y$，$T_2$ 把读到的 $x$ 加倍。考虑

r1(x)->5; w1(x,4);
r2(x)->4; w2(x,8);
r1(y)->7; w1(y,8);
c1; c2

两个事务各自的事件次序都未改变，所以这是一个调度。$r_2(x)$ 的 reads-from 是 $w_1(x,4)$，但它发生在 $c_1$ 前；调度对象由此保留了一次未提交读取。它是否可接受，要交给可恢复调度公理库可恢复事务调度Recoverable transaction schedule · Recoverable schedule要求读取其他事务写入的事务不能先于写者提交，从而避免已承诺结果依赖后来中止的来源。或更强条件判断，不能从“保持程序次序”推出。

若把 $r_1(y)$ 移到 $w_1(x,4)$ 前，仍可能保持 $T_1$ 的源码次序吗？答案取决于原事务程序；调度定义不能自行重排同一事务。若日志只记录写而省略读，也无法恢复 reads-from，因而不足以判定视图等价或读取异常。

中止事件还带来另一层边界。调度可以记录 $a_1$，但“删除 $T_1$ 的写”需要恢复语义；物理页上是否曾出现这些值不是调度单独回答的问题。分析可串行性时必须说明只看已提交投影，还是使用包含中止与补偿的扩展历史。

单版本解释中，$r_j(x)$ 通常读它之前最近且未被撤销的可见写；多版本解释还要给版本序与读视图。同一串事件若省略版本标识，可能在两种模型下得到不同 reads-from，因此“把调度交给判定器”前必须固定读取语义。

事务调度是 冲突可串行化公理库冲突可串行化Conflict serializability · Conflict-serializable schedule以冲突操作的相对次序定义串行等价，并用前驱图无环精确判定有限调度。、视图可串行化公理库视图可串行化View serializability · View-serializable schedule以初值读取、读取来源和最终写者保持来定义调度的视图等价，并覆盖部分含盲写的非冲突串行历史。、SQL 隔离现象以及恢复性层级的共同输入。共享一个明确事件字母表能避免同一符号在一处表示逻辑写、另一处却表示物理页刷盘。

测试工具可从数据库 trace 归一化出候选调度，但墙钟时间相同不等于事件相同，缺失的读值也不能靠最终状态唯一补回。要把运行日志用于证明，必须说明事务标识、操作边界、提交结果及不确定顺序如何处理。

调度还可以作为并发测试的缩减对象：保留每个事务程序次序与真实冲突次序，折叠不影响数据库观察的线程内部计算。缩减是否可靠取决于投影定义；把触发器写、索引范围锁或约束查询漏掉，会制造一个比真实执行更温和的调度。