METHODS, SYSTEMS, AND MEDIA FOR RESOLVING DATABASE QUERIES USING ALGEBRAIC EXPRESSIONS USING MATRIX-MATRIX MULTIPLICATION

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.