In-memory processing of unbounded recursive graph queries in relational databases

Abstract

A computer-implemented method includes receiving a graph pattern matching query, determining that the query is an unbounded recursive path query (RPQ), and initializing an unbounded root vertex match operator (UBRM) using a starting vertex as input to the UBRM; the UBRM is configured to compute multiple hops between vertices on the graph. The method also includes performing a first reachability search using the UBRM; the UBRM traverses the graph to identify all vertices reachable from the starting vertex. The method further includes generating first level vertices of a path pattern that computes the RPQ; and adding the first level vertices to a first level context for processing by a successor match operator; the successor match operator comprises an unbounded intermediate neighbor match operator (UBNM), the UBNM is configured to compute multiple hops between vertices on the graph and to identify neighbors for each of the first level vertices.