一种基于查询工作量估算的XML分片方法

摘要

一种基于查询工作量估算的XML分片方法：(1)采用区间编码Zhang编码规则对XML树中每个结点进行编码；(2)为每个结点生成相关的XPath查询步，加入XPath队列中；(3)对XML文档树从根结点开始，采用深度优先遍历的顺序，递归的对每个结点进行查询工作量估算；(4)根据查询工作量估算结果将XML文档树划分为查询工作量约为W0的子树；(5)将分片后的XML片段以查询工作量估算值进行排序，以“回形”的方式分配给各个处理节点。本发明仅用XML文档结构进行查询工作量估算，不需知道用户查询，并以查询工作量估算值作为XML存储度量，达到了更好的查询负载均衡和扩展性支持。

说明书

技术领域

本发明涉及一种针对海量XML的分布式存储与并行查询的高效XML分片方 法，尤其涉及一种在未知用户查询的前提下根据XML自身结构进行查询工作量 估算从而达到更好的查询负载均衡的分片方法。

背景技术

eXtensible Markup Language(XML)作为可扩展标记语言，具有扩展性、 自描述性、自相容性等优点，已成为Internet上数据表示、存储和交换的标 准。于是海量XML数据的生成使XML的有效存储管理成为新的问题。并行XML 处理是一种有效解决方案，而数据分片是影响并行系统整体性能的最关键因 素。

查询负载均衡是影响并行查询效率的重要因素，在之前的XML分片方法研 究中，如XGP、WIN方法已经考虑到了负载均衡，但是需要根据用户查询来进 行分片，在最常用的应用场景下，在XML存储时用户查询是未知的。再者，一 些XML分片方法是将XML映射为关系数据表，然后对关系数据表进行分片。然 而将XML映射为关系数据表是低效的，而且破坏了XML本来的结构特征。最后， 扩展性也是XML分片方法需要考虑的。NSNRR、PSPIB、WIN等方法均将XML划 分为N个片段然后分发到N个节点上。如果集群扩展，那么重新组织分布在N 个结点上的数据就会开销很大。

所以，针对XML分布式存储和并行处理的应用场景以及特性，提出一种新 的高效的XML分片方法有重要意义。

发明内容

本发明的技术解决问题：克服现有方法的不足，提出一种基于查询工作量 估算的XML分片方法，用XML自身结构进行查询工作量的估算，无需使用用户 查询。且以查询工作量估算值作为XML文档的存储度量，将XML划分为查询工 作量约为W0的片段，均匀分布在各个节点上，以支持集群扩展性，并在并行 查询时达到更好的负载均衡。

本发明的技术解决方案：一种基于查询工作量估算的XML分片方法，其特 征在于步骤如下：

(1)将XML树中每个结点编码。编码规则参考区间编码Zhang编码，由于 所有结点均处于同一文档，故省略文档编号doc_id属性，添加查询工作估算 值workload属性，用于存放以该结点作为根节点的子树的查询工作量估算值。

(2)为每个结点生成相关的XPath查询步。查询步中以该结点为祖先或父 亲结点，生成相应的包含查询步。

(3)查询工作量估算。对一个XML文档树从根结点开始，采用深度优先遍 历的顺序，递归的对所有的结点进行查询工作量估算。

(4)基于查询工作量估算结果进行XML分片。XML文档树被划分为查询工 作量估算值约为W0的各个子树。

(5)XML分配。将分片后的XML片段以查询工作量估算值升序排序，以一 种“回形”的方式分发到各个处理节点上。

根据本发明的又一个方面，其中步骤(3)进一步包括步骤：

(3.a)从XPath查询步队列中提取出与该结点相关的XPath查询步列表；

(3.b)对XPath查询步列表中的每个查询步进行连接结果大小估算，将估 算值添加到变量workload中；

(3.c)如果该结点为叶子节点，则返回workload；

(3.d)如果不是叶子节点，则遍历该结点的孩子结点，递归调用该方法， 以孩子结点作为参数，将其返回值添加到workload，重新转向(a)。

根据本发明的又一个方面，其中步骤(4)进一步包括：

(4.a)设变量PN表示可能的分割结点列表，finalPN表示最终的分割结 点列表，初始将root加入PN，finalPN中为空；

(4.b)如果PN不为空，从PN中取出一个结点node；如果PN为空，转 向步骤(f)；

(4.c)如果node的workload不在W0附近且大于W0，则将其孩子结点全 部加入PN；

(4.d)如果node的workload在W0附近，则将node加入finalPN；

(4.e)如果node的workload不在W0附近且小于W0，则将node加入 tempList中，转向步骤(b)；

(4.f)如果tempList不为空，对tempList中的具有相同父亲的结点进行 合并。将具有相同父亲的结点归为一组，和它的兄弟节点进行合并，如果某几 个兄弟节点的workload之和在W0附近，则将其父亲结点添加一个特殊标志， 加入finalPN；如果同一组中所有节点workload之和都达不到W0或者剩余的 结点达不到W0，就将这些节点合并在一起，上溯一层，将其父亲结点加入 tempList，重新转向步骤(e)；如果tempList为空，转向步骤(g)；

(4.g)根据finalPN将XML树划分为子树，每个子树形成一个XML片段。

本发明与现有方法相比的优点在于：本发明考虑XML分布式存储与并行查 询的最常用的应用场景，即XML存储时用户查询未知的场景，为达到并行查询 负载均衡，仅使用XML自身结构进行查询工作量估算，并将其作为XML存储的 度量，将XML划分为查询工作量估算值接近存储单元W0的片段，达到了更好 的查询时负载均衡，并且支持集群扩展。实验表明，在查询未知的应用场景下， 本发明能够达到较好的并行查询时负载均衡，较大的提升了并行系统的加速比 和缩放比指标。

附图说明

图1为本发明的方法基本流程图；

图2为本发明与对比方法WIN的加速比指标对比图，其中，图2(a)为10M XML文档分布在2-6台处理机的查询加速比对比图；图2(b)为20M XML文档 的查询加速比对比图；图2(c)为30M XML文档的查询加速比对比图；图2(d) 为40M XML文档的查询加速比对比图；图2(e)为50M XML文档的查询加速比 对比图；

图3为本发明与对比方法WIN的缩放比指标对比图。

具体实施方式

下面参考附图，对本发明的实施例进行详细的说明。

首先对本发明的方法原理进行说明。

研究表明，在考虑查询负载均衡的XML分片方法中，查询工作量估算值将 会很大程度上影响XML的分片结果，进而影响整个并行系统的性能。只使用XML 结构进行查询工作量估算，需要探索XML结构与XML查询之间的关系。在XML 查询中用于选择定位结点最常用的是XPath语言。对于复杂的XPath表达式， 如“a/b//c[attr＝”XX”]”)”，一般的XML查询引擎将其分裂为多个子查询步， 如”a/b”、”b//c”、”c[attr]”和”attr＝”XX””。然后计算每个子查询步的结 果，最后将这些结果合并作为原始XPath表达式的查询结果。基于此，将XML 文档树中所有的子查询步的查询结果合并起来作为XML文档的查询工作量估算 值。并且，由于XML文档结构的灵活性，查询的开销不能与XML文档的长度建 立一种直接的线性关系，所以采用XML查询工作量估算值作为XML存储的度量， 且设定一个存储单元W0，使划分的子树的查询工作量估算值都约为W0，以支 持系统扩展性。

具体而言，本发明所提出的方法基本流程如图1所示。

本发明主要包括的核心思想：根据XML自身结构进行查询工作量估算，以 XML查询工作量估算值作为XML的存储度量，并设定存储单元W0，将XML划分 为查询工作量估算值约为W0的片段，均匀分布在各个节点中，以支持集群扩 展性和达到更好的并行查询时负载均衡。

在描述方法前先定义如下变量及方法：

1.设XML存储单元为W0，为基本查询工作量估算值；

2.设XML文档树编码后，等价转换的节点列表为nodelist；

3.设XPathQueue用于存放生成的XPath查询步，XPathList为某节点相 关的XPath查询步列表；

4.设XML查询工作量估算的方法为workloadEstimation，其返回值为查询 工作量估算值；

5.设XML分片的方法为XMLPartition，其中合并小枝的方法merge，进行 XML文档划分的方法为partition；

6.设变量PN表示可能的分割结点列表，finalPN表示最终的分割结点列 表。

本发明的方法描述如下：

(1)将XML树中每个结点编码。编码规则参考区间编码Zhang编码，由于 所有结点均处于同一文档，故省略文档编号doc_id属性，添加查询工作量估 算值workload属性，用于存放以该结点作为根节点的子树的查询工作量估算 值，即每个元素结点编码为四元组<begin，end，level，workload>，其中， begin表示遍历该结点的所有后裔结点之前，访问该节点产生的序号，end表 示在遍历完该结点所有后裔结点之后，访问该节点产生的序号，level表示该 结点在树中所处的层次，workload即以该结点作为根节点的子树的查询工作量 估算值；每个属性节点编码为<begin，end，parent_node，workload>，其中， begin、end和workload表示的意义与前述相同，parent_node表示该属性节 点的父节点；文本节点编码为<begin，parent_node>，文本结点没有后裔，故 只遍历该结点一次，产生序号begin，parent_node表示文本结点的父节点。 在这种编码方式下，XML树被等价转换为以begin属性升序排序的结点列表 nodeList。

(2)为nodeList中每个结点生成相关的XPath查询步。查询步中以该结点 为祖先或父亲结点，生成相应的包含查询步，并将其加入到XPathQueue中。

(3)查询工作量估算。对一个XML文档树从根结点开始，采用深度优先遍 历的顺序，递归的对所有的结点进行查询工作量估算。查询工作量估算方法 workloadEstimation以结点node作为输入参数，输出以该结点为根的子树的 查询工作量估算值。运行方法的步骤如下：

(a)初始化变量workload为0；

(b)从XPathQueue队列中提取出与该结点相关的XPath查询步列表 XPathList，对XPathList中的每个查询步进行连接结果大小估算，将估算值 添加到变量workload中。

(c)如果node为叶子节点，则返回workload；

(d)如果不是叶子节点，则取出nodelist中的下一个结点nextNode；

(e)如果nextNode是node的孩子结点，递归调用该方法，以nextNode 作为参数，将其返回值添加到workload，重新转到步骤(a)。

(4)基于查询工作量估算结果进行XML分片。XML文档树被划分为查询工 作量估算值接近W0的各个子树。首先找到用于分割的分割结点列表finalPN， 然后根据finalPN进行XML分片。以包含查询工作量估算值的nodelist作为 输入，输出分片之后的XML片段。

(a)初始将根节点root加入PN，finalPN中为空。

(b)如果PN不为空，从PN中取出一个结点node；如果PN为空，则转 向步骤(f)。

(c)如果node的workload不在W0附近且大于W0，则将其孩子结点全部 加入PN；

(d)如果node的workload在W0附近，则将node加入finalPN；

(e)如果node的workload不在W0附近且小于W0，则将node加入tempList 中，转到步骤(b)；

(f)如果tempList不为空，使用merge方法对tempList中的具有相同 父亲的结点进行合并。将具有相同父亲的结点归为一组，和它的兄弟节点进行 合并，如果某几个兄弟节点的workload之和在W0附近，则将其父亲结点添加 一个特殊标志，加入finalPN；如果同一组中所有节点workload之和都达不到 W0或者剩余的结点达不到W0，就将这些节点合并在一起，上溯一层，将其父 亲结点加入tempList，重新转向步骤(f)；如果tempList为空，转向步骤(g)；

(g)partition方法根据finalPN将XML树划分为子树，每个子树形成一 个XML片段。

(5)XML分配。将分片后的XML片段以查询工作量估算值升序排序，以一 种“回形”的方式分发到各个处理节点上。

以下通过本发明与WIN方法的对比，进一步说明在查询未知的应用场景下， 本发明可以较大提升并行系统的加速比和缩放比指标(参见附图2)，主要因为 其可以达到更好的并行查询时负载均衡。

对于本领域的普通技术人员来说可显而易见的得出其他优点和修改。因 此，具有更广方面的本发明并不局限于这里所示出的并且所描述的具体说明及 示例性实施例。因此，在不脱离由随后权利要求及其等价体所定义的一般发明 构思的精神和范围的情况下，可对其作出各种修改。