一种XML文档的流水线XPath查询方法、终端设备及存储介质

摘要

本发明涉及一种XML文档的流水线XPath查询方法、终端设备及存储介质，该方法中包括：S1：获取输入的XML文档；S2：获取输入的XPath查询表达式，并提取XPath查询表达式中包含的所有统计变量的类型；S3：对XML文档进行解析，以获取XML文档对应的节点的区间编码信息和关系索引，同时根据提取的统计变量的类型对XML文档中的各统计变量进行统计并计算XML统计信息；S4：根据获取的节点的区间编码信息、关系索引、XML统计信息以及XPath查询表达式，对XPath查询表达式包含的所有查询原语构建流水线；S5：分配线程至流水线的各流水阶段后执行流水线查询；S6：输出查询结果。本发明采用流水化的查询原语进行基于关系索引的查询步处理。

说明书

技术领域

本发明涉及XML文档查询领域，尤其涉及一种XML文档的流水线XPath查询方法、终端设备及存储介质。

背景技术

半结构化数据在Web应用和信息集成领域中十分常见。XML作为一种强大的半结构化数据描述工具，已成为数据存储和交换的标准被广为使用。XPath作为一种在XML数据中查找信息的专用语言，是XML数据处理的基础，其性能直接关系到XML应用的处理能力。近年来随着多核计算环境的普及，充分利用多线程并行计算资源以获取应用处理性能的提升已成为一种常用的优化设计途径。

从语义角度看，XPath求值就是根据节点关系条件定位XML树的节点的过程。XPath表达式中每个查询步获得前驱查询步的求值结果后，完成本步骤计算，再把结果传递给后继查询步，查询步之间的处理存在内在串行性，难以直接对XPath查询的整体进行并行化处理。另一方面，XPath查询过程具备数据流处理的基本特点，可适应流水化处理方式。然而各个查询步的计算结果大小往往难以预测，可能相差很大，查询步之间存在负载不平衡现象，容易造成处理性能下降。

发明内容

为了解决上述问题，本发明提出了一种XML文档的流水线XPath查询方法、终端设备及存储介质。

具体方案如下：

一种XML文档的流水线XPath查询方法，包括以下步骤：

S1：获取输入的XML文档；

S2：获取输入的XPath查询表达式，并提取XPath查询表达式中包含的所有统计变量的类型；

S3：对XML文档进行解析，以获取XML文档对应的节点的区间编码信息和关系索引，同时根据提取的统计变量的类型对XML文档中的各统计变量进行统计并计算XML统计信息；

S4：根据获取的节点的区间编码信息、关系索引、XML统计信息以及XPath查询表达式，对XPath查询表达式包含的所有查询原语构建流水线；

S5：分配线程至流水线的各流水阶段后执行流水线查询；

S6：输出查询结果。

进一步的，提取的统计变量的类型包括N

进一步的，节点的区间编码信息通过6元组表示，即设定节点u的区间编码ε

进一步的，XML统计信息包括包含均值和过滤率，计算公式分别为：

V

P

其中，包含均值V

进一步的，步骤S4中流水线的创建过程包括以下步骤：

S101：根据XPath查询表达式抽取所有查询原语组成原语序列；

S102：对原语序列中的每个原语进行代价估算以获得对应的代价，配置线程数，设定代价累计值为0；

S103：根据每个原语的代价计算XPath查询表达式中所有原语的总代价和流水阶段的平均代价；

S104：判断原语序列中的原语的个数是否多于线程数，如果是，进入S105；否则，进入S109；

S105：判断原语序列中是否还有原语未处理，如果是，进入S106；否则，进入S111；

S106：从原语序列内提取一个原语，并将其代价累加至代价累计值后，将其从原语序列内剪切至临时原语序列内；

S107：判断代价累计值是否超过流水阶段的平均代价，如果是，进入S108；否则，返回S105；

S108：根据临时原语序列创建一个新流水阶段，设定代价累计值为0，同时清空临时原语序列，返回S105；

S109：判断原语序列中是否还有原语未处理，如果是，进入S110；否则，进入S111；

S110：从原语序列内提取一个原语创建一个流水阶段，返回S109；

S111：调整各邻接的流水阶段的连接关系。

进一步的，查询原语的工作流程包括以下步骤：

S201：从输入单元数据中获得当前待处理节点u；

S202：判断是否存在未处理的节点u的包含节点，如果是，进入S203；否则，结束；

S203：判断节点u的包含节点是否满足原语的查询条件，如果是，进入S204，否则，返回S202；

S204：判断节点u的包含节点是否有后继原语，如果是，进入S205；否则，输出结果值到全局结果集，返回S202；

S205：更新输入的单元数据的历史域；

S206：根据结果值和更新后的历史域创建输出单元数据；

S207：将输出单元数据放入后继原语的阻塞队列，返回S202。

进一步的，查询原语进行代价估算的方法为：

针对类型为非谓词查询原语的查询原语，其代价估算计算公式为：

针对类型为谓词查询原语的查询原语，其代价估算计算公式为：

其中，M

进一步的，步骤S111中各邻接的流水阶段的连接关系通过阻塞队列进行调整。

一种XML文档的流水线XPath查询终端设备，包括处理器、存储器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现本发明实施例上述的方法的步骤。

一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现本发明实施例上述的方法的步骤。

本发明采用如上技术方案，采用流水化的查询原语进行基于关系索引的查询步处理。在流水线构建过程中，引入了一种基于XML统计信息的代价估算模型，以适应流水化处理过程的代价估算，为查询原语序列的划分和流水阶段创建提供指导。在充分利用多核计算环境中可用工作线程的同时，优化了流水阶段间的负载均衡。

附图说明

图1所示为本发明实施例一的流程图。

图2所示为该实施例中输入XML文档示意图。

图3所示为该实施例中流水线创建流程图。

图4所示为该实施例中查询原语工作流程图。

图5所示为该实施例中XPath查询原语原始结构图。

图6所示为该实施例中按照线程数2划分的XPath查询原语结构图。

图7所示为该实施例中按照线程数4划分的XPath查询原语结构图。

具体实施方式

为进一步说明各实施例，本发明提供有附图。这些附图为本发明揭露内容的一部分，其主要用以说明实施例，并可配合说明书的相关描述来解释实施例的运作原理。配合参考这些内容，本领域普通技术人员应能理解其他可能的实施方式以及本发明的优点。

现结合附图和具体实施方式对本发明进一步说明。

实施例一：

本发明实施例提供了一种XML文档的流水线XPath查询方法，如图1所示，所述方法包括以下步骤：

S1：获取输入的XML文档。

该实施例中，假设输入的XML文档如图2所示。

S2：获取输入的XPath查询表达式，并提取XPath查询表达式中包含的所有统计变量的类型。

该实施例中，假设输入的XPath查询表达式为“//S[./VBP]//PP/VP”，其中，//S表示求标签名为S的节点的子孙，/VP表示求标签名为VP的节点的孩子，[./VBP]表示谓词。

对获取的XPath查询表达式进行分析，根据XPath查询表达式中涉及的标签名及节点关系，提取出所需的统计变量。一般需要提取的统计变量的类型包括N

(1)N

(2)N

(3)N

具体的，该实施例中对于获取的XPath查询表达式，需要提取的N

S3：对XML文档进行解析，以获取XML文档对应的节点的区间编码信息和关系索引，同时根据提取的统计变量的类型对XML文档中的各统计变量进行统计并计算XML统计信息。

(1)XML节点的区间编码信息

对XML文档的解析后将获得XML节点的区间编码信息。区间编码可用6元组表示。如节点u的区间编码ε

表1

(2)XML文档的关系索引

关系索引是记录XML节点之间的有效关系的存储结构，用元组表示形式如

表2

(3)XML统计信息

该实施例中XML统计信息包括均值和过滤率，其中：

包含均值用V

过滤率用P

对于步骤S2中获取的XPath查询表达式，需要计算的过滤率有P

步骤S3的具体实现代码如下：

Preprocess

输入:XML文档数据

输出:XML节点区间编码信息ε，索引信息

在上述具体实现代码中，第1行代码对输入的XPath查询表达式进行分析，获取需要进行统计的信息，包括标签字符串集合A.τ1,A.τ1*和A.τ2、关系条件字符串集合A.τ1θτ2。第4～22行在对XML文档进行解析处理过程中，当遇到XML节点头标签时，创建一个新XML节点项；当遇到XML节点尾标签时，除了更新XML节点项的文档结束位置信息以外(第9行)，主要工作是进行统计变量计数和索引项创建。其中第7行和第9行进行XML解析获得当前节点的区间编码；第10～16行进行统计值累计；第17～20行对当前节点和以当前节点为根节点的子树所包含的节点进行关系计算，以创建当前节点的索引项。第23行进行XML统计信息的计算，即计算所需要的包含均值和过滤率。

S4：根据获取的节点的区间编码信息、关系索引、XML统计信息以及XPath查询表达式，对XPath查询表达式包含的所有查询原语构建流水线，通过构建的流水线对各查询原语进行查询。

如图3所示，该实施例中流水线的创建过程包括以下步骤：

S101：根据XPath查询表达式抽取所有查询原语组成原语序列；

S102：对原语序列中的每个原语进行代价估算以获得对应的代价，配置线程数，设定代价累计值为0；

S103：根据每个原语的代价计算XPath查询表达式中所有原语的总代价和流水阶段的平均代价；

S104：判断原语序列中的原语的个数是否多于线程数，如果是，进入S105；否则，进入S109；

S105：判断原语序列中是否还有原语未处理，如果是，进入S106；否则，进入S111；

S106：从原语序列内提取一个原语，并将其代价累加至代价累计值后，将其从原语序列内剪切至临时原语序列内；

S107：判断代价累计值是否超过流水阶段的平均代价，如果是，进入S108；否则，返回S105；

S108：根据临时原语序列创建一个新流水阶段，设定代价累计值为0，同时清空临时原语序列，返回S105；

S109：判断原语序列中是否还有原语未处理，如果是，进入S110；否则，进入S111；

S110：从原语序列内提取一个原语创建一个流水阶段，返回S109；

S111：调整各邻接的流水阶段的连接关系。

下面对上述各步骤的具体实现进行说明。

(1)查询原语

查询原语包含非过滤型原语和过滤型原语这两类原语。非过滤型原语为对应XPath查询表达式的一般轴操作的实现，如求取子孙的原语GetDescendant，求取孩子的原语GetChild等。过滤型原语为对应XPath查询表达式的谓词操作的实现，包括基本过滤原语FilterInput1byInput2，以及过滤型原语的变体，如带AND条件过滤原语、带OR条件过滤原语、带NOT条件过滤原语等。

该实施例中采用符号M

对于步骤S2获取的XPath查询表达式，获取的所有查询原语分别为：

M

M

M

M

M

具体的，如图4所示，各种查询原语有相似的实现方式，查询原语的工作流程包括以下步骤：

S201：从输入单元数据中获得当前待处理节点u；

S202：判断是否存在未处理的节点u的包含节点，如果是，进入S203；否则，结束；

S203：判断节点u的包含节点是否满足原语的查询条件，如果是，进入S204，否则，返回S202；

S204：判断节点u的包含节点是否有后继原语，如果是，进入S205；否则，输出结果值到全局结果集，返回S202；

S205：更新输入的单元数据的历史域；

S206：根据结果值和更新后的历史域创建输出单元数据；

S207：将输出单元数据放入后继原语的阻塞队列，返回S202。

下面以GetDescendant原语进行示例说明，GetDescendant原语的算法如下：

GetDescendant(

输入：

输出：无。局部计算结果在以下算法中处理：或者入队或者输出到全局结果集ε

单元数据是指流水化处理过程中传递的数据参数，用

(2)代价估算

该实施例中用

对于步骤S2获取的XPath查询表达式对应的原语代价估算过程如表3所示。

表3

(3)各邻接的流水阶段的连接关系的调整

该实施例中的流水阶段是一个可执行的功能整体，内部包含一个或多个查询原语，通过阻塞队列进行流水阶段内部和流水阶段外部的通信。流水阶段在形式上是对查询原语进行包装处理，以便于分配线程运行。当包含有两个以上查询原语时，流水阶段内部以流水方式组织各个查询原语，便于以一致的方式进行流水化处理。为了避免频繁的线程切换，每个流水阶段需要分配一个工作线程。流水阶段的工作过程描述如下算法：

PipeStage(primitiveName[],tagName[],i[],j[],

输入：primitiveName[],tagName[],i[],j[],

输出：无返回。局部计算结果在算法中处理：进入下个流水阶段里的队列或者输出到全局结果集ε

在上述具体实现代码中，首先根据查询原语个数s，创建s-1个局部阻塞队列(第1,2行)，每个原语内含有一个阻塞队列。对于首个流水阶段里的首个原语含有的阻塞队列为空。接下来定义执行体，其内部以嵌套迭代的方式处理查询原语的调用(第4～15行)。在阶段内处理首个原语时，如果检测到结束标志，则把结束信息继续往下个流水阶段传递后，立即退出执行体的迭代操作(第6～8行)；在处理其它原语时，先检测上级原语是否有计算结果产出，若没有则退出本原语的迭代处理(第11行)，否则获取上级原语的计算结果的一个项作为输入单元数据，再利用PipedPrimitive函数进行查询原语的调用(第9,13行)。

PipedPrimitive函数提供了对各种查询原语的调用接口，例如：PipedPrimitive(GetDescendant,

进一步的，在构造流水线时，为了获得更好性能，考虑到两个原则：一是充分利用可得工作线程；二是尽可能保持流水阶段负载均衡，避免阶段之间的过多同步等待。基于上述的原则，采用的线程分配策略为：当查询步数少于线程数，则每个查询步作为一个流水阶段，分配一个线程执行。当查询步数多于线程数时，需要通过合理的划分，合并代价小的查询步，以便每个阶段都可获得一个工作线程，其作用在于，一方面可以避免一个线程因执行多个阶段引起上下文切换开销，另一方面可使得各阶段的负载较为均衡，避免阶段之间过多的等待。

查询步数多于线程数的情形，划分算法转换为规划的求值问题，如式(1)所示。其中，T表示可用线程数，也就是划分的阶段数，C

假设查询原语按查询步求值顺序进行编号，即有编号p∈[0,P-1]，划分的方法就是对此序列按编号顺序分为T组，第s组中，若查询原语编号s∈

[s1,s2],0≤s1≤s2≤P-1。划分结果使得各流水阶段的代价方差最小化。即满足式(1)。

步骤S4的创建流水线的总体算法框架如下：

CreatePipeline(Ep,S,T)

输入:XPath查询表达式Ep，XML统计信息S,可用工作线程数T。

输出:以流水阶段序列表示的流水线L

在上述具体实现代码中，先根据XPath查询表达式抽取查询原语序列(第1行)，再根据代价估算规则求取原语序列M

对于步骤S2获取的XPath表达式，图5显示了未划分的流水线结构。如果按可用线程数为2进行划分，图6是获得的一种可能结果。如果按可用线程数为4进行划分，图7是获得的一种可能结果。

对应图6的流水线包含2个流水阶段，描述如下：

λ1←PipeStage({GetDescendant,GetChild},tagName{PP,VP},i{0,0},j{0,0},

λ0←PipeStage({GetDescendant,GetChild,FilterInput1byInput2},tagName{S,VBP,

对应图7的流水线包含4个流水阶段，描述如下：

λ3←PipeStage({GetChild},tagName{VP},i{0},j{0},

λ2←PipeStage({GetDescendant},tagName{PP},i{0},j{0},λ3.

λ1←PipeStage({GetChild,FilterInput1byInput2},tagName{VBP,

λ0←PipeStage({GetDescendant},tagName{S},i{0},j{0},λ1.

S5：分配线程至流水线的各流水阶段后执行流水线查询。

具体的，由于流水阶段PipeStage是可执行的对象，从线程池分配线程运行各个流水阶段。用XML根节点信息设置单元数据的初始值，再通过设置单元数据

S6：输出查询结果。

本发明实施例一采用流水化的查询原语进行基于关系索引的查询步处理。在流水线构建过程中，引入了一种基于XML统计信息的代价估算模型，以适应流水化处理过程的代价估算，为查询原语序列的划分和流水阶段创建提供指导。在充分利用多核计算环境中可用工作线程的同时，优化了流水阶段间的负载均衡。

实施例二：

本发明还提供一种XML文档的流水线XPath查询终端设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现本发明实施例一的上述方法实施例中的步骤。

进一步地，作为一个可执行方案，所述XML文档的流水线XPath查询终端设备可以是桌上型计算机、笔记本、掌上电脑及云端服务器等计算设备。所述XML文档的流水线XPath查询终端设备可包括，但不仅限于，处理器、存储器。本领域技术人员可以理解，上述XML文档的流水线XPath查询终端设备的组成结构仅仅是XML文档的流水线XPath查询终端设备的示例，并不构成对XML文档的流水线XPath查询终端设备的限定，可以包括比上述更多或更少的部件，或者组合某些部件，或者不同的部件，例如所述XML文档的流水线XPath查询终端设备还可以包括输入输出设备、网络接入设备、总线等，本发明实施例对此不做限定。

进一步地，作为一个可执行方案，所称处理器可以是中央处理单元(CentralProcessing Unit，CPU)，还可以是其他通用处理器、数字信号处理器(Digital SignalProcessor，DSP)、专用集成电路(Application Specific Integrated Circuit，ASIC)、现场可编程门阵列(Field-Programmable Gate Array，FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等，所述处理器是所述XML文档的流水线XPath查询终端设备的控制中心，利用各种接口和线路连接整个XML文档的流水线XPath查询终端设备的各个部分。

所述存储器可用于存储所述计算机程序和/或模块，所述处理器通过运行或执行存储在所述存储器内的计算机程序和/或模块，以及调用存储在存储器内的数据，实现所述XML文档的流水线XPath查询终端设备的各种功能。所述存储器可主要包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需的应用程序；存储数据区可存储根据手机的使用所创建的数据等。此外，存储器可以包括高速随机存取存储器，还可以包括非易失性存储器，例如硬盘、内存、插接式硬盘，智能存储卡(Smart Media Card,SMC)，安全数字(Secure Digital,SD)卡，闪存卡(Flash Card)、至少一个磁盘存储器件、闪存器件、或其他易失性固态存储器件。

本发明还提供一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现本发明实施例上述方法的步骤。

所述XML文档的流水线XPath查询终端设备集成的模块/单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明实现上述实施例方法中的全部或部分流程，也可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一计算机可读存储介质中，该计算机程序在被处理器执行时，可实现上述各个方法实施例的步骤。其中，所述计算机程序包括计算机程序代码，所述计算机程序代码可以为源代码形式、对象代码形式、可执行文件或某些中间形式等。所述计算机可读介质可以包括：能够携带所述计算机程序代码的任何实体或装置、记录介质、U盘、移动硬盘、磁碟、光盘、计算机存储器、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)以及软件分发介质等。

尽管结合优选实施方案具体展示和介绍了本发明，但所属领域的技术人员应该明白，在不脱离所附权利要求书所限定的本发明的精神和范围内，在形式上和细节上可以对本发明做出各种变化，均为本发明的保护范围。