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值是元素开头和结尾的绝对物理或逻辑位移。如果一个节点的编码覆盖的区域完全包含在另一个节点的编码覆盖的区域中，则该节点是另一个节点的后代节点。为了确定多个文档查询和父子关系，元素的编码也可以扩展到(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　路径分解法

这种方法目前被广泛使用。其基本思路是将复杂的查询路径分解为简单路径。简单路径可以由一个元素、一个谓词条件或一个元素和一个谓词条件组成，也可以是由两个元素组成的路径。首先计算这些简单的路径表达式，然后连接每个简单路径表达式的计算结果。其本质决定了节点之间的结构关系（祖先、后代或父子关系），因此这种操作称为结构连接。与关系数据库中的连接操作一样，结构连接操作非常昂贵，结构连接是查询处理的核心操作。因此，在这种查询处理模式中，查询优化的关键是开发高效的结构连接算法，结构连接的顺序也极大地影响了结构连接操作的性能。