數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)

作者簡(jiǎn)介
譯者序
前言
第1章
DBMS實(shí)現(xiàn)概述 1
1.1
Megatron?2000數(shù)據(jù)庫(kù)系統(tǒng)介紹 1
1.1.1
Megatron?2000實(shí)現(xiàn)細(xì)節(jié) 2
1.1.2
Megatron?2000如何執(zhí)行查詢 3
1.1.3
Megatron?2000有什么問(wèn)題 4
1.2
數(shù)據(jù)庫(kù)管理系統(tǒng)概述 4
1.2.1
數(shù)據(jù)定義語(yǔ)言命令 4
1.2.2
查詢處理概述 5
1.2.3
主存緩沖區(qū)和緩沖區(qū)管理器 6
1.2.4
事務(wù)處理 6
1.2.5
查詢處理器 7
1.3
本書(shū)梗概 8
1.3.1
預(yù)備知識(shí) 8
1.3.2
存儲(chǔ)管理概述 8
1.3.3
查詢處理概述 9
1.3.4
事務(wù)處理概述 9
1.3.5
信息集成概述 9
1.4
數(shù)據(jù)庫(kù)模型和語(yǔ)言回顧 10
1.4.1
關(guān)系模型回顧 10
1.4.2
SQL回顧 10
1.4.3
關(guān)系的和面向?qū)ο蟮臄?shù)據(jù) 12
1.5
小結(jié) 13
1.6
參考文獻(xiàn) 14
第2章
數(shù)據(jù)存儲(chǔ) 15
2.1
存儲(chǔ)器層次 15
2.1.1
高速緩沖存儲(chǔ)器 16
2.1.2
主存儲(chǔ)器 16
2.1.3
虛擬存儲(chǔ)器 17
2.1.4
第二級(jí)存儲(chǔ)器 18
2.1.5
第三級(jí)存儲(chǔ)器 19
2.1.6
易失和非易失存儲(chǔ)器 20
習(xí)題 21
2.2
磁盤 21
2.2.1
磁盤結(jié)構(gòu) 21
2.2.2
磁盤控制器 23
2.2.3
磁盤存儲(chǔ)特性 24
2.2.4
磁盤訪問(wèn)特性 25
2.2.5
塊的寫(xiě)入 28
2.2.6
塊的修改 28
習(xí)題 28
2.3
第二級(jí)存儲(chǔ)器的有效使用 29
2.3.1
計(jì)算的I/O模型 30
2.3.2
第二級(jí)存儲(chǔ)器中的數(shù)據(jù)排序 30
2.3.3
歸并排序 31
2.3.4
兩階段多路歸并排序 32
2.3.5
擴(kuò)展多路歸并以排序更大的關(guān)系 34
習(xí)題 35
2.4
改善第二級(jí)存儲(chǔ)器的訪問(wèn)時(shí)間 36
2.4.1
按柱面組織數(shù)據(jù) 37
2.4.2
使用多磁盤 38
2.4.3
磁盤鏡像 39
2.4.4
磁盤調(diào)度和電梯算法 39
2.4.5
預(yù)取和大規(guī)模緩沖 42
2.4.6
各種策略及其優(yōu)缺點(diǎn) 43
習(xí)題 44
2.5
磁盤故障 45
2.5.1
間斷性故障 45
2.5.2
校驗(yàn)和 46
2.5.3
穩(wěn)定存儲(chǔ) 47
2.5.4
穩(wěn)定存儲(chǔ)的錯(cuò)誤處理能力 47
習(xí)題 48
2.6
從磁盤崩潰中恢復(fù) 48
2.6.1
磁盤的故障模型 48
2.6.2
作為冗余技術(shù)的鏡像 49
2.6.3
奇偶?jí)K 50
2.6.4
一種改進(jìn)：RAID?5 52
2.6.5
多個(gè)盤崩潰時(shí)的處理 53
習(xí)題 55
2.7
小結(jié) 57
2.8
參考文獻(xiàn) 58
第3章
數(shù)據(jù)元素的表示 60
3.1
數(shù)據(jù)元素和字段 60
3.1.1
關(guān)系型數(shù)據(jù)庫(kù)元素的表示 60
3.1.2
對(duì)象的表示 61
3.1.3
數(shù)據(jù)元素的表示 62
3.2
記錄 65
3.2.1
定長(zhǎng)記錄的構(gòu)造 65
3.2.2
記錄首部 67
3.2.3
定長(zhǎng)記錄在塊中的放置 68
習(xí)題 68
3.3
塊和記錄地址的表示 69
3.3.1
客戶機(jī)-服務(wù)器系統(tǒng) 69
3.3.2
邏輯地址和結(jié)構(gòu)地址 70
3.3.3
指針混寫(xiě) 71
3.3.4
塊返回磁盤 74
3.3.5
被固定的記錄和塊 74
習(xí)題 75
3.4
變長(zhǎng)數(shù)據(jù)和記錄 77
3.4.1
具有變長(zhǎng)字段的記錄 77
3.4.2
具有重復(fù)字段的記錄 78
3.4.3
可變格式記錄 79
3.4.4
不能裝入一個(gè)塊中的記錄 80
3.4.5
BLOBS 81
習(xí)題 82
3.5
記錄的修改 83
3.5.1
插入 83
3.5.2
刪除 84
3.5.3
更新 85
習(xí)題 85
3.6
小結(jié) 86
3.7
參考文獻(xiàn) 87
第4章
索引結(jié)構(gòu) 88
4.1
順序文件上的索引 89
4.1.1
順序文件 89
4.1.2
稠密索引 90
4.1.3
稀疏索引 92
4.1.4
多級(jí)索引 93
4.1.5
重復(fù)查找鍵的索引 94
4.1.6
數(shù)據(jù)修改期間的索引維護(hù) 97
習(xí)題 101
4.2
輔助索引 102
4.2.1
輔助索引的設(shè)計(jì) 103
4.2.2
輔助索引的應(yīng)用 104
4.2.3
輔助索引中的間接 105
4.2.4
文檔檢索和倒排索引 107
習(xí)題 109
4.3
B樹(shù) 111
4.3.1
B樹(shù)的結(jié)構(gòu) 111
4.3.2
B樹(shù)的應(yīng)用 114
4.3.3
B樹(shù)中的查找 116
4.3.4
范圍查詢 116
4.3.5
B樹(shù)的插入 117
4.3.6
B樹(shù)的刪除 119
4.3.7
B樹(shù)的效率 122
習(xí)題 123
4.4
散列表 124
4.4.1
輔存散列表 124
4.4.2
散列表的插入 125
4.4.3
散列表的刪除 126
4.4.4
散列表索引的效率 126
4.4.5
可擴(kuò)展散列表 127
4.4.6
可擴(kuò)展散列表的插入 127
4.4.7
線性散列表 129
4.4.8
線性散列表的插入 130
習(xí)題 132
4.5
小結(jié) 133
4.6
參考文獻(xiàn) 134
第5章
多維索引 136
5.1
需要多維的應(yīng)用 136
5.1.1
地理信息系統(tǒng) 137
5.1.2
數(shù)據(jù)立方體 138
5.1.3
SQL多維查詢 138
5.1.4
使用傳統(tǒng)索引執(zhí)行范圍查詢 139
5.1.5
利用傳統(tǒng)索引執(zhí)行最鄰近查詢 140
5.1.6
傳統(tǒng)索引的其他限制 141
5.1.7
多維索引結(jié)構(gòu)綜述 141
習(xí)題 142
5.2
多維數(shù)據(jù)的類散列結(jié)構(gòu) 143
5.2.1
網(wǎng)格文件 143
5.2.2
網(wǎng)格文件的查找 144
5.2.3
網(wǎng)格文件的插入 145
5.2.4
網(wǎng)格文件的性能 146
5.2.5
分段散列函數(shù) 147
5.2.6
網(wǎng)格文件和分段散列的比較 148
習(xí)題 149
5.3
多維數(shù)據(jù)的類樹(shù)結(jié)構(gòu) 151
5.3.1
多鍵索引 151
5.3.2
多鍵索引的性能 152
5.3.3
kd樹(shù) 153
5.3.4
kd樹(shù)的操作 154
5.3.5
使kd樹(shù)適合輔存 156
5.3.6
四叉樹(shù) 157
5.3.7
R樹(shù) 158
5.3.8
R樹(shù)的操作 159
習(xí)題 161
5.4
位圖索引 162
5.4.1
位圖索引的誘因 163
5.4.2
壓縮位圖 164
5.4.3
游程長(zhǎng)度編碼位向量的操作 166
5.4.4
位圖索引的管理 166
習(xí)題 168
5.5
小結(jié) 168
5.6
參考文獻(xiàn) 169
第6章
查詢執(zhí)行 171
6.1
一種查詢代數(shù) 172
6.1.1
并.?交和差 173
6.1.2
選擇操作符 174
6.1.3
投影操作符 175
6.1.4
關(guān)系的積 176
6.1.5
連接 177
6.1.6
消除重復(fù) 179
6.1.7
分組和聚集 179
6.1.8
排序操作符 181
6.1.9
表達(dá)式樹(shù) 181
習(xí)題 183
6.2
物理查詢計(jì)劃操作符介紹 185
6.2.1
掃描表 186
6.2.2
掃描表時(shí)的排序 186
6.2.3
物理操作符計(jì)算模型 186
6.2.4
衡量代價(jià)的參數(shù) 187
6.2.5
掃描操作符的I/O代價(jià) 188
6.2.6
實(shí)現(xiàn)物理操作符的迭代器 188
6.3
數(shù)據(jù)庫(kù)操作的一趟算法 191
6.3.1
一次多元組操作的一趟算法 192
6.3.2
全關(guān)系的一元操作的一趟算法 193
6.3.3
二元操作的一趟算法 195
習(xí)題 197
6.4
嵌套循環(huán)連接 198
6.4.1
基于元組的嵌套循環(huán)連接 198
6.4.2
基于元組的嵌套循環(huán)連接的迭代器 199
6.4.3
基于塊的嵌套循環(huán)連接算法 200
6.4.4
嵌套循環(huán)連接的分析 201
6.4.5
迄今為止的算法小結(jié) 201
習(xí)題 202
6.5
基于排序的兩趟算法 202
6.5.1
利用排序消除重復(fù) 202
6.5.2
利用排序進(jìn)行分組和聚集 204
6.5.3
基于排序的并算法 204
6.5.4
基于排序的交和差算法 205
6.5.5
基于排序的一個(gè)簡(jiǎn)單的連接算法 206
6.5.6
簡(jiǎn)單排序連接的分析 208
6.5.7
一種更有效的基于排序的連接 208
6.5.8
基于排序的算法小結(jié) 209
習(xí)題 209
6.6
基于散列的兩趟算法 211
6.6.1
通過(guò)散列劃分關(guān)系 211
6.6.2
基于散列的消除重復(fù)算法 211
6.6.3
基于散列的分組和聚集算法 212
6.6.4
基于散列的并.?交.?差算法 212
6.6.5
散列連接算法 213
6.6.6
節(jié)省一些磁盤I/O 213
6.6.7
基于散列的算法小結(jié) 215
習(xí)題 216
6.7
基于索引的算法 216
6.7.1
聚簇和非聚簇索引 217
6.7.2
基于索引的選擇 217
6.7.3
使用索引的連接 219
6.7.4
使用有排序索引的連接 220
習(xí)題 221
6.8
緩沖區(qū)管理 222
6.8.1
緩沖區(qū)管理結(jié)構(gòu) 222
6.8.2
緩沖區(qū)管理策略 223
6.8.3
物理操作符選擇和緩沖區(qū)管理的
關(guān)系 225
習(xí)題 226
6.9
使用超過(guò)兩趟的算法 226
6.9.1
基于排序的多趟算法 227
6.9.2
基于排序的多趟算法的性能 227
6.9.3
基于散列的多趟算法 228
6.9.4
基于散列的多趟算法的性能 228
習(xí)題 229
6.10
關(guān)系操作的并行算法 229
6.10.1
并行模型 229
6.10.2
一次一個(gè)元組的并行操作 232
6.10.3
全關(guān)系操作的并行算法 233
6.10.4
并行算法的性能 233
習(xí)題 235
6.11
小結(jié) 235
6.12
參考文獻(xiàn) 237
第7章
查詢編譯器 238
7.1
語(yǔ)法分析 238
7.1.1
語(yǔ)法分析與語(yǔ)法分析樹(shù) 239
7.1.2
SQL的一個(gè)簡(jiǎn)單子集的語(yǔ)法 239
7.1.3
預(yù)處理器 243
習(xí)題 243
7.2
用于改進(jìn)查詢計(jì)劃的代數(shù)定律 244
7.2.1
交換律與結(jié)合律 244
7.2.2
涉及選擇的定律 246
7.2.3
下推選擇 248
7.2.4
涉及投影的定律 249
7.2.5
有關(guān)連接與積的定律 252
7.2.6
有關(guān)消除重復(fù)的定律 252
7.2.7
涉及分組與聚集的定律 253
習(xí)題 254
7.3
從語(yǔ)法分析樹(shù)到邏輯查詢計(jì)劃 255
7.3.1
轉(zhuǎn)換成關(guān)系代數(shù) 255
7.3.2
從條件中去除子查詢 256
7.3.3
邏輯查詢計(jì)劃的改進(jìn) 261
7.3.4
結(jié)合/交換操作符的分組 262
習(xí)題 263
7.4
操作代價(jià)的估計(jì) 264
7.4.1
中間關(guān)系大小的估計(jì) 264
7.4.2
投影大小的估計(jì) 265
7.4.3
選擇大小的估計(jì) 266
7.4.4
連接大小的估計(jì) 268
7.4.5
多連接屬性的自然連接 269
7.4.6
多個(gè)關(guān)系的連接 271
7.4.7
其他操作的大小估計(jì) 272
習(xí)題 273
7.5
基于代價(jià)的計(jì)劃選擇介紹 274
7.5.1
大小參數(shù)估計(jì)值的獲取 275
7.5.2
統(tǒng)計(jì)量的增量計(jì)算 277
7.5.3
減少邏輯查詢計(jì)劃代價(jià)的啟發(fā)式 278
7.5.4
枚舉物理計(jì)劃的方法 279
習(xí)題 281
7.6
連接順序的選擇 283
7.6.1
連接的左右變?cè)囊饬x 283
7.6.2
連接樹(shù) 283
7.6.3
左深連接樹(shù) 284
7.6.4
通過(guò)動(dòng)態(tài)編程來(lái)選擇連接順序和
分組 286
7.6.5
帶有更具體的代價(jià)函數(shù)的動(dòng)態(tài)編程 289
7.6.6
選擇連接順序的貪婪算法 290
習(xí)題 291
7.7
物理查詢計(jì)劃選擇的完成 292
7.7.1
選取選擇方法 292
7.7.2
選取連接方法 294
7.7.3
流水線操作與物化 294
7.7.4
一元流水線操作 295
7.7.5
二元流水線操作 296
7.7.6
物理查詢計(jì)劃的符號(hào) 298
7.7.7
物理操作的順序 300
習(xí)題 300
7.8
小結(jié) 301
7.9
參考文獻(xiàn) 302
第8章
系統(tǒng)故障對(duì)策 304
8.1
可回復(fù)操作的問(wèn)題和模型 304
8.1.1
故障模式 304
8.1.2
關(guān)于事務(wù)的進(jìn)一步討論 306
8.1.3
事務(wù)的正確執(zhí)行 307
8.1.4
事務(wù)的原語(yǔ)操作 308
習(xí)題 310
8.2
undo日志 310
8.2.1
日志記錄 311
8.2.2
undo日志規(guī)則 312
8.2.3
使用undo日志的恢復(fù) 314
8.2.4
檢查點(diǎn) 315
8.2.5
非靜止檢查點(diǎn) 316
習(xí)題 318
8.3
redo日志 319
8.3.1
redo日志規(guī)則 320
8.3.2
使用redo日志的恢復(fù) 320
8.3.3
redo日志的檢查點(diǎn) 321
8.3.4
使用帶檢查點(diǎn)的redo日志的恢復(fù) 322
習(xí)題 323
8.4
undo/redo日志 323
8.4.1
undo/redo規(guī)則 323
8.4.2
使用undo/redo日志的恢復(fù) 324
8.4.3
undo/redo日志的檢查點(diǎn) 325
習(xí)題 326
8.5
防備介質(zhì)故障 327
8.5.1
備份 327
8.5.2
非靜止轉(zhuǎn)儲(chǔ) 328
8.5.3
使用備份和日志的恢復(fù) 329
習(xí)題 330
8.6
小結(jié) 330
8.7
參考文獻(xiàn) 331
第9章
并發(fā)控制 333
9.1
串行調(diào)度和可串行化調(diào)度 333
9.1.1
調(diào)度 333
9.1.2
串行調(diào)度 334
9.1.3
可串行化調(diào)度 335
9.1.4
事務(wù)語(yǔ)義的影響 335
9.1.5
事務(wù)和調(diào)度的一種記法 336
習(xí)題 337
9.2
沖突可串行性 337
9.2.1
沖突 337
9.2.2
優(yōu)先圖及沖突可串行性判斷 339
9.2.3
優(yōu)先圖測(cè)試發(fā)揮作用的原因 341
習(xí)題 341
9.3
使用鎖的可串行性實(shí)現(xiàn) 343
9.3.1
鎖 343
9.3.2
封鎖調(diào)度器 345
9.3.3
兩階段封鎖 346
9.3.4
兩階段封鎖發(fā)揮作用的原因 346
習(xí)題 347
9.4
用多種鎖方式的封鎖系統(tǒng) 349
9.4.1
共享鎖與排他鎖 349
9.4.2
相容性矩陣 350
9.4.3
鎖的升級(jí) 351
9.4.4
更新鎖 352
9.4.5
增量鎖 353
習(xí)題 354
9.5
封鎖調(diào)度器的一種體系結(jié)構(gòu) 356
9.5.1
插入鎖動(dòng)作的調(diào)度器 356
9.5.2
鎖表 358
習(xí)題 360
9.6
數(shù)據(jù)庫(kù)元素層次的管理 360
9.6.1
多粒度的鎖 360
9.6.2
警示鎖 361
9.6.3
幻像與插入的正確處理 363
習(xí)題 364
9.7
樹(shù)協(xié)議 364
9.7.1
基于樹(shù)的封鎖的動(dòng)機(jī) 365
9.7.2
訪問(wèn)樹(shù)結(jié)構(gòu)數(shù)據(jù)的規(guī)則 365
9.7.3
樹(shù)協(xié)議發(fā)揮作用的原因 366
習(xí)題 368
9.8
使用時(shí)間戳的并發(fā)控制 369
9.8.1
時(shí)間戳 369
9.8.2
物理上不可實(shí)現(xiàn)的行為 369
9.8.3
臟數(shù)據(jù)的問(wèn)題 370
9.8.4
基于時(shí)間戳調(diào)度的規(guī)則 371
9.8.5
多版本時(shí)間戳 373
9.8.6
時(shí)間戳與封鎖 374
習(xí)題 374
9.9
使用有效性確認(rèn)的并發(fā)控制 375
9.9.1
基于有效性確認(rèn)的調(diào)度器的結(jié)構(gòu) 375
9.9.2
有效性確認(rèn)規(guī)則 376
9.9.3
三種并發(fā)控制機(jī)制的比較 378
習(xí)題 379
9.10
小結(jié) 379
9.11
參考文獻(xiàn) 380
第10章
再論事務(wù)管理 382
10.1
讀未提交數(shù)據(jù)的事務(wù) 382
10.1.1
臟數(shù)據(jù)問(wèn)題 382
10.1.2
級(jí)聯(lián)回滾 384
10.1.3
回滾的管理 384
10.1.4
成組提交 385
10.1.5
邏輯日志 387
習(xí)題 388
10.2
視圖可串行性 389
10.2.1
視圖等價(jià)性 389
10.2.2
多重圖與視圖可串行性的判斷 390
10.2.3
視圖可串行性的判斷 393
習(xí)題 393
10.3
死鎖處理 394
10.3.1
超時(shí)死鎖檢測(cè) 394
10.3.2
等待圖 394
10.3.3
通過(guò)元素排序預(yù)防死鎖 396
10.3.4
時(shí)間戳死鎖檢測(cè) 397
10.3.5
死鎖管理方法的比較 399
習(xí)題 400
10.4
分布式數(shù)據(jù)庫(kù) 401
10.4.1
數(shù)據(jù)的分布 401
10.4.2
分布式事務(wù) 402
10.4.3
數(shù)據(jù)復(fù)制 402
10.4.4
分布式查詢優(yōu)化 403
習(xí)題 403
10.5
分布式提交 404
10.5.1
分布式原子性的支持 404
10.5.2
兩階段提交 404
10.5.3
分布式事務(wù)的恢復(fù) 406
習(xí)題 407
10.6
分布式封鎖 408
10.6.1
集中封鎖系統(tǒng) 408
10.6.2
分布式封鎖算法的代價(jià)模型 409
10.6.3
封鎖多副本的元素 410
10.6.4
主副本封鎖 410
10.6.5
局部鎖構(gòu)成的全局鎖 410
習(xí)題 411
10.7
長(zhǎng)事務(wù) 412
10.7.1
長(zhǎng)事務(wù)的問(wèn)題 412
10.7.2
saga（系列記載） 414
10.7.3
補(bǔ)償事務(wù) 414
10.7.4
補(bǔ)償事務(wù)發(fā)揮作用的原因 416
習(xí)題 416
10.8
小結(jié) 417
10.9
參考文獻(xiàn) 418
第11章
信息集成 420
11.1
信息集成的方式 420
11.1.1
信息集成的問(wèn)題 420
11.1.2
聯(lián)邦數(shù)據(jù)庫(kù)系統(tǒng) 421
11.1.3
數(shù)據(jù)倉(cāng)庫(kù) 423
11.1.4
Mediator 425
習(xí)題 426
11.2
基于Mediator系統(tǒng)的包裝器 427
11.2.1
查詢模式的模板 428
11.2.2
包裝器生成器 429
11.2.3
過(guò)濾器 429
11.2.4
其他在包裝器上進(jìn)行的操作 430
習(xí)題 431
11.3
聯(lián)機(jī)分析處理 432
11.3.1
OLAP應(yīng)用 433
11.3.2
OLAP數(shù)據(jù)的多維視圖 433
11.3.3
星型模式 434
11.3.4
切片和切塊 436
習(xí)題 437
11.4
數(shù)據(jù)立方體 438
11.4.1
立方體操作符 438
11.4.2
通過(guò)物化視圖實(shí)現(xiàn)立方體 441
11.4.3
視圖的格 443
習(xí)題 444
11.5
數(shù)據(jù)挖掘 445
11.5.1
數(shù)據(jù)挖掘的應(yīng)用 446
11.5.2
關(guān)聯(lián)規(guī)則的挖掘 447
11.5.3
A-Priori算法 449
11.6
小結(jié) 450
11.7
參考文獻(xiàn) 451
索引 453