基于MapReduce的XML结构连接处理*

李　东，邓泽航，李祖立华南理工大学 软件学院，广州 510006

基于MapReduce的XML结构连接处理*

李东+，邓泽航，李祖立
华南理工大学 软件学院，广州 510006

LI Dong,DENG Zehang,LI Zuli.Structural join processing for XML based on MapReduce.Journal of Frontiers of Computer Science and Technology,2016,10(8)：1080-1091.

摘要：可扩展标记语言（extensible markup language，XML）已经成为Web上数据表达和数据交换的事实标准，Hadoop已成为云计算和大数据处理典型支撑框架之一，基于Hadoop MapReduce来实现XML查询处理十分必要。为了实现基于MapReduce的XML查询处理，首先实现了区间编码、前缀编码和层次编码等3种不同的XML数据编码方式，以此为基础来研究和实现基于MapReduce的XML结构连接处理。为查询处理建立了代价模型，通过代价估算获得优化的查询计划树。最后开展了XML查询处理实验评估，结果表明相对其他两种XML编码方式，区间编码方式下实现的查询处理速度较快，基于代价估算的优化方法能进一步有效地提高XML查询处理性能。

关键词：可扩展标记语言（XML）；结构连接；MapReduce

1　引言

可扩展标记语言（extensible markup language，XML）已经成为Web上数据表达和数据交换的事实标准，各种Web应用促使XML数据量呈海量趋势增长。作为开源的分布式计算框架，Hadoop[1]及其改进系统以其可靠性、高效性、高容错性和低成本等特点，成为云计算和大数据处理典型支撑框架，基于Hadoop来研究XML查询处理十分必要。

本文主要研究如何基于Hadoop MapReduce计算模型对XML数据进行编码，并利用MapReduce进行查询处理。XPath是XML查询处理的核心，其中结构连接又是最核心的操作之一，如何基于MapReduce来高效实现结构连接对处理海量XML数据至关重要。本文基于3种不同的XML编码，利用MapReduce实现XML海量数据的查询，并为查询处理建立了代价模型，通过代价估算方法对查询计划进行优化。

本文的主要贡献如下：

（1）实现了MapReduce框架下3种不同的XML编码。

（2）实现了MapReduce框架下不同编码方式的结构连接的XPath查询处理算法。

（3）实现了MapReduce框架下基于代价估算的查询优化算法。

（4）实验结果验证了基于代价估算方法的有效性。

本文组织结构如下：第2章介绍相关工作；第3和第4章分别介绍MapReduce框架下对XML进行编码和查询处理的具体算法；第5章介绍查询优化算法；第6章进行实验结果分析；最后总结全文。

2　相关工作

XML结构连接是XML查询处理的核心操作之一，现有的基于MapReduce的连接算法主要有相似性连接算法、等值连接算法和θ连接算法等。

相似性连接算法大体上可分为水平划分方法和垂直划分方法。水平划分方法首先划分所有的数据对，之后独立地针对每个划分执行连接，最后将所有划分的执行结果进行合并。为了只对有效对进行划分，可以采用相应的裁剪技术对候选对进行过滤[2-3]。而垂直划分方法首先建立反转表索引，然后在每个索引的划分中枚举数值对检查其相似性[4-5]。当合并结果集时，要消去重复项完成最终的相似性连接。有些论文研究了等值连接[6]的MapReduce算法以及θ连接[7-8]的MapReduce算法，与以上不同的是，本文研究XML结构连接的MapReduce算法。

基于MapReduce的XML数据查询处理典型系统主要有ChuQL[9]和Xadoop。其中ChuQL主要是通过对XQuery语法进行扩展来实现在Hadoop上处理XML数据，对于XML数据处理则没有经过任何索引，每次使用扩展的XQuery语句进行查询都要处理整个文档来获得结果。Xadoop将XQuery作为操作Hadoop的一种语言来处理半结构化数据，主要研究XQuery代码的自动并行化，以及不同任务之间的数据传输和索引管理，仅支持以行为单位的分块方法，且执行效率较低。相较于ChuQL，只要编码一次，便可以利用编码文件进行多次查询，而不用每次查询都处理整个XML文档，相对于Xadoop而言，处理XML文档也不需要一定以行为单位，可以跨行进行数据读取。

文献[10]也提出了一种基于MapRedcue的XML结构连接算法，它使用的是前缀编码格式的数据进行结构连接。Map阶段根据分区算法对数据进行随机分区，一个数据将产生多个副本分配到不同区，副本数由参数m和n决定，m是人为定义的（当m为1 时Reduce只有1个区），n是XPath语句出现的标签名数目，每个数据都会产生m的n次幂个副本；Reduce阶段读取所有数据后排序再进行结构连接。此算法存在着Map阶段输出冗余度过大，Reduce阶段内存消耗过大，容易造成内存溢出的缺点。而本文算法中分区根据不同编码的特点进行算法设计，Map阶段输出的冗余度远小于该算法，Shuffle阶段又对数据进行了二次排序，在Reduce阶段数据已经是有序的，不需要全部读取后再排序，降低了Reduce阶段内存溢出的风险。

基于MapReduce的查询优化目前主要的研究都是针对SQL语句的查询优化。SQL语句中多表连接操作通常被分解成多个作业，每个作业执行两个表的连接操作。而优化的方向主要有两种：一种是多个SQL语句并行执行时共享连接结果来加速处理[11]；另一种是针对一条语句通过代价估算来确定代价最低的多表连接次序[12]。本文提出的优化算法也是在代价估算的基础上针对一条XPath语句进行连接次序的优化，但是SQL确定的是作业的连接次序，本文确定的是两个节点集是做Map端连接还是Reduce端连接，对于查询计划的生成都采用了启发式方法。

3 基于MapReduce的XML编码算法

为了对XML数据进行索引和有效查询，可以对XML树进行编码，本研究中一共实现了3种不同编码方案：区间编码[13]、前缀编码[13]和层次编码[14]。图1、图2、图3为3种编码示例。

Fig.1　Interval encoding图1区间编码

Fig.2　Prefix encoding图2前缀编码

Fig.3　Hierarchy encoding图3层次编码

使用MapReduce进行XML编码首要解决问题是对XML进行读取时文件划分成多个分片，会造成分片的开头或结尾出现标签不全的问题。如“”标签被分为“”被分到了分片2。解决策略是：每次读取一个字节，读到“<”符号就会一直往下读到下一个“<”符号为止，即使超出了分片的范围。

区间编码算法和前缀编码算法都是在Map阶段对节点进行不完整的编码并输出，每处理完一个分片将分片的偏移信息记录下来，保存到HDFS上。Reduce阶段读取所有分片信息建立偏移表，对编码进行矫正并输出。具体实现可以参照文献[13]，本文研究借鉴了其实现思想，做的改进主要是在Map输出key值时，还额外输出了节点编码用于二次排序，使得最后Reduce的输出是有序的。

要对一个节点进行层次编码，需要获取到它的父节点的层次编码和它的兄弟节点信息。层次编码实现利用了前缀编码的结果，先将深度相同的前缀编码放在一个文件中，文件中节点按在XML文件中的顺序排好序。

层次编码对节点按深度从小到大进行编码，每一层使用一个作业完成。各层的编码算法主要思路如下：

当深度为1和2时，节点N(i,level)的编码Hid按照层次编码规则赋值。

当深度大于2时，将启动MapReduce作业，使用算法1、算法2进行编码。

编码阶段将根据标签名把编码后的节点信息按从小到大的顺序存储到HDFS上不同的文件中。

算法1 Map Encoding

输入：未编码数据集ENR，上一层已编码数据集LR。

输出：不完整编码的数据集。

/*EN属性分别为节点的前缀编码、标签名*/

1.For（EN in ENR）do：

/*通过节点的前缀编码可以获知其父亲编码*/

2.parentEN←getParent（EN）；

/*获取父亲节点的层次编码*/

3.parentHid←getHid（parentEN，LR）；

4.newEN←（，EN）；

5.output（newEN）；

6.Endfor；

算法2 Reduce Encoding

输入：父节点相同的一组数据集ENR。

输出：完整编码的数据集。

1.初始化Set；

/*EN属性分别为父节点层次编码、节点本身的前缀编码、标签名*/

2.For（EN in ENR）do：

3.add NAME（EN）into Set；

/*将EN名字在Set中的位置按规则转为二进制*/

4.S←Transform（EN，Set）；

/*S加上父节点的层次编码形成子节点层次编码*/

5.Hid←S+parentHid（EN）；

6.output（EN，Hid）；

7.Endfor

图4、图5为层次编码过程示例。

4 基于MapReduce的XML查询算法

4.1编码大小比较规则

定义1“Ni

Fig.4　Map process of hierarchy encoding图4 层次编码Map过程示例

Fig.5　Reduce process of hierarchy encoding图5　层次编码Reduce过程示例

区间编码的大小按start的值进行判断，如果Ni

前缀编码的大小判断规则如下，示例1.1<1.1.1< 1.1.2<1.2。

设Ni的前缀编码为A1.A2.….Ai，设Nj的前缀编码为B1.B2.….Bj，如果Ni

（1）i

（2）∃m

层次编码的大小判断规则如下，示例0<0010< 0110<10110。

设Ni的层次编码为AiAi-1…A1，设Nj的前缀编码为BjBj-1…B1，如果Ni

（1）i

（2）∃m≤min(i,j),Am

4.2查询算法总体思想

本文查询算法主要包括Map端连接和Reduce端连接两部分。

在Map阶段，查询算法采取的策略是首先对读取的节点进行谓词过滤。根据查询计划树的不同有两种不同操作：第一种是进行两两元素之间的连接操作，对连接产生的中间结果进行区域划分；第二种是直接对读取的节点进行区域划分，再利用shuffle过程按key排序的特性对节点信息进行排序。在Reduce阶段，对已经排好序的中间结果进行连接。各阶段详细讨论将在后续几节介绍。图6为总体查询处理过程。

Fig.6　Query process图6查询过程

4.3Map端连接

当查询语句存在谓词时，对于谓词过滤都在Map阶段进行处理，读取到一个节点后，如果需要进行谓词连接，则进行相应的条件过滤和连接判定，连接判定过程参考Map端连接算法。Map端进行过滤可以减少Map的输出节点数目，减少shuffle和reduce开销。Map结构连接过程如图7所示。

Map阶段进行组合的连接操作，每次读到一个节点的编码信息，就找出与其进行连接的祖先节点，进行连接判定，具体过程参算法3。

算法3 Map Join

输入：节点数据集ENR，其祖先节点数据集AR。

输出：节点对数据集。

1.parentEN←the first item inAR；

2.初始化List；

/*EN为一个节点的编码信息（3种编码中任意一种）*/

3.For（EN in ENR）do：

/*EN先与List里的节点做连接判定，并删除不满足连接条件的节点*/

4.JoinList（EN，List）；

/*parentEN

5.While parentEN

6.If join（parentEN，EN）=true then

/*满足连接条件，分区后输出到reduce*/

7.partitionAndOutput（parentEN,EN）；

8.Add parentEN to List；

9.Endif

10.parentEN←the next item inAR；

11.Endwhile

12.Endfor

Map阶段在输出结果时需要根据节点的信息或节点对中子节点的信息进行分区再输出，各个编码的分区规则如下。

（1）区间编码分区规则

节点N的区间编码为，分区长度为B，则[0,B-1]为区域0，[B,2B-1]为区域1，以此类推。

Fig.7　Map join process图7Map结构连接过程

令 first=start/B，last=end/B，则节点N将输出到区域first至区域last。例如N编码为<20,30,3>, B=5，分配到区域4、5、6。

（2）前缀编码分区规则

节点N的前缀编码为A1.A2.….Ai，分区长度为B，那么当i≥B时，N将分配到区域A1.A2.….AB，当i

（3）层次编码分区规则

节点N的层次编码为 AiAi-1…A1，分区长度为B，那么当i≥B时，N将分配到AB…A2A1，当i

通过分区，数据会产生一定的冗余，例如同个节点编码输出到了不同的区域里，但是保证了Reduce端连接时每一组包含连接所需要的所有节点信息。

4.4Reduce端连接

Reduce阶段进行连接操作。对于已经完全排好序的中间结果集来说连接是较直观的，每读到一个节点数据，找出对应的祖先节点的栈；跟栈中节点进行连接判定，判定成功的话，如果该数据不是最后要输出的数据，则压到对应的栈里；如果是最后要输出的数据，则先判断分区id是否为节点Map输出进行分区时id最大的分区，是的话才输出，不是则抛弃，这是为了避免不同分区输出相同的结果。

4.5默认查询计划

未优化的查询算法默认采用的处理策略是对表达式以两个标签为一个组合进行分解，分解后的组合将在Map阶段进行连接操作生成中间结果。因为组合中祖先节点的文件大小通常小于子孙节点的文件大小，所以祖先节点的文件不作为输入文件，而将子孙节点的存储文件作为MapReduce任务的输入文件，如图8所示。

Fig.8　Decomposition of XPath图8XPath语句分解示例

从图8可以看到，/site/regions//item/description/ parlist/listitem//parlist/listitem语句中有两个组合是相同的，即{parlist/listitem}。当读到{parlist/listitem}的结果数据时，要与{parlist/listitem}的结果进行Ancestor-Descendant关系判断呢还是跟{item/description}的结果进行Parent-Child关系判定呢？由于不能马上判断出读到的数据是属于哪个{parlist/listitem}组合，采取的策略是按表达式从后向前进行连接判定，先判断{parlist/listitem}与{parlist/listitem}两个是否是Ancestor-Descendant关系，不是的话再判断{parlist/listitem} 与{item/description}的Parent-Child关系。

4.6数据重用

对一条查询语句构造其查询计划树，可能出现Map阶段输出结果可以重用或者输入文件可以重用的情况，这时可以利用重用数据以减少开销。

例如A/B/C/B，默认查询计划树中标签B在Map中需要做A/B和C/B连接判断，都需要标签B的节点编码文件要作为输入文件，此时可以输入一遍标签B的节点就行。又如A/B/A/B，查询计划中Map端需要做A/B的连接判定两次，也可以合并为1次。

5　基于代价评估的查询优化

如图6及图8所示，对于一个查询语句，不同的查询计划树会使得模块1和2的执行代价不同。为了对代价进行评估，需要对结构连接操作结果集的数目进行估算，对MapReduce作业建立代价模型。

5.1结构连接操作结果集的估算

文献[14]提出了一个在单节点环境下根据层次编码统计信息对XPath查询的CPU执行代价估算的方法。本文结构连接操作结果集的估算使用文献[14]中的方法，来对两个节点集连接结果进行估算。

对于父子连接操作的结果集估算，如A/B，A表示一个标签名，A.result表示名字相同的节点层次编码的集合。为了对A/B的结果集R进行估算，需要对B集合的每一项b，遍历A集合，查找A集合中是否存在节点a与节点b满足父子关系，如果是则停止查找，并将b添加到R中。最后将R中的每个节点编码信息中的nodeCount进行相加，得到的和就是A/B的结果集数目的预估值。

对于祖孙连接操作的结果集估算，如A//B，需要对B集合的每一项b，遍历A集合，查找A集合中是否存在节点a与节点b满足祖孙关系，如果是则将b添加到R中，并继续查找直到遍历完。最后将R中的每个节点编码信息中的nodeCount进行相加，得到的和就是A//B的结果集数目的预估值。

对于数值型谓词结果集的估算，如B>7，根据谓词对应的节点层次编码、比较操作符以及参与比较的数值，使用直方图进行估算，详细细节可看文献[14]。

5.2MapReduce查询代价模型

本文采用代价模型评估不同查询计划树在Map-Reduce框架下执行所消耗的代价。进行代价估算需考虑3个因素：一是I/O开销；二是CPU的开销；三是网络传输的开销。表1是代价模型所使用的参数。

Table 1　Model parameters表1模型参数

查询处理中Map过程有两种不同操作，现在对两种操作建立代价估算模型。首先定义Path(i,j)为路径表达式，当i=j时，代表Path(i,j)为一个节点名称，当i

Path(i,i)对应的节点数据集为Ii。按照式（1）～（3）可计算从HDFS上读取输入文件的代价RC（read cost），数据集进行分区输出的CPU代价PC（partition cost），Map数据输出到本地文件的代价WC（write cost），三者构成不进行连接操作的Map阶段代价。

Path(i,i)的Map阶段的代价计算公式如下所示：

按照式（5）～（7）可计算在HDFS读取祖先节点数据集的代价RAC（read ancestorƳs records cost），对连接结果数据集进行分区输出的CPU代价PPC（partition pair cost），结果数据集输出节点到本地磁盘的代价WPC （write pair cost）。

式（7）与式（3）的主要区别是代价乘以2，这是因为结果集中的每个数据都是由两个节点编码信息组成，所以大小也要多了一倍。

Path(i-1,i)的Map阶段代价计算公式如下所示：

Shuffle和Reduce阶段的代价估算主要考虑影响因素是Map输出的节点数据集（在本文算法中，Map的输出数据集总和与Reduce的输入数据集是相同的），假设RI为Reduce的输入数据集，则Reduce阶段的代价计算公式如下所示：

CR=Cshuffle(RI)+Crjoin(RI)+NUM(RO)×Cwh（9）

其中，Cshuffle(RI)代表从Map获取输出文件到Reduce输入的整个shuffle过程的全部代价；Crjoin(RI)代表在Reduce端对集合RI进行连接的CPU代价；NUM(RO)×Cwh代表的是Reduce的输出代价。

Job表示一个MapReduce作业，一个查询的Map-Reduce作业的全部代价计算公式如下所示：

其中，∑CMi是查询计划树中不做Map端连接的数据集Ii的Map阶段代价总和；∑CM(j-1,j)是查询计划树中进行Map端连接的数据集Ij的Map阶段代价。因为MapReduce作业的Map任务数与输入文件的大小相关，并行的Map任务数不同也会导致作业的效率不同，所以进行代价评估时也需要考虑并行Map任务数的影响。而Reduce的组数一直大于集群中并行的Reduce任务数，因此这里不计入Reduce任务数的影响。假设查询计划的Map任务数为N，集群最大的并行Map任务数为M，则作业同时并行的Map任务数K=min(N,M)。

5.3启发式优化查询算法

定义2J为一个状态节点，保存了3个变量，第一个为路径表达式Path，第二个为Path的执行代价cost，第三个是Path中最后一个参与连接操作结构的类型type，type有两种类型EN和LP。EN表示元素节点名，LP表示一个二元连接结构的长路径。

定义3 Path＋EN表示将连接节点EN添加到路径表达式Path中，EN的数据集不进行Map端连接操作。

定义4 Path-EN表示将路径表达式Path中的最后一个连接节点EN除去。

定义5 EN1*EN2表示一个二元连接结构，EN1与EN2两个节点数据集在Map端进行连接操作。

本文使用最佳优先搜索算法[15]查找代价最小的查询计划。对一个查询语句，从左往右逐个增加连接结构生成查询计划树，具体过程如下:

初始化优先队列Queue，用于保存状态节点并每次返回执行代价最低的状态节点；minCost用于查询语句的最低执行代价，初始化为双浮点最大值；minJ用于存储执行代价最低的完整查询路径。

初始化第一个状态节点J，J.Path=Path(1,1)，根据表达式计算出各个变量的数据后存储，添加到Queue中。

当Queue不为空时，返回队列中代价最低的状态节点J，根据J的路径表达式结构添加新的连接节点EN1，添加规则如下所示。

当J.type=EN时，可以生成两个新的状态节点进行添加，假设J.Path的最后一个连接节点为EN′，则：

新的状态节点：

J1.Path=J.Path+EN1

J2.Path=J.Path-EN′+(EN′*EN1)

当J.type=LP时，可以生成一个新的状态节点：

J1.Path=J.Path+EN1

新的状态节点根据路径表达式更新作业的执行代价，当cost>minCost且type=LP时，该状态节点则放弃掉。当路径表达式已经是完整的查询语句时，如果cost

算法4 Optimization

输入：一个查询语句XPath。

输出：一个执行计划树。

/*对语句进行解析*/

1.Parse（XPath）；

2.初始化优先队列Queue，代价最小作业minJob；

3.minJob.cost←MAX；

4.J.Path←Xpath(1，1)；

5.Push J into Queue；

/*优先队列，每次返回代价最小节点*/

6.While Queue is not empty do

7.J←pop from Queue；

8.If(minJob.cost>J.cost)

9.break；

/*对路径根据类型进行扩展，不是完整路径则压入Queue中，是的话根据代价更新minJob*/

10.ExpandAndUpdate(J，minJob，Queue)；

11.Endwhile；

12.return minJob.path；

对于查询语句/A/B//C/D的优化过程如图9所示。图中用|号表示分割，分割点所在的连接操作在Reduce端完成，其余连接操作都在Map端完成。

Fig.9　Query optimization process图9 查询优化过程

6　实验测试

6.1实验环境

实验测试硬件环境是4台IBM刀片服务器。安装Openstack云计算平台，创建了6台CPU为2个虚拟内核，内存为4 GB的主机，其中1台为namenode，5台为datanode。

实验数据采用XMark[16]标准的数据集。实验测试采用的XML数据集如表2所示，所选取的主要查询语句如表3所示。实验测试有3部分：（1）3种编码方式下查询速度的实验对比。（2）区间编码方式下在不同数据集下的查询速度对比。（3）计划树优化前后的查询速度对比。实验中将在分布式环境下，对不同查询语句在不同数据集下进行多次查询（前两部分实验采用的查询计划树是未优化的查询计划树），记录查询时间并取得平均值。第三部分实验则选取查询性能最优的区间编码方式进行优化方法的查询性能测试。

Table 2　Dataset表2数据集

6.2实验结果与分析

（1）3种编码方式查询速度的实验对比

图10～图14为XP1到XP5在不同数据集下的查询时间对比。从测试结果中可以看出，区间编码的查询性能在不同数据集和查询语句下都是3种编码中最优的，且随着数据量的增大，查询性能的优越性越来越明显。前缀编码和层次编码两者的查询性能则比较接近，总体上层次编码查询速度更快。查询性能上的差异主要来自分区和排序的执行代价不同，区间编码的分区和排序是直接对长整数类型数据进行计算，而前缀编码和层次编码是先对字符串类型数据进行转化后再计算，前者代价相对小于后者。

Fig.10　Query time of XP1图10XP1查询时间

Fig.11　Query time of XP2图11XP2查询时间

Fig.12　Query time of XP3图12XP3查询时间

Fig.13　Query time of XP4图13XP4查询时间

Fig.14　Query time of XP5图14XP5查询时间

（2）查询速度随数据集变化的情况

为了更准确地观察，这里采用的性能指标为数据集节点数与查询时间之比。经过分析，XP1到XP5语句中查询性能变化情况主要有两种：第一种是如图15中XP1的查询性能变化情况，主要有XP1、XP2、XP3、XP5语句，随着数据集的变大，查询处理性能具有近线性特点。

Fig.15　XP1Ƴs query speed changing with record set图15　XP1查询速度随记录集变化图

第二种是如图16中XP4的变化情况，查询性能不断提高，直到R5时性能下降。主要的原因是XP4的查询数据处理量比其他几个语句大，在R5数据集下超过了集群的同时并行能力最大数，导致需要多个周期的并行而使得性能下降。

Fig.16　XP4Ƴs query speed changing with record set图16XP4查询速度随记录集变化

（3）不同计划树的查询速度对比

本实验中展示了只做Reduce连接的查询计划的执行时间。图17是XP1到XP5语句在R2（在其他数据集上也有相似结论）下的3种查询计划的执行情况。其中，RJ（reduce join）表示只做Reduce连接的查询计划，DJ（default join）表示默认的查询计划，OJ （optimized join）表示优化后的查询计划。

Fig.17　Results of R2 comparison before and after optimization图17　R2下优化前后结果对比

从图17可以看出，RJ在XP1、XP2、XP4中查询性能略高于DJ，其他几条语句则DJ的查询性能更好。而OJ则在不同的查询语句中都是查询性能最好的，在本研究开展过的实验中，OJ比DJ的查询效率提高最高可达20%。

7　结束语

本文研究和实现了3种不同XML数据编码算法，以此为基础实现了基于MapReduce的XML结构连接处理，最后还实现了基于MapReduce作业的XML查询处理代价模型和查询优化算法。实验结果表明，基于区间编码方式的XML查询处理性能在3者中最优，提出的代价估算模型和优化方法能有效地提高查询处理性能。下一步将研究如何动态调整分区长度以进一步提高XML查询处理性能。

References:

[1]Dai Wei,Bassiouni.M An improved task assignment scheme for Hadoop running in the clouds[J].Journal of Cloud Computing,2013,2(1):1-16.

[2]Kim Y,Shim K.Parallel top-k similarity join algorithms using MapReduce[C]//Proceedings of the 2012 IEEE 28th International Conference on Data Engineering,Washington, USA,Apr 1-5,2012.Piscataway,USA:IEEE,2012:510-521.

[3]Yu Jiang,Deng Dong,Wang Jiannan,et al.Efficient parallel partition-based algorithms for similarity search and join with edit distance constraints[C]//Proceedings of the Joint EDBT/ICDT 2013 Workshops,Genoa,Italy,Mar 22,2013. New York,USA:ACM,2013:341-348.

[4]Metwally A,Faloutsos C.V-SMART-Join:a scalable Map-Reduce framework for all-pair similarity joins of multisets and vectors[J].Proceedings of the VLDB Endowment,2012, 5(8):704-715.

[5]Vernica R,Carey M J,Li Chen.Efficient parallel set-similarity joins using MapReduce[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indianapolis,USA,Jun 6-10,2010.New York,USA:ACM, 2010:495-506.

[6]Zhang Xiaofei,Chen Lei,Wang Min.Efficient multi-way theta-join processing using MapReduce[J].Proceedings of the VLDB Endowment,2012,5(11):1184-1195.

[7]Okcan A,Riedewald M.Processing theta-joins using Map-Reduce[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data,Athens, Greece,Jun 12-16,2011.New York,USA:ACM,2011:949-960.

[8]Blanas S,Patel J M,Ercegovac V.A comparison of join algorithms for log processing in MapReduce[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,Indianapolis,USA,Jun 6-10,2010. New York,USA:ACM,2010:975-986.

[9]Khatchadourian S,Consens M,Siméon J.ChuQL:processing XML with XQuery using Hadoop[C]//Proceedings of the 2011 Conference of the Center for Advanced Studies on Collaborative Research.Riverton,USA:IBM Corp,2011:74-83.

[10]Wu Huayu.Parallelizing structural joins to process queries over big XML data using MapReduce[C]//LNCS 8645:Proceedings of the 25th International Conference on Database and Expert Systems Applications,Munich,Germany,Sep 1-4,2014.Berlin:Springer International Publishing,2014: 183-190.

[11]Wang Guoping,Chan C Y.Multi-query optimization in Map-Reduce framework[J].Proceedings of the VLDB Endowment,2013,7(3):145-156.

[12]Wu Sai,Li Feng,Mehrotra S,et al.Query optimization for massively parallel data processing[C]//Proceedings of the 2nd ACM Symposium on Cloud Computing,Cascais,Portugal,Oct 26-28,2011.New York,USA:ACM,2011:12.

[13]Choi H,Lee K H,Lee Y J.Parallel labeling of massive XML data with MapReduce[J].The Journal of Supercomputing,2014,67(2):408-437.

[14]Li Dong,Chen Wenhao,Liang Xiaochong,et al.Cost-based query optimization for XPath[J].Applied Mathematics& Information Sciences,2014,8(4):1935-1948.

[15]Dechter R,Pearl J.Generalized best-first search strategies and the optimality of A∗[J].Journal of the ACM,1985,32 (3):505-536.

[16]Schmidt A,Waas F,Kersten M,et al.XMark:a benchmark for XML data management[C]//Proceedings of the 28th International Conference on Very Large Data Bases,Hong Kong,China,Aug 20-23,2002:974-985.

LI Dong was born in 1970.He received the Ph.D.degree in computer science from Huazhong University of Science and Technology in 2001.Now he is a professor at South China University of Technology,and the member of CCF.His research interests include XML databases,mobile database and business process management,etc.

李东（1970—），男，湖南邵东人，2001年于华中科技大学获得博士学位，现为华南理工大学教授，CCF会员，主要研究领域为XML数据库，移动数据库，商业流程管理等。

DENG Zehang was born in 1991.He is an M.S.candidate at South China University of Technology.His research interest is distributed computation.

邓泽航（1991—），男，广东汕头人，华南理工大学硕士研究生，主要研究领域为分布式计算。

LI Zuli was born in 1992.He is an M.S.candidate at South China University of Technology.His research interest is distributed computation.

李祖立（1992—），男，广东惠州人，华南理工大学硕士研究生，主要研究领域为分布式计算。

*The Integration Project of Industry,Education and Research of Guangdong Province under Grant No.2013C001(广东省部产学研结合项目);the Project of Technology Bureau in Duanzhou District of Zhaoqing under Grant No.2014-5(肇庆市端州区科技局项目). Received 2015-07,Accepted 2015-09.

CNKI网络优先出版:2015-10-13,http://www.cnki.net/kcms/detail/11.5602.TP.20151013.1624.004.html

文献标志码：A

中图分类号：TP391

doi:10.3778/j.issn.1673-9418.1509011

Structural Join Processing for XMLBased on MapReduceƽ

LI Dong+,DENG Zehang,LI Zuli
School of Software Engineering,South China University of Technology,Guangzhou 510006,China +Corresponding author:E-mail:cslidong@scut.edu.cn

Abstract:Extensible markup language(XML)has become the defacto standard of data representation and data exchange on Web.Hadoop is a typical framework for cloud computing and big data processing,thus making a study on XML query processing based on MapReduce is necessary.In order to implement the XML query processing based on MapReduce,this paper proposes three different encoding algorithms such as interval encoding,prefix encoding and hierarchy encoding,and designs the corresponding structural join algorithms based on MapReduce to support XML queries.This paper sets up a cost model for the query processing,and proposes a cost-based approach to determine the optimal execution tree.In the end,the XML query processing experiments are made,the experimental results show that relative to other two XML encoding schemes,the query processing based on interval encoding has a higher query performance.And the cost-based optimal approach is effective and further improves the performance of XML query processing.

Key words:extensible markup language(XML);structural join;MapReduce