METHODS AND APPARATUS RELATED TO GRAPH TRANSFORMATION AND SYNCHRONIZATION

• US 20130006935A1
• Filed: 06/30/2011
• Published: 01/03/2013
• Est. Priority Date: 06/30/2011
• Status: Active Grant

• Current Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Original Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Inventors: Grisby, Duncan P.
• Granted Patent: US 9,116,968 B2
• Time in Patent Office: Days
• US Class Current: 707/635
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

In one general aspect, a computer system can include instructions configured to store on a non-transitory computer-readable storage medium. The computer system can include a subgraph transformer configured to transform a plurality of subgraphs of a source graph into a plurality of transformed subgraphs, and configured to define a target graph that is a transformed version of the source graph based on the plurality of transformed subgraphs. The computer system can include a change detector configured to receive an indicator that a portion of the source graph has been changed, and a synchronization module configured to synchronize a portion of the target graph with the changed portion of the source graph.

Claims

1. A computer system including instructions stored on a non-transitory computer-readable storage medium, the computer system comprising:

a subgraph transformer configured to transform a plurality of subgraphs of a source graph into a plurality of transformed subgraphs, and configured to define a target graph that is a transformed version of the source graph based on the plurality of transformed subgraphs;

a change detector configured to receive an indicator that a portion of the source graph has been changed; and

a synchronization module configured to synchronize a portion of the target graph with the changed portion of the source graph.

2. The computer system of claim 1, wherein the source graph includes a plurality of nodes and relationships between the plurality of nodes, each subgraph from the plurality of subgraphs includes at least a portion of the plurality of nodes and at least a portion of the relationships between the plurality of nodes.

3. The computer system of claim 1, further comprising instructions to:

identify a node within the source graph as a source root node associated with the changed portion of the source graph, the portion of the target graph that is synchronized includes a node corresponding with the source root node.

4. The computer system of claim 1, wherein each subgraph from the plurality of subgraphs is identified for transformation into a plurality of subgraphs based on a subgraph collection rule, a first portion of the plurality of subgraphs are transformed during a first time period and a second portion of the plurality of subgraphs are transformed during a second time period.

5. The computer system of claim 1, wherein the change detector is further configured to identify, in response to the indicator, a source root node associated with the changed portion of the source graph;

the computer system further comprising;

a subgraph collector configured to identify, based on a subgraph collection rule, a subgraph associated with the changed portion of the source graph starting with the source root node,

the subgraph transformer further configured to define, based on a transformation rule, a transformed subgraph associated with the changed portion based on the subgraph of the source graph, and

the synchronization module further configured to modify the portion of the target graph based on the transformed subgraph associated with the changed portion.

6. The computer system of claim 1, wherein the synchronization module is further configured to identify the portion of the target graph for synchronization based on a key of the changed portion of the source graph matching within a key of the portion of the target graph.

7. The computer system of claim 1, wherein a transformed subgraph from the plurality of transformed subgraphs of the target graph corresponds with a subgraph from the plurality of subgraphs of the source graph, the transformed subgraph associated with the target graph includes nodes and relationships between nodes in a configuration different from nodes and relationships between nodes of the subgraph associated with the source graph.

8. The computer system of claim 1, further comprising:

a subgraph collector configured to identify a subgraph of the source graph that includes the changed portion in response to the indicator,

the subgraph transformer further configured to produce a first transformed subgraph based on a version of the subgraph of the source graph before the change to the subgraph and a second transform based on a version of the subgraph before the change to the subgraph of the source graph.

the synchronization module is configured to synchronize the portion of the target subgraph within the changed portion of the source graph based on the first transformed subgraph and based on the second transformed subgraph.

9. A computer-readable storage medium storing instructions that when executed cause a processor to perform a process, the instructions comprising instructions to:

access at least a portion of a source graph including a plurality of nodes and relationships between the plurality of nodes;

access at least a portion of a target graph including a plurality of nodes and relationships between the plurality of nodes;

identify, based on a subgraph collection rule, a subgraph of the source graph starting at a node from the plurality of nodes identified as a source root node;

define, based on a transformation rule, a transformed subgraph based on the subgraph of the source graph; and

modify a subgraph from the target graph based on the transformed subgraph.

10. The computer-readable storage medium of claim 9, further comprising instructions to:

receive an indicator of a change to the source graph; and

identify a node from the plurality of nodes as a source root node associated with the change to the source graph.

11. The computer-readable storage medium of claim 9, further comprising instructions to:

associate a class graph with the subgraph of the source graph, the class graph including nodes having a probability of being included in the subgraph of the source graph, the instructions to modify include instructions to modify the subgraph from the target subgraph based on a combination of the transformed subgraph and the class graph.

12. The computer-readable storage medium of claim 9, further comprising instructions to:

identify a node from the plurality of nodes of the target graph as corresponding with the source root node of the source graph; and

identify, based on the subgraph collection rule, a subgraph from the target graph starting at the node from the plurality of nodes corresponding with source root node.

13. The computer-readable storage medium of claim 9, further comprising instructions to:

modify the subgraph from the target graph until the subgraph from the target graph is identical to the transformed subgraph.

14. The computer-readable storage medium of claim 9, wherein the target graph is a transformed version of the source graph.

15. The computer-readable storage medium of claim 9, wherein at least some of the nodes of the target graph are excluded from the nodes of the source graph, at least some of the relationships between the plurality of nodes of the target graph are excluded from the relationships between the plurality of nodes of the source graph.

16. The computer-readable storage medium of claim 9, wherein at least a portion of the plurality of nodes of the target graph represent devices within a computer network.

17. The computer-readable storage medium of claim 9, wherein at least a portion of the plurality of nodes of the target graph represent portions of a social network.

18. A computer-readable storage medium storing instructions that when executed cause a processor to perform a process, the instructions comprising instructions to:

receive an indicator of a changed portion of a source graph including a plurality of nodes and relationships between at least a portion of the plurality of nodes;

identify, in response to the indicator, a subgraph of the source graph that includes the changed portion;

identify a subgraph of a target graph corresponding with the subgraph of the source graph; and

identify, based on a class graph, a node to be modified within the subgraph of the target graph, the node being an instance of a node included in a class of nodes from the class graph.

19. The computer-readable storage medium of claim 18, wherein at least a portion of the changed portion of the source graph is based on deletion of the node from the source graph.

20. The computer-readable storage medium of claim 18, wherein a root node of the class graph is a transformed version of a source root node of the subgraph of the source graph.

21. The computer-readable storage medium of claim 18, wherein the subgraph of the source graph includes at least a portion of the plurality of nodes and at least a portion of the relationships between the plurality of nodes.

22. The computer-readable storage medium of claim 18, wherein the node to be modified is identified based on a comparison of the subgraph of the source graph with the subgraph of the target graph,

the instructions further comprising instructions to:

search for instances of nodes within the class of nodes based on the class of nodes being included in the class graph, the node to be modified is identified in response to the search.

23. The computer-readable storage medium of claim 18, wherein the class graph is a target class graph that is a transformed version of a source class graph corresponding with the source graph.

24. A computer-readable storage medium storing instructions that when executed cause a processor to perform a process, the instructions comprising instructions to:

receive an indicator of a changed portion of a source graph including a plurality of nodes and relationships between at least a portion of the plurality of nodes;

identify, in response to the indicator, a subgraph of the source graph that includes the changed portion;

identify a subgraph of a target graph corresponding with the subgraph of the source graph; and

modify the subgraph of the target graph based on a log characterizing changes to the changed portion to the source graph.

25. The computer-readable storage medium of claim 24, wherein at least a portion of the changed portion of the source graph is based on deletion of the node from the source graph.