路径表达查询优化的一般方法

1.路径表达式重写优化

路径表达式重写优化的基本思想将复杂、高成本的查询路径表达式转化为简单、低成本的等价路径表达式。查询重写技术的一般特点可总结如下：①查询解析后查询计划生成前发生重写优化；②重写优化是将查询转换为等价查询；③采用启发式方法选择查询转换方法，选定的查询转换方法可提高大多数查询的执行性能；④查询重写通常是基于查询本身获取的信息、完整性约束或数据模式，而不考虑数据和数据的存储模式和统计数据。

1.1　根据结构约束删除冗余冗余

第一个研究路径表达式的最小化问题是和谐，文献只包括祖先和后代的边缘“//”最小化简单的路径表达式，献研究不包括*路径表达式的最小化。其基本思想是将查询中的路径表示为查询模式树，并根据给定的结构约束逐步查询模式树中的冗余路径节点或冗余谓词。

对包含所有操作符的文献，*}研究了路径表达式的最小化。算法的基本思想是从原模式树中逐步找到最小子模式并将其连接起来，证明这是一个NP同时，它还指出，在一定程度上限制了路径表达式分支的数量和形状。表达式最小化算法的复杂性可以达到多项式级别。显然，用户不可能将查询限制特定形式的路径表达式。

1.2　删除路径表达式中的固有冗余

文献提出了两种优化策略：缩短路径策略和补充路径策略。缩短路径法是试图用等价相对路径代替绝对路径，缩短路径表达式本身，从而降低查询成本。该方法利用元素的唯一访问路径、唯一父元素、关键祖先等概念，将绝对路径表达式转换为相对路径表达式，使路径表达式的查询匹配不再从根元素开始，从而缩短了路径表达式的查询时间。假设查询的绝对路径表达式EIClE2C2E3…CnEn，如果UAP(E2)=C1E2，则可以用C2E3…CnEn代替EIClE2C2E3…CnEn。这里的关键问题决定了唯一的访问路径、唯一的父元素和关键的祖先。

互补路径法定义了互补路径，相对于某一元素的互补路径是等价的，因此可以用互补路径代替原始查询。其基本思想是用一些简单、低成本的互补路径表达式代替用户写的复杂、昂贵的查询路径表达式。该策略的目的是减少连接次数和连接结果集的大小，因此如何确定查询路径的互补路径并估算成本成为关键问题。

1.3　删除非冗余的通配符步

当某条路径中的元素名称未知或不重要时，通常使用通配符。在路径匹配过程中，通配符需要与当前节点的所有子节点（或后代节点）进行匹配，这表明通配符的计算成本相当高。文献提出消除路径表达式中的非冗余通配符步，以降低路径表达式的计算成本。为了消除路径中的通配符步，引入了一个layer∞ds重写带通配符的路径表达式查询，在形式上形成child：：*/…/child*/ehild1:在查询中，layeraxis可用于替代所有路径的通配步，从而将查询等价地表示为Li::t1.一方面缩短了路径表达式，另一方面使系统只加载与查询相关的内容XML数据，从而大大优化了查询。

2.基于树木遍历的路径查询优化

基于树遍历的查询优化应使用路径索引来缩小搜索范围。这种优化方法的关键问题是设计有效、合理、易于维护的路径索引。DataGuides它是最早的路径索引，也是路径索引中最具影响力的代表。它采用标签路径合并策略来减少文档结构，DmGuides每个节点都有一个目标集。该目标集记录了通过该标签路径可访问的数据节点，因此只需要执行路径查询Dataguides查找路径，获得的目标集是符合条件的查询结果。当文档的数据结构比较规则时，Dataguides可以很好地减少文档结构，从而大大提高查询性能。

文献中提出了一种使用图模式(GraphSchemas)缩小查询范围的方法。这里的图形模式也起到了作用。DataGuides它的作用，但它采用了合并类似边缘的策略。图形模式中的节点称为状态，每个状态对应一个状态扩展，即文档中相应的节点集。在此基础上，文档提出了两种查询优化策略：剪切查询和使用状态扩展集重写查询。剪切查询是将查询的搜索限制在仅与查询结果相关的子树上，后者将原始查询改写为图形模式上的查询。这两种方法都使用非确定自动机作为剪切工具。

与上述两种方法不同，文献提出了一种新的路径查询方法，该方法将XML文档中的文本数据被提取并单独存储，因此文档树只由带标签的元素或属性组成种结构被称为文档的骨架(skeleton)。为了使大文档的骨架尽可能地放入内存中。树骨架通过共享的公共子树进一步压缩，压缩树骨架的每个节点对应于一组未压缩树的节点，它们之间的对应关系表示为双向相似关系。