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

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.