Enforcing path consistency in graph database path query evaluation

Patent metadata

Field	Value
Publication number	US-2021397601-A1
Application number	US-202117466717-A
Country	US
Kind code	A1
Filing date	Sep 3, 2021
Priority date	Sep 30, 2019
Publication date	Dec 23, 2021
Grant date	—

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, comprising:
executing one or more processes for storing a graph in a base version of a graph database, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates; and when a query of the graph database is received, using one or more of the processes to process the query by:
storing 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;
tracking, in the structure, representations of data, relationships, and path consistency in the query;
applying one or more operations to existing rows in the structure to generate a final result of the query; and
providing the final result in a response to the query.

2 . The method of claim 1 , further comprising:
identifying one or more constraints associated with the query; and generating the one or more operations based on the one or more constraints.

3 . The method of claim 1 , wherein the one or more operations comprise a batch expand operation that expands multiple rows from a first table into multiple rows in a second table.

4 . The method of claim 1 , wherein the one or more operations comprise a zip operation that comprises producing a cross product from source rows in multiple tables while ensuring that all paths from each row in the cross product reach a common row in all ancestors of the multiple tables.

5 . The method of claim 4 , wherein applying the zip operation to the existing rows in the structure comprises:
for a table in the multiple tables, constructing a relation comprising a first set of rows representing a second set of rows in the table and a set of columns, wherein each column in the set of columns comprises source rows in a common ancestor of the multiple tables; incrementally adding columns to the set of columns until all ancestors of the table are included in the relation; and after a column is added to the set of columns, evaluating the cross products using an attribute represented by the column.

6 . The method of claim 1 , wherein the one or more operations comprise an unzip operation that comprises:
extracting one or more columns from one or more source tables into a destination table; creating a first set of links from a first set of rows in the destination table to corresponding rows in the one or more source tables; and creating a second set of links from a second set of rows in one or more base tables to the first set of rows in the destination table based on paths between the second set of rows and the corresponding rows in the one or more source tables.

7 . The method of claim 1 , wherein the one or more operations comprise a reduce operation that aggregates multiple rows from a first table into one or more rows in a second table based on groupings of the multiple rows in a third table.

8 . The method of claim 1 , wherein the one or more operations comprise a stitch operation that creates a link between a first row in a destination table and a second row in a source table when the first and second rows share a common ancestor and one or more columns with matching values.

9 . The method of claim 1 , wherein tracking the path consistency in the query comprises:
verifying a valid path from a root table in the structure to the rows in all other tables in the structure; and verifying that all paths from a first row in a destination table to a source table reach a common row in the source table.

10 . The method of claim 1 , wherein applying the one or more operations to the existing rows in the structure to generate the final result of the query comprises:
applying an operation to one or more rows of a source table in the structure to produce a result of the operation; and updating the data structure to reflect the result and enforce the path consistency.

11 . The method of claim 1 , wherein applying the one or more operations to the existing rows in the structure to generate the final result of the query comprises:
for each table in the set of tables, setting an evaluation mode of the table to be disjunctive, conjunctive, or optional; and propagating removal of one or more of the rows across the set of tables based on the evaluation mode.

12 . The method of claim 1 , wherein the relationships comprise:
a one-to-one relationship between a first source row in a first table and a first destination row in a second table; and a one-to-many relationship between a second source row in the first table and multiple destination rows in the second table.

13 . A system, comprising:
one or more processors; and memory storing instructions that, when executed by the one or more processors, cause the system to:
execute one or more processes for storing a graph in a base version of a graph database, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates; and
when a query of the graph database is received, using one or more of the processes to process the query by:
storing 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;
tracking, in the structure, representations of data, relationships, and path consistency in the query;
applying one or more operations to existing rows in the structure to generate a final result of the query; and
providing the final result in a response to the query.

14 . The system of claim 13 , wherein the one or more operations comprise a zip operation that comprises producing a cross product from source rows in multiple tables while ensuring that all paths from each row in the cross product reach a common row in all ancestors of the multiple tables.

15 . The system of claim 14 , wherein applying the zip operation to the existing rows in the structure comprises:
for a table in the multiple tables, constructing a relation comprising a first set of rows representing a second set of rows in the table and a set of columns, wherein each column in the set of columns comprises source rows in a common ancestor of the multiple tables; incrementally adding columns to the set of columns until all ancestors of the table are included in the relation; and after a column is added to the set of columns, evaluating the cross products using an attribute represented by the column.

16 . The system of claim 13 , wherein the one or more operations comprise an unzip operation that comprises:
extracting one or more columns from one or more source tables into a destination table; creating a first set of links from a first set of rows in the destination table to corresponding rows in the one or more source tables; and creating a second set of links from a second set of rows in one or more base tables to the first set of rows in the destination table based on paths between the second set of rows and the corresponding rows in the one or more source tables.

17 . The system of claim 13 , wherein the one or more operations comprise a reduce operation that aggregates multiple rows from a first table into one or more rows in a second table based on groupings of the multiple rows in a third table.

18 . The system of claim 13 , wherein the one or more operations comprise a stitch operation that creates a link between a first row in a destination table and a second row in a source table when the first and second rows share a common ancestor and one or mor

Assignees

• Microsoft Technology Licensing Llc

Inventors

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

Classifications

• G06F16/9024

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

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F17/10 Primary

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F16/284

  Relational databases · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title