事务信息系统：并发控制与恢复的理论、算法与实践

.文献注释 21
第2章 计算模型 23
2.1 目标和概述 23
2.2 计算模型的组成部分 23
2.3 页模型 24
2.4 对象模型 27
2.5 本书的“路线图” 30
2.6 小结 31
习题 31
文献注释 32
第二部分 并 发 控 制
第3章 并发控制：页模型正确性的概念 33
3.1 目标和概述 33
3.2 经典的并发问题 33
3.3 历史和调度的语法 35
3.4 历史和调度的正确性 39
3.5 调度的herbrand语义 40
3.6 终态可串行性 42
3.7 视图可串行性 45
3.7.1 视图等价和结果正确性准则 46
3.7.2 检测视图可串行性的复杂性 47
3.8 冲突可串行性 51
3.8.1 冲突关系 51
3.8.2 csr类 52
3.8.3 冲突和交换性 54
3.8.4 冲突可串行性的约束 56
3.9 提交可串行性 57
3.10 一个可选的正确性准则：交叉存取说明 60
3.11 小结 65
习题 66
文献注释 67
第4章 并发控制算法 69
4.1 目标和概述 69
4.2 通用调度器的设计 69
4.3 锁调度器 72
4.3.1 简介 72
4.3.2 两阶段封锁协议 74
4.3.3 死锁处理 77
4.3.4 2pl的变体 79
4.3.5 有序的共享锁 80
4.3.6 利它锁 83
4.3.7 非两阶段封锁协议 86
4.3.8 封锁的几何学意义 89
4.4 非封锁调度器 91
4.4.1 时间戳排序 91
4.4.2 串行化图的检测 92
4.4.3 乐观协议 94
4.5 混合协议 96
4.6 小结 98
习题 99
文献注释 100
第5章 多版本并发控制 101
5.1 目标和概述 101
5.2 多版本调度 101
5.3 多版本可串行性 103
5.3.1 多版本视图可串行性 103
5.3.2 mvsr成员资格检测 105
5.3.3 多版本冲突可串行性 107
5.4 限制版本的数目 109
5.5 多版本并发控制协议 110
5.5.1 mvto协议 110
5.5.2 mv2pl协议 111
5.5.3 mvsgt协议 114
5.5.4 只读事务的多版本协议 115
5.6 小结 116
习题 116
文献注释 117
第6章 对象上的并发控制：正确性概念 119
6.1 目标和概述 119
6.2 历史和调度 119
6.3 平面对象事务的冲突可串行性 122
6.4 树可归约性 125
6.5 树可归约的充分条件 128
6.6 采用基于状态的可交换性 132
6.7 小结 135
习题 136
文献注释 137
第7章 对象上的并发控制算法 139
7.1 目标和概述 139
7.2 平面对象事务封锁 139
7.3 分层锁 140
7.4 通用事务森林上的封锁 144
7.5 混合算法 146
7.6 为返回值的可交换性加锁和契约锁 147
7.7 小结 150
习题 151
文献注释 151
第8章 关系数据库的并发控制 153
8.1 目标和概述 153
8.2 面向谓词的并发控制 154
8.3 关系的更新事务 157
8.3.1 语法和语义 158
8.3.2 可交换性和简化规则 159
8.3.3 历史和最终状态的可串行性 160
8.3.4 冲突可串行性 161
8.3.5 扩展的冲突可串行性 162
8.3.6 在函数依赖面前的可串行性 163
8.3.7 小结 165
8.4 应用事务程序知识 165
8.4.1 范例 166
8.4.2 事务分割 167
8.4.3 切割的适用性 169
8.5 小结 171
习题 171
文献注释 173
第9章 搜索结构上的并发控制 174
9.1 目标和概述 174
9.2 b+树搜索结构的实现 175
9.3 访问层的键范围封锁 178
9.4 页层的技术 183
9.4.1 锁耦合 184
9.4.2 链接技术 189
9.4.3 放弃技术 190
9.5 进一步的优化 191
9.5.1 无死锁的页闩锁 191
9.5.2 增强的键范围并发 191
9.5.3 降低封锁开销 192
9.5.4 利用暂态版本化 193
9.6 小结 193
习题 194
文献注释 195
第10章 实现和实用性问题 196
10.1 目标和概述 196
10.2 锁管理器的数据结构 196
10.3 多粒度封锁和动态提升 197
10.4 暂态版本化 199
10.5 事务内部并行的嵌套事务 201
10.6 调整选项 201
10.6.1 手动封锁 202
10.6.2 sql的隔离级别 202
10.6.3 短事务 204
10.6.4 多道程序级别的限制 206
10.7 过载控制 207
10.7.1 反馈驱动方法 208
10.7.2 等待深度限制 210
10.8 小结 210
习题 211
文献注释 211
第三部分 恢 复
第11章 事务恢复 213
11.1 目标和概述 213
11.2 带有显式undo操作的扩展调度 214
11.2.1 概念的直觉和概述 214
11.2.2 形式化模型 214
11.3 页模型的正确性准则 216
11.3.1 扩展冲突可串行性 216
11.3.2 可归约性与前缀可归约性 217
11.4 充分的句法条件 219
11.4.1 可恢复性.. 220
11.4.2 避免级联中止 220
11.4.3 严格性 221
11.4.4 严厉性 221
11.4.5 日志可恢复性 224
11.5 带有事务中止的页模型调度协议 227
11.5.1 为实现严格性和严厉性扩展两阶段封锁协议 227
11.5.2 为日志可恢复性扩展串行图检测 227
11.5.3 为日志可恢复性扩展其他协议 229
11.6 对象模型的正确性准则 229
11.6.1 平面对象调度中的中止 229
11.6.2 通用对象模型中的完全中止和部分中止 234
11.7 带有事务中止的对象模型调度协议 237
11.8 小结 237
习题 237
文献注释 239
第12章 崩溃恢复：正确性概念 241
12.1 目标和概述 241
12.2 系统体系结构和接口 243
12.3 系统模型 244
12.4 正确性准则 246
12.5 算法路线图 248
12.6 小结 250
习题 251
文献注释 251
第13章 页模型崩溃恢复算法 252
13.1 目标和概述 252
13.2 基本数据结构 253
13.3 重做胜者范型 256
13.3.1 正常操作期间的操作 256
13.3.2 简单的三遍扫描（三趟）算法 259
13.3.3 增强算法：日志截断、检查点、重做优化 269
13.3.4 完整的算法：处理事务中止和撤销完成 281
13.4 重做历史范型 288
13.4.1 正常操作期间的操作 288
13.4.2 简单的三趟算法和两趟算法 288
13.4.3 增强的算法：日志截断、检查点和重做优化 294
13.4.4 完整的算法：处理事务回滚和撤销完成 294
13.5 小结 299
习题 306
文献注释 308
第14章 对象模型的故障恢复 309
14.1 目标和概述 309
14.2 重做历史算法的概念综述 309
14.3 一个简单的两层系统的重做历史算法 311
14.3.1 正常操作期间的操作 312
14.3.2 重启期间的操作 313
14.4 一个增强的两层系统的重做历史算法 316
14.5 一个完整的通用对象模型执行的重做历史算法 322
14.6 小结 324
习题 325
文献注释 327
第15章 恢复的特别问题 328
15.1 目标和概述 328
15.2 索引和大对象的日志和恢复 328
15.2.1 重做索引页分裂的逻辑日志条目 328
15.2.2 大对象操作的逻辑日志条目和刷出顺序 331
15.3 事务内部保存点和嵌套事务 334
15.4 在重启过程中使用并行性 338
15.5 对主存数据服务器的特殊考虑 339
15.6 数据共享机群的扩展 341
15.7 小结 344
习题 344
文献注释 346
第16章 介质恢复 347
16.1 目标和概述 347
16.2 基于日志的方法 348
16.2.1 正常操作期间的数据备份和归档日志 349
16.2.2 数据库恢复算法 351
16.2.3 对平均数据丢失时间的分析 352
16.3 存储冗余 355
16.3.1 基于镜像的技术 355
16.3.2 基于纠错码的技术 357
16.4 灾难恢复 363
16.5 小结 364
习题 364
文献注释 365
第17章 应用恢复 366
17.1 目标和概述 366
17.2 基于队列的无状态应用 367
17.3 基于队列的有状态应用 372
17.4 基于队列的工作流 374
17.4.1 故障可恢复工作流的状态和上下文 375
17.4.2 基于排队事务的分散工作流 376
17.5 一般的有状态应用 377
17.5.1 设计上考虑的事项 378
17.5.2 服务器应答日志算法综述 380
17.5.3 数据结构 381
17.5.4 正常操作期间的服务器日志活动 382
17.5.5 正常操作期间的客户端日志活动 384
17.5.6 日志截断 385
17.5.7 服务器重启 387
17.5.8 客户端重启 388
17.5.9 正确性推理 390
17.5.10 对于多层体系结构的适用性 393
17.6 小结 393
习题 394
文献注释 394
第四部分 分布式事务的协调
第18章 分布式并发控制 397
18.1 目标和概述 397
18.2 同构联邦中的并发控制 398
18.2.1 预备知识 399
18.2.2 分布式2pl 400
18.2.3 分布式to 401
18.2.4 分布式sgt 402
18.2.5 乐观协议 403
18.3 分布式死锁检测 404
18.4 异构联邦中的可串行性 406
18.4.1 全局历史 407
18.4.2 全局可串行性 408
18.4.3 准可串行性 410
18.5 通过本地的保证获得全局可串行性 411
18.5.1 严厉性 411
18.5.2 提交排序 412
18.6 基于ticket的并发控制 413
18.6.1 强迫冲突的显式ticket 413
18.6.2 隐式ticket 415
18.6.3 显示和隐式ticket的结合 415
18.7 异构联邦中对象模式的并发控制 416
18.8 数据共享系统的一致性和并发控制 417
18.9 小结 420
习题 421
文献注释 422
第19章 分布式事务恢复 424
19.1 目标和概述 424
19.2 基本的两阶段提交算法 425
19.2.1 2pc协议 425
19.2.2 重启和终止协议 430
19.2.3 独立恢复 435
19.3 事务树两阶段提交算法 436
19.4 分布式提交的优化算法 439
19.4.1 假设中止协议和假设提交协议 439
19.4.2 只读子树的优化 443
19.4.3 协调者转移 445
19.4.4 减少阻塞 447
19.5 小结 448
习题 449
文献注释 450
第五部分 应用与未来前景
第20章 下一步是什么 453
20.1 目标和概述 453
20.2 我们完成了什么 453
20.2.1 开发者可用的解决方案 453
20.2.2 高级的系统搭建者可用的最新技术 454
20.2.3 研究人员的方法学和新的挑战 455
20.3 用于普遍访问的数据复制 455
20.4 电子服务和工作流 457
20.5 性能和可用性保证 460
文献注释 462
参考文献... 464