\[ \def\po{\mathsf{\textcolor{red}{po}}} \def\so{\mathsf{\textcolor{purple}{so}}} \def\wr{\mathsf{\textcolor{green}{wr}}} \def\ww{\mathsf{\textcolor{red}{ww}}} \def\rw{\mathsf{\textcolor{blue}{rw}}} \def\co{\mathsf{\textcolor{orange}{co}}} \def\SO{\mathsf{\textcolor{purple}{SO}}} \def\VIS{\mathsf{\textcolor{green}{VIS}}} \]
摘要
分布式数据库系统出现了支持多协调器和多副本存储的新架构，这给事务调度的正确性带来了新的挑战，包括缺少中心协调器带来的新数据异常以及多副本机制带来的读取数据一致性等问题。基于事务隔离级别和分布式系统一致性协议的定义，为多协调器多副本分布式数据库的事务多级一致性构建了一个混合依赖图模型。该形式化模型为事务的正确调度提供具有鲁棒性的评价标准，可以方便地对数据库事务调度情况进行动态或静态分析检验.
作者：数据工程与知识工程教育部重点实验室(中国人民大学)、中国人民大学 信息学院 水治禹、卢卫、赵展浩、何粤阳、张孝、杜小勇
基于环的数据异常与隔离级别定义
当依赖图中出现某种环结构时，我们说该依赖图违反了对应的隔离级别。
分布式系统一致性建模
数据依赖图
基于环的数据异常与隔离级别定义
写已提交
定义 1 脏写
如果在数据依赖图中存在一个环，环全部由写写依赖边构成，那么我们就说历史序列 \(H\) 中存在一个脏写异常。
数据库隐式要求所有运行事务不允许出现脏写异常。在写已提交级别，可以保证禁止脏写异常。
定义 2 写已提交（在其他文献中被称为读未提交 Read Uncommitted）
禁止脏写异常环。在数据依赖图中，若不存在脏写，那么就称历史序列达到了写已提交级别。
达到写已提交级别，所写的数据可以看作是已提交的数据。在环定义中，并不要求所写数据一定是严格已提交的，即使是并发的写，只要不存在写写环，那么写操作所在的事务就等价于一个串行化的序列（仅考虑写操作）。
读已提交
定义 3 脏读
- 读回滚。如果历史记录 \(H\) 中 \(T_2\) 读取了 \(T_1\) 写过的数据，并且 \(T_1\) 回滚，则历史序列 \(H\) 中存在“读回滚”的脏读异常。
- 读中间。如果历史记录 \(H\) 中 \(T_2\) 读取了 \(T_1\) 写过但并不是最终提交版本的数据，则历史序列 \(H\) 中存在“读中间”的脏读异常。
- 写读环。如果在数据依赖图中存在一个环，环全部由写写依赖边或写读依赖边构成（即，\(\ww^*∪\wr^*\)），那么就说历史序列 \(H\) 中存在一个脏读异常。
定义 4 读已提交
禁止脏读异常. 在数据依赖图中, 不存在脏读异常, 那么称历史序列达到了读已提交级别.
