数据库事务模型分析（2）—— 等价关系

在本节中，基于上一节的页模型，提出并发执行正确性的概念，并建立多个事务在时间上交叉执行的模型，提出有关并发事务调度的概念。首先要明确的是，事务的执行是高度动态的，完全建模会带来巨大的理解成本，实际上，当事务到来，并发控制需要对该事务做出执行决定，并使能其和系统中正在运行的事务正确同步。其次，需要考虑执行失败而被终止的事务，在正常执行的路径中，包含提交终止。这些操作的处理方式和直觉很不一样。

并发执行的事务之间的数据访问操作存在潜在的冲突，比如“修改后丢失”、“读不一致”、“脏读”等问题，作为事务执行顺序的保证来说，这些异常都是要避免的，给外部执行一致的印象。

为了判断事务执行时，何种情况是期望的，何种情况是应该避免的，调度器需要在线的应用这些规则。首先，本文假定调度中包含了事务结束标志成功或者不成功，具体的，一个事务成功的结束使用$c$表示，即事务在没有被中断的情况下完成了内部所有的数据操作，而失败事务的结束使用$a$表示，一个被终止的事务不应该对底层数据产生任何影响，这由恢复过程保证。

调度和历史

设$T={t_1,…,t_n}$是一个有限事务集合，对每一个$t_i \in T$，都有$t_i=(op_i,<_i)$，其中$op_i$是$t_i$的操作集合，$<_i$表示操作的顺序，$i \in [1, n]$。
$T$中的一个历史$s=(op(s),<_s)$定义如下：

1. $op(s) \subseteq \bigcup_{i=1}^{n}op_i \bigcup_{i=1}^{n}{a_i,c_i}$，并且$\bigcup_{i=1}^{n}op_i \subseteq op(s)$，即事务的历史$s$是由事务所有操作的并集和每个事务的终止操作组成；
2. $ \forall i \in [1,n], c_i \in op(s) \Leftrightarrow a_i \notin op(s)$，也即每个事务都有结束，成功或者失败，但不能同时存在；
3. $ \bigcup_{i=1}^{n}<_i \subseteq <_s$，也即所有事务的顺序都包含在由$s$给出的偏序中；
4. $ \forall i \in [1,n], \forall p \in op_i, p <_s a_i | p <_s c_i$，也即成功或者失败总是作为事务最后一步出现；
5. 对每一个来自不同事务的一对操作$p,q \in op(s)$，如果访问同一个数据页并且其中至少一个为写操作，满足$p<_s q|q <_s p$。

因此一个历史，或者满足偏序的事务来说，必须：包含所有事务的所有操作（1），使每个事务都包含唯一的结束符（2），保持每个事务中操作的顺序（3），以结束符作为每个事务的最后一步（4），安排冲突操作的顺序（5）。由于（1）和（2），字面上历史也被称作完整调度。

同样的，也可以给出串行历史的调度：
一个事务序列历史$s$为串行的，当且仅当在$s$中对历史中的任意两个事务$t_i$和$t_j, i \neq j$，$t_j$的所有操作都在$t_i$之后，或者相反。

调度正确性判定准则

这一部分的目标是给出调度的正确性准则，如果$S$是所有调度的集合，正确性准则可以在形式上看作一个映射：
$$
\sigma.S \rightarrow {0,1}
$$
这个映射对每个调度$s \in S$返回一个布尔值，因此，对于调度$s \in S$，如果$s$是正确的，那么$\sigma(s)=1$，也即：
$$
correct(S):={ s \in S | \sigma(s) = 1}
$$

针对一个调度，判断其正确性的准则至少需要满足以下要求：

1. $S$ 中至少存在某些正确的调度；
2. $s \in correct(S)$是可以有效判定的，不存在停机问题；
3. 对于给定的事务集合，可以找到调度最优解。

本系列中要保持底层数据的完整性，并且每个事务都能保持数据的完整性。而串行事务执行总是正确的，在合适的选择事务调度的等价关系后，使用串行历史作为正确性的度量标准，因此可以给出在所有调度的集合$S$上的等价关系：
$$
([S]\approx) ={[s] \approx | s \in S }
$$
其中，$[S]\approx$是通过$\approx$得到的所有等价类的集合，显然，一个调度集合中的正确调度都是两两等价的，因此任意一个调度$s$都可以代表这个类。而对可以选出串行调度的调度集合，这种调度集合中的调度被成为可串行化的。因此在接下来的分析中，本文会做以下两件事：

1. 定义调度的等价概念；
2. 通过和串行历史的等价定义“可串行化”。

调度Herbrand等价语义

接下来本文将通过一种语义的概念在调度之间建立等价关系。精确地描述未知的事务语义是困难的，因此为了明确事务调度在事务上下文的语义，先明确在调度中出现的操作的语义，然后再定义事务调度本身。

本文在考虑调度等价的问题时，先对事务失败回滚的情况做出忽略，稍后在后面的章节对该问题进行展开。

对一个任意的调度$s$，有如下假设：

1. 一个事务$t_i \in trans(s)$的一个操作$r_i(x) \in s$读取在$r_i(x)$之前出现的最后一个$w_j(x), j \neq i$写入的值；
2. 一个操作$w_j(x) \in s$写入的新值潜在依赖于$t_i$中$w_j(x)$之前的属于$active(s) \cup committed(s)$的事务中读取的所有数据的值。

对于第一个假设，可能存在一个问题是，并不是调度中每个读操作前都有一个写操作，比如：
$$
s=r_1(x)r_2(x)w_1(x)r_2(x)…
$$
为了统一不同的情况，假设在每个调度的头部都有一个假想的初始事务$t_0$，$t_0$写入调度中提及的所有数据项后提交，这种情况下，上面提到的调度变成：
$$
s=w_0(x)w_0(y)c_0r_1(x)r_2(x)w_1(x)r_2(x)…
$$
简单来说，初始事务为一个给定的调度定义了初始状态。

设$s$是一个调度，操作$r_i(x), w_i(x) \in op(x)$的Herbrand语义$H_s$如下递归定义：

1. $H_s(r_i(x)) := H_s(w_j(x))$, 其中$w_j(x),j \neq i$，是$s$中在$r_i(x)$之前的对$x$的最后一个写操作；
2. $H_s(w_i(x)) := f_{ix}(H_s(r_i(y_1)),…,H_s(r_i(y_m)))$，其中$r_i(y_j), 1 \leq j \leq m$，是事务$t_i$在调度$s$里发生在$w_i(x)$之前所有读操作，而$f_{ix}$是一个未知m元函数。
   假设在每一个事务中，对每一个数据项至多只有一个写操作，易验证对每个操作$p \in op(s)$，$H_s(p)$的定义都是合理的。其次，初始事务$t_0$对数据的写操作和一个0元函数$f_{0x}$联系起来。

而在此基础上可以进一步推广“事务的Herbrand空间”，也即Herbrand全域。
设$D={x,y,z…}$是一个数据的有限集合，对于一个事务$t$，设$op(t)$是事务$t$对数据的操作集合，事务$t_i(i>0)$的Herbrand空间$HU$是满足下面条件的最小符合集合：

1. 对每个$x \in D$，有$f_{0x}() \in HU$；
2. 若$w_j(x) \in op(t_i), |{r_i(y)|(y \in D)r_i(y) < t_i w_i(x)}|=m$，并且如果$v_1,…,v_m \ in HU$，那么$f_{ix}(v_1,…v_m) \in HU$。

因此调度中对数据操作的语义范围是Herbrand空间值的集合，但Herbrand空间纯粹是基于数学符号的语义构造，没有真实事务读写真实数据的任何信息。

最后根据Herbrand全域定义可以推出调度的Herbrand语义，所以调度$s$的语义是映射：
$$
H[s]:D \rightarrow HU
$$
进一步的，
$$
H[s] (s) := H_s(w_i(s))
$$
其中对于每个$x \in D$，$w_i(x)$是$s$对$x$的最后一个写操作。也就是说，调度$s$的Herbrand语义是$s$中最终写入值得集合。而再次重申暂时不对异常终止做考虑。上述得定义虽然普通，但有趣得是，能适用于任意复杂具体事务的解释，但同样的，Herbrand一般性的代价是具体处理起来异常复杂。
有了以上定义，可以依据此定义不同可串行的事务调度形式，或者说定义了和串行调度等价的联系，而从根本上说，这样的等价关系定义只对历史（也就是完整调度）有意义，后面本系列会讨论如何定义任意调度的正确性问题，在这种情况下，调度也不必是历史。