文档介绍：并行数据库系统
1并行数据库概述
并行数据库系统是在并行机上运行的具有并行处理水平的数据库系统,是数据库技术与并行计算技术结合的产物.
：
,利用多个处理机对磁盘数allelism）和垂直并行 化（流水线并行化, Pipelining
Parallelism)
OPi OP2
（a）水平并行化 （b）垂直并行化
图2. 2. 并行化的两种形式
如果两个操作OP1、OP2无相互依赖关系, 多个操作或者一个操作内互相独立的多个子操作分别由 不同的处理机 并行执行的形式.
如果操作OP2直接依赖于OP1,并且OP2必须等待OP1处理完所有元组前方可开始执行,那么称 OP2 以阻塞方式直接依赖于OP1;如果OP2无需等待OP1执行完毕即可在另一处理机上开始执行,那么称 OP2 以流水线方式直接依赖 执行的形式.
例如,排序操作、扫描操作由不同的处理机并行执行就是 水平并行化的实例.
排序 排序 排序……
III
扫描 扫描 扫描…… III
例如：扫描操作、排序操作、连接操作、分组操作由不同的处理机并行执行就是 垂直并行优化的实
扫描
排序
连接
分组
由于关系代数的封闭性和数据操作的相对独立性,关系查询具有三种固有并行性,即 操作间的流水
线并行性、操作间的独立并行性 以及操作内的独立并行性,这为了关系代数的并行化提供了现实根底.
并行操作算法
法有并行结合算法、并行扫描算法、并行排序算法 等.
由于结合操作是关系数据库系统中最耗时且最常用的操作, 于嵌套循环的并行结合算法、基于合并扫描的并行结合算法 、基于HASH的并行结合算法、基于索引的并 行结合算法等.
一、 基于嵌套循环的并行结合算法 （S>>R）
输入：R, S:待结合的两个关系； A :连接属性； P:处理机数
输出：关系R和S的结合结果（结合属性为了 A ）
方法：（1）把S均匀地分布到P个处理机,设Si是S在结点i上的子集合；
（2） FOR I = 1 TO p DO （并行地）
处理机i根据结合属性值排序 S
END DO ;
（3） 在R所在的处理机上,对 R按结合的属性排序,再以流水线方式向P个处理机播送R的元组；
（4） FOR i = 1 TO p DO （流水线方式并行的）
处理机i以流水线方式接收 R的元组；
对磁盘上的S中元组和内存中R的元组结合、输出；
ENDFOR ;
该算法适合于S的元组数远远大于 R的元组数（R元组数较少）
R与S基于嵌套循环的并行结合示意图 一次哈希与排序并行结合图
二、基于排序的并行结合算法
基于排序的并行结合算法由两个阶段组成： ,它根据结合属性的值 排序
每个结合关系；在结合阶段,完成两个排序关系的结合.
输入：R, S:待结合的两个关系.
A:连接属性
P:处理机数
H