第1章 引言 1
1.1 什么是分布式數(shù)據(jù)庫系統(tǒng) 1
1.2 分布式DBMS的發(fā)展歷程 2
1.3 數(shù)據(jù)傳輸方案 4
1.4 分布式DBMS的承諾 5
1.4.1 分布式及復(fù)制數(shù)據(jù)的透明管理 6
1.4.2 基于分布式事務(wù)的可靠性 8
1.4.3 性能提升 8
1.4.4 可擴展性 9
1.5 設(shè)計問題 10
1.5.1 分布式數(shù)據(jù)庫設(shè)計 10
1.5.2 分布式數(shù)據(jù)控制 10
1.5.3 分布式查詢處理 10
1.5.4 分布式并發(fā)控制 11
1.5.5 分布式數(shù)據(jù)庫的可靠性 11
1.5.6 復(fù)制 11
1.5.7 并行數(shù)據(jù)庫 11
1.5.8 數(shù)據(jù)庫集成 12
1.5.9 其他分布式方法 12
1.5.10 大數(shù)據(jù)處理和NoSQL 12
1.6 分布式DBMS體系架構(gòu) 12
1.6.1 分布式DBMS體系架構(gòu)的模型 13
1.6.2 客戶/服務(wù)器系統(tǒng) 15
1.6.3 P2P系統(tǒng) 16
1.6.4 多數(shù)據(jù)庫體系架構(gòu) 18
1.6.5 云計算 20
1.7 本章參考文獻說明 23
第2章 分布與并行數(shù)據(jù)庫設(shè)計 25
2.1 數(shù)據(jù)分片 27
2.1.1 水平分片 28
2.1.2 垂直分片 39
2.1.3 混合分片 48
2.2 分配 49
2.2.1 輔助信息 50
2.2.2 分配模型 50
2.2.3 解決辦法 52
2.3 結(jié)合的方法 53
2.3.1 工作負(fù)載不可知時的劃分技術(shù) 53
2.3.2 工作負(fù)載可知的劃分技術(shù) 54
2.4 自適應(yīng)方法 57
2.4.1 檢測工作負(fù)載的變化 57
2.4.2 檢測受影響的數(shù)據(jù)項 58
2.4.3 增量重構(gòu) 58
2.5 數(shù)據(jù)目錄 60
2.6 本章小結(jié) 61
2.7 本章參考文獻說明 61
2.8 本章習(xí)題 63
第3章 分布式數(shù)據(jù)控制 66
3.1 視圖管理 66
3.1.1 集中式DBMS中的視圖 67
3.1.2 分布式DBMS中的視圖 69
3.1.3 物化視圖的維護 70
3.2 訪問控制 75
3.2.1 裁決式訪問控制 76
3.2.2 多級訪問控制 77
3.2.3 分布式訪問控制 79
3.3 語義完整性控制 81
3.3.1 集中式語義完整性控制 82
3.3.2 分布式語義完整性控制 85
3.4 本章小結(jié) 89
3.5 本章參考文獻說明 90
3.6 本章習(xí)題 91
第4章 分布式查詢處理 93
4.1 查詢處理概述 93
4.1.1 查詢處理問題 94
4.1.2 查詢優(yōu)化 96
4.1.3 查詢處理的分層結(jié)構(gòu) 98
4.2 數(shù)據(jù)本地化 101
4.2.1 主水平劃分的歸約 101
4.2.2 連結(jié)的歸約 103
4.2.3 垂直分片的歸約 104
4.2.4 誘導(dǎo)分片的歸約 105
4.2.5 混合分片的歸約 106
4.3 分布式查詢的連結(jié)排序 107
4.3.1 連結(jié)樹 107
4.3.2 連結(jié)排序 109
4.3.3 基于半連結(jié)的算法 110
4.3.4 連結(jié)與半連結(jié)的對比 113
4.4 分布式代價模型 114
4.4.1 代價函數(shù) 114
4.4.2 數(shù)據(jù)庫統(tǒng)計數(shù)據(jù) 115
4.5 分布式查詢優(yōu)化 116
4.5.1 動態(tài)方法 116
4.5.2 靜態(tài)方法 120
4.5.3 混合方法 122
4.6 自適應(yīng)查詢處理 126
4.6.1 自適應(yīng)查詢處理的流程 127
4.6.2 eddy方法 128
4.7 本章小結(jié) 129
4.8 本章參考文獻說明 130
4.9 本章習(xí)題 131
第5章 分布式事務(wù)處理 134
5.1 背景與概念定義 135
5.2 分布式并發(fā)控制 137
5.2.1 基于加鎖的并發(fā)控制算法 138
5.2.2 基于時間戳的并發(fā)控制算法 145
5.2.3 多版本并發(fā)控制算法 149
5.2.4 樂觀并發(fā)控制算法 150
5.3 基于快照隔離的分布式并發(fā)控制算法 152
5.4 分布式DBMS的可靠性 154
5.4.1 兩階段提交協(xié)議 155
5.4.2 兩階段提交協(xié)議的變型版本 161
5.4.3 處理站點故障 162
5.4.4 網(wǎng)絡(luò)劃分 168
5.4.5 Paxos共識協(xié)議 170
5.4.6 體系架構(gòu)方面的考慮 173
5.5 擴展事務(wù)管理的現(xiàn)代方法 174
5.5.1 Spanner系統(tǒng) 175
5.5.2 LeanXcale系統(tǒng) 175
5.6 本章小結(jié) 177
5.7 本章參考文獻說明 178
5.8 本章習(xí)題 181
第6章 數(shù)據(jù)復(fù)制 183
6.1 復(fù)制數(shù)據(jù)庫的一致性 184
6.1.1 相互一致性 184
6.1.2 相互一致性與事務(wù)一致性 186
6.2 更新管理策略 187
6.2.1 積極更新傳播 187
6.2.2 懶惰更新傳播 188
6.2.3 集中式技術(shù) 188
6.2.4 分布式技術(shù) 189
6.3 復(fù)制協(xié)議 189
6.3.1 積極集中式協(xié)議 189
6.3.2 積極分布式協(xié)議 194
6.3.3 懶惰集中式協(xié)議 194
6.3.4 懶惰分布式協(xié)議 199
6.4 分組通信 200
6.5 復(fù)制與故障 202
6.5.1 故障和懶惰復(fù)制 202
6.5.2 故障和積極復(fù)制 202
6.6 本章小結(jié) 205
6.7 本章參考文獻說明 205
6.8 本章習(xí)題 207
第7章 數(shù)據(jù)庫集成多數(shù)據(jù)庫系統(tǒng) 209
7.1 數(shù)據(jù)庫集成 209
7.1.1 自底向上的設(shè)計方法 210
7.1.2 模式匹配 213
7.1.3 模式集成 220
7.1.4 模式映射 221
7.1.5 數(shù)據(jù)清洗 227
7.2 多數(shù)據(jù)庫查詢處理 228
7.2.1 多數(shù)據(jù)庫查詢處理的關(guān)鍵問題 228
7.2.2 多數(shù)據(jù)庫查詢處理體系架構(gòu) 229
7.2.3 基于視圖的查詢重寫 231
7.2.4 查詢優(yōu)化和執(zhí)行 234
7.2.5 查詢翻譯和執(zhí)行 243
7.3 本章小結(jié) 245
7.4 本章參考文獻說明 246
7.5 本章習(xí)題 248
第8章 并行數(shù)據(jù)庫系統(tǒng) 258
8.1 并行數(shù)據(jù)庫系統(tǒng)的目標(biāo) 258
8.2 并行架構(gòu) 261
8.2.1 通用架構(gòu) 261
8.2.2 共享內(nèi)存架構(gòu) 262
8.2.3 共享磁盤架構(gòu) 264
8.2.4 無共享架構(gòu) 264
8.3 數(shù)據(jù)放置 265
8.4 并行查詢處理 268
8.4.1 數(shù)據(jù)處理的并行算法 268
8.4.2 并行查詢優(yōu)化 273
8.5 負(fù)載均衡 277
8.5.1 并行執(zhí)行的問題 277
8.5.2 算子內(nèi)負(fù)載均衡 279
8.5.3 算子間負(fù)載均衡 280
8.5.4 查詢內(nèi)負(fù)載均衡 280
8.6 容錯性 283
8.7 數(shù)據(jù)庫集群 284
8.7.1 數(shù)據(jù)庫集群架構(gòu) 285
8.7.2 復(fù)制 286
8.7.3 負(fù)載均衡 286
8.7.4 查詢處理 286
8.8 本章小結(jié) 289
8.9 本章參考文獻說明 289
8.10 本章習(xí)題 291
第9章 對等數(shù)據(jù)管理 293
9.1 基礎(chǔ)設(shè)施 295
9.1.1 非結(jié)構(gòu)化P2P網(wǎng)絡(luò) 296
9.1.2 結(jié)構(gòu)化P2P網(wǎng)絡(luò) 298
9.1.3 超級節(jié)點P2P網(wǎng)絡(luò) 301
9.1.4 P2P網(wǎng)絡(luò)比較 303
9.2 P2P系統(tǒng)上的模式映射 303
9.2.1 成對模式映射 303
9.2.2 基于機器學(xué)習(xí)技術(shù)的映射 304
9.2.3 公共協(xié)議映射 304
9.2.4 基于信息檢索技術(shù)的模式映射 305
9.3 P2P系統(tǒng)的查詢處理 306
9.3.1 Top-k查詢 306
9.3.2 連結(jié)查詢 316
9.3.3 區(qū)間查詢 317
9.4 副本一致性 320
9.4.1 DHT中的基本支持 320
9.4.2 DHT中的數(shù)據(jù)貨幣 321
9.4.3 副本協(xié)調(diào) 322
9.5 區(qū)塊鏈 325
9.5.1 區(qū)塊鏈定義 326
9.5.2 區(qū)塊鏈基礎(chǔ)設(shè)施 327
9.5.3 區(qū)塊鏈2.0 329
9.5.4 問題 330
9.6 本章小結(jié) 331
9.7 本章參考文獻說明 332
9.8 本章習(xí)題 333
第10章 大數(shù)據(jù)處理 335
10.1 分布式存儲系統(tǒng) 337
10.1.1 谷歌文件系統(tǒng) 338
10.1.2 對象存儲與文件存儲的結(jié)合 339
10.2 大數(shù)據(jù)處理框架 339
10.2.1 MapReduce數(shù)據(jù)處理 340
10.2.2 使用Spark處理數(shù)據(jù) 348
10.3 流數(shù)據(jù)處理 352
10.3.1 流模型、語言和算子 353
10.3.2 數(shù)據(jù)流的查詢處理 356
10.3.3 數(shù)據(jù)流系統(tǒng)容錯 362
10.4 圖分析平臺 363
10.4.1 圖劃分 365
10.4.2 MapReduce和圖分析 369
10.4.3 圖分析專用系統(tǒng) 369
10.4.4 以頂點為中心的整體同步系統(tǒng) 372
10.4.5 以頂點為中心的異步并行系統(tǒng) 374
10.4.6 以頂點為中心的聚集-應(yīng)用-分散系統(tǒng) 376
10.4.7 以劃分為中心的整體同步系統(tǒng) 377
10.4.8 以劃分為中心的異步并行系統(tǒng) 378
10.4.9 以劃分為中心的聚集-應(yīng)用-分散系統(tǒng) 378
10.4.10 以邊為中心的整體同步系統(tǒng) 378
10.4.11 以邊為中心的異步并行系統(tǒng) 379
10.4.12 以邊為中心的聚集-應(yīng)用-分散系統(tǒng) 379
10.5 數(shù)據(jù)湖 379
10.5.1 數(shù)據(jù)湖與數(shù)據(jù)倉庫 379
10.5.2 體系架構(gòu) 380
10.5.3 挑戰(zhàn) 382
10.6 本章小結(jié) 382
10.7 本章參考文獻說明 383
10.8 本章習(xí)題 385
第11章 NoSQL、NewSQL與Polystore技術(shù) 388
11.1 NoSQL系統(tǒng)提出的動機 388
11.2 鍵值存儲系統(tǒng) 390
11.2.1 DynamoDB 390
11.2.2 其他鍵值存儲系統(tǒng) 392
11.3 文檔存儲系統(tǒng) 392
11.3.1 MongoDB 393
11.3.2 其他文檔存儲 395
11.4 寬列存儲 395
11.4.1 Bigtable 396
11.4.2 其他寬列存儲系統(tǒng) 397
11.5 圖數(shù)據(jù)庫管理系統(tǒng) 397
11.5.1 Neo4j 398
11.5.2 其他圖數(shù)據(jù)庫系統(tǒng) 401
11.6 混合數(shù)據(jù)存儲系統(tǒng) 401
11.6.1 多模型NoSQL存儲系統(tǒng) 401
11.6.2 NewSQL數(shù)據(jù)庫系統(tǒng) 402
11.7 Polystore系統(tǒng) 404
11.7.1 松耦合的Polystore系統(tǒng) 405
11.7.2 緊耦合Polystore系統(tǒng) 408
11.7.3 混合系統(tǒng) 412
11.7.4 結(jié)束語 415
11.8 本章小結(jié) 416
11.9 本章參考文獻說明 417
11.10 本章習(xí)題 418
第12章 萬維網(wǎng)數(shù)據(jù)管理 419
12.1 萬維網(wǎng)圖管理 420
12.2 萬維網(wǎng)搜索 421
12.2.1 萬維網(wǎng)爬取 422
12.2.2 索引 423
12.2.3 排序與鏈接分析 424
12.2.4 對關(guān)鍵詞搜索的評價 425
12.3 萬維網(wǎng)查詢 426
12.3.1 半結(jié)構(gòu)化數(shù)據(jù)方法 427
12.3.2 萬維網(wǎng)查詢語言方法 430
12.4 問答系統(tǒng) 435
12.5 隱藏萬維網(wǎng)搜索與查詢 438
12.5.1 隱藏萬維網(wǎng)爬取 438
12.5.2 元搜索 439
12.6 萬維網(wǎng)數(shù)據(jù)集成 441
12.6.1 萬維網(wǎng)表格/融合表格 442
12.6.2 語義萬維網(wǎng)和鏈接開放數(shù)據(jù) 442
12.6.3 萬維網(wǎng)數(shù)據(jù)集成中的數(shù)據(jù)質(zhì)量問題 456
12.7 本章參考文獻說明 462
12.8 本章習(xí)題 464
附錄 465
參考文獻 466

8
分布式數(shù)據(jù)庫系統(tǒng)原理（第4版）

9
目 錄