、高代价的查询路径表达式转换为简单的、低代价的等价路径表达式。查询重写技术的一般特征可以概括如下：①重写优化发生在查询解析之后查询计划生成之前；②重写优化是将一个查询转换为一个等价的查询；③要使用启发式方法选择查询转换方法，被选择的查询转换方法能改善大多数查询的执行性能；④查询重写的依据通常是查询本身获得信息、完整性约束或数据模式，而不考虑数据以及数据的存储方式和数据的统计信息。
3.1.1 根据结构约束删除冗余
最先研究路径表达式最小化问题是和，文献中只对不包括祖先后代边“//”的简单路径表达式进行最小化，而文献研究了不包含*的路径表达式的最小化问题。其基本思想是将查询中的路径表示为查询模式树，根据给定的结构约束，逐步查询模式树中冗余路径节点或冗余谓词。
文献对包含全部操作符{/,//[],*}的路径表达式的最小化进行了研究，算法的基本思想是递归地从原模式树中查找最小子模式并连接它们，证明了这是一个np完全问题，同时，它还指出：在对路径表达式分支个数和形状加以一定限制的情况下。表达式最小化算法的复杂度可以达到多项式级。很显然，在实际查询中用户不可能将查询限制成一种特定形式的路径表达式。

3.1.2 删除路径表达式中的固有冗余
文献中提出了两种优化策略：缩短路径策略和补路径策略。缩短路径法是试图用等价相对路径取代绝对路径，缩短路径表达式本身，从而降低查询的代价。这种方法利用元素的唯一访问路径、唯一父元素、关键祖先等几个概念把绝对路径表达式转换为相对路径表达式，这样路径表达式的查询匹配就不再从根元素开始，从而缩短了路径表达式查询时间。如假定某查询的绝对路径表达式eicle2c2e3…cnen，如果uap(e2)=c1e2，则可以用c2e3…cnen代替eicle2c2e3…cnen。这里的关键问题确定唯一访问路径、唯一父元素和关键祖先。
在补路径法中定义了互补路径，相对于某元素的互补路径是等价的，这样就可以用补路径替换原查询。其基本思想是把用户书写的复杂的、代价高的查询路径表达式用一些简单的、查询代价低的互补路径表达式来替代。这种策略的目的是减少连接次数和连接结果集的大小，因此怎样确定查询路径的互补路径并进行代价估算成为其关键问题。
3.1.3 删除非冗余的通配符步
当在某条路径中一个元素名未知或无关紧要时通常采用通配符。进行路径匹配时，通配符需要和当前节点的所有子节点(或后代节点)匹配，由此可见，通配符的计算代价相当高。文献中提出消除路径表达式中的非冗余的通配符步，从而降低路径表达式的计算代价。为了消除路径中的通配符步，引入一个layer∞ds重写有通配符的路径表达式查询，在形如child：：*/…/child*/ehild1：的查询中，layer axis可以用来替代所有路径通配步，从而把查询等价地表示为li::t1。这样一方面缩短了路径表达式，另一方面使得系统仅仅加载与查询相关的xml数据，从而大大的优化了查询。
3.2 基于树遍历的路径查询优化
基于树遍历的查询优化要使用路径索引缩小搜索范围，这种优化方法的关键问题是要设计出有效合理的便于维护的路径索引。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-

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