Parallel structural join algorithms

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.