论文部分内容阅读
XML因其自描述性和可扩展性,已经作为网络中一种主要数据形式得到越来越多的应用。单一XML文档数据量变得越来愈大,而且XML文档具有半结构化的特性,这些因素使得采取结构化的关系型数据库不适用于XML文档的查询处理。如何有效地支持XML数据的查询,尤其是如何有效地满足一定特定语义得到相应的查询结果成为当前的一个研究热点。
本文采用MapReduce,它是一个分布式计算框架,应用于大数据开发平台Hadoop中,该平台可部署在廉价的PC集群中,数据会分布在集群中的各个节点中,从而实现数据的并行处理,因而将MapReduce用于XML的数据查询。在对XML文档的查询过程中,很多研究采取将XML文档转化为文档树,对其文档树节点进行编码,其中采用前缀流编码进行相关研究是最多的,但是使用前缀流编码进行编码时,节点编码长度会随着文档树深度的增加而不断变大,编码生成的节点集占用相当大的存储空间。同时,这类编码标记的节点只能在子树间比较节点间的位置关系,这种位置关系是从树的某一层这个角度来分析的,但是从这个XML文档树的角度,无法看出节点的绝对位置。这些因素导致基于该类编码设计的XML查询算法效率普遍不高。
根据前缀流编码存在的上述问题,本文提出一种新型编码Xwei码。该编码不同于普通前缀流编码的是采用先序编码,同时对应文档树的节点编码仅保留节点间相对的父子关系,因而文档树的深度增加对编码数据集的大小是没有太大影响的。先序编码方式可以很好地保留XML树的完整结构,基于MapReduce运行机制对整个XML树对应的节点集合进行一定的数据截取,获取较小的节点数据集合,然后使用对应这部分节点间的间接父子关系,设计相应的查询算法,得到满足一定查询语义的结果。
本文的实验过程是基于MapReduce计算框架完成的,选择前缀流编码Dewey码,ED码作为比较对象,在编码和查询两个方面做了对比实验。编码实验表明,当文档树深度不高时,Xwei的编码效率比Dewey,ED码高出10%,当提高文档树深度时,Xwei码的编码效率相对Dewey,ED码提高的幅度达到25%以上。在查询实验中,本文是基于查询语义SLCA和ELCA来求解的,Dewey码和ED码采用LISA算法来查询,Xwei码则是根据自身编码特点设计相应的查询算法。实验证明基于Xwei码设计的查询算法是一种高效的XML查询算法,它可以大幅度缩减了查询的流程步骤,从而提高了查询效率。基于两种查询语义的效率对比实验中,Xwei码的查询效率要比Dewey码,ED码高出75%以上。
本文采用MapReduce,它是一个分布式计算框架,应用于大数据开发平台Hadoop中,该平台可部署在廉价的PC集群中,数据会分布在集群中的各个节点中,从而实现数据的并行处理,因而将MapReduce用于XML的数据查询。在对XML文档的查询过程中,很多研究采取将XML文档转化为文档树,对其文档树节点进行编码,其中采用前缀流编码进行相关研究是最多的,但是使用前缀流编码进行编码时,节点编码长度会随着文档树深度的增加而不断变大,编码生成的节点集占用相当大的存储空间。同时,这类编码标记的节点只能在子树间比较节点间的位置关系,这种位置关系是从树的某一层这个角度来分析的,但是从这个XML文档树的角度,无法看出节点的绝对位置。这些因素导致基于该类编码设计的XML查询算法效率普遍不高。
根据前缀流编码存在的上述问题,本文提出一种新型编码Xwei码。该编码不同于普通前缀流编码的是采用先序编码,同时对应文档树的节点编码仅保留节点间相对的父子关系,因而文档树的深度增加对编码数据集的大小是没有太大影响的。先序编码方式可以很好地保留XML树的完整结构,基于MapReduce运行机制对整个XML树对应的节点集合进行一定的数据截取,获取较小的节点数据集合,然后使用对应这部分节点间的间接父子关系,设计相应的查询算法,得到满足一定查询语义的结果。
本文的实验过程是基于MapReduce计算框架完成的,选择前缀流编码Dewey码,ED码作为比较对象,在编码和查询两个方面做了对比实验。编码实验表明,当文档树深度不高时,Xwei的编码效率比Dewey,ED码高出10%,当提高文档树深度时,Xwei码的编码效率相对Dewey,ED码提高的幅度达到25%以上。在查询实验中,本文是基于查询语义SLCA和ELCA来求解的,Dewey码和ED码采用LISA算法来查询,Xwei码则是根据自身编码特点设计相应的查询算法。实验证明基于Xwei码设计的查询算法是一种高效的XML查询算法,它可以大幅度缩减了查询的流程步骤,从而提高了查询效率。基于两种查询语义的效率对比实验中,Xwei码的查询效率要比Dewey码,ED码高出75%以上。