# US 10,503,781 B2 · Extending graph traversals with application logic > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,503,781 B2 - Document ID: US10503781B2 - Status: Granted - Kind: B2 - Application number: 14/820,357 - Filed: 2015-08-06 - Published: 2016-10-20 - Granted: 2019-12-10 - Earliest claimed: 2015-04-14 - Assignees: Sap SE - Applicants: Sap SE - Inventors: Marcus Paradies; Wolfgang Lehner; Michael Rudolf - Web page: https://patentgrep.com/patent/US10503781B2 ## CPC - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 16/90335: {Query processing} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method as in claim 1, wherein the traversal hooks are event-based and comprise traversal operators configured to visit vertices and edges of the graph data in an ordered manner. ### Claim 3 (depends on 1) The method as in claim 1, wherein the traversal hooks are event-based and comprise traversal operators configured to identify a vertex and/or edge that has previously been visited during processing of the query. ### Claim 4 (depends on 1) The method as in claim 1, further comprising: detecting, by the at least one programmable processor, a traversal event associated with a traversal hook; identifying, by the at least one programmable processor, executable graph data traversal code that is associated with the traversal hook which in turn is associated with the traversal hook; and executing, by the at least one programmable processor, the executable graph data traversal code associated with the traversal hook. ### Claim 5 (depends on 4) The method as in claim 4, wherein a traversal event includes the identification of a vertex and/or edge of the graph data having a core-defined status during a traversal of the graph data. ### Claim 6 (depends on 1) The method as in claim 1, wherein compiling the groups of traversal hooks is performed by a just-in-time compiler. ### Claim 7 (depends on 1) The method as in claim 1, wherein the traversal script includes a user-defined output. ### Claim 8 (depends on 1) The method as in claim 1, wherein the traversal script includes an instruction to abandon a traversal of the graph data in response to the occurrence of a restriction condition. ### Claim 9 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. ### Claim 10 (depends on 9) The system as in claim 9, wherein the traversal hooks are event-based and comprise traversal operators configured to visit vertices and edges of the graph data in an ordered manner. ### Claim 11 (depends on 9) The system as in claim 9, wherein the traversal hooks are event-based and comprise traversal operators configured to identify a vertex and/or edge that has previously been visited during processing of the query. ### Claim 12 (depends on 9) The system as in claim 9, wherein the operations comprise: detecting a traversal event associated with a traversal hook; identifying executable graph data traversal code that is associated with the traversal hook which in turn is associated with the traversal hook; and executing the executable graph data traversal code associated with the traversal hook. ### Claim 13 (depends on 12) The system as in claim 12, wherein a traversal event includes the identification of a vertex and/or edge of the graph data having a core-defined status during a traversal of the graph data. ### Claim 14 (depends on 9) The system as in claim 9, wherein compiling the groups of traversal hooks is performed by a just-in-time compiler. ### Claim 15 (depends on 9) The system as in claim 9, wherein the traversal script includes a user-defined output. ### Claim 16 (depends on 9) The system as in claim 9, wherein the traversal script includes an instruction to abandon a traversal of the graph data in response to the occurrence of a restriction condition. ### Claim 17 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. ### Claim 18 (depends on 17) The non-transitory computer program product as in claim 17, wherein the traversal hooks are event-based and comprise traversal operators configured to visit vertices and edges of the graph data in an ordered manner. ### Claim 19 (depends on 17) The non-transitory computer program product as in claim 17, wherein the traversal hooks are event-based and comprise traversal operators configured to identify a vertex and/or edge that has previously been visited during processing of the query. ### Claim 20 (depends on 17) The non-transitory computer program product as in claim 17, wherein the operations further comprise: detecting, by the at least one programmable processor, a traversal event associated with a traversal hook; identifying, by the at least one programmable processor, executable graph data traversal code that is associated with the traversal hook which in turn is associated with the traversal hook; and executing, by the at least one programmable processor, the executable graph data traversal code associated with the traversal hook.