Large-scale graph data query method in distributed environment based on Datalog

Abstract

The invention discloses a large-scale graph data query method in a distributed environment based on Datalog. The method comprises the following steps of: 1) performing grammatical analysis on a large-scale graph query instruction based on a Datalog rule set input by a user, and producing a corresponding grammatical tree; 2) constructing an execution plan in which a Datalog rule is used as a unit according to the grammatical tree, and constructing a corresponding Map execution function and a Reduce execution function according to each Datalog rule; and 3) implementing inter-rule optimization, inner-rule optimization and operation function optimization by using an equivalence rule and statistical data, and improving the efficiency of a large-scale graph query execution plan. By the large-scale graph data query method, the cost that a final user writes a graph query script is simplified; expanded recursion Daralog query is provided; and the user can express the corresponding large-scale graph query by using a simple description language. The invention also provides a method for constructing a MapReduce environment execution plan for recursion Daralog query. Datalog graph query can be executed under a MapReduce framework.

Description

technical field [0001] The invention specifically relates to querying large-scale data in a distributed environment, in particular to a method for querying large-scale data in a distributed environment based on Datalog, and belongs to the field of information technology. Background technique [0002] In modern society, graphs are used more and more widely. The rapid development of technologies in the fields of social networks, bioinformatics, and traffic navigation has produced large-scale graph data. How to effectively manage these large-scale data faces many challenges: First, the traditional stand-alone computing model is difficult to support the management of large-scale data, and the storage capacity of a single-machine is limited, so it is difficult to load the entire large-scale data into memory. The processing capability of large graph data is also insufficient, and it is difficult to effectively support various complex operations on large graph data; secondly, the ...

AI Technical Summary

Problems solved by technology

[0007] The present invention aims at using the existing relatively mature MapReduce distributed computing framework to query large-scale data, and aims at the problems that the query performance of large-scale data under the existing framework is difficult to meet the application requirements, and the user's writing of graph data processing scripts is cumbersome and inefficient. A Datalog-based method for large-scale data query in MapReduce distributed environment

[0008] The present invention uses the existing relatively mature MapReduce distributed computing framework to query large-scale data, and the existing large-scale data management system requires users to have strong professional knowledge and the query performance of large-scale data under the existing MapReduce framework is difficult to meet In order to solve problems such as application requirements, the present invention proposes a large-scale data query method in a distributed environment based on Datalog, the steps of which include:

Images