基于XPath的XML查询优化

摘要：随着XML作为Internet上数据表示和交换的标准，如何高效地进行XML数据的查询己经变得越来越重要，许多XML查询语言也随之出现。这些查询语言虽然种类繁多，但都有个共同特征：使用基于XPath数据模型下规则路径表示来查询XML数据。研究表明，当前的关系数据库技术在处理规则路径表示的查询时通常效率不高。

文章在介绍了传统的基于遍历树的方法的基础上重点讨论了基于路径分解的查询处理算法，并对选择连接顺序算法提出了基于动态规划思想的改进。

关键词：XPath；XML；查询优化；动态规划

中图分类号：TP311文献标识码：A 文章编号：1009-3044(2008)28-0020-04

XML Query Optimization Based on XPath

XU Yi

(School of Software Engineering,Tongji University,Shanghai 201804,China)

Abstract: With the advent of XML as a standard for data representation and exchange on the Internet, querying XML data becomes more and more important. Several XML query Language have been proposed, and the common feature of the languages is the use of regular path expression based on XPath Data Model to query XML data. Research shows that the current relational database technology often inefficient when deal with the regular path expression.

This paper first introduce the traditional traversing tree algorithm, and then discuss the query parse algorithm which based on regular path expression, and optimize the structural join order by dynamic programming.

Key words: XPath; XML; query optimization; dynamic programming

1 引言

XML是由W3C开发的，主要目的是为了克服HTML缺乏结构和元数据信息的缺点，为Web信息的集成、交换建立一种新的灵活的机制。

它在以下几个领域正改变着Web：

1) 简化了数据交换。使用XML，每个实体可以创建单一的实用程序，该实用程序将该实体的内部数据格式转换成XML，反之亦然。

2) XML支持智能代码。因为可以使XML文档结构化以标识每个非常重要的信息片段以及这些片段之间的关系，所以可以编写无需人工干预就能处理这些XML文档的代码。

3)XML支持智能搜索。尽管搜索引擎这些年在稳步改进，但从搜索中得到错误的结果仍很常见。搜索 XML文档会给一个好得多的结果集。

随着XML数据的增多，如何对其进行高效的查询时非常重要的，本文从XML的基本概念入手，着重对当前XML数据查询的处理方法进行分析研究，并加以改进和优化，来进一步提高查询处理效率。

2 XPath

谈及XML数据查询，就不得不谈到XPath。作为XML数据查询语言的核心部分，XPath用来对XML文档的内容进行定位、检索。XQuery和XPath公用的数据模型提供了XML文档的树形表示―节点树。节点有七类，包括根节点、元素节点、属性节点、文本节点、命名空间节点、处理指令节点、注释节点。XPath的最主要构件路径表达式就是通过这样的节点树来跟踪路径，识别出所有被路径表达式检索的节点。下面给出的是一个简单的定位表达式：

/pub/book/author

定位路径有两种，分别是相对定位路径和绝对定位路径。每个定位路径表达式都由一个或者多个定位步组成，每个定位步之间用正斜杠分开。绝对路径以正斜杠开始，它从文档的根节点开始定位路径；而相对路径则直接从某个定位步开始定位路径。

XPath中用上下文节点集来描述定位路径的求值过程是如何进行的。上下文节点集定义为：表达式中给定集确定的当前节点集。上下文定义为：正在处理的当前节点。

定位路径表达式是求值过程是由定位步骤决定。定位步骤按顺序(从左到右)一次一个地求值。每一个定位步骤都是对照上下文节点集中的节点进行求值的。第一个定位步骤是把上下文节点集中的每个节点当作上下文节点进行求值。 然后结果节点集被合并为新的节点集，这个节点集成为下一步操作的上下文节点集。这样的处理在路径的每一个定位步骤中持续进行。最后的定位步骤产生的节点集就是这个表达式的结果。

定位步包含三部分：

一个轴，它指定了定位步选择节点与上下文节点之间的树状关系。XPath定义了13个轴。每个轴都有个方向，向前或者向后。

一个节点测试，它指定了定位步选择的节点类型或者节点名。如果给定点的节点测试为真，则它保留在结果节点集中，否则将它从结果节点集中删除。

零个或多个谓词，它使用专有的谓词表达式来进一步筛选定位步选择的节点集合。

3 XML数据查询处理方法

利用路径表达式导航XML查询是XML查询语言的共同特点.目前对XML路径表达式的计算有两种方法:一种是基于树遍历的方法,另外一种是路径连接方法。

3.1 基于遍历树的方法

基于遍历树的方法有两种次序：top-down和bottom-up。下面以查询表达式Q1:/city/school/class/student[@name=”Tom”]为例来说明。按top-down的次序来处理时，要顺着所有开始于city节点的路径，去查找是否有school的节点作为后代，这一步要对XML数据库中的所有的city节点来执行， 这就意味着在XML树中要遍历从city节点到叶节点的每一条可能的路径，如果city节点是根节点，那么整棵XML树都必须被遍历。按bottom-up的次序来遍历可以降低遍历的成本,对于同样的查询Q1来讲，所有带有属性name值为”Tom”的student节点都要被搜索，从每一个这样的student节点开始向上遍历来确定是否存在class节点，然后再从每一个这样的class节点向上遍历来确定是否存在school节点作为祖先， 依次类推… 这种向上遍历的方法在一般情况下较简单、耗时较小，但对于符合条件的student节点数目很大，而class节点、school节点或city节点数目较小的情况，这种遍历方式的成本可能会高于top-down方式。

一种折衷的处理方法是同时按照top-down 和bottom-up的次序进行遍历，最终会在路径的某个中间位置相遇，从而得出查询结果。这种方法结合了top-down和bottom-up的优点，但它的高效性并不总能得到保证，下面改进的方法中采用了路径分解和连接算法来处理，避免了多次遍历树。

3.2 基于路径分解的查询处理算法

Quanzhongli和Bongki Moon将规则路径查询表达式分解为以下五种基本表达式的组合。

1) 只由单一元素或单一属性组成的表达式,如author、@year;

2) 由一个元素和一个属性组成的表达式，如book[@year=2007];

3) 由两个元素组成的的表达式，如chapter//title、book/@isbn;book[descendant::section]、book[chapter];

4) 一个子表达式的kleene闭包

5) 两个子表达式的并集

对第1种情况可利用元素或属性的索引直接得到结果，对第2、3、4种情况需分别需要采用EA-Join、EE-Join和KC-Join三个算法来进行中间结果的连接合并；第5 种情况可通过组合两个中间结果或直接按文件分组来处理。

三个算法如下：

1) EA-Join算法 ( 用于元素集合和属性集合的合并，对应于由一个元素和一个属性组成的子表达式) :

输入:{E1,…,Em}, Ei表示拥有相同文件标示符(did)的元素集

{A1,…,An}, Aj表示拥有相同文件标示符(did)的元素集

输出:元素为(e,a)的集合，要求满足a是e的属性

//据文件标示符来分类合并集合{Ei} 和{Aj}

l :for each Ei and Aj with the same did do

//据孩子父母关系分类合并Ei和Aj

2 : for each e∈Ei and a∈Aj do

3 : if(e is a parent of a) then output(e,a)

end

end

2) EE-Join算法 ( 用于元素集合和属性集合的合并，对应于由一个元素和一个属性组成的子表达式)：

输入:{E1,…,Em}和{F1,…,Fn}, Ei和Fj表示拥有相同文件标示符(did)的元素集

输出:元素为(e,f)的集合，要求满足e是f的属性

//据文件标示符来分类合并集合{Ei} 和{Fj}

l :for each Ei and Fj with the same did do

//据孩子父母关系分类合并Ei和Fj

2 : for each e∈Ei and f∈Fj do

3 : if(e is an ancestor of f) then output(e,f)

end

end

3) kleene closure算法 ( 对应于求一个子表达式的kleene闭包) :

输入:{E1,…,Em}, Ei表示一个XML文档的一组元素

输出: {E1,…,Em}的kleene闭包

//重复执行EE-Join算法

1:set i=1

2:set Kci ={E1,…,Em};

3:repeat

4:set I =i+1

5:set Kci=EE-Join(Kci-1, Kc1)

until (Kci is empty)

6:output union of Kc1 ,Kc2, ……, Kci-1;

4 XML数据查询处理优化

路径分解算法（见3.2节）在合并中间结果集时，由于各个集合中元素的个数不同，在采用不同的连接合并的次序的情况下，执行的开销有很大不同。如果能够选择恰当的结构连接顺序，将使原算法得到进一步的优化。因此如何应用动态规划算法，使得在尽量小的搜寻空间里找到最好的方案是本节的主题。

4.1 动态规划的基本思想

动态规划算法的基本思路是用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中，在需要时再找出，这样就可避免大量的重复计算。

动态规划算法通常用于求解具有某种最优性质的问题。这类问题中，可能会有许多可行解，每个解都对应一个值，我们希望找到最优值 ( 最大值或最小值)的那个解。设计一个动态规划算法，通常可按以下几个步骤进行:

1) 找出最优解的性质，并刻画其结构特征。

2) 递归地定义最优值。

3) 以自底向上的方式计算出最优值。

4) 根据计算最优值时得到的信息，构造一个最优解。

用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。

4.2 动态规划算法的设计

一个XPath语句通常被建模成为一个树，这种查询也被称为树模式查询。一个查询的求解过程为：从初始查询数开始，每次处理树中的一条边，即将相连的两个节点进行连接，连接的结果用一个新的节点表示，并替代原树中的2个节点。每次连接的时候都会减少一个节点，产生一个新的树。当最后的树只包含一个节点的时候，整个求解过程便告结束。图1给出了一个查询树求解的例子。

■

图1 使用动态规划时的查询树求解图

查询数的求解图实际上是一个有向无环图。图中所有类似于AB的聚集点成为状态节点，每个查询数称为一个状态，从一个查询树变换到另一个查询树的过程称为移动。从初始状态开始经过k步移动后到达的状态被称为k层状态。只有当第k层所有状态产生后才能移动到第k+1层。因而查询树的求解过程就是从初始状态出发，经过n次移动到达结束状态的过程，n为初始查询树中边的数目。在这n次移动过程中经过的路径就给出了连接的计划即连接的顺序。比如：S00-S10-S24-S31表示连接的顺序为：先连接节点A和B，在将中间结果和D连接，最后与C连接。现在的问题是，要选择一条路径，使得按照该顺序连接的总体代价最小。

如果将每一步的连接代价作为状态树每个边的权，则这个问题上实际就是经典的求最小路径问题。把最短路径问题的动态规划算法应用到这里，就变成了连接顺序求解的动态规划策略。其过程为：从初始状态出发，每次进行一步移动。移动到第k层时，可能得到多个状态，而且每个状态又可能从多个路径转换而来。这些路径的代价不一样，只保留其中代价最小的那条路径。然后从第k层状态出发，移动到下一层，并按同样的方法选择最佳路径。这样到最后得到的路径便是最短路径，也是最优的连接顺序。

DijkstraShortestPathes算法:

输入:具有非负权值的简单无向加权图G，以及G的一个特殊顶点v：

输出:对于G中每个顶点u,输出标记D[u],满足D[u]是G中从v到u的距离

//初始化

1:set D[v]=0;

2:for G中每个顶点u ≠ v do

set D[u]=+ ∞;

//设优先队列Q包含G中所有的顶点，利用D标记作为关键字

3:while Q 非空 do

//把一个新顶点u从Q中加入到初始化为空集的集合C中

set u = Q.removeMin();

for u 的每个邻接顶点Z且Z在Q中 do

//对边(u,z)进行松弛过程

if D[u] + w(u,z) < D[z] then

set D[z] = D[u] + w(u,z);

改变Q中顶点Z的关键字

算法运行时间分析：

反复向Q中插入带有初始关键字的所有顶点，所需时间为O（nlogn），如果利用自底向上的构造堆，则所需时间为O(n)在while循环中，从顶点Q中删除顶点u所需时间为O（nlogn）,对于依附于顶点u的边，执行松弛过程的时间为O(dev(v)logn)总时间为Σv∈G（1+dev（v））logn即：总运行时间为O（（n+m）logn）

4.3 几种查询处理算法的比较

基于遍历树的处理方法比较直观，但祖先后代关系的判断需要多次对树进行遍历，特别对查询路径较长的情况将耗费较多时间，效率不高。路径分解法处理时将长的查询表达式分成五种基本子表达式，处理完每个子表达式后，再将中间结果集合按照具体算法进行合并，得出原查询表达式的结果，此方法节省了时间，提高了效率。在此基础上，动态规划算法对此路径分解法进一步优化，在进行合并中间结果集前先确定出合并的最优次序，减少了计算量，提高了效率。

5 小结

随着XML作为Internet上数据表示和交换的标准，如何高效地进行XML数据的查询己经变得越来越重要，本文对规则路径表示下XML数据的查询处理算法进行了分析研究，其中重点讨论了基于XPath的查询表达式的分解、中间结果集的合并算法等，主要工作如下:基于动态规划的思想，设计出具体算法，在进行中间结果集合并之前，先求出合并的最优次序，大大降低了合并结果集的计算量，提高了查询处理效率，实现了对路径分解算法的进一步优化。

事实上，对于一个复杂的查询来说，上述算法的搜索空间依然很大，还有进一步优化的空间，这也是后续的研究方向。

参考文献：

[1] Li Q,Moon B.Indexing and Querying XML Data for Regular Path Expression[A].In: Apers PMG et al Eds. Proceedings of the 27th VLDB International Conference on Very Large Database.[C] Rome, Italy. September 11-14,2001.San Francisco: Morgan Publishers,2001:361-370.

[2] Wu Y,Patel J M,Jagadish H V.Structural Join Order Selection for XML Query Optimization[A].In: Casati F et al Eds. Proceedings of the 19th IEEE ICDE International Conference on Data Engineering.[C] Bangalore, India. March 5-8, 2003. Los Alamitos: IEEE Computer Society,2003:443-454.

[3] World Wide Web Consortium. XML Path Language(XPath) Version 1.0. [S].W3C Recommendation.16 November,1999.