数据库管理系统中数据异常体系化定义与分类-李海翔，李晓燕，刘畅，杜小勇，卢卫，潘安群.pdf
免费下载
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software, 2022,33(3):909−930 [doi: 10.13328/j.cnki.jos.006442] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
数据库管理系统中数据异常体系化定义与分类
∗
李海翔
1
,
李晓燕
2
,
刘
畅
1
,
杜小勇
3,4
,
卢
卫
3,4
,
潘安群
1
1
(腾讯科技(北京)有限公司, 北京 100080)
2
(北京大学 数学科学学院 信息与计算科学系, 北京 100871)
3
(数据工程与知识工程教育部重点实验室(中国人民大学), 北京 100872)
4
(中国人民大学 信息学院, 北京 100872)
通信作者: 李海翔, E-mail: blueseali@tencent.com
摘 要: 数据异常尚没有统一的定义, 其含义是指可能破坏数据库一致性状态的特定数据操作模式. 已知的数据
异常有脏写、脏读、不可重复读、幻读、丢失更新、读偏序和写偏序等. 为了提高并发控制算法的效率, 数据异
常也被用于定义隔离级别, 采用较弱的隔离级别以提高事务处理系统的效率. 体系化地研究了数据异常以及对应
的隔离级别, 发现了 22 种未被其他文献报告过的新的数据异常, 并对全部数据异常进行分类. 基于数据异常的分
类, 提出了新的且不同粒度的隔离级别体系, 揭示基于数据异常定义隔离级别的规律, 使得对于数据异常和隔离
级别等相关概念的认知可以更加简明.
关键词: 事务处理; 数据异常; 隔离级别; 并发访问控制算法; 数据库
中图法分类号: TP311
中文引用格式: 李海翔, 李晓燕, 刘畅, 杜小勇, 卢卫, 潘安群. 数据库管理系统中数据异常体系化定义与分类. 软件学报,
2022, 33(3): 909–930. http://www.jos.org.cn/1000-9825/6442.htm
英文引用格式: Li HX, Li XY, Liu C, Du XY, Lu W, Pan AQ. Systematic Definition and Classification of Data Anomalies in Data
Base Management Systems. Ruan Jian Xue Bao/Journal of Software, 2022, 33(3): 909−930 (in Chinese). http://www.jos.org.cn/1000-
9825/6442.htm
Systematic Definition and Classification of Data Anomalies in Data Base Management Sy stems
LI Hai-Xiang
1
, LI Xiao-Yan
2
, LIU Chang
1
, DU Xiao-Yong
3,4
, LU Wei
3,4
, PAN An-Qun
1
1
(Tencent Technology (Beijing) Co., Ltd, Beijing 100080, China)
2
(Department of Information and Computational Sciences, School of Mathematical Sciences, Peking University, Beijing 100871, China)
3
(Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China), Ministry of Education, Beijing 100872,
China)
4
(School of Information, Renmin University of China, Beijing 100872, China)
Abstra ct : There is no unified definition of data anomalies, which refers to the specific data operation mode that may destroy the
consistency of the database. Known data anomalies include Dirty Write, Dirty Read, Non-repeatable Read, Phantom, Read Skew, Write
Skew, etc. In order to improve the efficiency of concurrency control algorithms, data anomalies are also used to define the isolation levels,
because the weak isolation level can improve the efficiency of transaction processing systems. This work systematically studies the data
anomalies and the corresponding isolation levels. Twenty-two new data anomalies are reported that have not been reported by other
researches, and all data anomalies are classified miraculously. Based on the classification of data anomalies, two new isolation levels with
different granularity are proposed, which reveals the rule of defining isolation levels based on data anomalies and makes the cognition of
data anomalies and isolation levels more concise.
∗ 基金项目: 国家重点研发计划(2017YFB1001803); 国家自然科学基金(61872008)
本文由“数据库系统新型技术”专题特约编辑李国良教授、于戈教授、杨俊教授和范举教授推荐.
收稿时间: 2021-06-30; 修改时间: 2021-07-31; 采用时间: 2021-09-13; jos 在线出版时间: 2021-10-21
910
软件学报 2022 年第 33 卷第 3 期
Key words: transaction processing; data anomalies; isolation level; concurrency control algorithm; database
数据库的隔离级别是通过消除特定的数据异常来定义的. ANSI-SQL 标准
[1]
描述了 4 种数据异常: 脏写
(Dirty Write)、脏读(Dirty Read)、不可重复读(fuzzy or non-repeatable read)、幻读(phantom). 相应地,其定义了
4 种隔离级别: 读未提交、读已提交、可重复读、可串行化. 例如, 读已提交可以消除脏写和脏读异常, 最高
的可串行化级别可以消除所有的数据异常. 大多数数据库都支持了这 4 种隔离级别, 如 DB2、Informix、
MySQL、PostgreSQL、TDSQL 等. 这些数据库在默认配置下, 使用较弱的隔离级别, 而较弱的隔离级别被认
为可以提高数据库事务处理的吞吐量.
Berenson 等人
[2]
指出: ANSI-SQL 标准对数据异常的描述缺少形式化定义, 造成对数据异常的理解存在偏
差. 因此, 基于形式化表达对上述 4 个数据异常进行了重新定义, 并提出了 4 个新的数据异常: 丢失更新(Lost
Update 和 Cursor Lost Update)、读偏序(Read Skew)、写偏序(Write Skew). 截止到目前, 本文通过对相关文献
的详细调研, 发现已被公开报告过的数据异常共有 18 个
[1−12]
, 见表 1.
表 1 现存数据异常汇总
编号
异常名称
(
异常名称
,
文献
(
年份
))
形式化定义
1 Dirty Write, Ref.[1](1992), Ref.[2](1995) W
1
[x]…W
2
[x]…(C
1
or A
1
) and (C
2
or A
2
) in any order
2 Lost Update, Ref.[2](1995) R
1
[x]…W
2
[x]…W
1
[x]… C
1
3 Dirty Read, Ref.[1](1992), Ref.[2](1995) W
1
[x]…R
2
[x]…(A
1
and C
2
in either order)
4 Aborted Read, Ref.[3](2000), Ref.[4](2015) W
1
(x1:i)…R
2
(x1:i)…(A
1
and C
2
in any order)
5 Fuzzy or Non-repeatable Read, Ref.[1](1992) R
1
[x]…W
2
[x]…C
2
…R
1
[x]…C
1
6 Phantom, Ref.[1](1992) R
1
[P]…P
2
[y in P]…C
2
…R
1
[P]…C
1
7 Intermediate Read, Ref.[3](2000), Ref.[4](2015) W
1
(x1:i)…R
2
(x1:i)…W
1
(x1:j) C
2
8 Read Skew, Ref.[2](1995) R
1
[x]…W
2
[x]…W
2
[y]…C
2
…R
1
[y]…(C
1
or A
1
)
9
未命名的异常
, Ref.[5](2000)
R
3
[y]R
1
[x]W
1
[x]R
1
[y]W
1
[y]C
1
R
2
[x]W
2
[x]R
2
[z]W
2
[z]C
2
R
3
[z]C
3
10 Fractured Read, Ref.[6](2014), Ref.[7](2017) R
1
[x
0
]…W
2
[x
1
]…W
2
[y
1
]…C
2
…R
1
[y
1
]
11 Serial-concurrent-phenomenon, Ref.[8](2014) R
1
[x
0
]…W
2
[x
1
]…W
2
[y
1
]…C
2
…R
1
[y
1
]
12 Cross-phenomenon, Ref.[8](2014) R
1
[x
0
]…R
2
[y
0
]…W
3
[x
1
]…C
3
…W
4
[y
1
]C
4
…R
2
[x
1
]…R
1
[y
1
]
13 Long Fork Anomaly, Ref.[7](2017) R
4
[x
0
]…W
1
[x
1
]…R
3
[y
0
]…R
3
[x
1
]…W
2
[y
1
]…R
4
[y
1
]
14 Causality Violation Anomaly, Ref.[7](2017) R
3
[x
0
]…W
1
[x
1
]…C
1
…R
2
[x
1
]…W
2
[y
1
]…C
2
…R
3
[y
1
]
15
A Read-only Transaction Anomaly,
Ref.[9](1982), Ref.[10](2004)
R
2
(x
0
,0)R
2
(y
0
,0)R
1
(y
0
,0)W
1
(y
1
,20)C
1
R
3
(x
0
,0)R
3
(y
1
,20)C
3
W
2
[x
2
,
−
11]C
2
16 Write Skew, Ref.[2](1995) R
1
[x]…R
2
[y]…W
1
[y]…W
2
[x]…(C
1
and C
2
occur)
17 Predicate-based Write Skew, Ref.[11](2005) R
1
({x
0
in P})…R
2
({y
0
in P})…W
1
[{y
1
in P}]…C
1
…W
2
[{x
1
in P}]
18
读半已提交数据异常
(
分布式数据库
), Ref.[12](2019)
R
1
[x]…W
2
[x]…W
2
[y]…C
2
…R
1
[y]…C
1
本文的主要贡献在于: 体系化地研究了数据异常, 用统一的方法定义了数据异常(并提出 22 种未被报告
过的数据异常), 并研究了数据异常的特征, 对所有数据异常进行分类, 基于数据异常的分类方法演示了如何
基于数据异常定义不同粒度的隔离级别. 本文第 1 节描述相关工作. 第 2 节给出描述数据异常的框架, 并对数
据异常进行分类和形式化定义. 第 3 节基于数据异常的分类定义隔离级别. 第 4 节总结全文并致谢.
1 相关工作
过往研究未曾有对数据异常进行系统化地研究, 已知的文献研究提及数据异常的,主要有以下几个方面.
• 不断以案例的方式报告新的数据异常, 缺乏体系化研究.
数据异常一直没有被体系化地展开过研究, 对于数据异常的认识停留在了案例式的方式. 如表 1 所示,
2000 年、2005 年、2014 年、2017 年等都有新的数据异常被提出, 表明数据异常的研究一直没有间断过.
ANSI-SQL 标准
[1]
提出的 4 种数据异常都是单个变量构成的数据异常. 文献[3,4]提出的中间读
(Intermediate Reads)、回滚读(Abort Read)等异常也是只和单个变量相关的数据异常. 文献[2]提出的读偏序和
写偏序等异常涉及了两个变量造成的数据异常. 文献[5]提出了 3 个变量相关的类似读偏序的异常. 文献[13]
在 PostgreSQL 中讨论了更多形式的写偏序异常的变种. 文献[9,10]描述了两个变量 3 个并发事务造成的异常
(A Read-only Transaction Anomaly). 文献[6−11]提出的 3 个或 4 个事务构成的两变量异常, 没有进一步研究更
多变量是否会造成新数据异常. 尽管数据异常看似和变量个数有关, 但没有研究结果表明变量个数和异常之
of 22
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论