Time Complexity and Parallel Speedup of Relational Queries to Solve Graph Problems

Nowadays parallel DBMSs compete with graph Hadoop Big Data systems to analyze large graphs. In this paper, we study the processing and optimization of relational queries to solve fundamental graph problems, giving a theoretical foundation on time complexity and parallel processing. Specifically, we consider reachability, shortest paths from a single vertex, weakly connected components, PageRank, transitive closure and all pairs shortest paths. We explain how graphs can be stored on a relational database and then we show relational queries can be used to efficiently analyze such graphs. We identify two complementary families of algorithms: iteration of matrix-vector multiplication and iteration of matrix-matrix multiplication. We show all problems can be solved with a unified algorithm with an iteration of matrix multiplications. We present intuitive theory results on cardinality estimation and time complexity considering graph size, shape and density. Finally, we characterize parallel computational complexity and speedup per iteration, focusing on joins and aggregations.