Unbounded Regular Path Queries In SQL

Abstract

A relational database system compiles and executes unbounded regular path queries (RPQs). A compilation stage splits the unbounded RPQ query in three portions: the prefix, the recursion, and the suffix. The compilation stage generates a relational execution tree. The recursive portion of the query is compiled using a specialized algorithm via an inline graph algorithm function (GAF) framework. The compilation stage generates a GAF node in the relational execution tree having a left child that is the specialized algorithm and a right child that is the suffix portion. The compilation stage generates a NESTED LOOPS join node in the relational execution tree having a left child that is the prefix portion and a right child that is the GAF node. The suffix portion uses results of the specialized algorithm. The values from the prefix portion and the suffix portion are concatenated by using the current semantics of NESTED LOOPS join.

What is claimed is: 
     
         1 . A method comprising:
 a relational database system compiling an unbounded regular path graph query into a relational execution tree, wherein:
 the unbounded regular path graph query is issued against a graph having vertices and edges stored in a plurality of tables, and 
 compiling the unbounded regular path graph query comprises:
 splitting the unbounded regular path graph query into a prefix portion, a recursive portion, and a suffix portion; 
 generating a graph algorithm function (GAF) node for the recursive portion in the relational execution tree; 
 generating a nested loops join node in the relational execution tree, wherein:
 the nested loops join node has a left child comprising the prefix portion and a right child comprising the GAF node, and 
 the GAF node has a left child comprising a recursive graph algorithm and a right node comprising the suffix portion; and 
 
 
   the relational database system executing the relational execution tree, wherein executing the relational execution tree generates a result for the unbounded regular path graph query,   wherein the method is performed by one or more computing devices.   
     
     
         2 . The method of  claim 1 , wherein compiling the unbounded regular path graph query further comprises:
 determining a set of one or more prefix specializations for the prefix portion of the unbounded regular path graph query;   determining a transitive closure of reachable vertex and edge tables for the one or more prefix specializations; and   determining a set of one or more suffix specializations for the suffix portion of the unbounded regular path graph query based on the transitive closure of reachable vertex and edge tables.   
     
     
         3 . The method of  claim 2 , wherein the transitive closure is used to reduce the set of vertex and edge tables considered in the recursive graph algorithm. 
     
     
         4 . The method of  claim 2 , wherein compiling the unbounded regular path graph query further comprises translating the set of one or more prefix specializations and the set of one or more suffix specializations to SQL. 
     
     
         5 . The method of  claim 1 , wherein executing the relational execution tree comprises:
 executing the prefix portion to generate a set of prefix result rows, wherein each row in the set of prefix result rows represents a pattern in the graph that matches the prefix portion of the unbounded regular path graph query;   executing the nested loops join node by:
 fetching a given row from the set of prefix result rows; 
 calling the GAF node to execute the recursive graph algorithm based on a starting vertex from the given row to generate a set of recursive graph algorithm result rows, wherein each row in the set of recursive graph algorithm result rows represents a vertex that is reachable from the starting vertex and matches a starting vertex of the suffix portion, and to execute the suffix portion to generate a set of GAF result rows; 
 fetching the set of GAF result rows; and 
 performing a join of the set of prefix result rows and the set of GAF result rows. 
   
     
     
         6 . The method of  claim 5 , wherein:
 the graph comprises one or more vertex tables,   each execution of the recursive graph algorithm generates a side table for each of the one or more vertex tables to form one or more side tables, and   executing the suffix portion reads from the one or more side tables for path and destination information.   
     
     
         7 . The method of  claim 6 , wherein the one or more side tables comprise one or more cursor duration temporary tables (CDTs). 
     
     
         8 . The method of  claim 6 , wherein executing the suffix portion comprises one or more joins between the one or more side tables and vertex or edge tables of the graph. 
     
     
         9 . The method of  claim 6 , wherein each of the one or more side tables stores a row for each step in a path that reaches a destination vertex from the starting vertex. 
     
     
         10 . The method of  claim 9 , wherein:
 each row of a given side table stores path information comprising a property value of a vertex or edge for a corresponding step, and   the suffix portion performs an aggregation of the property values of the steps of a path from the starting vertex to the destination vertex.   
     
     
         11 . The method of  claim 6 , wherein the unbounded regular path graph query is a reachability query and wherein each of the one or more side tables stores a row for each destination vertex that is reachable from the starting vertex. 
     
     
         12 . The method of  claim 5 , wherein:
 the graph is homogeneous,   each execution of the recursive graph algorithm generates a row-source,   executing the nested loops join node further comprises executing the suffix portion, and   executing the suffix portion reads from the row-source for path and destination information.   
     
     
         13 . The method of  claim 1 , wherein the unbounded regular path graph query is a shortest path query and wherein the recursive graph algorithm is a breadth first search (BFS) algorithm. 
     
     
         14 . The method of  claim 13 , wherein the BFS algorithm performs batch expand by expanding more than one vertex in each query. 
     
     
         15 . The method of  claim 1 , wherein the unbounded regular path graph query is a cheapest path query and wherein the recursive graph algorithm is a Dijkstra algorithm. 
     
     
         16 . One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause:
 a relational database system compiling an unbounded regular path graph query into a relational execution tree, wherein:
 the unbounded regular path graph query is issued against a graph having vertices and edges stored in a plurality of tables, and 
 compiling the unbounded regular path graph query comprises:
 splitting the unbounded regular path graph query into a prefix portion, a recursive portion, and a suffix portion; 
 generating a graph algorithm function (GAF) node for the recursive portion in the relational execution tree; 
 generating a nested loops join node in the relational execution tree, wherein:
 the nested loops join node has a left child comprising the prefix portion and a right child comprising the GAF node, and 
 the GAF node has a left child comprising a recursive graph algorithm and a right node comprising the suffix portion; and 
 
 
   the relational database system executing the relational execution tree, wherein executing the relational execution tree generates a result for the unbounded regular path graph query.   
     
     
         17 . The one or more non-transitory storage media of  claim 16 , wherein compiling the unbounded regular path graph query further comprises:
 determining a set of one or more prefix specializations for the prefix portion of the unbounded regular path graph query;   determining a transitive closure of reachable vertex and edge tables for the one or more prefix specializations; and   determining a set of one or more suffix specializations for the suffix portion of the unbounded regular path graph query based on the transitive closure of reachable vertex and edge tables.   
     
     
         18 . The one or more non-transitory storage media of  claim 16 , wherein executing the relational execution tree comprises:
 executing the prefix portion to generate a set of prefix result rows, wherein each row in the set of prefix result rows represents a pattern in the graph that matches the prefix portion of the unbounded regular path graph query;   executing the nested loops join node by:
 fetching a given row from the set of prefix result rows; 
 calling the GAF node to execute the recursive graph algorithm based on a starting vertex from the given row to generate a set of recursive graph algorithm result rows, wherein each row in the set of recursive graph algorithm result rows represents a vertex that is reachable from the starting vertex and matches a starting vertex of the suffix portion; 
 fetching the set of recursive graph algorithm result rows; and 
 performing a join of the set of prefix result rows and the set of recursive graph algorithm result rows. 
   
     
     
         19 . The one or more non-transitory storage media of  claim 18 , wherein:
 the graph comprises one or more vertex tables,   each execution of the recursive graph algorithm generates a side table for each of the one or more vertex tables to form one or more side tables, and   executing the suffix portion reads from the one or more side tables for path and destination information.   
     
     
         20 . The one or more non-transitory storage media of  claim 18 , wherein:
 the graph is homogoneous,   each execution of the recursive graph algorithm generates a row-source,   executing the nested loops join node further comprises executing the suffix portion, and   executing the suffix portion reads from the row-source for path and destination information.