摘要：xml查询语言的共同特点是利用路径表达式来导航xml文档的查询并返回指定路径所能访问到的节点集，因此路径表达式的查询优化是xml数据库查询优化的关键，本文详细分析了当前路径表达式查询的几种优化技术，指出了它们要解决的关键问题和主要技术特点。

1 基本概念

1.1 xml数据模型和xml数据模式
一个xml文档树是一个有序标签树(如果考虑元素之间的应用关系则以xml文档的基本结构为图)，每个节点与一个元素或值(文本)相对应，边表示元素和子元素(或值)之间的嵌套关系。xml文档的数据模式是一个有向图，它为xml数据提供完整性约束。
1.2 xml数据的编码方法
到目前为止处理路径表达式查询有两种方法：一种是基于树遍历的方法，另一种不遍历文档树就可以快速决定节点之间结构关系的方法，元素之间结构关系的确定主要依赖于有效的xml节点编码方法。
1.2.1 基于区域的编码方案
目前，最常用的编码方法是区域编码方法，最先使用区域编码确定树节点之间的结构关系的是dietz。它给每个节点赋予一个(pre,post)编码，其中，pre是节点的前序遍历值，post是节点的后序遍历值，对于任意两个不同的节点x和y，x是y的一个祖先当且仅当x.pre 文献。给每个节点赋予一个(start,end)编码，一个节点的start和end值是该元素的开始和结尾的绝对物理或逻辑位移，如果一个节点的编码所覆盖的区域被另一个节点的编码所覆盖的区域完全包含，则这个节点是另一个节点的后代节点。LOcAlhOSt为适用于多个文档查询和父子关系的确定，还可以将元素的编码扩展为(d，cid,start,end,levd)，docid是文档的标识符，level是节点在文档树中的层数。文献提出一种类似于区域编码方案——扩展的前序和后代范围编码，其目是的为了支持数据的动态插入和删除，每个节点被赋予一个(order，size)，order是节点的前序遍历序号。size表示节点所覆盖的范围，它可以是任意一个大于该节点后代节点总数的整数值。
除了区域编码以外还有另外一种相对区域编码方，每个节点被赋予一个到其父节点的相对位移。这种编码可以转换成区域编码，其主要缺点是为了确定节点的绝对位置查询代价沿着查询路径从祖先节点到被查询节点逐步增加。
1.2.2 基于前缀的编码方法
不同于区域编码方法，基于前缀的编码方式保存路径信息。在这种编码方法中祖先后代关系和前缀子串的包含关系相对应。文献提出了k-ary编码，该方法通过增加虚节点把文档看成一个完全k分树，根据树的层次遍历顺序给树中的节点编码，在这种编码方法中节点的编码带有文档的结构信息。类似于k-ary编码，文献提出了一种特殊的pbitree编码，这种编码方案是通过增加虚拟节点将文档树嵌入到一个完全二叉树中。这种编码的优点是可以利用完全二叉树的优良特性来计算节点间的结构关系。pbitree中的虚拟节点起着—个占位符的作用，这样有利于数据的动态更新，同时它们对查询性能也有一定的影响。
1.3 xml数据索引
为了提高查询的性能，许多专家和学者都致力于索引的研究与开发。目前提出的索引有两种：一种是基于结构连接的索引；另一种是基于路径的索引。基于结构连接的索引m首先将文档树中的所有节点以的形式进行分解后存储在多张表中。这样，当处理查询//e1/e2/……/en时，对包含ei(i=-1，…，m)的表按次序要进行多次连接操作得到查询结果。基于路径的索引则是以文档树为基本数据结构，按照路径将树中的节点进行拆分、合并等操作，索引结构仍然是一个树，使用这种索引处理查询//el/e2/……/en时，基本上要遍历整个索引树才能得到结果。文献提出了一种自适应的路径索引结构，这种索引利用频繁使用的路径来改善查询性能，并且这种索引可以随着查询工作量的不同而动态改变，从而有效地缩小了索引文件。

2 路径表达式的查询处理方式

2.1 树遍历方法
最朴素的路径访问方法是树遍历的方法：一般采用自顶向下的方式遍历文档树，使用该方法进行查询时需要遍历某元素通往叶子节点的所有可能路径。为了减少树遍历的代价引入自底向上的方法，首先查找符合谓词条件的所有原子节点，然后再寻找它们的父节点。这种方法一般情况下比较简单、耗时较少。但对于符合谓词条件的节点数目很大而符合路径表达式的路径很少时，这种遍历方式的代价可能会高于自顶向下方式。一种折中的方法是同时按自顶向下和自底向上两种方法进行遍历，最后在路径的某个中间位置汇合，从而得到查询结果。当路径上某节点的扇人度(在文档中的)很大而符合谓词条件的原子节点很少时，该方法可以达到最优。在这种方法中优化路径表达式查询的一个中心思想是设法缩小查询范围。使得不需要遍历整个树就可以获得符合条件的查询结果。
2.2 路径分解法
这一种方法是目前用的比较多的，它的基本思路是将复杂的查询路径分解成简单路径，简单路径可以是由一个元素、一个谓词条件或一个元素加一个谓词条件，还可以是由两个元素组成的路径。首先计算这些简单路径表达式，再将每个简单路径表达式的计算结果连接起来。其本质确定节点间的结构关系(祖先后代或父子关系)，因此这种操作叫结构连接。像关系数据库中的连接运算一样，结构连接操作的代价非常昂贵，结构连接又是查询处理的核心操作，因此在这种查询处理模式中查询优化的关键开发高效的结构连接算法，同时结构连接的顺序也极大地影响着结构连接运算的性能。

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

3.1 路径表达式的重写优化
路径表达式重写优化的基本思想将复杂的

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