基于直方图的并行结构连接算法

Parallel Structural Join Algorithms

连接操作是最昂贵且常用的数据库操作 在传统数据库系统中 ,主要的连接操作是等值连接操作 ,因此 ,传统的并行连接算法主要集中于并行等值连接操作 另外 ,随着XML在Web应用中变得越来越重要 ,XML已经成为Internet上一种新的数据交换标准 对XML数据的连接操作不同于传统数据库中的等值连接操作 ,它属于结构连接操作 以前适合等值连接操作的并行连接算法并不能有效地解决结构连接问题 因此 ,第 1次提出了并行结构连接问题 ,并且通过应用直方图的思想于并行连接中 ,从而提出两种基本的并行XML结构连接算法、等高直方图连接算法和等宽直方图连接算法

Join operation is the most expendable operation as well as the most universal operation in database system The main join operation is equi join operation in traditional database systems, and previous work about parallel join mainly focuses on the equi join operation In addition, with the growing importance of XML in Web applications, XML has become the new standard for data exchange over Internet Unlike the equi join in traditional databases, the join operation about XML belongs to structural join operation Previous parallel join algorithms that are suitable to equi join cannot solve structural join problems Therefore, the problem of parallel structural join is proposed for the first time Also proposed in this paper are two parallel structural join algorithms, equal high histogram join algorithm and equal breadth histogram join algorithm, that are proposed by utilizing histogram on parallel join Experimental results indicate that both algorithms can improve the performance of structural joins