Back to results
US 2020/0004748 A1Published application
Reusing sub-query evaluation results in evaluating query for data item having multiple representations in graph
AssigneeInternational Business Machines Corporation
InventorScott N. Gerard
Life of this patent
Estimating the term…
Abstract
Sub-queries for a query are determined. The query is for retrieving a data item of a data graph. The data graph stores representations of the data item. Each representation of the data item stores knowledge represented by the data item in a different way or manner. Each sub-query corresponds to a different representation by which the data graph stores the data item. The sub-queries are evaluated to determine an appropriate representation of the data item in fulfillment of the query without duplicatively traversing the data graph, such as by reusing evaluation results of the sub-queries that overlap one another.
Claims20
A method comprising:
- receiving, by a computing device, a query for retrieving a data item of a data graph, the data graph storing a plurality of representations of the data item, wherein the data graph comprises a plurality of nodes interconnected via a plurality of edges, and wherein each representation of the data item corresponds to a different node or edge of the data graph;
- evaluating, by the computing device, a plurality of sub-queries for the query, including reusing evaluation results of the sub-queries that overlap one another,
- wherein evaluating the sub-queries, including reusing the evaluation results of the sub-queries that overlap one another, comprises, for a current sub-query:
- for a current node of a traversal path through the data graph corresponding to the current sub-query, determining whether the current node is present in a composite traversal path corresponding to a composite sub-query;
- in response to determining that the current node is present in the composite traversal path, reusing the evaluation results of the sub-queries instead of traversing the data graph at the current node;
- and
- in response to determining that the current node is absent from the composite traversal path, traversing the data graph at the current node, storing the current node within the evaluation results of the sub-queries, and augmenting the composite traversal path with the current node.
4 more elements
A computer program product comprising:
- one or more computer-readable storage media having program instructions embodied therewith, the program instructions executed by a computing device to:
- determine a plurality of sub-queries for a query, the query for retrieving a data item of a data graph, the data graph storing a plurality of representations of the data item, each sub-query corresponding to a different representation by which the data graph stores the data item;
- and
- evaluate the sub-queries to determine an appropriate representation of the data item in fulfillment of the query, wherein the computing device is to evaluate the sub-queries by, for a current sub-query:
- for a current node of a traversal path through the data graph corresponding to the current sub-query, determining whether the current node is present in a composite traversal path corresponding to a composite sub-query;
- in response to determining that the current node is present in the composite traversal path, reusing the evaluation results of the sub-queries instead of traversing the data graph at the current node;
- in response to determining that the current node is absent from the composite traversal path, traversing the data graph at the current node, storing the current node within the evaluation results of the sub-queries, and augmenting the composite traversal path with the current node;
- for a current edge of the traversal path connected to the current node, determining whether the current edge is present in the composite traversal path;
- in response to determining that the current edge is present in the composite traversal path, reusing the evaluation results of the sub-queries instead of traversing the data graph at the current edge;
- and
- in response to determining that the current edge is absent from the composite traversal path, traversing the data graph at the current edge, storing the current edge within the evaluation results of the sub-queries, and augmenting the composite traversal path with the current edge.
8 more elements
A system comprising:
- network hardware to communicatively connect to a network over which a query for retrieving a data item of a data graph is received;
- a storage device to store the data graph, the data graph having a plurality of nodes interconnected by a plurality of edges, the data graph including a plurality of representations of the data item, each representation corresponding to a different node or edge of the data graph;
- and
- logic comprising hardware, to:
- select an appropriate representation of the data item in satisfaction of the query by evaluating a plurality of sub-queries for the query, each sub-query corresponding to a different representation by which the data graph stores the data item,
- wherein the logic is to evaluate the sub-queries by, for a current sub-query:
- for a current node of a traversal path through the data graph corresponding to the current sub-query, determining whether the current node is present in a composite traversal path corresponding to a composite sub-query;
- in response to determining that the current node is present in the composite traversal path, reusing the evaluation results of the sub-queries instead of traversing the data graph at the current node;
- in response to determining that the current node is absent from the composite traversal path, traversing the data graph at the current node, storing the current node within the evaluation results of the sub-queries, and augmenting the composite traversal path with the current node;
- for a current edge of the traversal path connected to the current node, determining whether the current edge is present in the composite traversal path;
- in response to determining that the current edge is present in the composite traversal path, reusing the evaluation results of the sub-queries instead of traversing the data graph at the current edge;
- and
- in response to determining that the current edge is absent from the composite traversal path, traversing the data graph at the current edge, storing the current edge within the evaluation results of the sub-queries, and augmenting the composite traversal path with the current edge.
10 more elements
Dependencies are inferred from the claim text.