分佈式數據庫系統原理（第4版） Principles of Distributed Database Systems, 4/e

本書主要介紹分佈式數據庫管理系統的基本概念、基本理論和設計問題，涵蓋了分佈式數據庫系統的設計、實現和管理等方面的諸多專題。全書由兩大部分組成， 第一部分包括第1～14章，以關系數據庫為主，講述了分佈式數據管理的基礎原理，內容包括分佈式數據庫設計，分佈式查詢的分解與優化，事務管理，分佈式並發控制，分佈式數據庫管理系統的可靠性，數據復制等分佈式數據管理技術的經典內容，第14章還討論了並行數據庫系統。第二部分包括第15～18章，介紹了互聯網時代分佈式數據管理研究的前沿，包括分佈式對象數據庫管理，P2P數據管理，萬?

目    錄

第1章  引言 1

1.1  什麽是分佈式數據庫系統 1

1.2  分佈式DBMS的發展歷程 2

1.3  數據傳輸方案 4

1.4  分佈式DBMS的承諾 5

1.4.1  分佈式及復制數據的透明管理 6

1.4.2  基於分佈式事務的可靠性 8

1.4.3  性能提升 8

1.4.4  可擴展性 9

1.5  設計問題 10

1.5.1  分佈式數據庫設計 10

1.5.2  分佈式數據控制 10

1.5.3  分佈式查詢處理 10

1.5.4  分佈式並發控制 11

1.5.5  分佈式數據庫的可靠性 11

1.5.6  復制 11

1.5.7  並行數據庫 11

1.5.8  數據庫集成 12

1.5.9  其他分佈式方法 12

1.5.10  大數據處理和NoSQL 12

1.6  分佈式DBMS體系架構 12

1.6.1  分佈式DBMS體系架構的模型 13

1.6.2  客戶/服務器系統 15

1.6.3  P2P系統 16

1.6.4  多數據庫體系架構 18

1.6.5  雲計算 20

1.7  本章參考文獻說明 23

第2章  分佈與並行數據庫設計 25

2.1  數據分片 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  結合的方法 53

2.3.1  工作負載不可知時的劃分技術 53

2.3.2  工作負載可知的劃分技術 54

2.4  自適應方法 57

2.4.1  檢測工作負載的變化 57

2.4.2  檢測受影響的數據項 58

2.4.3  增量重構 58

2.5  數據目錄 60

2.6  本章小結 61

2.7  本章參考文獻說明 61

2.8  本章習題 63

第3章  分佈式數據控制 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  本章小結 89

3.5  本章參考文獻說明 90

3.6  本章習題 91

第4章  分佈式查詢處理 93

4.1  查詢處理概述 93

4.1.1  查詢處理問題 94

4.1.2  查詢優化 96

4.1.3  查詢處理的分層結構 98

4.2  數據本地化 101

4.2.1  主水平劃分的歸約 101

4.2.2  連結的歸約 103

4.2.3  垂直分片的歸約 104

4.2.4  誘導分片的歸約 105

4.2.5  混合分片的歸約 106

4.3  分佈式查詢的連結排序 107

4.3.1  連結樹 107

4.3.2  連結排序 109

4.3.3  基於半連結的算法 110

4.3.4  連結與半連結的對比 113

4.4  分佈式代價模型 114

4.4.1  代價函數 114

4.4.2  數據庫統計數據 115

4.5  分佈式查詢優化 116

4.5.1  動態方法 116

4.5.2  靜態方法 120

4.5.3  混合方法 122

4.6  自適應查詢處理 126

4.6.1  自適應查詢處理的流程 127

4.6.2  eddy方法 128

4.7  本章小結 129

4.8  本章參考文獻說明 130

4.9  本章習題 131

第5章  分佈式事務處理 134

5.1  背景與概念定義 135

5.2  分佈式並發控制 137

5.2.1  基於加鎖的並發控制算法 138

5.2.2  基於時間戳的並發控制算法 145

5.2.3  多版本並發控制算法 149

5.2.4  樂觀並發控制算法 150

5.3  基於快照隔離的分佈式並發控制算法 152

5.4  分佈式DBMS的可靠性 154

5.4.1  兩階段提交協議 155

5.4.2  兩階段提交協議的變型版本 161

5.4.3  處理站點故障 162

5.4.4  網絡劃分 168

5.4.5  Paxos共識協議 170

5.4.6  體系架構方面的考慮 173

5.5  擴展事務管理的現代方法 174

5.5.1  Spanner系統 175

5.5.2  LeanXcale系統 175

5.6  本章小結 177

5.7  本章參考文獻說明 178

5.8  本章習題 181

第6章  數據復制 183

6.1  復制數據庫的一致性 184

6.1.1  相互一致性 184

6.1.2  相互一致性與事務一致性 186

6.2  更新管理策略 187

6.2.1  積極更新傳播 187

6.2.2  懶惰更新傳播 188

6.2.3  集中式技術 188

6.2.4  分佈式技術 189

6.3  復制協議 189

6.3.1  積極集中式協議 189

6.3.2  積極分佈式協議 194

6.3.3  懶惰集中式協議 194

6.3.4  懶惰分佈式協議 199

6.4  分組通信 200

6.5  復制與故障 202

6.5.1  故障和懶惰復制 202

6.5.2  故障和積極復制 202

6.6  本章小結 205

6.7  本章參考文獻說明 205

6.8  本章習題 207

第7章  數據庫集成——多數據庫系統 209

7.1  數據庫集成 209

7.1.1  自底向上的設計方法 210

7.1.2  模式匹配 213

7.1.3  模式集成 220

7.1.4  模式映射 221

7.1.5  數據清洗 227

7.2  多數據庫查詢處理 228

7.2.1  多數據庫查詢處理的關鍵問題 228

7.2.2  多數據庫查詢處理體系架構 229

7.2.3  基於視圖的查詢重寫 231

7.2.4  查詢優化和執行 234

7.2.5  查詢翻譯和執行 243

7.3  本章小結 245

7.4  本章參考文獻說明 246

7.5  本章習題 248

第8章  並行數據庫系統 258

8.1  並行數據庫系統的目標 258

8.2  並行架構 261

8.2.1  通用架構 261

8.2.2  共享內存架構 262

8.2.3  共享磁盤架構 264

8.2.4  無共享架構 264

8.3  數據放置 265

8.4  並行查詢處理 268

8.4.1  數據處理的並行算法 268

8.4.2  並行查詢優化 273

8.5  負載均衡 277

8.5.1  並行執行的問題 277

8.5.2  算子內負載均衡 279

8.5.3  算子間負載均衡 280

8.5.4  查詢內負載均衡 280

8.6  容錯性 283

8.7  數據庫集群 284

8.7.1  數據庫集群架構 285

8.7.2  復制 286

8.7.3  負載均衡 286

8.7.4  查詢處理 286

8.8  本章小結 289

8.9  本章參考文獻說明 289

8.10  本章習題 291

第9章  對等數據管理 293

9.1  基礎設施 295

9.1.1  非結構化P2P網絡 296

9.1.2  結構化P2P網絡 298

9.1.3  超級節點P2P網絡 301

9.1.4  P2P網絡比較 303

9.2  P2P系統上的模式映射 303

9.2.1  成對模式映射 303

9.2.2  基於機器學習技術的映射 304

9.2.3  公共協議映射 304

9.2.4  基於信息檢索技術的模式映射 305

9.3  P2P系統的查詢處理 306

9.3.1  Top-k查詢 306

9.3.2  連結查詢 316

9.3.3  區間查詢 317

9.4  副本一致性 320

9.4.1  DHT中的基本支持 320

9.4.2  DHT中的數據貨幣 321

9.4.3  副本協調 322

9.5  區塊鏈 325

9.5.1  區塊鏈定義 326

9.5.2  區塊鏈基礎設施 327

9.5.3  區塊鏈2.0 329

9.5.4  問題 330

9.6  本章小結 331

9.7  本章參考文獻說明 332

9.8  本章習題 333

第10章  大數據處理 335

10.1  分佈式存儲系統 337

10.1.1  谷歌文件系統 338

10.1.2  對象存儲與文件存儲的結合 339

10.2  大數據處理框架 339

10.2.1  MapReduce數據處理 340

10.2.2  使用Spark處理數據 348

10.3  流數據處理 352

10.3.1  流模型、語言和算子 353

10.3.2  數據流的查詢處理 356

10.3.3  數據流系統容錯 362

10.4  圖分析平臺 363

10.4.1  圖劃分 365

10.4.2  MapReduce和圖分析 369

10.4.3  圖分析專用系統 369

10.4.4  以頂點為中心的整體同步系統 372

10.4.5  以頂點為中心的異步並行系統 374

10.4.6  以頂點為中心的聚集-應用-分散系統 376

10.4.7  以劃分為中心的整體同步系統 377

10.4.8  以劃分為中心的異步並行系統 378

10.4.9  以劃分為中心的聚集-應用-分散系統 378

10.4.10  以邊為中心的整體同步系統 378

10.4.11  以邊為中心的異步並行系統 379

10.4.12  以邊為中心的聚集-應用-分散系統 379

10.5  數據湖 379

10.5.1  數據湖與數據倉庫 379

10.5.2  體系架構 380

10.5.3  挑戰 382

10.6  本章小結 382

10.7  本章參考文獻說明 383

10.8  本章習題 385

第11章  NoSQL、NewSQL與Polystore技術 388

11.1  NoSQL系統提出的動機 388

11.2  鍵值存儲系統 390

11.2.1  DynamoDB 390

11.2.2  其他鍵值存儲系統 392

11.3  文檔存儲系統 392

11.3.1  MongoDB 393

11.3.2  其他文檔存儲 395

11.4  寬列存儲 395

11.4.1  Bigtable 396

11.4.2  其他寬列存儲系統 397

11.5  圖數據庫管理系統 397

11.5.1  Neo4j 398

11.5.2  其他圖數據庫系統 401

11.6  混合數據存儲系統 401

11.6.1  多模型NoSQL存儲系統 401

11.6.2  NewSQL數據庫系統 402

11.7  Polystore系統 404

11.7.1  松耦合的Polystore系統 405

11.7.2  緊耦合Polystore系統 408

11.7.3  混合系統 412

11.7.4  結束語 415

11.8  本章小結 416

11.9  本章參考文獻說明 417

11.10  本章習題 418

第12章  萬維網數據管理 419

12.1  萬維網圖管理 420

12.2  萬維網搜索 421

12.2.1  萬維網爬取 422

12.2.2  索引 423

12.2.3  排序與鏈接分析 424

12.2.4  對關鍵詞搜索的評價 425

12.3  萬維網查詢 426

12.3.1  半結構化數據方法 427

12.3.2  萬維網查詢語言方法 430

12.4  問答系統 435

12.5  隱藏萬維網搜索與查詢 438

12.5.1  隱藏萬維網爬取 438

12.5.2  元搜索 439

12.6  萬維網數據集成 441

12.6.1  萬維網表格/融合表格 442

12.6.2  語義萬維網和鏈接開放數據 442

12.6.3  萬維網數據集成中的數據質量問題 456

12.7  本章參考文獻說明 462

12.8  本章習題 464

附錄 465

參考文獻 466

 

 

 

8

分佈式數據庫系統原理（第4版）

 

9

目    錄