tree)算法，前者是传统数据库合并连接的推广，后者是一种基于堆栈的结构连接的算法，通过内存中保留一个栈结构来达到对输入数据的一次扫描的目标。文献对stack-tree算法做了改进，利用附加的索引跳过不需要参加连接的节点。堆栈合并算法(stack-tree)既可以应用在xml的关系存储系统中，也可以应用在原生xml系统中。
除了基于区域编码的结构连接算法，文献目中还针对它提出的pbitree编码提出了基于划分的结构连接算法，其划分策略有两种：水平划分和垂直划分，分别按节点在树中的高度和所在分支对数据集合的划分，这种算法不要求输入的数据有序或建立索引。结构连接算法在一定程度上依赖于节点的编码方法，目前普遍使用的编码方法是区域编码。由于使用区域编码可以快速确定节点间的包含关系，开发高效基于区域编码的结构连接算法仍然是一个值得研究的课题。
3.3.2 结构连接的顺序选择
在结构连接中，无论采用什么样的结构连接算法，结构连接的顺序极大地影响着结构连接运算的性能，文献使用简单的代价估算模型提出了5种结构连接的顺序选择算法。其基本思想是使用动态规划算法在整个解空间中搜索代价最小的连接计划，当连接节点过多时解空间会发生组合爆炸，使用动态规划算法进行搜索将会变得非常缓慢。为了加速搜索速度，在动态规划算法中引入了各种不同的启发式规则，这虽然极大地提高了搜索速度却冒着一些可能丢失最优解的风险。结构连接顺序选择的目标是用较小的代价获得最优的连接计划，要实现这个目标还有待于新的结构连接顺序选择算法的提出。

4 总结

xml路径表达式查询优化技术是xml查询优化的关键技术。文中概括了3种优化技术。重写优化技术在查询解析之后查询计划生成之前使用，其目的是消除路径中的冗余步，把长的查询路径变为等价的短路径，一方面在基于路径分解查询中减少连接次数和中间连接结果，另一方面在树遍历方法中也可以减少扫描的节点数，从而极大地优化了查询性能。基于树遍历的查询优化和基于路径分解的查询优化则是在查询计划生成阶段使用的。采用什么样的优化技术主要取决于路径表达式的处理方法。节点编码技术和结构连接紧密相关，索引技术也是xml查询优化的关键技术，在这些优化技术中很少使用到xml的数据模式(dtd或schame)。在查询中合理有效地使用数据模式将会给查询优化带来一片新的天地

上一页  [1] [2] [3]