第一章 数据库机器和并行数据库系统概述 1
1．1 新一代数据库应用的特点 1
1．1．1 复杂数据对象 2
1．1．2 规则管理 2
1．1．3 数据模型中的新概念 3
1．1．4 巨型数据库 3
1．1．5 第三级存储器 3
1．1．6 长事务处理 4
1．1．7 版本与格局 4
1．2 Von Neumann计算机系统结构的不适应性 4
1．2．1 数据存取问题 5
1．2．2 并行处理问题 5
1．2．3 处理器瓶颈问题 6
1．2．4 存储器瓶颈问题 6
1．2．5 I/O瓶颈问题 7
1．2．6 总结 7
1．3 数据库机器 8
1．3．1 数据库机器的分类 8
1．3．2 具有数据库级索引的数据库机器 10
1．3．3具有关系级索引的数据库机器 13
1．3．4 具有页索引级的数据库机器 15
1．3．5 数据库机器的问题和意义 16
1．4 并行数据库系统概述 18
1．4．1 并行数据库系统的进展 19
1．4．2 关系数据库系统的固有并行性 19
1．4．3 支持并行数据库系统的并行计算结构 21
1．4．4 并行数据库系统的软件结构 22
1．5 文献阅读导引 23
参考文献 23
第二章 并行计算机系统与并行算法 27
2．1 并行计算机系统的发展 27
2．2 并行计算机系统的分类模型 28
2．2．1 SISD计算机系统 28
2．2．2 MISD计算机系统 28
2．2．3 SIMD计算机系统 29
2．2．4 MIMD计算机系统 31
2．3 连接网络 32
2．3．1 动态连接网络 32
2．3．2 静态连接网络 35
2．3．3 静态连接网络的性能分析 39
2．4 计算机机群并行计算系统 42
2．4．1 机群并行计算系统的特点 42
2．4．2 机群并行计算系统的高速通信网络 43
2．4．3 机群并行计算系统的硬件环境 43
2．4．4 机群并行计算系统的软件环境 46
2．5 并行算法及其复杂性分析 49
2．5．1 并行执行时间 50
2．5．2 工作量 50
2．5．3 加速比 50
2．5．4 效率 51
2．5．5 伸缩性 51
2．5．6 算法复杂性测度函数的阶 51
2．6 文献阅读导引 52
参考文献 53
第三章 并行数据库的物理存储方法 57
3．1 一维数据分布方法 57
3．1．1 Round-Robin分布方法 57
3．1．2 Hash分布方法 58
3．1．3 Range分布方法 58
3．1．4 Hybrid-Range-Partition分布方法 59
3．2 多维数据分布方法CMD 62
3．2．1 基本概念 62
3．2．2 CMD数据分布方法 64
3．2．3 CMD方法的性能分析 66
3．2．4 单处理机上的数据组织 70
3．2．5 数据更新操作 71
3．3 基于错误校正码的多维数据分布方法 71
3．3．1 线性错误校验码 71
3．3．2 ECC数据分布方法 73
3．4 其它多维数据分布方法 74
3．4．1 随机数据分布方法 74
3．4．2 一般化的CMD数据分布方法 74
3．4．3 BM数据分布方法 75
3．4．4 FX数据分布方法 75
3．4．5 基于Hilbert曲线的数据分布方法 76
3．4．6 BERD多维数据分布方法 77
3．5 并行B-树 78
3．5．1 大结点并行B-树 78
3．5．2 基于记录分布的并行B-树 80
3．5．3 基于树结点分布的并行B-树 82
3．6 简单并行GRID文件 86
3．6．1 SPGRID文件结构的初始构造算法 86
3．6．2 动态数据平衡算法 88
3．7 两级并行GRID文件 90
3．7．1 逻辑并行GRID文件 91
3．7．2 物理并行GRID文件 91
3．7．3 并行GRID文件结构的构造和数据加载算法 92
3．8 文献阅读导引 101
参考文献 101
第四章 并行数据操作算法 104
4．1 并行排序算法 105
4．1．1 基于合并操作的并行排序算法 105
4．1．2 基于比较-交换操作的并行排序算法 108
4．1．3 基于数据划分的并行排序算法 110
4．2 并行选择、投影和集合操作算法 113
4．2．1 并行选择算法 113
4．2．2 并行投影算法 115
4．2．3 并行集合操作算法 117
4．3 并行连接算法 120
4．3．1 并行嵌套循环连接算法 120
4．3．2 并行排序合并连接算法 122
4．3．3 并行Hash连接算法 124
4．4 抗数据偏斜的并行连接算法 128
4．4．1 简单抗数据偏斜并行连接算法 129
4．4．2 并行Tuple-Interleaving-Hash连接算法 130
4．4．3 并行Adaptive-Load-Balancing-Hash连接算法 131
4．4．4 扩展的并行Adaptive-Load-Balancing-Hash连接算法 135
4．5 基于CMD并行存储结构的并行连接算法 137
4．5．1 基本概念 138
4．5．2 CMD Join算法 139
4．6 基于并行B-树存储结构的并行连接算法 144
4．6．1 基于RANGE划分策略的并行B-树连接算法 144
4．6．2 基于Hash划分策略的并行B-树连接算法 150
4．7 文献阅读导引 152
参考文献 153
第五章 并行查询优化处理的数据流方法 157
5．1 顺序数据库操作算法 157
5．1．1 选择操作的实现算法 157
5．1．2 笛卡儿乘积的实现算法 159
5．1．3 连接操作的实现算法 161
5．1．4 投影操作的实现算法 164
5．1．5 集合的并、交、差实现算法 165
5．2 数据库操作结果大小的估计 167
5．3 简单并行数据流方法 171
5．3．1 简单并行数据流图 171
5．3．2 处理机分配算法 172
5．3．3 并行查询计划的调度执行算法 173
5．3．4 处理机之间的通信 175
5．3．5 改进的处理机分配和查询计划调度执行算法 176
5．4 基于数据划分的并行数据流方法 178
5．4．1 DPBPDF方法概述 178
5．4．2 DPBPDF方法的查询处理器 179
5．4．3 执行顺序图的构造算法 181
5．4．4 数据操作划分算法 183
5．4．5 分解与合并操作连接算法 187
5．5 文献阅读导引 191
参考文献 191
第六章 并行数据库查询优化方法 192
6．1 引言 192
6．2 两阶段查询优化方法 193
6．2．1 以最小化查询执行时间为目标的方法 193
6．2．2 以充分利用系统资源为目标的优化算法 198
6．3 基于左线性树的查询优化方法 201
6．3．1 查询执行计划模型和查询执行计划空间 202
6．3．2 左线性树查询执行计划的复杂性模型 203
6．3．3 查询优化算法 206
6．3．4 存储空间限制问题 207
6．4 基于右线性树的查询优化算法 208
6．4．1 查询执行计划模型和查询执行计划空间 208
6．4．2 右线性树查询执行计划的复杂性模型 208
6．4．3 查询优化算法 210
6．5 基于片段式右线性树的查询优化方法 211
6．5．1 查询执行计划模型和查询执行计划空间 211
6．5．2 SRD树查询执行计划的复杂性模型 212
6．5．3 基于SRD树的查询优化算法 213
6．6 基于浓密树的查询优化算法 216
6．6．1 查询执行计划模型和查询执行计划空间 216
6．6．2 查询优化算法 217
6．7 基于多重加权树的查询优化方法 221
6．7．1 查询执行计划模型和查询执行计划空间 221
6．7．2 多重加权树并行查询计划的复杂性模型 225
6．7．3 并行查询优化算法 229
6．8 文献阅读导引 243
参考文献 244