Change monitoring spanning graph queries

Patent metadata

Field	Value
Publication number	US-10545945-B2
Application number	US-201615338290-A
Country	US
Kind code	B2
Filing date	Oct 28, 2016
Priority date	Oct 28, 2016
Publication date	Jan 28, 2020
Grant date	Jan 28, 2020

Abstract

Approximate Membership Query (AMQ) Filters are used in conjunction with graph queries to a relational graph to provide change monitoring that span views associated with the queries. Each node from the relational graph spanned by a graph query and the index structure for the view are added as members to an AMQ filter. When a change is made to the relational graph, the changed nodes are queried against the AMQ filter. When a changed node is noted as a candidate member of the AMQ filter, the graph query may be rerun to update the view associated with the query. Otherwise, the graph query is not rerun, thus saving computing resources and improving the systems hosting and querying the relational graph.

First claim

We claim:

1. A method for improving computational efficiency in monitoring changes to a relational graph, comprising:
receiving, from a client device, a graph query at a graph server hosting the relational graph;
running the graph query to span the relational graph to produce a view of the relational graph;
recording identities of nodes spanned by the graph query in a membership set associated with the graph query;
receiving, at the graph server, graph changes affecting the relational graph;
parsing the received graph changes to determine nodes that have changed, each node having an individual identifier;
determining, based on an individual identifier, whether a given node is recorded in the membership set;
in response to determining that the given node is recorded in the membership set:
rerunning the graph query to span the relational graph and produce a new view;
determining whether the new view is equivalent to the view; and
in response to determining that the new view is not equivalent to the view, exposing a change to the relational graph to the client device by transmitting the new view to the client device.

2. The method of claim 1 , further comprising:
wherein the identities of nodes spanned by the graph query are recorded in the membership set associated with the graph query comprises in an Approximate Membership Query (AMQ) filter, which comprises:
initializing a membership array of the AMQ filter, the membership array comprising a plurality of bits, wherein each bit is set to a first state;
receiving the identifiers for the nodes spanned by the graph query;
hashing the identifiers to produce positional values for each of the identifiers; and
recording the nodes in the membership array by setting a bit of the plurality of bits positioned in the membership array at each of the positional values to a second state;

wherein determining whether the given node is recorded in the membership set includes querying the AMQ filter with the given node, which comprises:
receiving a given identifier for the given node;
hashing the given identifier to produce candidate positions for the given node in the membership array; and
determining a state to which each bit at the candidate positions in the membership array is set; and
in response to determining that each bit at the candidate positions in the membership array is set to the second state, probabilistically determining that the given node is recorded in the membership set.

3. The method of claim 2 further comprising:
in response to determining that at least one bit at the candidate positions in the membership array is set to the first state, returning a negative response to querying the AMQ filter and not exposing the change to the client device.

4. The method of claim 1 , wherein the change to the relational graph affects multiples nodes, the multiple nodes including the given node.

5. The method of claim 1 , further comprising:
receiving an index structure of the view; and
recording the index structure in the membership set.

6. The method of claim 5 , wherein the index structure comprises identifiers of the nodes spanned by the graph query in a flattened tree structure.

7. The method of claim 1 , wherein exposing the change to the client device includes transmitting a change notification to the client device.

8. The method of claim 1 , wherein exposing the change to the client device includes transmitting a notification to the client device that the new view is available.

9. The method of claim 1 , wherein the nodes spanned by the graph query include nodes that are part of the view and nodes that are connected by an edge that is part of the view.

10. The method of claim 1 , further comprising:
in response to determining that the given node is recorded in the membership set, but prior to rerunning the graph query to span the relational graph and produce the new view, determining whether rerun approval rules are satisfied;
in response to determining that the rerun approval rules are satisfied, proceeding to rerun the graph query; and
in response to determining that the rerun approval rules are not satisfied, preventing the graph query from being rerun.

11. The method of claim 10 , wherein the rerun approval rules include:
a threshold number of changed nodes;
a rule to ignore the change unless an index structure of the view has also changed; and
a minimum time between updates to the view.

12. A system for improving computational efficiency in monitoring changes to a relational graph, comprising:
a processor; and
a memory storage device, including instructions that when executed are operable to:
maintain a membership array;
receive a member node identifier and record the member node identifier in the membership array;
receive a candidate node identifier;
in response to determining that the candidate node identifier is recorded in the membership array:
run a graph query to produce a view of the relational graph;
compare the view to a prior view of the relational graph produced by the graph query; and
in response to the view and the prior view not matching, expose the change to the relational graph to a client by transmitting the view to the client.

13. The system of claim 12 , wherein the member node identifier is received in response to the graph query being run and is associated with a node in the relational graph that is spanned by the graph query.

14. The system of claim 12 , wherein the candidate node identifier is included in a change stream received in response to the change affecting the relational graph.

15. The system of claim 12 , wherein the system is operable to determine whether the query is affected by the change to the relational graph by comparing a first index structure against a second index structure, wherein the first index structure is a tree structure of nodes included in the prior view, and wherein the second index structure is a tree structure of nodes included in the view;
in response to the first index structure being equivalent to the second index structure, determine that the query is unaffected by the change; and
in response to the first index structure not being equivalent to the second index structure, determine that the query is affected by the change.

16. The system of claim 12 , wherein to expose the change to the relational graph to the client the system is further operable to:
transmit a change notification to a client device associated with the client;
receive a request for the view from the client device in response to the change notification; and
transmit the view to the client device in response to receiving the request.

17. The system of claim 12 , wherein the system is further operable to:
provide one or more hash functions, each of the one or more hash functions operable to output a position in the membership array;
wherein the membership array includes an ordered plurality of bits initialized at a first state;
wherein to record the member node identifier in the membership array, the system is further operable to:
hash the member node identifier with the one or more hash functions to produce one or more member positions; and
set one or more bits of the ordered plurality of bits, at the one or more member positions, to a second state; and

wherein to determine whether the candidate node identifier is recorded in the membership array, the system is further operable to:
hash the candidate node identifier with the one or more hash functions to produce one or more candidate positions;
determine whether every b

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Heen Peter Dahle
• Eidesen Dag Steinnes
• Johansen Amund Kronen
• Brattli Dag
• Karlberg Jan-Ove Almli
• Kreutzer Tor
• Kvalnes Åge
• Viken Valvåg Steffen

Classifications

• G06F16/24575

  using context · CPC title

• G06F16/9024

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

• G06F16/284

  Relational databases · CPC title

• G06F16/2358 Primary

  Change logging, detection, and notification (replication G06F16/27) · CPC title

• G06F16/2393

  Updating materialised views · CPC title