文章基本信息

标题：Graph Processing in RDBMSs
本地全文：下载
作者：Kangfei Zhao ; Jeffrey Xu Yu
期刊名称：Bulletin of the Technical Committee on Data Engineering
出版年度：2017
卷号：40
期号：3
页码：6
出版社：IEEE Computer Society
摘要：To support analytics on massive graphs such as online social networks, RDF, Semantic Web, etc. manynew graph algorithms are designed to query graphs for a specific problem, and many distributed graphprocessing systems are developed to support graph querying by programming. A main issue to be addressedis how RDBMS can support graph processing. And the first thing is how RDBMS can supportgraph processing at the SQL level. Our work is motivated by the fact that there are many relations storedin RDBMS that are closely related to a graph in real applications and need to be used together to querythe graph, and RDBMS is a system that can query and manage data while data may be updated overtime. To support graph processing, we propose 4 new relational algebra operations, MM-join, MV-join,anti-join, and union-by-update. Here, MM-join and MV-join are join operations between two matricesand between a matrix and a vector, respectively, followed by aggregation computing over groups, givena matrix/vector can be represented by a relation. Both deal with the semiring by which many graphalgorithms can be supported. The anti-join removes nodes/edges in a graph when they are unnecessaryfor the following computing. The union-by-update addresses value updates to compute PageRank, forexample. The 4 new relational algebra operations can be defined by the 6 basic relational algebra operationswith group-by & aggregation. We revisit SQL recursive queries and show that the 4 operationswith others are ensured to have a fixpoint, following the techniques studied in DATALOG, and we enhancethe recursive with clause in SQL’99. RDBMSs are capable of dealing with graph processing inreasonable time.