基于路径分解的查询优化

结构连接是基于节点的节点NML文档中的位置表示确定XML节点之间的包含关系。给出祖先(或父)节点集合A和后代(或子)节点集合AD，结构连接操作的任务是用高效的方法找到所有节点(ai，di)，其中ai是di祖先(或父亲)，ai，di分别是A，D中的元素。A，D它可能来自索引扫描或计算的中间结果。结构连接操作的成本非常昂贵，因此结构连接算法的质量直接影响查询的效率，结构连接的顺序也极大地影响了结构连接操作的性能。

1.结构连接算法

有两种结构连接算法：排序合并[2、3、7、19]和划分方法。排序合并法的主要特点是：①节点之间的结构关系由区域编码确定；②要求输入的数据集有序或在数据集上建立索引；③为了快速定位某一节点，可以使用元素索引、路径索引或值索引。文献中提出了一种多谓词合并连接算法(MP-MGJN)，该算法需要多次扫描数据集；ε－jion，εA－lion和κe-iion算法也有同样的缺点。文献提出了两种算法：树合并：(Tree-Merge)算法与堆栈结合(stack-Tree)算法，前者是传统数据库合并连接的推广，后者是基于堆栈的结构连接的算法，通过在内存中保留栈结构来扫描输入数据。文献对Stack-Tree改进算法，使用附加索引跳过不需要参与连接的节点。堆栈合并算法(stack-Tree)可应用于XML关系存储系统也可用于原始存储系统XML系统中。

除了基于区域编码的结构连接算法外，文献还提出了PBiTree编码提出了基于划分的结构连接算法。划分策略有两种：水平划分和垂直划分，根据节点在树上的高度和分支对数据集的划分。该算法不要求输入的数据有序或建立索引。结构连接算法在一定程度上取决于节点的编码方法，目前常用的编码方法是区域编码。由于使用区域编码可以快速确定节点之间的包含关系，开发基于区域编码的高效结构连接算法仍然是一个值得研究的课题。

2.结构连接的顺序选择

在结构连接中，无论采用什么样的结构连接算法，结构连接的顺序都极大地影响了结构连接操作的性能。文献采用简单的成本估算模型，提出了五种结构连接的顺序选择算法。其基本思想是利用动态规划算法在整个解决空间中搜索成本最低的连接计划。当连接节点过多时，解决空间会发生组合爆炸，使用动态规划算法进行搜索会变得非常缓慢。为了加快搜索速度，在动态规划算法中引入了各种启发性规则，虽然大大提高了搜索速度，但存在一些可能失去最优解的风险。选择结构连接顺序的目标是以较小的成本获得最优的连接计划。要实现这一目标，需要提出新的结构连接顺序选择算法。

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