论文部分内容阅读
随着社交网络分析、生物信息网络分析、交通导航等新兴应用的快速增长,不同领域出现了规模庞大、内部结构复杂、查询需求多样的大图数据。传统的单机计算模式难以满足大图数据管理需求,利用分布式框架来对大图进行管理成为不可避免的趋势。尽管现有的分布式计算框架能够减轻用户实现图查询的代价,但是对于普通用户来说,在分布式环境中编写复杂的图操作程序仍然是非常困难的。此外,为了提高分布式程序的执行性能,用户不得不对底层分布式平台进行深入的研究和学习。 为了减轻用户利用分布式框架管理大图的负担,本文扩展了传统的Datalog查询,设计了一种描述性的图查询语言GLog,用户通过GLog可以简洁地表达查询任务。GLog查询引擎会将用户的查询翻译成一系列MapReduce作业,并提交给Hadoop平台运行。本文的主要贡献如下: 1.设计了一种能够结合关系数据与图数据二者优势的数据模型RG(Relational-Graph)表。基于RG表设计了一种描述性图查询语言GLog,GLog保持了传统Datalog语言的简洁性,同时增加了对嵌套数据和显示数据流控制的支持,还引入了更多的内嵌函数。 2.提出了一种将GLog查询翻译为一系列MapReduce作业的方法。该方法首先根据GLog规则在RG表上定义了一系列操作,然后为查询建立执行计划,最后根据翻译模版将查询计划翻译为MapReduce作业。 3.设计了一系列优化翻译规则来减少翻译生成的MapReduce作业数目。在翻译过程中,通过合并操作以及重写迭代过程可以显著地减少作业数目,提高查询执行的效率。 4.实现了基于Hadoop平台的原型系统,并在人工图和真实图数据上进行了大量测试。 实验结果表明,本文提出的GLog语言不仅能够简洁地表达多种图分析任务,而且还具有良好的性能和可拓展性。