多版本序列化依赖图

三条小约束如何保护一次读 ​

假设键x的版本链为 $x_A\prec x_B\prec x_C$，事务R读到 $x_B$。wr要求B先于R；ww要求A先于B、B先于C；rw要求R先于C。于是R被放进B和C之间，恰好读到B版本。

若只保留wr，就可能把C排在R前面，令R在串行运行时看见C而非B。若只保留“谁与谁访问同键”而不分方向，也无法知道R应夹在哪两个写者之间。

无环为什么足够 ​

取图的任意拓扑序理路拓扑排序Topological sort给有向无环图顶点排列线性次序，使每条边从前指向后。，按它逐笔运行事务。对键x，所有写者受ww链约束，发布次序与输入相同。若事务T外部读 $x_h$，wr把来源写者放在T前；所有比 $x_h$更晚的外部写者又被rw放到T后。因此T读之前的最新外部版本恰为 $x_h$。初始读没有来源写者，却同样被rw排在所有后续写者之前。

事务自己的写仍按原程序次序覆盖私有层；它不改变上述外部来源约束。逐读得到同样输入后，确定性事务沿同样分支产生同样写与返回值，最终写者也由版本链保持。若应用还有时钟、随机数或外部调用结果，必须先将这些输入冻结，不能从数据库依赖图推出它们也相同。

反向更直接：任何符合要求的串行顺序都必须遵守三类边，有限全序不可能遵守有向环。因此图上的具体环就是“不存在保持此版本序的串行见证”的拒绝证书。

一笔只读事务补上最后一条边 ​

初态 $x=y=0$。P先开始，读到 $y_0=0$，准备写x=1但尚不提交。Q写y=1并提交；R此后开始，读到x的初始版本和Q的y版本，再先于P提交。最后P发布x=1。可用下列事件序号核算：

图中有 $Q\stackrel{wr(y)}{\to }R$、$R\stackrel{rw(x)}{\to }P$、$P\stackrel{rw(y)}{\to }Q$。没有两笔事务写同一键，版本链各自也正确；矛盾来自Q必须在R前、R必须在P前、P又必须在Q前。R没有写，仍能通过读取来源参与环。

这里rw不按墙钟读写事件的先后机械产生：R读取旧x时，P的私有写可能已经准备好，也可能尚未发生；决定箭头的是返回版本与最终发布版本的顺序。未提交私有副本不是R的读取来源。

删除一次读取，环就消失 ​

如果R只读x、不读y，删去Q→R，余下只有R→P→Q，拓扑序R、P、Q成为合法串行见证。提交的现实先后是Q、R、P，却可以有不同的串行解释。只看到两条连续rw边，不能宣称已经找到环；SSI理路可串行化快照隔离Serializable snapshot isolation · SSI在SI前提下证明环必含两条相邻并发读写反依赖，以可复算危险结构保守拒绝提交，并限定只读快照、历史保留和重试条件。正是利用这种必要但非充分的结构作保守拒绝。

固定版本顺序的失败，不等于一般视图失败 ​

再看一份不要求SI写写规则的快照历史：B先开始并读x的初始版本；A随后盲写x=1、y=1并先提交；B写y=2后提交；最后C盲写x=3、y=3并提交。给定提交版本序中，y的A版本在B前，产生A→ww B；B没看见A的x，又产生B→rw A，形成环。

若允许改变中间版本顺序，串行B、A、C仍保留唯一外部读x₀，最终写者也都是C。它是另一份合法视图，但不保留y的A、B先后。这说明本页特意固定版本序的量词确实更强；这份历史也因A、B并发写y而不满足经典SI，不能拿它否定SSI定理。

数值相等不能合并版本身份 ​

设A写x=1，B后来也写x=1，R读取B版本。将R的来源标为A不会改变显示数字，却删掉真实的B→R约束。若另一个键把A、B、R连起来，这个“按值去重”的图可能从有环变成无环。事务日志用于审计时，创建者或唯一版本标识必须和数值一起保存。

谓词读取也不能只记录返回行。查询[10,13)为空仍观察了该域的缺失状态；随后插入11会覆盖其中一个缺失版本。有限键域模型可把这次查询展开成对10、11、12的三个读，因此会产生所需rw边。真实开放键空间需要范围、谓词或等价访问证据，不能枚举不存在的全宇宙来冒充数据库实现。

构图成本与判定成本分开 ​

若已经给出n个顶点、e条边，拓扑排序或深度优先搜索的成本为 $O(1+n+e)$。输入构图另计：设版本总数V、外部读记录数R，本页参考程序为每次读扫描相应键的全部后继，粗略上界为 $O(1+V+RV+n)$，显式去重后边存储至多 $O(n^2)$，逐键证据列表还可超过这个数量。

若只生成直接后继边，已排序的版本链可以降低边量；但“图检测线性”始终是对已经生成的图说的，不自动意味着从任意数据库日志到结果也线性。附件保留易检查的全部后继表示，不声称做了最优增量维护。

事后证书与提交控制 ​

对已全部确认提交的历史发现环，只能报告已有违约，不能任选一笔已承诺事务强行改成中止。在线控制必须在最后相关提交尚可拒绝时介入；乐观验证理路乐观并发验证Optimistic concurrency control · OCC · 串行提交验证以固定快照和私有写集执行事务，在一个原子步骤内验证所有外部读再发布，证明按提交顺序的串行见证并暴露拆开验证的竞态。让全部已接受事务沿提交顺序解释，SSI则保留更宽的候选顺序。

快照验证终结任务要求交付版本链、reads-from、三类逐键边、拓扑序或环，并把只读三环改成无环双边链。成功标准是每条边都能回到具体版本证据，不能只画一圈事务名字。