XML路径表达式的查询优化技术(3)
2015-12-23 01:40
导读：基于树遍历的查询优化要使用路径索引缩小搜索范围，这种优化方法的关键问题是要设计出有效合理的便于维护的路径索引。DataGuides算得上是最早的路径
基于树遍历的查询优化要使用路径索引缩小搜索范围，这种优化方法的关键问题是要设计出有效合理的便于维护的路径索引。DataGuides算得上是最早的路径索引，也是路径索引中最有影响力的代表。它采用了一种标签路径合并策略对文档结构进行缩减，DmGuides中的每个节点都有一个目标集。这个目标集记录了通过这个标签路径可访问到的数据节点，这样执行一个路径查询时只需要在Dataguides中查找该路径，获得的目标集即为满足条件的查询结果。当文档的数据结构比较规则时Dataguides能很好地缩减文档的结构，从而极大地改善查询的性能。
文献中提出了一种使用图模式(Graph Schemas)缩小查询范围的方法。这里的图模式也起着DataGuides的作用，但是它采用了合并同类边的策略。图模式中的节点叫状态，每个状态都对应一个状态扩展，集即该状态在文档中所对应的节点集。在此基础上文档提出了两种查询优化策略：剪切查询和使用状态扩展集重写查询。剪切查询是将查询的搜索限制在仅与查询结果有关的子树上，后者则是将原查询改写为在图模式上的查询，两种方法都使用非确定自动机为剪切工具。
不同于以上两种方式，文献提出了一种新的路径查询方法，该方法将XML文档中的文本数据抽取出来单独存储，这样文档树仅由带标签的元素或属性组成，这样的结构被叫做文档的骨架(skeleton)。为了使大的文档的骨架尽可能地放入内存中。这个树骨架进一步通过共享的公共子树被压缩，被压缩的树骨架的每个节点与未压缩树的一组节点相对应，他们之间的对应关系用双向相似关系表示。
3.3 基于路径分解的查询优化
结构连接是基于节点在NML文档中的位置表示确定XML节点间的包含关系。给定一个祖先(或父)节点集合A和一个后代(或子)节点集合D，结构连接操作的任务就是要用高效的方法找到所有的节点对(ai,di)，其中ai是di的祖先(或父亲)，ai、di分别是A、D中的元素。A、D可能来自索引扫描也可能是某个计算的中间结果。结构连接运算的代价非常昂贵，因此结构连接算法的好坏直接影响着查询的效率，同时结构连接的顺序也极大地影响着结构连接运算的性能。
中国大学排名
3.3.1 结构连接算法
目前，已经提出的结构连接算法有两种：排序合并[2，3,7,19]和划分方法。排序合并法的主要特点是：①节点采用区域编码确定节点间的结构关系；②要求输入的数据集有序或在数据集上建立索引；③为了快速定位某类节点，可以利用元素索引、路径索引或值索引。文献中提出了一种多谓词合并连接算法(MP-MGJN)，该算法需要多次扫描数据集；文献中提出的ε－jion、εA－lion和κe-iion算法存在同样的缺点。文献提出了两类算法：树合并(Tree-Merge)算法和堆栈合并(stack-Tree)算法，前者是传统数据库合并连接的推广，后者是一种基于堆栈的结构连接的算法，通过内存中保留一个栈结构来达到对输入数据的一次扫描的目标。文献对Stack-Tree算法做了改进，利用附加的索引跳过不需要参加连接的节点。堆栈合并算法(stack-Tree)既可以应用在XML的关系存储系统中，也可以应用在原生XML系统中。
除了基于区域编码的结构连接算法，文献目中还针对它提出的PBiTree编码提出了基于划分的结构连接算法，其划分策略有两种：水平划分和垂直划分，分别按节点在树中的高度和所在分支对数据集合的划分，这种算法不要求输入的数据有序或建立索引。结构连接算法在一定程度上依赖于节点的编码方法，目前普遍使用的编码方法是区域编码。由于使用区域编码可以快速确定节点间的包含关系，开发高效基于区域编码的结构连接算法仍然是一个值得研究的课题。
3.3.2 结构连接的顺序选择
在结构连接中，无论采用什么样的结构连接算法，结构连接的顺序极大地影响着结构连接运算的性能，文献使用简单的代价估算模型提出了5种结构连接的顺序选择算法。其基本思想是使用动态规划算法在整个解空间中搜索代价最小的连接计划，当连接节点过多时解空间会发生组合爆炸，使用动态规划算法进行搜索将会变得非常缓慢。为了加速搜索速度，在动态规划算法中引入了各种不同的启发式规则，这虽然极大地提高了搜索速度却冒着一些可能丢失最优解的风险。结构连接顺序选择的目标是用较小的代价获得最优的连接计划，要实现这个目标还有待于新的结构连接顺序选择算法的提出。
中国大学排名
4 总结
XML路径表达式查询优化技术是XML查询优化的关键技术。文中概括了3种优化技术。重写优化技术在查询解析之后查询计划生成之前使用，其目的是消除路径中的冗余步，把长的查询路径变为等价的短路径，一方面在基于路径分解查询中减少连接次数和中间连接结果，另一方面在树遍历方法中也可以减少扫描的节点数，从而极大地优化了查询性能。基于树遍历的查询优化和基于路径分解的查询优化则是在查询计划生成阶段使用的。采用什么样的优化技术主要取决于路径表达式的处理方法。节点编码技术和结构连接紧密相关，索引技术也是XML查询优化的关键技术，在这些优化技术中很少使用到XML的数据模式(DTD或Schame)。在查询中合理有效地使用数据模式将会给查询优化带来一片新的天地。
