Uni ed Algorithm to Solve several Graph Problems with Relational Queries

Abstract

Several important graph algorithms can be solved as an iteration of vector-matrix multiplication over di erent semirings. On this basis, we show that the Bellman-Ford (single source shortest paths), reachability, PageRank, and topological sort algorithms can be expressed as relational queries, to solve analytic graph problems in relational databases. As a main contribution, we present a general algorithm that uni es all graph algorithms aforementioned.

Introduction

Graph Dataset Let G = (V; E) be a directed graph, where V is a set of vertices and E is a set of edges, considered as an ordered pairs of vertices. Let n = jV j vertices and m = jEj edges. An edge (i; j) in E links two vertices in V and has a direction. We use E to name both the set of edges of G as well as the adjacency matrix, depending on the context. In general, real-life graphs are sparse. Therefore, it is reasonable to store the adjacency matrix E in a sparse representation, which saves both computing, memory and storage resources. Several methods to represent sparse matrices are well known, and the interested reader may check [ 1 ]. In our work, the adjacency matrix of a graph G is stored in a table E(i; j; v), with primary key (i; j). The sparse matrix representation avoids storing zeroes. Thus, the space required for table E is O(m), much smaller than the space necessary in the dense representation, O(n2).

We consider a matrix sparse when the number of non-zero cells is O(n). Likewise, we consider a graph as sparse when the number of edges is O(n). Certain classes of graph are clearly sparse. For instance, both trees and spanning trees are graphs where m = n 1. Many graph problems are solved computing powers of E. For large graphs computing such powers is challenging; even if E is a sparse graph, it is possible that after k multiplications by itself, the number of non-zero entries increases to O(n2). Thus, Ek is not necessarily sparse. Matrix Multiplication and Semirings Semirings are algebraic structures consisting of a set R, an additive operator with identity element 0, a product operator with identity element 1, and commutative, associative and distributive properties holding for the two operators in the usual manner, succinctly represented as (R; ; ; 0; 1). For instance, the regular matrix multiplication is de ned under (R; +; ; 0; 1). A general de nition of matrix multiplication expands it to any semiring. On the min-plus semiring, also known as "tropical semiring", min is the additive operator , and + is the product operator . The min-plus semiring is used to solve shortest path problems, as in [ 2 ]. The boolean semiring, with _ (logical OR) as operator and _ (logical OR) as operator, is used frequently in linear algebra to represent some graph algorithms. 3

Graphs Algorithms computed with Relational Queries We use as starting point known linear algebra approaches for Bellman-Ford, reachability and PageRank, as well as a novel way to express Topological Sort with matrix operations. On this foundation, we will show how all these algorithms can be expressed as relational queries. As is already known, BellmanFord and reachability can be solved by powers of the adjacency matrix and a vector-matrix multiplication. Topological sort also can be solved in the same manner, as we will show shortly. Likewise, PageRank can be solved by powers of the transition matrix. These four algorithms can be solved in a general way by Equation 1:

Sk = S0 Ek = S0 E

E ::: (1) where S0 stores the initial state and Sk stores the nal result. The last iteration is k. Instead of solving Ek, it is more e cient to compute Sk with iterative vector-matrix products: Sd Sd 1 E for d = 1 : : : k. Algorithms are below. Bellman-Ford: Shortest paths from a source s. Initialization: S0[i] = 0 if i = s; 1 otherwise. After k successive vector matrix multiplications (under the min + semiring), the vector Sk contains the minimun distance from s to every vertex. Reachability: Initialization: S0[i] = 0 if i = s, 0 otherwise. Vector matrix multiplications are computed under the natural numbers semiring. At iteration d, Sd[i] contains 1 if there exists a path of length d from the s to the vertex i. PageRank: It is well known that PageRank can be computed as powers of a modi ed transition matrix [ 4 ]. Since PageRank is conceived as a Markov process, it can be computed as an iterative process that stops when the Markov chain stabilizes. Let S0[i] = 1=n. The transition matrix T is de ned as Ti;j = Ej;i=outdeg(j) when Ej;i = 1; otherwise Ti;j = 0. Let A be a n n matrix, whose cells contain always 1=n, and 0 < p < 1 the damping factor; let T 0 = T + D , where D is a matrix such that Di;j = 1=n if the column j is a 0 column. The power method can be applied on T 00 de ned as: T 00 = (1 p)T 0 + pA, computing Sd Sd 1 T " iteratively, from d = 1 until stabilization of the Markov chain. Topological Sort: Sd holds the relative ordering for the vertices, and Sd[j] = 0 when the relative order of j is not yet determined. Initialization: S0[j] = 1 if outdeg(j) = 0, otherwise S0[j] = 1. The algorithm can be outlined in this manner: For each vertex j 2 Sd 1, nd every father vertex such that 8i successor of ; i 2 S, and let Sd[ ] = 1. Repeat the process until 8i 2 V , S[i] 6= 0. The topological order is given by S0 + S1 + :::Sk. This algorithm can be expressed as in Equation 1, where Sk is solved with iterative vector-matrix multiplication. In this case, the operation is the logical AND: ^, and the is the logical implication ). As result of the vector-matrix multiplication, Sd[j] = 1 if for all j0 successors of j , Sd[j0] = 1. Although the operators ^ and ) cannot comprise a semiring (the commutative property for ) does not hold), it is possible to express Sd E with SPJA queries, like in the previous algorithms. Considering that S and E are stored in relational tables S(j; v) and E(i; j; v), the vector-matrix product can be clearly computed with a relational query as:

S:i;E:j:sum(S:v E:v)(S ./S:j=E:i E). Table 1 shows a comparison of the properties of the four algorithms of our concern. All of them are computed by a combined else end

Rd

Sd end

f (Rd 1; Sd 1; Rd; Sd) Algorithm 1: Uni ed Algorithm

Input: Table E, S0, R0, f (); g(); ; ; unionF lag . Optional input: s (source) Output: Table Rd(j; v) d 0; 1; while > do d d + 1 ; Sd j:g()(Sd 1:v E:v)(Sd 1 ./j=i E) if unionFlag then

Rd j:sum(v)(Sd [ Rd 1) join/aggregation between S and E (or T ") as the main operation of the iteration. This SPJA query computes a vector-matrix multiplication on di erent semirings, depending on the speci c algorithm, with time complexity O(nlogn). The meaning of the value in S[i] is di erent in every case. While Bellman-Ford and reachability return results concerning an unique source vertex, topological sort and PageRank return results with respect to the entire graph. The execution time of these algorithms will depend on n and the number of iterations k. For instance, reachability may nish in less iterations than Bellman-Ford, for the same graph. It is possible to conceptualize a Uni ed Algorithm to solve these four graphs problems, as presented in Algorithm 5. The main operation remains the matrix multiplication, with parameters ; . Other input parameters are the initial vector S0. and unionFlag, wich controls if the output is Sd or the cumulative sum of S0 + S1::: + Sd. F 5

Conclusions

We demonstrate that Bellman-Ford, reachability, PageRank and Topological Sort can be expressed as an iteration of relational queries, to solve graph problems in data sets stored in databases. Based on the conceptual foundation of vector-matrix products under di erent semirings, these algorithms run as SPJA queries; they are secondary memory algorithms, not limited by the system RAM. The e ciency of our algorithms is supported by: sparse storage, which avoids wasting both space and computing time; conditions for early termination, which avoids useless iterations; and light weight relational queries. Moreover, we compared these algorithms and proposed a Uni ed Algorithm to solve them. Further research will identify and integrate into the Uni ed Algorithm more algorithms that follow the vector-matrix multiplication pattern. Besides, we will study these algorithms in large and complex graphs, especially in parallel clusters.

References

1. Z. Bai , J. Demmel , J. Dongarra , A. Ruhe , and H. van der Vorst. Templates for the solution of algebraic eigenvalue problems: a practical guide , volume 11 . Siam , 2000 .

2. T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition , 2009 .

3. A. Jindal , P. Rawlani , E. Wu, S. Madden , A. Deshpande , and M. Stonebraker . Vertexica: your relational friend for graph analytics ! Proceedings of the VLDB Endowment , 7 ( 13 ): 1669 { 1672 , 2014 .

4. S. D. Kamvar , T. H. Haveliwala , C. D. Manning , and G. H. Golub . Extrapolation methods for accelerating pagerank computations . In Proceedings of the 12th Int. Conf. on World Wide Web , pages 261 { 270 . ACM, 2003 .

5. C. Ordonez , W. Cabrera , and A. Gurram . Comparing columnar, row and array DBMSs to process recursive queries on graphs . Information Systems , pages {, 2016 .

6. N. Yakovets , P. Godfrey , and J. Gryz . Evaluation of SPARQL property paths via recursive SQL . In Proc. AMW , 2013 .