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

1. A method for resolving a database query 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,

wherein building the algebraic expression for the path comprises:

creating an expression that is empty;

for each edge on 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;

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;

if the edge is reversed, transposing the representation type matrix; 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 dividing the query graph into a plurality of connected components which includes the connected component.

3. The method of claim 1 , wherein the connected component is a disjoint search pattern.

4. 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.

5. 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.

6. 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.

7. A system for resolving a database query comprising:

a memory;

at least one hardware processor coupled to the memory and collectively configured to:

identify a connected component in a query graph corresponding to the database query;

determine a longest path length for the connected component;

select a path having the longest path length;

build an algebraic expression for the path;

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 edge is reversed, swapping a designation of a source node for the edge and a designation of a destination node for the edge;

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;

if the edge is reversed, transposing the representation type matrix; 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.

8. The system of claim 7 , wherein the at least one processor is also collectively configured to divide the query graph into a plurality of connected components which includes the connected component.

9. The system of claim 7 , wherein the connected component is a disjoint search pattern.

10. The system of claim 7 , wherein the connected component has a length greater than or equal to any other connected component in the query graph.

11. The system of claim 7 , 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.

12. The system of claim 7 , wherein the at least one 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.

13. 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:

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,

wherein building the algebraic expression for the path comprises:

creating an expression that is empty;

for each edge on 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;

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;

if the edge is reversed, transposing the representation type matrix; 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.

14. The non-transitory computer-readable medium of claim 13 , wherein the method further comprises dividing the query graph into a plurality of connected components which includes the connected component.

15. The non-transitory computer-readable medium of claim 13 , wherein the connected component is a disjoint search pattern.

16. The non-transitory computer-readable medium of claim 13 , wherein the connected component has a length greater than or equal to any other connected component in the query graph.

17. The non-transitory computer-readable medium of claim 13 , 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.

18. The non-transitory computer-readable medium of claim 13 , 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.