Parallel algorithms for path expressions

Path expression is an essential query facility to locate complex objects in object-oriented database systems. Thus, optimizing and parallelizing execution of path expressions are critical factors to achieve high performance of object-oriented database systems. Because of the orthogonality of OQL language, a path expression can be placed in the SELECT, FROM, and/or WHERE clauses. This paper focuses on the parallel execution of path expressions in the WHERE clauses, and this kind of path expressions is also referred to as complex predicates. After analyzing the existing approaches to path expressions, this paper presents a parallel cascade semi-join (PCSJ) algorithm and a parallel forward pointer chasing (PFPC) algorithm for parallelly computing path expressions. In order to parallelize computation of a path expression, the expression can be converted to a join expression. However, it is sufficient that a path expression is converted to a cascade semi-join expression which generates the equivalent result to the path expression. Since the cost of a semi-join is always less than that of the corresponding join, the PCSJ algorithm can always outperform the other parallel algorithms based on join operations. The PFPC algorithm is a parallel version of forward pointer chasing algorithm that fully exploits pipelining parallelism and executes I/O operations in parallel.