一种基于索引的XPath查询模式树匹配方法

摘要

本发明公开了一种基于索引的XPath查询模式树匹配方法，包括：对XML数据库中的文档集合建立索引；解析XPath查询语句，并构建查询语句对应的查询模式树；将查询模式树拆分成若干个子查询，并通过索引获取子查询结果；恢复子查询获取的结果节点流数据，并对节点流数据进行模式树匹配。本发明基于索引结合数据恢复的方法，优化了模式树匹配要处理的数据规模，减少了I/O开销，提高了匹配性能，此外，本发明提出了配合位置索引进行模式树匹配的方法，有效地解决了位置查询的问题。

说明书

技术领域

本发明涉及数据库查询领域，尤其涉及一种在XML数据库中基 于索引的XPath查询模式树匹配方法。

背景技术

随着信息技术的迅猛发展，XML已经逐渐成为数据表达和数据 交换的标准和载体，在电子商务，网络服务和数字图书馆等诸多重要 领域都得到了大规模的应用。对日益增长的海量XML数据进行高性 能查询处理也成为了一个重要的问题。

XPath是一种对XML文件中的节点进行定位的查询语言，它之 于XML数据库的关系就相当于SQL之于关系数据库。XPath的核心 语法表示形式是路径表达式，一个路径表达式是从XML文件中的一 个节点到另一个节点或一个节点集合的一组步骤，这些步骤以“/” 字符分隔，每个步骤包括三个构成组件：轴（axis），它用于以最直 接的方式，依靠节点间的结构关系（例如祖先，后代），从上下文节 点定位到下一节点集合；节点测试（nodetest），它依据节点名称，节 点类型或处理指令类型，对轴定位的节点集进行筛选；一个或多个谓 词（predicate）的语法形式为：[表达式]，用于对节点测试筛选后的 节点集进一步过滤，根据表达式筛除掉一些不符合表达式要求的节 点。

一个XPath查询语句通常可建模为一棵树状结构的查询模式树。 XML数据库查询的核心操作就是根据查询模式树所表示的结构和内 容特征，在XML数据空间中进行搜索，提取与之相匹配的数据。

目前查询模式树匹配的主流方案可分为以下三类：

第一类方法基于导航的思想，通过在XML文档中导航来匹配查 询模式，缺点是处理大文档时效率很低，并且只适用于线性模式查询， 不适用于带分支的树模式查询。

第二类方法基于整体匹配的思想，将XML数据的文档树和查询 模式树映射成特定的序列，然后基于序列进行匹配，通常做法是映射 到字符串序列，这种方法虽然简洁，但也有其缺陷，对字符串的大量 连接和匹配操作，使得性能开销加大，对数据的大量扫描也增加了I/O 的负担。

第三类方法基于先分解再连接的思想，将查询模式分解成若干个 片段，分别求出每个片段的查询结果然后进行合并，这类方法的缺陷 在于分解粒度过细，导致连接和中间结果的数目太多。

此外，现有方案的主要关注点是结构和内容的模式匹配。而在实 际应用中，用户不仅关注XML文档的结构和内容信息，也关注XML 文档节点的位置信息，例如，用户可能想查询文档集合中所有论文的 名为“张三”的第一作者，对应的XPath语句为//paper/author[1][.=’ 张三’]。对于此类位置查询，或位置与内容相结合的查询，现有的模 式匹配方法做的尝试较少，解决方法也不够高效。

发明内容

为解决上述中存在的问题与缺陷，本发明提供了一种基于索引 的XPath查询模式树匹配方法。所述技术方案如下：

一种基于索引的XPath查询模式树匹配方法，包括：

对XML数据库中的文档集合建立索引；

解析XPath查询语句，并构建查询语句对应的查询模式树；

将查询模式树拆分成若干个子查询，并通过索引获取子查询结 果；

恢复子查询获取的结果节点流数据，并对节点流数据进行模式树 匹配。

本发明提供的技术方案的有益效果是：

1、有效支持多类型查询的索引方法，尤其是支持位置查询的索 引方法。该方法在索引方面提供了位置索引和值索引，在一定范围 内解决了位置查询及位置和内容相结合的查询问题；在索引数据内 容组织方面，以XML文档的结构信息作为索引的数据项，有利于结 构模式匹配和数据恢复，以B树为数据组织形式，为高效处理海量 数据的查询提供了可靠支持。

2、以路径为粒度进行子查询分解，减少了中间结果的数目。

3、基于索引查询得到的路径末端节点数据流，文档树的叶子节 点向文档树的根节点方向恢复，其索引查询只需返回路径的末端模 式节点对应的数据节点，优化了模式树匹配处理的数据集规模，减 少了I/O开销，提高了查询性能。

附图说明

图1是基于索引的XPath查询模式树匹配方法流程图；

图2是恢复节点流数据及对节点流数据进行模式树匹配的流程 图；

图3是基于索引的XPath查询模式树查询示例图；

图4是索引数据组织示例图；

图5是数据结构示例图。

具体实施方式

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

本实施例提供了一种基于索引的XPath查询模式树匹配方法，如 图1所示，该方法包括：

步骤10对XML数据库中的文档集合建立索引；

根据用户的需求，对XML数据库中的某个XML文档集合，建立 用户指定类型的索引，将建立成功的索引存储到外存物理设备中。所 述索引包括值索引、路径索引和位置索引，具体包括：

建立文档集合的文档数据中的所有模式路径对应的路径索引，其 中每条模式路径对应一个简单路径表达式，将索引数据存储到外存物 理设备；

优选地，根据指定的简单路径表达式和值的类型，为对应的路径 建立相应的值索引，辅助实现值查询功能；

优选地，根据用户指定的简单路径表达式，为对应的路径建立位 置索引，辅助实现位置查询功能；

上述值索引、路径索引和位置索引存储的数据以节点为粒度，存 储的是与简单路径表达式相匹配的数据中，与路径末端模式节点相匹 配的数据节点信息。

索引包括值索引、路径索引、位置索引，其中值索引的类型又分 为字符串索引、整数索引、浮点数索引、日期索引、日期-时间表索 引，以满足用户的精确查询需求。

索引的数据组织形式基于B树，它是一种高性能的外存树状数据 结构，具有平衡，树层数较少等优点，适用于大规模数据的磁盘存储 和查找。针对不同类型的索引，B树存储的数据项和数据项键值也有 所不同。值索引存储的数据项以节点文本值为键，数据项内容为<节 点文本值，节点的树结构编码，节点的路径结构编码>；位置索引存 储的数据项以位置为键，数据项内容为<位置，节点的树结构编码， 节点的路径结构编码>；节点测试索引存储的数据项以节点的路径结 构编码为键，数据项内容为<节点的路径结构编码，节点的树结构编 码>。节点的树结构编码反映的是它在文档树中的整体位置，节点的 路径结构编码反映的是它属于文档树中的哪一条路径模式。例如图4 就是图3文档对应的路径索引的数据组织图。

步骤20解析XPath查询语句，并构建查询语句对应的查询模式 树；

将用户输入的XPath查询语句进行解析，在内存中构建查询语句 对应的查询模式树。

对用户输入的XPath查询语句，进行词法解析，语法解析和静态 类型检查，构建该语句对应的抽象语法树；基于该抽象语法树进行优 化，构建查询模式树，模式树中的模式节点包括三类：查询节点、谓 词节点和逻辑运算符节点；查询节点用于表示XPath中每步的节点测 试，谓词节点表示值查询约束或者位置范围约束，逻辑运算符节点表 示逻辑运算符AND和OR。

如图3中的XPath查询语句//a[.//b]//c[1][.>4and.<8]被建模为图3 中的模式树，三类模式节点用三类不同的图形组件表示，圆形节点表 示的是查询节点，方形节点表示的是谓词节点，例如图中的c就有三 个子孙谓词节点，表示c需要满足位置为1，值大于4，且值小于8这三 个条件。菱形节点表示的是逻辑运算符节点，例如图中的c的两个值 约束谓词的父节点为AND，表示c需要同时满足这两个条件。

步骤30将查询模式树拆分成若干个子查询，并通过索引获取子 查询结果；

将查询模式树进行优化，拆分成若干个子查询，分析子查询的查 询类型，使用对应类型的索引获取子查询结果。从查询模式树的根节 点开始，按先序对树进行递归周游，将查询树分解成一个或多个XPath 路径查询单元，寻找路径查询单元的策略是：如果访问到一个叶子节 点，则找到了从查询模式树的根节点到叶子节点的一条路径，该路径 对应着一个XPath路径查询单元。图3中的查询语句可以分解为三个 XPath路径查询单元，如下表所示：

表1

路径查询单元编号 简单路径表达式 谓词 1 //a//b 无 2 //a//c 位置谓词，pos=1 3 //a//c 两个值比较谓词,value>4,value<8

分解成查询单元后，索引模块会对每个路径查询单元分析查询类 型，并使相应类型的索引进行查询。例如，上述三个查询单元分别使 用路径索引、位置索引和整数类型的值索引查询。

步骤40恢复子查询获取的结果节点流数据，并对节点流数据进 行模式树匹配。

该步骤用到的数据结构包括模式树对应的模式节点线性表，构造 中间结果时的堆栈和线性表。例如，图3中的模式树对应的模式节点 线性表有三个节点，如图5所示，每个模式节点的区间编码Region记 录它在模式树中的后代范围，Name记录节点名称，Axis记录节点轴； 数据中间栈用于自底向上地构建中间结果，从索引得到的叶子节点流 进行数据恢复后，恢复的节点按照先序入栈，以后序弹出。例如，图 5中的数据中间栈里已有两个节点进栈，分别对应着图3中数据树的根 节点，和根节点的第一个子节点，每个数据节点保存着该节点的内容 信息，结构信息，以及匹配模式需要的信息，其中deweyId表示树结 构编码，pathId表示路径结构编码，dsMap记录节点后代在中间结果 线性表中的结果区间开始和结束位置，path表示这个节点是由哪一条 路径查询单元得到的节点恢复得到的；中间结果线性表记录每个模式 节点对应的匹配的数据节点列表，例如，图5中模式节点a对应的中间 结果线性表有两个满足的数据节点，第一个数据节点的模式为b的后 代数据节点的结果范围为模式节点b对应的线性表的第1个元素到第4 个元素，以先序排列。

上述简单路径表达式（Simple Path Expression）：是一种形式简 洁的XPath查询语句。它的语法组件包括一个或多个步（Step），每 个步由轴(axis)和节点名称测试(nametest)组成，语法形式为：

SimplePath::=Step|Step/SimplePath|step//SimplePath

Step::=nametest|nametest

简单路径表达式没有谓词（predicate）,例如，/child::A是一个简 单路径表达式，但/child::A[B]不是简单路径表达式。

如果把XML文档建模成一棵文档节点树，简单路径表达式可以 用来表示从文档节点树的根节点到某个子节点的有向直线路径，该路 径没有分叉，每个节点和后续节点的对应关系都是唯一的。因此，简 单路径表达式很适合用于路径结构查询，定位满足特定路径结构的节 点。

XPath路径查询单元（XPath Path Query Unit）：用于表示本发明 将用户的XPath查询语句解析成查询模式树后，拆分得到的原子路径 查询单元，也就是交由索引应答的最小查询对象。

它的语法组件为一个简单路径表达式，零个或多个值比较谓词， 和零个或一个位置范围谓词。值比较谓词和位置范围谓词的作用是对 由简单路径表达式筛选得到的节点集合，再次进行基于值比较或位置 范围的过滤。

例如，//a//c[1]为一个XPath路径查询单元，由简单路径表达式//a//c 和位置谓词[1]组成；//b//d[.=’14’]也为一个XPath路径查询单元，由简 单路径表达式//b//d和值比较谓词[.=’14’]组成。

该查询单元不仅能支持结构查询，也有效地支持了值查询和位置 范围查询。

如图2所示，上述步骤40具体包括：

步骤401，先序历遍模式树，将模式树映射到一个模式节点线性 表，并对每个模式节点进行区间编码，记录每个模式节点包含的结构 信息和位置信息。

步骤402，对每个子查询得到的数据节点流进行排序，该排序基 于数据节点的树结构编码，按先序排列，例如，图3中的树结构编码 为”1”的节点排列在树结构编码为“1.1.1”的节点之前。

步骤403，取当前数据流中按先序第一个节点，记为LeafNode， 根据该节点判断当前堆栈是否有与模式树局部子树片段相匹配的数 据节点，并将该数据节点弹出堆栈放入对应的线性表。如果数据流的 节点已取完，跳至步骤406。

步骤404基于LeafNode自底向上地恢复数据，所谓自底向上的 “底”指的是叶子节点，也就是说从文档树的叶子节点往文档树的根 节点方向，在内存中重构节点。

步骤405，从恢复栈中依次取出恢复的数据节点，根据节点对应 的模式节点，和中间结果线性表，标记它在模式树中的后代在中间结 果线性表中对应的结果区间的开始位置，然后放入数据中间栈中，并 返回步骤403。

步骤406，处理完从索引得到的所有的数据流后，从模式节点线 性表的第一个模式节点，也就是模式树的根节点开始，递归地自顶向 下枚举最终结果，历遍当前模式节点对应的线性表的结果区间内的可 选节点，并更新每个可选节点在模式树上的所有模式节点后代的数据 节点结果区间，直到匹配完模式节点线性表的每个模式节点为止。如 果模式节点线性表的每个节点都能枚举到对应的数据节点，说明在数 据中存在着匹配整个模式树的一组数据节点，匹配成功。例如，图3 中的示例，匹配成功的节点组包括：<1,1.1.1,1.2.3>,<1,1.2.1, 1.2.3>,<1,1.2.1.1,1.2.3>,<1,1.2.2,1.2.3>,<1,1.1.1,1.3>,<1,1.2.1, 1.3>,<1,1.2.1.1,1.3>,<1,1.2.2,1.3>,<1.2,1.2.1,1.2.3>,<1.2,1.2.1.1, 1.2.3>,<1.2,1.2.2,1.2.3>。

上述步骤403具体包括如下：

步骤403a取所有XPath路径查询单元得到的数据流中当前按先 序第一个节点，例如路径查询单元1的当前第一个数据节点编码为 1.1.1，路径查询单元2的当前第一个数据节点编码为1.2.3，路径查询 单元3的当前第一个节点的编码为1.2.3。则按编码先序，取1.1.1对应 的数据节点。如果同一个编码的节点位于不同的两个流中，则进行消 重。

如，对应于图3的例子，步骤403a取的LeafNode的deweyId为 1.2.1，需要恢复该节点到deweyId为1的节点之间与模式树的模式节点 相匹配的数据节点，根据以上方法，编码为1.2的节点将被恢复。

步骤403b判断堆栈的当前栈顶数据节点是否是LeafNode在文档 树中的祖先，如果是的话则结束步骤403，如果不是的话则执行操作 403c。

例如，当前栈顶数据节点的编码为1.1，LeafNode的编码为1.2.1， 两个编码不为前缀关系，此时栈顶数据节点不是LeafNode的祖先。

步骤403c判断该栈顶节点是否能弹出放入它的模式对应的中间 结果线性表。首先更新栈顶数据节点的所有模式树后代对应的中间结 果线性表中的结束位置，例如，编码为1.1的节点弹出时，它在模式 表中的后代分别为b和c，b对应的中间结果列表的结果区间为[1,1]， 但c对应的中间结果列表无结果，则说明该节点没有模式为c的后代， 此时节点与模式树不匹配，弹出栈，但不放入模式对应的中间结果线 性表。

步骤403d如果栈不为空，则跳至操作403a继续循环，否则结束 步骤403。

上述步骤404具体包括如下：

步骤404a确定恢复数据的区间，如果当前堆栈不为空，并且当 前LeafNode的path和栈顶节点的path非同一条，则恢复区间为 [LeafNode,栈底节点]，否则恢复区间为[LeafNode,栈顶节点]；如果当 前堆栈为空，则恢复区间为[LeafNode,文档树根节点]。

步骤404b根据恢复区间的起始和结束节点的树结构编码，计算 这两个节点之间在文档树上相隔的偏移量；然后自底向上地根据叶子 节点的pathId，deweyId，以及到该层的偏移量，重构该层祖先节点， 并判断该祖先节点的模式是否属于模式树，如果属于则说明该节点为 需要恢复的节点，保留到恢复节点数据栈中。

上述实施例基于索引结合数据恢复的方法，优化了模式树匹配要 处理的数据规模，减少了I/O开销，提高了匹配性能，此外，本发明 提出了配合位置索引进行模式树匹配的方法，有效地解决了位置查询 的问题。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在 本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均 应包含在本发明的保护范围之内。