Back to results
US 10,503,781 B2Granted
Extending graph traversals with application logic
AssigneeSap SE
InventorsMarcus Paradies, Wolfgang Lehner, Michael Rudolf
Life of this patent
Estimating the term…
Abstract
Traversal hooks are based on an event-oriented programming model and provide an expressive mechanism to extend a graph traversal operator with domain-specific coding. A traversal operator can visit (i.e., traversal events) vertices and edges of a graph in an ordered manner. Related apparatus, systems, techniques and articles are also described.
Claims20
A method for implementation by at least one programmable processor forming at least one computing device, the method comprising:
- receiving, by the at least one programmable processor, a query of a set of graph data, the query including one or more conditions for assessing the set of graph data that causes the graph data to be traversed, the set of graph data including a plurality of vertices and a plurality of edges between pairs of vertices;
- generating, by the at least one programmable processor, an intermediate machine-readable code that includes instructions for executing one or more traversal operators for traversing the set of graph data and which includes interwoven instructions for executing one or more traversal hooks, the generating comprising interweaving an in memory (LLVM) intermediate representation (LLVM IR) of the one or more traversal operators with generated code of the one or more traversal hooks;
- extracting, by the at least one programmable processor, a filter predicate from the one or more traversal hooks;
- preprocessing, by the at least one programmable processor, the filter predicate separately from the one or more traversal hooks;
- identifying, by the at least one programmable processor, traversal hooks of the one or more of traversal hooks that can be independently executed;
- grouping, by the at least one programmable processor, independently executable traversal hooks that are capable of being processed in parallel;
- and
- compiling, by the at least one programmable processor, the intermediate machine-readable code and the groups of traversal hooks to generate executable graph data traversal code for use during processing of the query.
5 more elements
A system comprising at least one programmable processor forming at least one computing device, the at least one programmable processor configured by machine readable instructions to perform operations comprising:
- receiving a query of a set of graph data, the query including one or more conditions for assessing the set of graph data that causes the graph data to be traversed, the set of graph data including a plurality of vertices and a plurality of edges between pairs of vertices;
- generating an intermediate machine-readable code that includes instructions for executing one or more traversal operators for traversing the set of graph data and which includes interwoven instructions for executing one or more traversal hooks, the generating comprising interweaving an in memory (LLVM) intermediate representation (LLVM IR) of the one or more traversal operators with generated code of the one or more traversal hooks;
- extracting a filter predicate from the one or more traversal hooks;
- preprocessing the filter predicate separately from the one or more traversal hooks;
- identifying traversal hooks of the one or more of traversal hooks that can be independently executed;
- grouping independently executable traversal hooks that are capable of being processed in parallel;
- and
- compiling the intermediate machine-readable code and the groups of traversal hooks to generate executable graph data traversal code for use during processing of the query.
5 more elements
A non-transitory computer program product storing instructions which, when executed by at least one data processor forming part of at least one computing device, result in operations comprising:
- receiving, by the at least one programmable processor, a query of a set of graph data, the query including one or more conditions for assessing the set of graph data that causes the graph data to be traversed, the set of graph data including a plurality of vertices and a plurality of edges between pairs of vertices;
- generating, by the at least one programmable processor, an intermediate machine-readable code that includes instructions for executing one or more traversal operators for traversing the set of graph data and which includes interwoven instructions for executing one or more traversal hooks, the generating comprising interweaving an in memory (LLVM) intermediate representation (LLVM IR) of the one or more traversal operators with generated code of the one or more traversal hooks;
- extracting, by the at least one programmable processor, a filter predicate from the one or more traversal hooks;
- preprocessing, by the at least one programmable processor, the filter predicate separately from the one or more traversal hooks;
- identifying, by the at least one programmable processor, traversal hooks of the one or more of traversal hooks that can be independently executed;
- grouping, by the at least one programmable processor, independently executable traversal hooks that are capable of being processed in parallel;
- and
- compiling, by the at least one programmable processor, the intermediate machine-readable code and the groups of traversal hooks to generate executable graph data traversal code for use during processing of the query.
5 more elements
Dependencies are inferred from the claim text.