杨 扬，李海歌

（1.河南大学 计算中心，河南 开封475004；2.开封市建筑设计院有限公司，河南 开封475004）

0 引 言

XML作为互联网中一种数据表示与交换的标准，具有高效结构连接算法的查询方法成为XML数据库的研究热点。当前，为优化XML数据查询和更新，AList和DList列表之间的结构连接操作构成了结构查询的核心，为了加速结构连接，研究人员首先对XML文档树结点编码来判断结点之间的结构关系，而无需遍历整棵XML文档树。再者通过高效的结构连接算法提高查询效率。高效的XML查询重在优化的结构连接算法，与之相关的有益算法大多基于归并思想，根据XML文件格式的特点和编码规则减少或避免了无效的结构连接。为了能够规避不参与结构连接的结点，一些算法思想采用索引结构进一步减少连接的扫描代价，但索引的维护又需要额外的时间和空间开销。为解决上述问题，本文给出的扩展的Dewey编码，加速了结点的结构关系判断，在此基础上，论文改进了Stack－Tree－Desc（STD）算法，提出了一种不依赖于索引结构的优化算法，利用栈进行缓存来减少连接次数，在查找下一个需要参与连接的结点时引入二分查找，有效地跳过了不必要的结构连接，无需顺序扫描，最坏情况下AList和DList列表只需各遍历一次。实验结果表明，论文所用编码方案和改进算法具有较好的查询效果。

1 相关研究

当前，多数结构连接算法基于归并结构，根据XML文件格式的特点和编码规则减少或避免了无效的结构连接。C.Zhang和J.Naughton等提出了一种执行性能优于关系查询引擎的结构连接算法MPMGJN，该算法能有效地实现包含连接，但多次重复地扫描内表会影响算法性能。……