Skip relation pattern for graph structures

• US 20080162616A1
• Filed: 12/29/2006
• Published: 07/03/2008
• Est. Priority Date: 12/29/2006
• Status: Abandoned Application

• Current Assignee: SAP AG (SAP SE)
• Original Assignee: SAP AG (SAP SE)
• Inventors: Kaiser, Martin, Gross, Rene, Scheyter, Thorsten
• Application Number:
  US11/647,937
• Publication Number:
  US 20080162616A1
• Time in Patent Office: Days
• US Class Current: 708/300
• CPC Class Codes: G06Q 10/00 Administration; Management

Abstract

Systems and processes may apply a filter to data in a graph structure using an interface. The filter may be applied upon request from a business application. The interface may determine which portions of the graph structure satisfy the filter criteria. The interface may replace nodes and/or relations that do not satisfy filter criteria with skip nodes or functions. For example, software can be operable to apply a filter to a graph structure that includes nodes and relations between the nodes and evaluating the graph structure according to the filter. The software then replaces a first of the nodes that does not satisfy the filter with a first skip node.

Claims

1. A computer implemented method for efficiently filtering graphs comprising:

applying a filter to a graph structure that includes nodes and relations between the nodes;

evaluating the graph structure according to the filter; and

replacing a first of the nodes that does not satisfy the filter with a first skip node.

2. The method of claim 1 further comprising replacing a relation associated with the first node with a skip relation associated with the first skip node, the skip relation including an identity of the replaced first node of the graph structure.

3. The method of claim 2, wherein the skip relation associated with the first skip node further includes an identity of a valid node of the graph structure.

4. The method of claim 1, wherein a last valid node prior to a skip function in a portion of a graph structure includes an outgoing relation.

5. The method of claim 4, wherein the valid node includes an incoming relation.

6. The method of claim 1 further comprising instantiating a skip graph structure based on the remaining nodes of the filtered graph structure and the replacement nodes.

7. The method of claim 1 further comprising replacing a second of the nodes that does not satisfy the filter with a second skip node.

8. The method of claim 1, wherein the filter is applied upon request from a business application.

9. Software for efficiently filtering graphs comprising computer readable instructions embodied on media and operable to:

apply a filter to a graph structure that includes nodes and relations between the nodes;

evaluate the graph structure according to the filter; and

replace a first of the nodes that does not satisfy the filter with a first skip node.

10. The software of claim 9 further operable to replace a relation associated with the first node with a skip relation associated with the first skip node, the skip relation including an identity of the replaced first node of the graph structure.

11. The software of claim 9, wherein the skip relation associated with the first skip node further includes an identity of a valid node of the graph structure.

12. The software of claim 9, wherein a last valid node prior to a skip function in a portion of a graph structure includes an outgoing relation.

13. The software of claim 12, wherein the valid node includes an incoming relation.

14. The software of claim 9 further operable to instantiate a skip graph structure based on the remaining nodes of the filtered graph structure and the replacement nodes.

15. The software of claim 9 further operable to replace a second of the nodes that does not satisfy the filter with a second skip node.

16. The software of claim 9, wherein the filter is applied upon request from a business application.

17. A system for efficiently filtering graphs comprising:

means for applying a filter to a graph structure that includes nodes and relations between the nodes;

means for evaluating the graph structure according to the filter; and

means for replacing a first of the nodes that does not satisfy the filter with a first skip node.

18. The system of claim 17 further comprising means for replacing a relation associated with the first node with a skip relation associated with the first skip node, the skip relation including an identity of the replaced first node of the graph structure.