Performance evaluation of a parallel cascade semijoin algorithm for computing path expressions in object database systems
With the emerging of new applications, especially in Web, such as E-Commerce, Digital Library and DNA Bank, object database systems show their stronger functions than other kinds of database systems due to their powerful representation ability on complex semantics and relationship. One distinguished feature of object database systems is path expression, and most queries on an object database are based on path expression because it is the most natural and convenient way to access the object database, for example, to navigate the hyperlinks in a web-based database. The execution of path expression is usually extremely expensive on a very large database. Therefore, the improvement of path expression execution efficiency is critical for the performance of object databases. As an important approach realizing high-performance query processing, the parallel processing of path expression on distributed object databases is explored in this paper. Up to now, some algorithms about how to compute path expressions and how to optimize path expression processing have been proposed for centralized environments. But, few approaches have been presented for computing path expressions in parallel. In this paper, a new parallel algorithm for computing path expression named Parallel Cascade Semijoin (PCSJ) is proposed. Moreover, a new scheduling strategy called right-deep zigzag tree is designed to further improve the performance of the PCSJ algorithm. The experiments have been implemented in an NOW distributed and parallel environment. The results show that the PCSJ algorithm outperforms the other two parallel algorithms (the parallel version of forward pointer chasing algorithm (PFPC) and the index splitting parallel algorithm (IndexSplit)) when computing path expressions with restrictive predicates and that the right-deep zigzag tree scheduling strategy has better performance than the right-deep tree scheduling strategy.
path expression object database parallel algorithm scheduling strategy