第1章 引言 1
1.1 什么是分布式數(shù)據(jù)庫(kù)系統(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 可擴(kuò)展性 9
1.5 設(shè)計(jì)問(wèn)題 10
1.5.1 分布式數(shù)據(jù)庫(kù)設(shè)計(jì) 10
1.5.2 分布式數(shù)據(jù)控制 10
1.5.3 分布式查詢(xún)處理 10
1.5.4 分布式并發(fā)控制 11
1.5.5 分布式數(shù)據(jù)庫(kù)的可靠性 11
1.5.6 復(fù)制 11
1.5.7 并行數(shù)據(jù)庫(kù) 11
1.5.8 數(shù)據(jù)庫(kù)集成 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 客戶(hù)/服務(wù)器系統(tǒng) 15
1.6.3 P2P系統(tǒng) 16
1.6.4 多數(shù)據(jù)庫(kù)體系架構(gòu) 18
1.6.5 云計(jì)算 20
1.7 本章參考文獻(xiàn)說(shuō)明 23
第2章 分布與并行數(shù)據(jù)庫(kù)設(shè)計(jì) 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í)的劃分技術(shù) 53
2.3.2 工作負(fù)載可知的劃分技術(shù) 54
2.4 自適應(yīng)方法 57
2.4.1 檢測(cè)工作負(fù)載的變化 57
2.4.2 檢測(cè)受影響的數(shù)據(jù)項(xiàng) 58
2.4.3 增量重構(gòu) 58
2.5 數(shù)據(jù)目錄 60
2.6 本章小結(jié) 61
2.7 本章參考文獻(xiàn)說(shuō)明 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 物化視圖的維護(hù) 70
3.2 訪問(wèn)控制 75
3.2.1 裁決式訪問(wèn)控制 76
3.2.2 多級(jí)訪問(wèn)控制 77
3.2.3 分布式訪問(wèn)控制 79
3.3 語(yǔ)義完整性控制 81
3.3.1 集中式語(yǔ)義完整性控制 82
3.3.2 分布式語(yǔ)義完整性控制 85
3.4 本章小結(jié) 89
3.5 本章參考文獻(xiàn)說(shuō)明 90
3.6 本章習(xí)題 91
第4章 分布式查詢(xún)處理 93
4.1 查詢(xún)處理概述 93
4.1.1 查詢(xún)處理問(wèn)題 94
4.1.2 查詢(xún)優(yōu)化 96
4.1.3 查詢(xún)處理的分層結(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 分布式查詢(xún)的連結(jié)排序 107
4.3.1 連結(jié)樹(shù) 107
4.3.2 連結(jié)排序 109
4.3.3 基于半連結(jié)的算法 110
4.3.4 連結(jié)與半連結(jié)的對(duì)比 113
4.4 分布式代價(jià)模型 114
4.4.1 代價(jià)函數(shù) 114
4.4.2 數(shù)據(jù)庫(kù)統(tǒng)計(jì)數(shù)據(jù) 115
4.5 分布式查詢(xún)優(yōu)化 116
4.5.1 動(dòng)態(tài)方法 116
4.5.2 靜態(tài)方法 120
4.5.3 混合方法 122
4.6 自適應(yīng)查詢(xún)處理 126
4.6.1 自適應(yīng)查詢(xún)處理的流程 127
4.6.2 eddy方法 128
4.7 本章小結(jié) 129
4.8 本章參考文獻(xiàn)說(shuō)明 130
4.9 本章習(xí)題 131
第5章 分布式事務(wù)處理 134
5.1 背景與概念定義 135
5.2 分布式并發(fā)控制 137
5.2.1 基于加鎖的并發(fā)控制算法 138
5.2.2 基于時(shí)間戳的并發(fā)控制算法 145
5.2.3 多版本并發(fā)控制算法 149
5.2.4 樂(lè)觀并發(fā)控制算法 150
5.3 基于快照隔離的分布式并發(fā)控制算法 152
5.4 分布式DBMS的可靠性 154
5.4.1 兩階段提交協(xié)議 155
5.4.2 兩階段提交協(xié)議的變型版本 161
5.4.3 處理站點(diǎn)故障 162
5.4.4 網(wǎng)絡(luò)劃分 168
5.4.5 Paxos共識(shí)協(xié)議 170
5.4.6 體系架構(gòu)方面的考慮 173
5.5 擴(kuò)展事務(wù)管理的現(xiàn)代方法 174
5.5.1 Spanner系統(tǒng) 175
5.5.2 LeanXcale系統(tǒng) 175
5.6 本章小結(jié) 177
5.7 本章參考文獻(xiàn)說(shuō)明 178
5.8 本章習(xí)題 181
第6章 數(shù)據(jù)復(fù)制 183
6.1 復(fù)制數(shù)據(jù)庫(kù)的一致性 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 本章參考文獻(xiàn)說(shuō)明 205
6.8 本章習(xí)題 207
第7章 數(shù)據(jù)庫(kù)集成多數(shù)據(jù)庫(kù)系統(tǒng) 209
7.1 數(shù)據(jù)庫(kù)集成 209
7.1.1 自底向上的設(shè)計(jì)方法 210
7.1.2 模式匹配 213
7.1.3 模式集成 220
7.1.4 模式映射 221
7.1.5 數(shù)據(jù)清洗 227
7.2 多數(shù)據(jù)庫(kù)查詢(xún)處理 228
7.2.1 多數(shù)據(jù)庫(kù)查詢(xún)處理的關(guān)鍵問(wèn)題 228
7.2.2 多數(shù)據(jù)庫(kù)查詢(xún)處理體系架構(gòu) 229
7.2.3 基于視圖的查詢(xún)重寫(xiě) 231
7.2.4 查詢(xún)優(yōu)化和執(zhí)行 234
7.2.5 查詢(xún)翻譯和執(zhí)行 243
7.3 本章小結(jié) 245
7.4 本章參考文獻(xiàn)說(shuō)明 246
7.5 本章習(xí)題 248
第8章 并行數(shù)據(jù)庫(kù)系統(tǒng) 258
8.1 并行數(shù)據(jù)庫(kù)系統(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 共享磁盤(pán)架構(gòu) 264
8.2.4 無(wú)共享架構(gòu) 264
8.3 數(shù)據(jù)放置 265
8.4 并行查詢(xún)處理 268
8.4.1 數(shù)據(jù)處理的并行算法 268
8.4.2 并行查詢(xún)優(yōu)化 273
8.5 負(fù)載均衡 277
8.5.1 并行執(zhí)行的問(wèn)題 277
8.5.2 算子內(nèi)負(fù)載均衡 279
8.5.3 算子間負(fù)載均衡 280
8.5.4 查詢(xún)內(nèi)負(fù)載均衡 280
8.6 容錯(cuò)性 283
8.7 數(shù)據(jù)庫(kù)集群 284
8.7.1 數(shù)據(jù)庫(kù)集群架構(gòu) 285
8.7.2 復(fù)制 286
8.7.3 負(fù)載均衡 286
8.7.4 查詢(xún)處理 286
8.8 本章小結(jié) 289
8.9 本章參考文獻(xiàn)說(shuō)明 289
8.10 本章習(xí)題 291
第9章 對(duì)等數(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 超級(jí)節(jié)點(diǎn)P2P網(wǎng)絡(luò) 301
9.1.4 P2P網(wǎng)絡(luò)比較 303
9.2 P2P系統(tǒng)上的模式映射 303
9.2.1 成對(duì)模式映射 303
9.2.2 基于機(jī)器學(xué)習(xí)技術(shù)的映射 304
9.2.3 公共協(xié)議映射 304
9.2.4 基于信息檢索技術(shù)的模式映射 305
9.3 P2P系統(tǒng)的查詢(xún)處理 306
9.3.1 Top-k查詢(xún) 306
9.3.2 連結(jié)查詢(xún) 316
9.3.3 區(qū)間查詢(xún) 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 問(wèn)題 330
9.6 本章小結(jié) 331
9.7 本章參考文獻(xiàn)說(shuō)明 332
9.8 本章習(xí)題 333
第10章 大數(shù)據(jù)處理 335
10.1 分布式存儲(chǔ)系統(tǒng) 337
10.1.1 谷歌文件系統(tǒng) 338
10.1.2 對(duì)象存儲(chǔ)與文件存儲(chǔ)的結(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 流模型、語(yǔ)言和算子 353
10.3.2 數(shù)據(jù)流的查詢(xún)處理 356
10.3.3 數(shù)據(jù)流系統(tǒng)容錯(cuò) 362
10.4 圖分析平臺(tái) 363
10.4.1 圖劃分 365
10.4.2 MapReduce和圖分析 369
10.4.3 圖分析專(zhuān)用系統(tǒng) 369
10.4.4 以頂點(diǎn)為中心的整體同步系統(tǒng) 372
10.4.5 以頂點(diǎn)為中心的異步并行系統(tǒng) 374
10.4.6 以頂點(diǎn)為中心的聚集-應(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ù)倉(cāng)庫(kù) 379
10.5.2 體系架構(gòu) 380
10.5.3 挑戰(zhàn) 382
10.6 本章小結(jié) 382
10.7 本章參考文獻(xiàn)說(shuō)明 383
10.8 本章習(xí)題 385
第11章 NoSQL、NewSQL與Polystore技術(shù) 388
11.1 NoSQL系統(tǒng)提出的動(dòng)機(jī) 388
11.2 鍵值存儲(chǔ)系統(tǒng) 390
11.2.1 DynamoDB 390
11.2.2 其他鍵值存儲(chǔ)系統(tǒng) 392
11.3 文檔存儲(chǔ)系統(tǒng) 392
11.3.1 MongoDB 393
11.3.2 其他文檔存儲(chǔ) 395
11.4 寬列存儲(chǔ) 395
11.4.1 Bigtable 396
11.4.2 其他寬列存儲(chǔ)系統(tǒng) 397
11.5 圖數(shù)據(jù)庫(kù)管理系統(tǒng) 397
11.5.1 Neo4j 398
11.5.2 其他圖數(shù)據(jù)庫(kù)系統(tǒng) 401
11.6 混合數(shù)據(jù)存儲(chǔ)系統(tǒng) 401
11.6.1 多模型NoSQL存儲(chǔ)系統(tǒng) 401
11.6.2 NewSQL數(shù)據(jù)庫(kù)系統(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é)束語(yǔ) 415
11.8 本章小結(jié) 416
11.9 本章參考文獻(xiàn)說(shuō)明 417
11.10 本章習(xí)題 418
第12章 萬(wàn)維網(wǎng)數(shù)據(jù)管理 419
12.1 萬(wàn)維網(wǎng)圖管理 420
12.2 萬(wàn)維網(wǎng)搜索 421
12.2.1 萬(wàn)維網(wǎng)爬取 422
12.2.2 索引 423
12.2.3 排序與鏈接分析 424
12.2.4 對(duì)關(guān)鍵詞搜索的評(píng)價(jià) 425
12.3 萬(wàn)維網(wǎng)查詢(xún) 426
12.3.1 半結(jié)構(gòu)化數(shù)據(jù)方法 427
12.3.2 萬(wàn)維網(wǎng)查詢(xún)語(yǔ)言方法 430
12.4 問(wèn)答系統(tǒng) 435
12.5 隱藏萬(wàn)維網(wǎng)搜索與查詢(xún) 438
12.5.1 隱藏萬(wàn)維網(wǎng)爬取 438
12.5.2 元搜索 439
12.6 萬(wàn)維網(wǎng)數(shù)據(jù)集成 441
12.6.1 萬(wàn)維網(wǎng)表格/融合表格 442
12.6.2 語(yǔ)義萬(wàn)維網(wǎng)和鏈接開(kāi)放數(shù)據(jù) 442
12.6.3 萬(wàn)維網(wǎng)數(shù)據(jù)集成中的數(shù)據(jù)質(zhì)量問(wèn)題 456
12.7 本章參考文獻(xiàn)說(shuō)明 462
12.8 本章習(xí)題 464
附錄 465
參考文獻(xiàn) 466

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

9
目 錄