XML路径表达式的查询优化技术(2)
2015-12-23 01:40
导读：2.1 树遍历方法 最朴素的路径访问方法是树遍历的方法：一般采用自顶向下的方式遍历文档树，使用该方法进行查询时需要遍历某元素通往叶子节点的所有
2.1 树遍历方法
最朴素的路径访问方法是树遍历的方法：一般采用自顶向下的方式遍历文档树，使用该方法进行查询时需要遍历某元素通往叶子节点的所有可能路径。为了减少树遍历的代价引入自底向上的方法，首先查找符合谓词条件的所有原子节点，然后再寻找它们的父节点。这种方法一般情况下比较简单、耗时较少。但对于符合谓词条件的节点数目很大而符合路径表达式的路径很少时，这种遍历方式的代价可能会高于自顶向下方式。一种折中的方法是同时按自顶向下和自底向上两种方法进行遍历，最后在路径的某个中间位置汇合，从而得到查询结果。当路径上某节点的扇人度(在文档中的)很大而符合谓词条件的原子节点很少时，该方法可以达到最优。在这种方法中优化路径表达式查询的一个中心思想是设法缩小查询范围。使得不需要遍历整个树就可以获得符合条件的查询结果。
2.2 路径分解法
这一种方法是目前用的比较多的，它的基本思路是将复杂的查询路径分解成简单路径，简单路径可以是由一个元素、一个谓词条件或一个元素加一个谓词条件，还可以是由两个元素组成的路径。首先计算这些简单路径表达式，再将每个简单路径表达式的计算结果连接起来。其本质确定节点间的结构关系(祖先后代或父子关系)，因此这种操作叫结构连接。像关系数据库中的连接运算一样，结构连接操作的代价非常昂贵，结构连接又是查询处理的核心操作，因此在这种查询处理模式中查询优化的关键开发高效的结构连接算法，同时结构连接的顺序也极大地影响着结构连接运算的性能。
3 路径表达查询优化的一般方法
3.1 路径表达式的重写优化
（科教范文网http://fw.NSEAC.com编辑发布）
路径表达式重写优化的基本思想将复杂的、高代价的查询路径表达式转换为简单的、低代价的等价路径表达式。查询重写技术的一般特征可以概括如下：①重写优化发生在查询解析之后查询计划生成之前；②重写优化是将一个查询转换为一个等价的查询；③要使用启发式方法选择查询转换方法，被选择的查询转换方法能改善大多数查询的执行性能；④查询重写的依据通常是查询本身获得信息、完整性约束或数据模式，而不考虑数据以及数据的存储方式和数据的统计信息。
3.1.1 根据结构约束删除冗余
最先研究路径表达式最小化问题是和，文献中只对不包括祖先后代边“//”的简单路径表达式进行最小化，而文献研究了不包含*的路径表达式的最小化问题。其基本思想是将查询中的路径表示为查询模式树，根据给定的结构约束，逐步查询模式树中冗余路径节点或冗余谓词。
文献对包含全部操作符{/,//[],*}的路径表达式的最小化进行了研究，算法的基本思想是递归地从原模式树中查找最小子模式并连接它们，证明了这是一个NP完全问题，同时，它还指出：在对路径表达式分支个数和形状加以一定限制的情况下。表达式最小化算法的复杂度可以达到多项式级。很显然，在实际查询中用户不可能将查询限制成一种特定形式的路径表达式。
3.1.2 删除路径表达式中的固有冗余
文献中提出了两种优化策略：缩短路径策略和补路径策略。缩短路径法是试图用等价相对路径取代绝对路径，缩短路径表达式本身，从而降低查询的代价。这种方法利用元素的唯一访问路径、唯一父元素、关键祖先等几个概念把绝对路径表达式转换为相对路径表达式，这样路径表达式的查询匹配就不再从根元素开始，从而缩短了路径表达式查询时间。如假定某查询的绝对路径表达式EIClE2C2E3…CnEn，如果UAP(E2)=C1E2，则可以用C2E3…CnEn代替EIClE2C2E3…CnEn。这里的关键问题确定唯一访问路径、唯一父元素和关键祖先。
（科教论文网 lw.NsEac.com编辑整理）
在补路径法中定义了互补路径，相对于某元素的互补路径是等价的，这样就可以用补路径替换原查询。其基本思想是把用户书写的复杂的、代价高的查询路径表达式用一些简单的、查询代价低的互补路径表达式来替代。这种策略的目的是减少连接次数和连接结果集的大小，因此怎样确定查询路径的互补路径并进行代价估算成为其关键问题。
3.1.3 删除非冗余的通配符步
当在某条路径中一个元素名未知或无关紧要时通常采用通配符。进行路径匹配时，通配符需要和当前节点的所有子节点(或后代节点)匹配，由此可见，通配符的计算代价相当高。文献中提出消除路径表达式中的非冗余的通配符步，从而降低路径表达式的计算代价。为了消除路径中的通配符步，引入一个layer∞ds重写有通配符的路径表达式查询，在形如child：：*/…/child*/ehild1：的查询中，layer axis可以用来替代所有路径通配步，从而把查询等价地表示为Li::t1。这样一方面缩短了路径表达式，另一方面使得系统仅仅加载与查询相关的XML数据，从而大大的优化了查询。
3.2 基于树遍历的路径查询优化
