论文部分内容阅读
近年来,随着计算机技术和信息技术的迅速发展,互联网中的数据信息呈现“滚雪球”式的增长。面对如此庞大的信息海洋,如何高效地处理和分析这些海量数据,并从中获取用户感兴趣的信息已经成为工业界和学术界共同关心的课题。关于海量数据的查询处理与优化技术也逐渐成为数据库领域新的研究热点,特别是在MapReduce框架下的查询处理与优化问题更是受到了广泛的关注,并且具有深远的理论研究意义和重要的实际应用价值。本文详细而深入地分析和研究了MapReduce框架下的海量数据查询处理与优化问题,提升了MapReduce框架的处理能力,提高了top-k、kNN、Skyline、连接等查询的处理性能。本文的贡献点可概括如下:(1)提出了一个具有轻量级通信功能的MapReduce框架-ComMapReduce,提高了现有MapReduce框架的处理性能。ComMapReduce框架通过增加轻量级的通信功能产生共享信息,通过获取共享信息,ComMapReduce框架能够有效地过滤Map阶段的无用数据,从而减少Reduce阶段的输入数据量,在不影响MapReduce框架基本特性的前提下,大幅度地提升了MapReduce框架的性能。(2)针对Skyline查询,首先,提出了在MapReduce框架下的Skyline查询处理算法。其次,利用Skyline查询结果的数量往往小于原始数据量的特点,提出了在ComMapReduce框架下的Skyline查询处理算法,能够有效地过滤部分不能成为查询结果的数据对象,减少Map任务的输出,使得在有效地处理Skyline查询的同时也提高了算法的执行效率,降低了网络开销。最后,提出了优化Skyline查询处理算法,进一步地提高了在MapReduce和ComMapReduce框架下Skyline查询的处理性能。(3)针对不确定数据的概率Skyline查询,首先,分析和总结了概率Skyline查询的特点和性质。其次,提出了filter-refine两阶段的处理方法,将不可分解的概率Skyline查询转换成了两个可分解的问题,分别是求解全局候选集和影响集的问题和计算最终概率Skyline结果的问题。其中,filter阶段获得全局候选集和影响集,refine阶段利用全局候选集和影响集求得最终的概率Skyline查询结果。最后,提出了在MapReduce框架和ComMapReduce框架下的filter-refine概率Skyline查询处理算法。通过有效地运用ComMapReduce框架的通信策略,过滤部分无用的中间结果,提高了不确定数据概率Skyline查询的处理性能。(4)针对连接查询,首先,深入地分析和研究了在MapReduce框架下连接查询处理算法,其中包括两表连接查询处理算法和多表连接查询处理算法。其次,提出了在ComMapReduce框架下的连接查询处理算法。运用ComMapReduce框架的通信功能确定共享信息,避免了对无用元组的传递和排序,降低了处理代价,提高了连接查询处理算法的效率。最后,提出了有效的连接顺序分析方法,优化了连接查询的处理顺序,进一步地提高了连接查询的处理性能。