Selective use of data structure operations for path query evaluation

Patent metadata

Field	Value
Publication number	US-11704309-B2
Application number	US-202117362907-A
Country	US
Kind code	B2
Filing date	Jun 29, 2021
Priority date	Jun 29, 2021
Publication date	Jul 18, 2023
Grant date	Jul 18, 2023

Abstract

The disclosed technologies are capable of selectively using data structure operations for path query evaluation. One technique involves reading a query that traverses at least two nodes and at least one edge of a graph in a graph database; compiling the query into a set of variables and a set of constraints, where the set of variables and the set of constraints correspond to the two nodes and the one edge of the graph; creating an in-memory data structure that comprises a table; using the set of variables and the set of constraints to determine an operation that is performable using the in-memory data structure; checking for an existence of a condition relating to the in-memory data structure or the operation; skipping the operation if the condition exists or executing the operation if the condition does not exist; and storing a set of intermediate query results in the table.

First claim

What is claimed is:

1. A method comprising:
reading a query that traverses at least two nodes and at least one edge of a graph in a graph database;
compiling the query into a set of variables and a set of constraints, the set of variables and the set of constraints corresponding to the at least two nodes and the at least one edge of the graph;
creating an in-memory data structure comprising at least one table;
using the set of variables and the set of constraints, determining an operation that is performable using the in-memory data structure;
checking for an existence of a condition relating to the in-memory data structure or the operation;
if the condition exists, skipping the operation;
if the condition does not exist, executing the operation;
storing a set of intermediate query results in the at least one table;
wherein checking for the existence of the condition comprises determining whether the in-memory data structure comprises a nested disjunction that includes at least one disjunctive child table that has zero rows;
if the in-memory data structure comprises a nested disjunction that includes at least one disjunctive child table that has zero rows, the condition exists and skipping the operation comprises skipping a path consistency checking operation; and
if the in-memory data structure does not comprise a nested disjunction that includes at least one disjunctive child table that has zero rows, the condition does not exist and executing the operation comprises executing a path consistency checking operation;
wherein the method is performed by at least one computing device.

2. The method of claim 1 , wherein checking for the existence of the condition comprises determining whether a variable of the set of variables is a single row variable.

3. The method of claim 2 , wherein, if the variable is a single row variable, the condition exists and skipping the operation comprises skipping a path consistency checking operation.

4. The method of claim 3 , further comprising reading the set of intermediate query results from a data storage.

5. The method of claim 1 , wherein checking for the existence of the condition comprises determining whether a variable of the set of variables is a multi-row variable.

6. The method of claim 5 , wherein, if the variable is a multi-row variable, the condition does not exist and executing the operation comprises executing a path consistency checking operation.

7. The method of claim 6 , further comprising executing the path consistency checking operation prior to reading the set of intermediate query results from a data storage.

8. The method of claim 1 , wherein checking for the existence of the condition comprises determining whether the operation is non-selective.

9. The method of claim 8 , wherein, if the operation is non-selective, the condition exists and skipping the operation comprises skipping a table creation operation.

10. The method of claim 9 , further comprising creating an execution head without executing the table creation operation.

11. The method of claim 1 , wherein checking for the existence of the condition comprises determining whether the operation is selective.

12. The method of claim 11 , wherein, if the operation is selective, the condition does not exist and executing the operation comprises executing a table creation operation.

13. The method of claim 12 , further comprising creating an execution head prior to executing the table creation operation.

14. At least one non-transitory machine-readable storage medium comprising instructions which, when implemented by at least one machine, cause the at least one machine to perform operations comprising:
reading a query that traverses at least two nodes and at least one edge of a graph in a graph database;
compiling the query into a set of variables and a set of constraints;
creating an in-memory data structure comprising at least one table;
using the set of variables and the set of constraints, determining an operation that is performable using the in-memory data structure;
checking for an existence of a condition relating to the in-memory data structure or the operation;
if the condition exists, skipping the operation;
storing a set of intermediate query results in the at least one table; and
if the condition does not exist, executing the operation;
wherein checking for the existence of the condition comprises:
determining whether a variable of the set of variables is a single row variable, and if the variable is a single row variable, the condition exists and skipping the operation comprises skipping a path consistency checking operation; or
determining whether a variable of the set of variables is a multi-row variable, and if the variable is a multi-row variable, the condition does not exist and executing the operation comprises executing a path consistency checking operation.

15. At least one non-transitory machine-readable storage medium comprising instructions which, when implemented by at least one machine, cause the at least one machine to perform operations comprising:
reading a query that traverses at least two nodes and at least one edge of a graph in a graph database;
compiling the query into a set of variables and a set of constraints;
creating an in-memory data structure comprising at least one table;
using the set of variables and the set of constraints, determining an operation that is performable using the in-memory data structure;
checking for an existence of a condition relating to the in-memory data structure or the operation;
if the condition exists, skipping the operation;
storing a set of intermediate query results in the at least one table; and
if the condition does not exist, executing the operation;
wherein checking for the existence of the condition comprises:
determining whether the operation is non-selective, and if the operation is non-selective, the condition exists and skipping the operation comprises skipping a table creation operation; or
determining whether the operation is selective, and if the operation is selective, the condition does not exist and executing the operation comprises executing a table creation operation.

16. At least one non-transitory machine-readable storage medium comprising instructions which, when implemented by at least one machine, cause the at least one machine to perform operations comprising:
reading a query that traverses at least two nodes and at least one edge of a graph in a graph database;
compiling the query into a set of variables and a set of constraints;
creating an in-memory data structure comprising at least one table;
using the set of variables and the set of constraints, determining an operation that is performable using the in-memory data structure;
checking for an existence of a condition relating to the in-memory data structure or the operation;
if the condition exists, skipping the operation;
storing a set of intermediate query results in the at least one table; and
if the condition does not exist, executing the operation;
wherein checking for the existence of the condition comprises:
determining whether the in-memory data structure comprises a nested disjunction that includes at least one disjunctive child table that has zero rows;
if the in-memory data structure comprises a nested disjunction that includes at least one disjunctive child table that has zero rows, the condition exists and skipping the operation comprises skipping a path consistency checking operation; or
if the in-memory data structure does not comprise a nested disjunction that inclu

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Carter Andrew J
• Yang Yiming
• Yao Jiajun
• Shah Siddharth
• Rathore Dhruvesh
• Liang Tiance

Classifications

• G06F16/2425 Primary

  Iterative querying; Query formulation based on the results of a preceding query · CPC title

• G06F16/2453 Primary

  Query optimisation · CPC title