Patent ID: 9280585
Filing Date: 2016-03-08
CPC Classification: G06F

Claim Text:
1. A method for optimizing semantic web queries, the method comprising: receiving a semantic query over a database, the semantic query comprising a plurality of triple patterns; creating a data flow graph that captures inter-relationships resulting from sharing of at least one of common variables and constraints among the plurality of triple patterns; using the data flow graph and costs estimates for traversing all triple patterns in the semantic query to determine an order of optimization of the plurality of triple patterns and a query plan for executing the semantic query; and using the query plan to evaluate the semantic query over the database; wherein the data flow graph comprises a plurality of triple pattern and access method pair nodes connected by a plurality of edges representing dependencies among execution of the triple patterns in the semantic query; and wherein each edge in the data flow graph comprises a cost associated with evaluating a given triple pattern by a given access method with respect to statistics of the database for a triple pattern and access pair node associated with that edge; and the step of using the data flow graph and costs estimates further comprises determining the order of optimization of the plurality of triple patterns and the query plan for executing the semantic query such that edges in an optimal flow tree through the data flow graph comprise a minimum cumulative cost.