路径表达式的并行算法研究

在面向对象数据库系统中，路径表达式是用于定位复杂对象的必要查询设施，因此，优化和并行化路径表达式的执行是实现高性能面向对象数据库系统的关键因素之一，由于ＯＱＬ语言的正交性，在ＳＥＬＥＣＴ，ＦＲＯＭ和（或）ＷＨＥＲＥ子句中均可嵌套路径表达式，而我们将着重讨论ＷＨＥＲＥ子句子路径表达式的并行计算，种路径表达式也称之为复杂谓词。本文分析了现有路径表达式的计算方法后，提出了两种新的路径表达式并行计算算法，

THE 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 for achieving 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, 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.