Methods, systems, and media for resolving database queries using algebraic expressions using matrix-matrix multiplication

Abstract

Method, systems, and media for resolving a database query are provided, comprising: identifying a connected component in a query graph corresponding to the database query; determining a longest path length for the connected component; selecting a path having the longest path length; building an algebraic expression for the path; solving the algebraic expression using matrix-matrix multiplication to provide a solution; and responding to the query based on the solution.

1 . A method for resolving a database query comprising:
 building an algebraic expression for a path having a longest path length for a connected component in a query graph corresponding to the database query;   solving the algebraic expression using matrix-matrix multiplication to provide a solution; and   responding to the query based on the solution,   wherein building the algebraic expression for the path comprises:
 creating an expression that is empty; 
 for each edge on the path:
 if the source node is labelled, getting a label matrix represented by the source node and add the label matrix as a right-most operand of the expression; 
 retrieving a representation type matrix represented by the source node; and 
 adding the representation type matrix as a right-most operand of the expression; 
 
 for a last edge on the path, if the destination node of the last edge is labelled, adding a label matrix of the destination node of the last edge to the right-most operand of the expression; and 
 setting a source node of the expression to a first node of the path and a destination node of the expression to a last node of the path. 
   
     
     
         2 . The method of  claim 1 , further comprising:
 for each edge on the path when building the algebraic expression for the path, if the edge is reversed, swapping a designation of a source node for the edge and a designation of a destination node for the edge.   
     
     
         3 . The method of  claim 1 , further comprising:
 for each edge on the path when building the algebraic expression for the path, if the edge is reversed, transposing the representation type matrix.   
     
     
         4 . The method of  claim 1 , further comprising dividing the query graph into a plurality of connected components which includes the connected component. 
     
     
         5 . The method of  claim 1 , wherein the connected component is a disjoint search pattern. 
     
     
         6 . The method of  claim 1 , wherein the connected component has a length greater than or equal to any other connected component in the query graph. 
     
     
         7 . The method of  claim 1 , wherein the longest path length is a path length that is larger than any other path length for the query graph, and the path length is a count of consecutive edges traversed in the query graph without revisiting a node. 
     
     
         8 . The method of  claim 1 , further comprising removing from the connected component: all edges of the path; and then any nodes in the path that have no remaining connected edges. 
     
     
         9 . A system for resolving a database query comprising:
 a memory;   at least one hardware processor coupled to the memory and collectively configured to at least:
 build an algebraic expression for a path having a longest path length for a connected component in a query graph corresponding to the database query; 
 solve the algebraic expression using matrix-matrix multiplication to provide a solution; and 
 respond to the query based on the solution, 
 wherein building the algebraic expression for the path comprises:
 creating an expression that is empty; 
 for each edge on the path:
 if the source node is labelled, getting a label matrix represented by the source node and add the label matrix as a right-most operand of the expression; 
 retrieving a representation type matrix represented by the source node; and 
 adding the representation type matrix as a right-most operand of the expression; 
 
 for a last edge on the path, if the destination node of the last edge is labelled, adding a label matrix of the destination node of the last edge to the right-most operand of the expression; and 
 setting a source node of the expression to a first node of the path and a destination node of the expression to a last node of the path. 
 
   
     
     
         10 . The system of  claim 9 , wherein the at least one hardware processor is also collectively configured to:
 for each edge on the path when building the algebraic expression for the path, if the edge is reversed, swapping a designation of a source node for the edge and a designation of a destination node for the edge.   
     
     
         11 . The system of  claim 9 , wherein the at least one hardware processor is also collectively configured to:
 for each edge on the path when building the algebraic expression for the path, if the edge is reversed, transposing the representation type matrix.   
     
     
         12 . The system of  claim 9 , wherein the at least one hardware processor is also collectively configured to divide the query graph into a plurality of connected components which includes the connected component. 
     
     
         13 . The system of  claim 9 , wherein the connected component is a disjoint search pattern. 
     
     
         14 . The system of  claim 9 , wherein the connected component has a length greater than or equal to any other connected component in the query graph. 
     
     
         15 . The system of  claim 9 , wherein the longest path length is a path length that is larger than any other path length for the query graph, and the path length is a count of consecutive edges traversed in the query graph without revisiting a node. 
     
     
         16 . The system of  claim 9 , wherein the at least one hardware processor is also collectively configured to remove from the connected component: all edges of the path; and then any nodes in the path that have no remaining connected edges. 
     
     
         17 . A non-transitory computer-readable medium containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method for resolving a database query, the method comprising:
 building an algebraic expression for a path having a longest path length for a connected component in a query graph corresponding to the database query;   solving the algebraic expression using matrix-matrix multiplication to provide a solution; and   responding to the query based on the solution,   wherein building the algebraic expression for the path comprises:
 creating an expression that is empty; 
 for each edge on the path:
 if the source node is labelled, getting a label matrix represented by the source node and add the label matrix as a right-most operand of the expression; 
 retrieving a representation type matrix represented by the source node; and 
 adding the representation type matrix as a right-most operand of the expression; 
 
 for a last edge on the path, if the destination node of the last edge is labelled, adding a label matrix of the destination node of the last edge to the right-most operand of the expression; and 
 setting a source node of the expression to a first node of the path and a destination node of the expression to a last node of the path. 
   
     
     
         18 . The non-transitory computer-readable medium of  claim 17 , wherein the method further comprises:
 for each edge on the path when building the algebraic expression for the path, if the edge is reversed, swapping a designation of a source node for the edge and a designation of a destination node for the edge.   
     
     
         19 . The non-transitory computer-readable medium of  claim 17 , wherein the method further comprises:
 for each edge on the path when building the algebraic expression for the path, if the edge is reversed, transposing the representation type matrix.   
     
     
         20 . The non-transitory computer-readable medium of  claim 17 , wherein the method further comprises dividing the query graph into a plurality of connected components which includes the connected component. 
     
     
         21 . The non-transitory computer-readable medium of  claim 17 , wherein the connected component is a disjoint search pattern. 
     
     
         22 . The non-transitory computer-readable medium of  claim 17 , wherein the connected component has a length greater than or equal to any other connected component in the query graph. 
     
     
         23 . The non-transitory computer-readable medium of  claim 17 , wherein the longest path length is a path length that is larger than any other path length for the query graph, and the path length is a count of consecutive edges traversed in the query graph without revisiting a node. 
     
     
         24 . The non-transitory computer-readable medium of  claim 17 , wherein the method further comprises removing from the connected component: all edges of the path; and then any nodes in the path that have no remaining connected edges.