Querying graphs and conducting graph analytics become important in data processing since many real applications are dealing with massive graphs, such as online social networks, Semantic Web, knowledge graphs, etc. Over the years, many distributed graph processing systems have been developed to support graph analytics using various programming models, and many graph querying languages have been proposed. A natural question that arises is how to integrate graph data and traditional non-graph data in a distributed system for users to conduct analytics. There are two issues. One issue is related to expressiveness on how to specify graph analytics as well as data analytics by a querying language. The other issue is related to efficiency on how to process analytics in a distributed system. For the first issue, <italic>SQL</italic> is a best candidate, since <italic>SQL</italic> is a well-accepted language for data processing. We concentrate on <italic>SQL</italic> for graph analytics. Our early work shows that graph analytics can be supported by <italic>SQL</italic> in a way from “semiring + while” to “relational algebra + while” via the enhanced recursive <italic>SQL</italic> queries. In this article, we focus on the second issue on how to process such enhanced recursive <italic>SQL</italic> queries based on the <italic>GAS</italic> (<italic>Gather</italic>-<italic>Apply</italic>-<italic>Scatter</italic>) model under which efficient graph processing systems can be developed. To demonstrate the efficiency, we implemented a system by tightly coupling <italic>Spark</italic> <italic>SQL</italic> and <italic>GraphX</italic> on <italic>Spark</italic> which is one of the most popular in-memory data-flow processing platforms. First, we enhance <italic>Spark</italic> <italic>SQL</italic> by adding the capability of supporting the enhanced recursive <italic>SQL</italic> queries for graph analytics. In this regard, graph analytics can be processed using a distributed <italic>SQL</italic> engine alone. Second, we further propose new transformation rules to optimize/translate the operations for recursive <italic>SQL</italic> queries to the operations by <italic>GraphX</italic>. In this regard, graph analytics by <italic>SQL</italic> can be processed in a similar way as done by a distributed graph processing system using the APIs provided by the system. We conduct extensive performance studies to test graph analytics using large real graphs. We show that our approach can achieve similar or even higher efficiency, in comparison to the built-in graph algorithms in the existing graph processing systems.
Paper
Full text
SQL-G: Efficient Graph Analytics by SQL
Semantic Scholar · Computer Science · 2021
Abstract
Querying graphs and conducting graph analytics become important in data processing since many real applications are dealing with massive graphs, such as online social networks, Semantic Web, knowledge graphs, etc. Over the years, many distributed graph processing systems have been developed to support graph analytics using various programming models, and many graph querying languages have been proposed. A natural question that arises is how to integrate graph data and traditional non-graph data in a distributed system for users to conduct analytics. There are two issues. One issue is related to expressiveness on how to specify graph analytics as well as data analytics by a querying language. The other issue is related to efficiency on how to process analytics in a distributed system. For the first issue, <italic>SQL</italic> is a best candidate, since <italic>SQL</italic> is a well-accepted language for data processing. We concentrate on <italic>SQL</italic> for graph analytics. Our early work shows that graph analytics can be supported by <italic>SQL</italic> in a way from “semiring + while” to “relational algebra + while” via the enhanced recursive <italic>SQL</italic> queries. In this article, we focus on the second issue on how to process such enhanced recursive <italic>SQL</italic> queries based on the <italic>GAS</italic> (<italic>Gather</italic>-<italic>Apply</italic>-<italic>Scatter</italic>) model under which efficient graph processing systems can be developed. To demonstrate the efficiency, we implemented a system by tightly coupling <italic>Spark</italic> <italic>SQL</italic> and <italic>GraphX</italic> on <italic>Spark</italic> which is one of the most popular in-memory data-flow processing platforms. First, we enhance <italic>Spark</italic> <italic>SQL</italic> by adding the capability of supporting the enhanced recursive <italic>SQL</italic> queries for graph analytics. In this regard, graph analytics can be processed using a distributed <italic>SQL</italic> engine alone. Second, we further propose new transformation rules to optimize/translate the operations for recursive <italic>SQL</italic> queries to the operations by <italic>GraphX</italic>. In this regard, graph analytics by <italic>SQL</italic> can be processed in a similar way as done by a distributed graph processing system using the APIs provided by the system. We conduct extensive performance studies to test graph analytics using large real graphs. We show that our approach can achieve similar or even higher efficiency, in comparison to the built-in graph algorithms in the existing graph processing systems.