基于XML文档中XPath查询与结构研究

本文是基于XML文档查询与结构的研究，分析了XPath的代数体系与表达能力，分析了XML文档节点的等价关系进行，建立查询语义结构特征与文档结构特征的相互关系，对给定文档中查询集的完备性进行分析，建立完备查询集的概念，生成了查询集。并且将等价概念推广到索引的结构划分，分析了若干索引与特定查询子集的可索引性。

【关键词】XPath 文档节点 完备性

随着XML技术研究与应用的深入，将会有大量XML文档不断涌现。来自数据结构和查询需求两方面的问题，导致基于关系和面向对象数据库的查询处理和优化技术均不能适应XML查询的需要，因此针对XML查询优化就显得十分必要。通常针对XML查询的研究不是针对完整XPath语言，而是针对XPath的某一部分的，因此本文的研究是基于XPath代数子集，研究特定子集在给定文档上的语义，进而分析其表达能力，建立查询语义结构特征与文档结构特征的相互关系，并对查询集在给定文档中的完备性进行分析，建立完备查询集的概念。

1 XPath的代数体系与表达能力

XPath的W3C标准是一个包含很多部分的复杂而庞大的语言体系。在研究XPath性质的时候，研究者会通过简洁的代数逻辑的抽象过程对该语言进行形式化的研究。作为最早的XPath子集，Core XPath能够描述大部分新的查询子集。

Core XPath所定义的表达式去除了XPath规范中与表达式表达能力无关的内容，将轴值关系作为表达式的核心构建表达式的结构描述。与XPath规范相比，其在结构描述上是完整的。因此，在之后的查询结构研究中所涉及的XPath子集都可以看作是Core XPath的结构意义上的子集。

2 文档节点等价关系

XPath/XQuery是针对XML文档的查询语言。在代数分析中XML文档通常会相应的进行简化，抽象出与查询代数相对应的结构特征，在两者之间建立映射关系作为查询研究的基础。

2.1 文档节点的结构等价关系

定义令y1和y2为文档x的节点，则y1和y2是正向结构相关（记为y1≥ y2））的，当且仅当：

・ λ（y1）=λ（y2）

・对每个y1的孩子节点n1，存在y2的孩子节点n2使得n1≥ n2。

正向的结构相关给出了文档从内部节点到叶节点方向的结构等价特征。对路径查询来说从根节点到目的节点的路径是导航查询最主要的查询途径。因此对从根到目标节点的路径进行正向结构相关在文档节点层次上的递归推广则得到：

如图1，d2和d1不是正向结构等价的。d2和d4是正向结构等价的，但不是结构等价的，d2和d3是结构等价的。

2.2 文档节点的表达式等价关系

XPath标准提供了丰富的操作符集与大量的功能函数。为问题表述清晰，我们将问题限定在XPath的特定子集。关注一种代数化的路径查询语言，记为Path+。Path+代数是众多代数体系中的一种，角标+表示该代数子集不包含集合补和集合差操作。

表达式与文档结构的关系：设y1，y2为文档x的节点，则y1exp y2，当且仅当y1 s y2。

3 查询完备性分析

首先讨论该查询集的存在性。这一过程需要首先确定查询子集。然后对该查询子集上的节点区分情况进行研究，利用节点区分情况对查询进行划分，最后说明查询集的存在性。

3.1 查询子集

Path+代数上查询，在其上建立了表达式等价与文档结构等价之间的关系。任意复杂的path+查询可以分解为利用两个自然连接相连的3个DPath+（π1）查询，同时满足表达式等价关系。

3.2 完备性分析

首先基于文档结构特征定义一个最小化的文档结构，该文档结构仅保留了文档的最简略的结构特征，但是同时文档结构需要能够保留原始文档的结构性质。

给定文档Y，定义文档结构Z为：以自上而下的方式检查文档Y，若存在节点m2使得m1 ≥S m2，则删除节点m1，最终得到文档结构Z。

若文档Y能够最小化为文档结构Z则称Y满足Z的完备查询集。

4 查询集生成

合并查询生成算法

生成过程主要分为三个部分，第一部分由文档结构生成核心集，然后将文档结构进行扩展，得到的扩展结构得到包含更多表达能力的其它非语义无关查询。最后将所的查询进行语义合并，最终得到相对文档完备的查询集。

5 结束语

要完整的分析研究查询处理过程，必须建立查询和数据（文档）之间的关系。本文研究了XML查询与XML数据之间的关系特征。首先介绍了现有的XML文档分析方法，对其适用领域进行了分析，其次从查询的表达能力的角度出发，将查询解析的研究方法应用到对文档的分析当中，建立特定查询子集与数据的结构关系，建立了查询语义结构特征与文档结构特征的相互关系，定义了文档节点的结构等价关系和表达式等价关系。然后给出了查询完备性的概念，对文档结构上的查询完备性进行了形式化分析。研究查询在与数据结构关联的条件下的完备性，研究基于数据的查询生成方法。接着给出了相关查询集的生成过程。最后将等价概念推广到索引的结构划分，并分析了若干索引与特定查询子集的可索引性。

作者单位

黄冈师范学院 湖北省黄冈市 438000