xml路径表达式的查询优化技术

《xml路径表达式的查询优化技术》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、XML路径表达式的查询优化技术摘要：xml查询语言的共同特点是利用路径表达式来导航xml文档的查询并返回指定路径所能访问到的节点集，因此路径表达式的查询优化是xml数据库查询优化的关键，本文详细分析了当前路径表达式查询的几种优化技术，指出了它们要解决的关键问题和主要技术特点。1基本概念1.1xml数据模型和xml数据模式一个xml文档树是一个有序标签树(如果考虑元素之间的应用关系则以xml文档的基本结构为图)，每个节点与一个元素或值(文本)相对应，边表示元素和子元素(或值)之间的嵌套关系。xml文档的数据模式是一个有向图，它为xml数据提

2、供完整性约束。1.2xml数据的编码方法到目前为止处理路径表达式查询有两种方法：一种是基于树遍历的方法，另一种不遍历文档树就可以快速决定节点之间结构关系的方法，元素之间结构关系的确定主要依赖于有效的xml节点编码方法。1.2.1基于区域的编码方案目前，最常用的编码方法是区域编码方法，最先使用区域编码确定树节点之间的结构关系的是dietz。它给每个节点赋予一个(pre,post)编码，其中，pre是节点的前序遍历值，post是节点的后序遍历值，对于任意两个不同的节点x和y，x是y的一个祖先当且仅当x.pre的形式进行分解后存储在多张表中。这

3、样，当处理查询//e1/e2/……/en时，对包含ei(i=-1，…，m)的表按次序要进行多次连接操作得到查询结果。基于路径的索引则是以文档树为基本数据结构，按照路径将树中的节点进行拆分、合并等操作，索引结构仍然是一个树，使用这种索引处理查询//el/e2/……/en时，基本上要遍历整个索引树才能得到结果。文献提出了一种自适应的路径索引结构，这种索引利用频繁使用的路径来改善查询性能，并且这种索引可以随着查询工作量的不同而动态改变，从而有效地缩小了索引文件。2路径表达式的查询处理方式2.1树遍历方法最朴素的路径访问方法是树遍历的方法：一般采

4、用自顶向下的方式遍历文档树，使用该方法进行查询时需要遍历某元素通往叶子节点的所有可能路径。为了减少树遍历的代价引入自底向上的方法，首先查找符合谓词条件的所有原子节点，然后再寻找它们的父节点。这种方法一般情况下比较简单、耗时较少。但对于符合谓词条件的节点数目很大而符合路径表达式的路径很少时，这种遍历方式的代价可能会高于自顶向下方式。一种折中的方法是同时按自顶向下和自底向上两种方法进行遍历，最后在路径的某个中间位置汇合，从而得到查询结果。当路径上某节点的扇人度(在文档中的)很大而符合谓词条件的原子节点很少时，该方法可以达到最优。在这种方法中优

5、化路径表达式查询的一个中心思想是设法缩小查询范围。使得不需要遍历整个树就可以获得符合条件的查询结果。2.2路径分解法这一种方法是目前用的比较多的，它的基本思路是将复杂的查询路径分解成简单路径，简单路径可以是由一个元素、一个谓词条件或一个元素加一个谓词条件，还可以是由两个元素组成的路径。首先计算这些简单路径表达式，再将每个简单路径表达式的计算结果连接起来。其本质确定节点间的结构关系(祖先后代或父子关系)，因此这种操作叫结构连接。像关系数据库中的连接运算一样，结构连接操作的代价非常昂贵，结构连接又是查询处理的核心操作，因此在这种查询处理模式中

6、查询优化的关键开发高效的结构连接算法，同时结构连接的顺序也极大地影响着结构连接运算的性能。3路径表达查询优化的一般方法3.1路径表达式的重写优化路径表达式重写优化的基本思想将复杂的、高代价的查询路径表达式转换为简单的、低代价的等价路径表达式。查询重写技术的一般特征可以概括如下：①重写优化发生在查询解析之后查询计划生成之前；②重写优化是将一个查询转换为一个等价的查询；③要使用启发式方法选择查询转换方法，被选择的查询转换方法能改善大多数查询的执行性能；④查询重写的依据通常是查询本身获得信息、完整性约束或数据模式，而不考虑数据以及数据的存储方式

7、和数据的统计信息。3.1.1根据结构约束删除冗余最先研究路径表达式最小化问题是和，文献中只对不包括祖先后代边“//”的简单路径表达式进行最小化，而文献研究了不包含*的路径表达式的最小化问题。其基本思想是将查询中的路径表示为查询模式树，根据给定的结构约束，逐步查询模式树中冗余路径节点或冗余谓词。文献对包含全部操作符{/,//[],*}的路径表达式的最小化进行了研究，算法的基本思想是递归地从原模式树中查找最小子模式并连接它们，证明了这是一个np完全问题，同时，它还指出：在对路径表达式分支个数和形状加以一定限制的情况下。表达式最小化算法的复杂度

8、可以达到多项式级。很显然，在实际查询中用户不可能将查询限制成一种特定形式的路径表达式。3.1.2删除路径表达式中的固有冗余文献中提出了两种优化策略：缩短路径策略和补路径策略。缩短路径法是试图用