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

在面向对象数据库系统中，路径表达式是用于定位复杂对象的必要查询设施，因此，优化和并行化路径表达式的执行是实现高性能面向对象数据库系统的关键因素之一．由于ＯＱＬ语言的正交性，在ＳＥＬＥＣＴ，ＦＲＯＭ和（或）ＷＨＥＲＥ子句中均可嵌套路径表达式，而我们将着重讨论ＷＨＥＲＥ子句中路径表达式的并行计算，这种路径表达式也称之为复杂谓词．本文在分析了现有路径表达式的计算方法后，提出了两种新的路径表达式并行计算算法：并行级联式半连接算法（ＰＣＳＪ）和并行正向指针跟踪算法（ＰＦＰＣ）．为了达到一个路径表达式的并行化计算，该表达式可以转换为一个等价的连接表达式，但是我们研究发现，一个路径表达式只要转换为一个级联式半连接表达式即可，该表达式产生与路径表达式等价的结果．由于一个半连接的代价总是少于一个连接操作的代价，因此ＰＣＳＪ算法总是要优于基于连接的并行算法．ＰＦＰＣ算法是集中式正向指针跟踪算法的并行实现，它能充分利用管道并行性和Ｉ／Ｏ并行性．

路径表达式的并行正向指针跟踪算法:设计与性能分析

在对象数据库系统中 ,路径表达式是用于定位复杂对象的不可缺少的工具·由于路径表达式的计算非常耗时 ,因此若要提高数据库性能 ,优化和并行计算路径表达式的执行是关键环节·并行正向指针跟踪算法 (PFPC)充分利用了管道并行性和I/O并行性·在基于分布式共享虚拟存储器 (DSVM)的分布式对象数据库FISH系统上完成了实现和测试·对算法的设计进行了详细描述并分析其性能·