《计算机学报》文章摘要 全文下载 | |
文章题目 | 路径表达式的并行算法研究 |
作者 | 王国仁 于 戈 张 斌 郑怀远 |
作者单位 | (东北大学计算机科学与工程系 沈阳 110006) |
发表年份 | 1999 |
发表月份 | 2期 (页码:126—133) |
文章摘要 | 在面向对象数据库系统中,路径表达式是用于定位复杂对象的必要查询设施,因此,优化和并行化路径表达式的执行是实现高性能面向对象数据库系统的关键因素之一.由于OQL语言的正交性,在SELECT,FROM和(或)WHERE子句中均可嵌套路径表达式,而我们将着重讨论WHERE子句中路径表达式的并行计算,这种路径表达式也称之为复杂谓词.本文在分析了现有路径表达式的计算方法后,提出了两种新的路径表达式并行计算算法:并行级联式半 连接算法(PCSJ)和并行正向指针跟踪算法(PFPC).为了达到一个路径表达式的并行化计算,该表达式可以转换为一个等价的连接表达式,但是我们研究发现,一个路径表达式只要转换为一个级联式半连接表达式即可,该表达式产生与路径表达式等价的结果.由于一个半连接的代价总是少于一个连接操作的代价,因此PCSJ算法总是要优于基于连接的并行算法.PFPC算法是集中式正向指针跟踪算法的并行实现,它能充分利用管道并行性和I/O并行性. 关键词 路径表达式,并行算法,面向对象数据库. |