Enforcing path consistency in graph database path query evaluation

Patent metadata

Field	Value
Publication number	US-11720543-B2
Application number	US-202117466717-A
Country	US
Kind code	B2
Filing date	Sep 3, 2021
Priority date	Sep 30, 2019
Publication date	Aug 8, 2023
Grant date	Aug 8, 2023

Abstract

The disclosed embodiments provide a system for processing queries of a graph database. During operation, the system stores intermediate results of the query in a structure comprising rows in a set of tables and links between pairs of rows in different tables in the set of tables. Next, the system tracks, in the structure, representations of data, relationships, and path consistency in the query. The system then applies one or more operations to existing rows in the structure to generate a final result of the query. Finally, the system provides the final result in a response to the query.

First claim

What is claimed is:

1. A method for storing intermediate results of a path query in a computer memory, the method comprising:
processing a query that traverses at least two nodes and at least one edge of a graph database;
configuring the computer memory according to an intermediate data structure, the intermediate data structure comprising:
a plurality of tables, each table comprising a plurality of rows and a plurality of columns;
a plurality of links between rows in different tables of the plurality of tables; and
at least one invariant that tracks or enforces path consistency during the processing of the query;

storing data related to processing a first portion of the query in a source table of the plurality of tables;
applying one or more operations to one or more rows of the source table;
storing output of the one or more operations in one or more rows of a destination table of the plurality of tables; and
creating a link between the one or more rows of the source table and the one or more rows of the destination table.

2. The method of claim 1 , further comprising:
storing a first set of intermediate results of processing a first portion of the query in a first table of the plurality of tables;
storing a second set of intermediate results of processing a second portion of the query different than the first portion in a second table of the plurality of tables; and
creating a link between one or more rows of the first table and one or more rows of the second table.

3. The method of claim 1 , further comprising:
determining first and second steps of processing the query;
storing data related to the first step in a first table of the plurality of tables;
storing data related to the second step in a second table of the plurality of tables different than the first table; and
creating a link between the first table and the second table.

4. The method of claim 1 , further comprising:
generating one or more additional tables in the intermediate data structure until the processing of the query produces a final result.

5. The method of claim 1 , further comprising:
adding one or more additional links between rows of the plurality of tables until the processing of the query produces a final result.

6. The method of claim 1 , wherein at least one of the links indicates a one-to-one relationship between a row of a source table of the plurality of tables and a row of a destination table of the plurality of tables.

7. The method of claim 1 , wherein at least one of the links indicates a one-to-many relationship between a row of a source table of the plurality of tables and a plurality of rows of a destination table of the plurality of tables.

8. The method of claim 1 , further comprising:
tracking relationships between rows of source and destination tables by storing, in an array, data representing one or more rows of a destination table produced from one or more rows of a source table.

9. The method of claim 1 , further comprising:
storing, in a column of a table of the plurality of tables, data that indicates an evaluation mode of the table.

10. A system, comprising:
one or more processors; and
computer memory storing instructions that, when executed by the one or more processors, cause the one or more processors to be capable of:
processing a path query;
creating an intermediate data structure comprising:
a plurality of tables, each table comprising a plurality of rows and a plurality of columns;
a plurality of links between rows in different tables of the plurality of tables; and
at least one invariant that tracks or enforces path consistency during the processing of the path query; and

tracking relationships between rows of source and destination tables by storing, in an array, data representing one or more rows of a destination table produced from one or more rows of a source table.

11. The system of claim 10 , wherein the instructions, when executed by the one or more processors, cause the one or more processors to be capable of:
storing a first set of intermediate results of processing a first portion of the path query in a first table of the plurality of tables;
storing a second set of intermediate results of processing a second portion of the path query different than the first portion in a second table of the plurality of tables; and
creating a link between one or more rows of the first table and one or more rows of the second table.

12. The system of claim 10 , wherein the instructions, when executed by the one or more processors, cause the one or more processors to be capable of:
determining first and second steps of processing the path query;
storing data related to the first step in a first table of the plurality of tables;
storing data related to the second step in a second table of the plurality of tables different than the first table; and
creating a link between the first table and the second table.

13. The system of claim 10 , wherein the instructions, when executed by the one or more processors, cause the one or more processors to be capable of:
storing data related to processing a first portion of the path query in a source table of the plurality of tables;
applying one or more operations to one or more rows of the source table;
storing output of the one or more operations in one or more rows of a destination table of the plurality of tables;
creating a link between the one or more rows of the source table and the one or more rows of the destination table.

14. The system of claim 10 , wherein the instructions, when executed by the one or more processors, cause the one or more processors to be capable of:
generating one or more additional tables in the intermediate data structure until the processing of the path query produces a final result.

15. The system of claim 10 , wherein the instructions, when executed by the one or more processors, cause the one or more processors to be capable of:
adding one or more additional links between rows of the plurality of tables until the processing of the path query produces a final result.

16. The system of claim 10 , wherein at least one of the links indicates a one-to-one relationship between a row of a source table of the plurality of tables and a row of a destination table of the plurality of tables.

17. The system of claim 10 , wherein at least one of the links indicates a one-to-many relationship between a row of a source table of the plurality of tables and a plurality of rows of a destination table of the plurality of tables.

18. The system of claim 10 , wherein the instructions, when executed by the one or more processors, cause the one or more processors to be capable of:
storing, in a column of a table of the plurality of tables, data that indicates an evaluation mode of the table.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Carter Andrew J
• Lu Ying
• Shah Siddharth
• Rodriguez Andrew
• Meyer Scott M

Classifications

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/248

  Presentation of query results · CPC title

• G06F16/284

  Relational databases · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title