一种基于索引的XML文档查询优化方法

摘要

本发明公开了一种基于索引的XML文档查询优化方法，所述方法包括：构建XPath查询所需路径的索引；将XPath表示为树形的查询形式；对树形表示的查询中的任意节点，根据索引获取相应文档标识集合，通过集合运算对文档是否匹配XPath进行筛选本发明通过利用简单的集合运算，借助索引的优势，避免了不必要的数据访问和操作，以及复杂的数据结构的构造与销毁，从而使基于XPath匹配的筛选在实际性能上得到大大提升，增强了其可用性。

说明书

技术领域

本发明涉及面向XML文档数据的查询优化方法，尤其涉及一种基于索 引的XML文档查询优化方法。

背景技术

XML是一种应用广泛的数据表示与传输标准，随着越来越多的基于XML 的文档出现，对XML文档数据进行管理成为一种迫切的需求。近年来，原生 XML数据库技术得到快速发展，针对XML数据模型特点研发了新型的存储、 索引、查询等技术。

XPath是一种标准的XML查询语言，是XQuery的子集，是操作XML 文档的核心，经常用于从XML文档中定位数据片段，测试XML文档是否满 足需求等。XPath的实现技术得到了广泛关注，典型的实现技术包括基于自 动机的方法、基于Twig的整体匹配方法等。然而，在数据库的背景下，当数 据量变得越来越大时，现有技术方法对于高效的XPath查询应答具有一定的 局限性，一方面由于数据本身的复杂性，XML数据是一种层次嵌套的结构， 并不是平面化的数据模型，另外XPath还需要考虑文档序；另一方面是因为 查询算法的复杂性，通常需要构建复杂的数据结构，进行代价高昂的迭代和 排序操作。

索引是一种特殊的数据结构，对管理的数据进行特殊编排，以实现快速 访问所需要数据的目标。专利申请号为“CN103177120A”的专利描述了一种 基于索引的XPath查询模式树匹配方法，将XPath查询转换为模式树匹配问 题，再通过访问所涉及的模式树节点的索引数据，利用整体匹配的Twig算法， 完成XPath的求值，该方法在一定程度上解决了XPath查询海量数据的问题， 但当数据规模持续增长，算法本身的开销越来越大，使得该方法的可用性下 降。

发明内容

为解决上述技术问题，本发明的目的是提供一种基于索引的XML文档 查询优化方法，该方法针对应用XPath对文档进行匹配过滤的场景(典型的 应用包括信息检索、SQL/XML中的XMLExists等)，提取了一个XPath子集， 通过改进的索引结构，可以通过简单的集合运算实现对XPsth筛选的应答， 既提升了查询性能，又提高了索引的空间性能。

本发明的目的通过以下的技术方案来实现：

一种基于索引的XML文档查询优化方法，该方法包括：

构建XPath查询所需路径的索引；

将XPath表示为树形的查询形式；

对树形表示的查询中的任意节点，根据索引获取相应文档标识集合，通 过集合运算对文档是否匹配XPath进行筛选。

与现有技术相比，本发明的一个或多个实施例可以具有如下优点：

本发明通过利用简单的集合运算，借助索引的优势，避免了不必要的数 据访问和操作，以及复杂的数据结构的构造与销毁，从而使基于XPath匹配 的筛选在实际性能上得到大大提升，增强了其可用性。

附图说明

图1是基于索引的XML文档查询优化方法流程图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合实施例及附图 对本发明作进一步详细的描述。

如图1所示，为基于索引的XML文档查询优化方法，该方法包括以下步 骤：

步骤10构建XPath查询所需路径的索引；

对于任意符合上文语法要求的XPath查询，将XPath表示为树结构，其 中谓词和逻辑连接符会引入分支。针对这样的一种树形表示的查询，对于从 根到任意叶节点的路径，都需要在与之对应的路径上创建索引，其中索引的 键为对应的数据内容，索引的值为对应的文档标识。

步骤20将XPath表示为树形的查询形式；

对XPath进行解析，经词法、语法分析，构成语法树，即树形表示的XPath 查询。

步骤30对树形表示的查询中的任意节点，根据索引获取相应文档标识集 合，通过集合运算，对文档是否匹配XPath进行筛选。

对树形表示的查询的中间节点，“or”操作按集合交运算处理，其他按 集合并处理。对树形表示的查询进行自底向上的求值，当计算完根节点后， 便得到了最终匹配的文档标识集合，即对应满足XPath的文档集合。

上述实施例适用的XPath语句是XPath的一个真子集，涵盖了常用的 XPath表达式及功能，具体语法形式如下：

<OPath>::＝<RootFork>？<NonForkPath>

<RootFork>::＝/<RootElemName><PosPred>？<LPred>*

<RootElemName>::＝nameTest|*

<PosPred>::＝[num]|[<PosFun><Cmp>num]

<PosFun>::＝position()

<LPred>::＝<Pred><LogicCom><LPred>|not(<LPred>)

<NonForkPath>::＝//<relPath>|/<relPath>

<relPath>::＝<simplePath>|<simplePath><PosPred>|<simplePath><Pred>

<simplePath>::＝<step>|<simplePath>/<step>|<simplePath>//<step>

<step>::＝nametTest|@nameTest|*|.

<Pred>::＝[<simplePath>]|[<PathPred>]

<PathPred>::＝<simplePath><Cmp>value

<Cmp>::＝<|<＝|＝|>＝|>|！＝

<LogicCom>::＝and|or

num整数值

value类型值

nameTest QName类型名称

直观上，本发明所支持的XPath真子集对应于一种只在根的位置进行分 叉的查询，其思想是确保不同简单路径相交处在文档中是唯一的，从而可以 通过整个文档标识的交集替换复杂的结构连接。原则上，只要能确保查询的 中间节点在文档中的唯一性，便可放宽语法限制，采用本方法进行处理。因 此，在模式可知的情况下，本实施例有进一步改进的空间。

虽然本发明所揭露的实施方式如上，但所述的内容只是为了便于理解本 发明而采用的实施方式，并非用以限定本发明。任何本发明所属技术领域内 的技术人员，在不脱离本发明所揭露的精神和范围的前提下，可以在实施的 形式上及细节上作任何的修改与变化，但本发明的专利保护范围，仍须以所 附的权利要求书所界定的范围为准。