基于Datalog的分布式环境下大图数据查询方法

摘要

本发明涉及一种基于Datalog的分布式环境下大图数据查询方法，其步骤包括：1）对用户输入的基于Datalog规则集合的大图查询指令进行语法分析，产生对应的语法树；2）根据语法树，构建以Datalog规则为单位的执行计划。针对每个Datalog规则，构造对应的Map和Reduce执行函数。3）利用等价规则和统计数据，实现规则间优化、规则内优化、操作函数的优化，提高大图查询执行计划的效率。本发明为了简化最终用户编写图查询脚本的代价，提出了扩展的递归DataLog查询，支持用户使用简单的描述性语言来表达对应大图查询。本发明还提出了递归Datalog查询的MapReduce环境执行计划的构建方法，使得Datalog图查询能够在MapReduce框架下执行。

说明书

技术领域

本发明具体涉及分布式环境下进行大图数据的查询，具体涉及了一种基于Datalog的分布 式环境下大图数据查询方法，属于信息技术领域。

背景技术

现代社会中，图的应用越来越广泛。社交网络、生物信息、交通导航等领域技术的迅猛 发展产生了规模庞大的图数据。如何有效的管理这些大图数据面临着许多挑战：首先是传统 的单机计算模式很难支持大图数据的管理，单机的存储能力有限，很难将整个大图数据都加 载到内存中，同时单机的处理能力也不足，很难有效支持大图数据上各种复杂的操作；其次 是大图数据上的应用需求日益复杂，大图上的操作不仅仅局限于检索结点和边这样简单的操 作，同时还包括各种复杂的查询，比如最短路径查询、子图模式匹配等。这些操作往往需要 循环迭代，涉及很大的搜索空间和执行代价。因此，利用分布式环境来对大图数据进行管理 成为发展的必然趋势。

目前出现了一些基于分布式环境的大图数据管理系统，其中具有代表性的系统包括 Google的Pregel系统，可具体参考【1】（Grzegorz Malewicz,Matthew H.Austern,Aart J.C.Bik, James C.Dehnert,Ilan Horn,Naty Leiser,Grzegorz Czajkowski:Pregel:a system for large-scale  graph processing.SIGMOD 2010:135-146）以及Microsoft的Trinity系统，这两个系统都不是 开源的，主要是针对图数据管理的特点，专门开发的大图数据分布式管理框架，需要用户自 己使用高级编程语言来实现查询，对用户的专业知识要求较高。

目前还出现了基于MapReduce框架支持SQL查询的工作，如在SIGMOD2007上出现的 Map-Reduce-Merge的工作，如参考文件【2】（Hung-chih Yang,Ali Dasdan,Ruey-Lung Hsiao, Douglas Stott Parker Jr.:Map-reduce-merge:simplified relational data processing on large clusters. SIGMOD 2007:1029-1040）,以及在hadoop环境中采用类SQL语言进行分析的Hive系统，可 参考文件【3】（Ashish Thusoo,Joydeep Sen Sarma,Namit Jain,Zheng Shao,Prasad Chakka,Ning  Zhang,Suresh Anthony，Hao Liu,Raghotham Murthy:Hive-a petabyte scale data warehouse using  Hadoop.ICDE 2010:996-1005）。但是，此类工作只是考虑单个关系数据的操作符号，并没有 考虑图递归Datalog查询对MapReduce函数生成和优化的影响。

针对Datalog查询的研究曾经是数据管理领域重点，如参考文件【4】（Serge Abiteboul, Richard Hull,and Victor Vianu.Foundations of Databases.http://webdam.inria.fr/Alice/.）Datalog 查询表达能力强，用户能够以简洁的方式表达其查询要求。本发明主要是利用Datalog对图 数据进行查询，图数据需要较为复杂的递归循环处理。本发明扩展了Datalog查询语言，所 设计的Datalog查询显式地给出循环的终止条件，支持更多的系统函数，在不增加用户太多 负担的情况下，扩展了图查询的表达能力。

大图数据管理系统建设的一种方案是充分考虑图数据管理的特点和需求，完全从底层开 始的实现。这种方式的优点是能够针对大图数据作出特定的优化，系统管理大图数据比较自 然。缺点是需要自己专门实现数据分布、任务调度、数据副本、结点失败等通用分布式计算 框架的功能，这会带来庞大的工程实现代价，同时也没有办法利用已有系统积累的优势。

发明内容

本发明针对利用现有相对成熟的MapReduce分布式计算框架来对大图数据进行查询，针 对现有框架下大图数据查询性能难以满足应用需求、用户编写图数据处理脚本繁琐低效等问 题，设计了一种基于Datalog的MapReduce分布式环境下大图数据查询方法。该方法的设计 主要包括如下三方面的内容：描述性图查询语言的设计、描述性查询语言执行计划的产生和 描述性查询语言执行计划的优化。

本发明利用目前已有的相对成熟的MapReduce分布式计算框架对大图数据进行查询，针 对已有大图数据管理系统要求用户具备较强专业知识以及现有MapReduce框架下大图数据查 询性能难以满足应用需求等问题，本发明提出一种基于Datalog的分布式环境下大图数据查 询方法，其步骤包括：

1）对用户输入的大图查询指令进行语法分析，产生对应的语法树；所述查询指令基于 Datalog规则；

2）根据所述语法树，建立Datalog查询规则的执行操作，基于每个Datalog规则将查询 转换为Map和Reduce函数中对应的执行操作；

2-1）在语法树中基于当前的图结点集合和边集合，导出新的结点集合；

2-2）对所述新结点进行递归操作，所述递归Datalog规则设定查询时递归操作终止条件， 所述Datalog规则支持聚集函数；

3）根据MapReduce中的等价规则和查询统计数据，执行Map和Reduce函数中操作指令， 完成查询，将查询得到的结果回传至用户。

将Datalog查询规则转换为初始执行、循环终止判定和循环内操作，所述循环终止判定 和循环内操作对应递归查询；所述初始执行操作设定查询的类型和起、终点；所述循环终止 判定操作根据查询终止条件和代价模型查询请求；所述循环内操作进行图上每一层的递归操 作。

对每个Datalog查询规则，将其转换到由关系代数的选择、连接、投影、聚集操作的基 本操作组成的查询规则，并将所述关系代数基本操作翻译为Map和Reduce函数。

初始执行后，每次递归操作处理上一层递归变化的部分；获取递归操作中导出视图的每 一层出现的新数据。

对于产生的Map和Reduce执行函数，循环递归操作出现聚集函数时，通过Hadoop中 Counter机制，来产生下一轮规则中的所需要的聚集函数值。

所述Datalog规则的查询转换为Map和Reduce函数中对应的执行操作时，若一个规则对 应的关系代数计划需要选择和连接操作，可以将选择和连接放入一个MapReduce函数中，选 择的逻辑操作在MapReduce函数的Map端函数完成。

所述Datalog规则的查询转换为Map和Reduce函数中对应的执行操作时，当进行聚集函 数后，实现连接操作，可以将聚集函数和连接操作放入一个MapReduce函数中，聚集函数的 逻辑操作在Reduce端函数完成。

在所述递归Datalog规则中，针对连接操作，根据图的统计信息和运行数据的统计信息， 选择Map端连接或Reduce端连接实现方式。

所述查询终止条件首先执行，判断查询结果是否为空。

所述Map和Reduce函数中执行操作指令在时，将任务的输出作下一轮递归操作的输入； 循环终止条件在执行MapReduce任务时，根据循环条件决定是否进入下一轮递归循环操作。

本发明的有益效果：

1）为了简化最终用户编写图查询脚本的代价，本发明提出了扩展的递归DataLog查询， 支持用户使用简单的描述性语言来表达对应大图查询。

2)本发明提出了递归Datalog查询的MapReduce环境执行计划的构建方法，使得Datalog 图查询能够在MapReduce框架下执行。

3）本发明提出了递归Datalog查询执行计划利用等价规则和统计数据，实现规则间优化、 规则内优化、操作函数的优化，提高大图查询执行计划的效率。

附图说明

图1是本发明基于Datalog的分布式环境下大图数据查询方法的系统框架图。

图2是本发明基于Datalog图查询的基本执行计划示意图。

图3是本发明基于Datalog的分布式环境下大图数据查询方法实施例中循环内Datalog 规则生成对应的MapReduce任务示意图。

图4是本发明基于Datalog的分布式环境下大图数据查询中图查询语言执行计划优化框 架图。

图5是本发明基于Datalog的分布式环境下大图数据查询方法的实施例中针对循环内 Datalog规则优化的MapReduce任务示意图。

具体实施方法

下面说明具体实现步骤和详细方法。

本实施方法是在Hadoop平台上进行的，主要针对描述性查询语言的设计、执行计划的构 建以及查询执行优化等问题进行考虑。这里首先给出整个发明的设计架构图，并且说明框架 各部分负责的内容，接着详细说明本发明特有模块的设计以及实现方式。

本发明的方法要求在Hadoop上高效地对大图数据进行管理，要求为最终用户提供描述性 的查询语言，要求尽可能优化描述性查询的执行和优化。针对上述要求，本发明提出了如图 1所示的系统框架，从图1中可以看出，本方法基于MapReduce框架的开源实现Hadoop系 统，实现描述性图查询的解析、优化、执行等。

1.1描述性图查询语言

描述性图查询语言可以简化用户编写大图数据处理脚本的代价，同时为后续的查询优化 提供基础。本发明采用基于递归Datalog的图描述性查询语言，抽象图代数系统的基本操作， 作为Datalog语言的操作原语，并通过Datalog语言的递归机制表达图查询中的循环迭代。

这个图查询语言的基本描述如下：

1）整个Datalog查询分为两部分，一个是查询规则集合，一个是查询终止条件。查询规 则符合标准的Datalog规则的要求，(具体可参见参考文献【4】

Serge Abiteboul,Richard Hull,and Victor Vianu.Foundations of Databases. http://webdam.inria.fr/Alice/.)。本发明中Datalog查询将在系统支持函数、终止条件方面进行 扩展。

2）整个查询的数据基础是结点集合或者是结点序列的集合。产生对应的语法树，基于目 前的图结点集合和边集合，导出新的结点集合。新的结点集合中的属性和查询目标相关。

3）查询规则是一个Datalog规则，包括规则头和规则体，基本思路是基于规则体中的基 本关系或者导出视图得到规则头中的另一个导出视图。在规则体和规则头中，支持聚集函数， 或者分组聚集函数。

3.1）如果是递归的操作，系统默认为是按照层次执行。初始化执行后，每次递归操作仅 仅处理上一层递归变化的部分。

3.2）系统提供Datalog查询过程中分层执行过程中，针对递归导出视图的每一层出现的新 的数据集合和全部数据集合的获取。

4）查询终止条件使用一个Datalog规则，并通过Exist函数判定导出视图是否为空作为循 环的终止判定。

本发明用两个例子说明这两个语言，包括

1）判定a和b是否可达

Reach(y):-edge(x,y),x=a

Reach(z):-reach(x),edge(x,z)

终止条件Exists(Result(z):-Reach(z),z=b)

对上述查询例子的解释：终止条件Exists(Result(b):-Reach(z),z=b)含义是首先执行 Result(z):-Reach(z),z=b这个Datalog查询规则，其导出视图为Result(z)。Exists判定Result(z) 是否为空。

2）获取a和b之间的最短路

Path(y，x,cost):-Edge(x,y，cost),x=a

Path(y，(pre,min(cost))):-Path(x,pre1,cost1),edge(x,y，cost2),cost=cost1+cost2,pre=pre1+x

终止条件：Exists(Result(x,pre,cost):-Path(x,pre,cost),x=b,cost<min(Path,cost,Last))

对上述查询例子的解释：第二个表达式中,Path(y，(pre,min(cost)))表示按照y分组，求所 有路径的最小cost值min(cost),同时保存最小cost值和其pre结点。Edge(x,y，cost)表示边的基 本表，从x结点到y结点的权重为cost。

在终止条件中，min(Path,Cost,Last)表示在Path数据集合当前最后一次(Last)扩展中，Cost 数据的最小值(Min)。Last是一个标识，表示是递归操作的当前最后一次扩展。Last的设置和 Datalog的执行相关。由于本发明Datalog是按照层次执行，所以Last就表示在Path这个导出 视图中，当前最后一次扩展变化的结点集合。

1.2图查询语言的解析器

图查询语言的Parser利用现有的解析技术如参考文献【5】（Alfred V.Aho，Monica S. Lam，Ravi Sethi and Jeffrey Ullman:Compilers:Principles,Techniques,and Tools(2nd Edition).Publisher:Prentice Hall;2 edition(September 10,2006)）将图查询语言进行语法分析， 保证所提交的图查询语言符合语法规范，同时产生对应的语法树，作为查询执行计划的基础。

1.3图查询语言执行计划的构造器

针对图查询的每个Datalog查询规则和终止规则，本发明构造其对应的执行块。每个执 行块对应一个Datalog的规则。由于Datalog规则可以等价的使用关系代数来执行（参见前述 参考文件【4】Serge Abiteboul,Richard Hull,and Victor Vianu.Foundations of Databases. http://webdam.inria.fr/Alice/.）,可以将每个Datalog规则使用关系代数中的选择、连接、投影、 聚集操作等来执行。对于每个具体的关系代数操作，有其固定的对应的MapRedue函数。

在本发明中称Datalog规则头出现的视图为导出视图。导出视图在分布式框架中对应一个 文件。导出视图中的每个数据是文件的一项，每个数据增加一个标记itr，标记这个数据在第 几次递归中被增加和处理。在第i次递归操作中，只有变化的部分才被追加到数据文件中， 这些新被追加的数据项的itr为i。如果第i次递归操作使得某些数据值发生改变，那么这新 改变的数据项的itr重新标记为i。

本发明举例说明图查询语言在MapReduce分布式环境下的翻译工作。针对最短路查询的 例子，本发明在构造递归执行计划:

图2是经过语法分析后，最短路径Datalog查询翻译之后的结果。执行计划包括三个执行 块，初始执行、循环终止判定和循环内操作。每个执行块都是由关系代数基本操作来实现。 本发明可以用MapReduce实现关系代数的基本操作

图3是针对图2执行计划中循环内规则翻译得到的关系代数基本操作和对应的 MapReduce函数的示意。以Path(x,pre1,cost1,itr)和edge(x,y，cost2)的连接操作为例，本发明启 动右子图下面那个MapReduce函数。在Map函数中，对于导出视图Path(x,pre1,cost1,itr)按照 x为键，判定其扩展次数itr，假定是新扩展访问的点(其itr和递归次数i等价)，直接输出， 对于基本表Edge(x,y，cost2)按照x为键，直接输出。在Reduce函数中，得到Path(x,pre1,cost1， itr)的数据项和边Edge(x,y，cost2)，新的pre数据项设置为pre+x，新的cost设置为cost1+cost2， 新的扩展标记itr设置为itr+1,按照y为键进行输出。右子图上图描述了按照y为键，获得不 同y结点路径代价cost最小值的MapReduce函数。

通过按照图2的执行流程，每个执行块执行对应的MapReduce任务，任务的输出作为文 件写回存储单元，作为下一轮递归操作的输入。循环终止块执行MapReduce任务，判定循环 条件是否终止。如果没有终止，则进入下一轮递归循环操作。

1.5图查询语言执行计划的优化器

给定一个Datalog的图查询执行计划，本发明的优化分为三大类：规则间的优化、规则 内的优化、操作符号的优化。如图4所示，这些优化源于某些MapReduce函数的等价规则。 某些优化策略需要图数据自身和运行数据的各类统计数据。

规则间的优化：如果聚集函数出现在递归规则中，一种方式是对这个聚集函数启动一次 MapReduce任务，这种方式处理代价较高。针对这一情况，本发明可以在循环中通过Hadoop 的Counter机制，来产生下一轮规则中的所需要的聚集函数值。

规则内的优化：基本思想就是通过等价性，来减少翻译之后的MapReduce任务。例如， 如果一个规则对应的关系代数计划需要选择和连接操作，查询计划中包含针对选择和连接各 自产生MapReduce函数。优化策略不必为选择单独产生一个MapReduce函数，而是将选择 和连接放入一个MapReduce函数中，选择的逻辑在MapReduce函数的Map端完成。再比如， 如果本发明聚集函数之后，实现连接操作，本发明也不需要针对聚集函数单独设置MapReduce 函数，而是将聚集函数和连接操作放入一个MapReduce函数中，聚集函数的逻辑在Reduce 端完成。

以图3翻译之后的MapReduce函数为例，直接翻译将产生二个MapReduce任务，其中 第二个MapReduce任务就是对y变量获取其最小值的聚集函数操作。由于下一轮操作是以y 为连接元素实现扩展表和边表的连接，那么，可以将上述两个MapReduce函数简化为一个函 数。以图5下侧的MapReduce为例，在Map函数中，输出导出视图Path(x,pre1,cost1,itr)的数 据项和边的集合，针对同一个x的不同示例，在reduce函数中首先计算其最小值，判定最小 值是否是最新扩展发现的(根据itr标记)。如果是，则根据这条最新发现的代价最小的路径和 边的信息进一步扩展x邻接结点的路径。

第三类的优化是操作符号的优化：在递归Datalog规则中，非常核心的操作是连接操作， 就是结点集合和边集合之间的连接。在这一步骤中，可以使用现有连接操作的各种可能实现， 如Map端连接和Reduce端连接等。具体选择何种实现方法依赖于对于图的统计信息和运行 数据的统计信息（可以采用参考文献【3】Ashish Thusoo,Joydeep Sen Sarma,Namit Jain,Zheng  Shao,Prasad Chakka,Ning Zhang,Suresh Anthony，Hao Liu,Raghotham Murthy:Hive-a petabyte scale data warehouse using Hadoop.ICDE 2010:996-1005中的方法）。