基于索引框架的XPath求值算法

2021-04-20李柳青

电子技术与软件工程 2021年3期

李柳青

（中征（北京）征信有限责任公司天津分公司天津市 300072）

当今时代是数据爆炸时代，各类格式化，非格式化爆炸激增，大数据分析已然成为当前主要研究课题。格式化数据结构清晰，可利用成熟的结构化数据库存储，非格式化数据格式多样，内容多样，XML 的出现正是为了表述此类数据[3]。因此，XML 文件成为目前主流的非格式数据存储方案。为分析此类大量存在的非格式化数据，对XML 文件的查询解析成为重中之重。

当前主流的XML 查询语言中[1]，XPath 和XQuery 是W3C 的推荐标准。这两种语法语言均利用路径表达式定位节点信息。表达式既包括标明上下级的结构约束，又包括语义表达的谓词约束。现有研究方法多数都聚焦在结构约束的解析，并通过提出结构关系连接算法提升查询效率。但这种方法基于XML 存储是用各类标签组合的倒序表的假设，没有考虑到原生XML 数据库的其他更高效的索引。倒序排列表提供的有限功能限制了XML 查询的效率。

基于上述描述，本文提出使用原生XML 数据库的索引框架进行XPath 求值的算法。本算法将查询语法树转换为查询优化树，将路径切割，然后对其做整体小枝连接，以期提升路径表示式的求值效率。图1 阐述了本算法的实现过程。

1 生成优化树算法

查询优化树运用了 XML 数据库提供的结构索引、值索引和全文索引，将原有查询树中满足特定条件的节点进行整合，最终生成查询优化树。构建查询优化树，既可降低次数，又统一了结构约束和谓词约束的处理方式，对执行器屏蔽了上次语法的差异，方便执行器以统一的方式处理语法树。

对查询树进行优化的步骤如下：

（1）利用结构索引，将PC 子路径的节点整合；

（2）优化比较运算符，充分运用值索引及全文索引优势；

查询优化树就是在原始查询树中找出一系列PC 子路径，并将子路径上的节点整合。找到的子路径可以使用结构索引将多个查询节点的连接操作转换为一次索引操作，大幅提升查询效率。

步骤1 是在生成查询树过程中，使用堆栈按DFS 遍历原始查询树，生成PC 子路径。伪码如下：

01：S:暂存查询树节点的栈结构；

02：L:暂存查询优化树节点的列表；

03：q:=Q 的根节点；

04：push(S,q)；

05：while (not empty(S)) do

06：node:=top(S)/* node 为栈顶节点*/

07：child:=firstChild(node)；/* child 是 node 的首个孩子节点*/

08：if(child!=null) ,then push(S,child)；

09：else 调用mergePCSubpath(S,L)处理叶子节点；

12：if (| (children(node) )|>1 ) then mergePCSubpath(S,L)/*处理分枝节点 */

13：pop(S)；

14：if (empty(S)) then break；/*处理完毕，跳出循环 */

15：node:=top(S)；

17：if (sibling ≠null) then push(S,sibling)；

18：return L[0]；/* L[0]是查询优化树 R1的根节点 */

function mergePCSubpath(S,L)/* 合并 PC 子路径上的查询节点*/

19：for (each node in S) do/* 按照从栈顶到栈底的顺序访问*/

20：if (|children (node)| >1 and isAD) then add(L,n)；return；

21：subpath:=subpath + lab(node) + "."；

22：if (type(＜parent(node),node>)=AD) then

23：isAD:=true；

24：subpath:=subpath + "*"；

25：n:=makeNode(n,m,subpath,S,L)；

26：m:=n；

27：subpath:=ε；

28：else isAD:=false；

29：n:=makeNode(n,m,subpath,S,L)；/*在 R1 中新建节点并添加相应的边*/

30：add(L,n)；

算法依据DFS 遍历原生查询树Q，若到了叶子节点，调用合并PC 子路径算法，从叶子逆向向上，将所有节点压入堆栈，直到遇到当前节点的父节点为分支节点，且为AD 边是停止处理；每个叶子处理完成后，会再将节点从堆栈中弹出，指挥刀弹出的节点有有兄弟节点为止。最终生成PC 子路径。

例如，对于图2(a)所示的查询树，调用算法1 后，得到的查询优化树 R1如图 2(b)所示。

步骤2 算法核心思想是对步骤1 生成的查询优化树，遍历每个叶子及叶子的祖先节点，构造正则表达式，直到某个节点不以通配符结尾。将值索引及全文索引存储在配置文件中。通过遍历文件，查找与正则表达式最匹配的索引，若找到，就新建查询树中节点，将之索引与相应节点的右兄弟进行比较运算，将结果存储在查询树中。用运算结果替换步骤1 生成的查询树，移除该节点与最近的分直接点间的所有节点，形成最终的优化树。

本算法的时间复杂度为O(|VQ|)，由查询树Q 生成查询优化树R 的总体时间复杂度为O(|VQ|)。

2 实验结果

实验旨在比对本算法与文献[5]提出的基于TwigStack 的XPath求值方法的查询性能。实验机器配置如下：CPU 为E7-8837，内存为32GB，硬盘为128GB，操作系统为 Windows XP。本实验的测试数据由XMark 工具生成，大小从10MB 递增至100MB，增量为10MB。图3 给出了两种方法的执行时间，从图中看出，本算法的效率远高于基于TwigStack 的算法。本算法以PC 子路径作为查询的最小单元，而基于TwigStack 的算法是以节点为单位查倒序表。本算法可以过滤掉了与查询语句无关的节点信息，但基于TwigStack 的算法要遍历所有节点，系统花销必然更大。