Method and apparatus for optimizing the evaluation of semantic web queries

• US 9,280,585 B2
• Filed: 04/07/2015
• Issued: 03/08/2016
• Est. Priority Date: 04/03/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bornea, Mihaela Ancuta, Dolby, Julian Timothy, Kementsietsidis, Anastasios, Srinivas, Kavitha
• Primary Examiner(s): Arjomandi, Noosha
• Application Number:
  US14/680,705
• Publication Number:
  US 20150213089A1
• Time in Patent Office: 336 Days
• Field of Search: 707/718
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/3331 Query processing
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A semantic query over an RDF database is received with RDF database statistics and access methods for evaluating triple patterns in the query. The semantic query is expressed as a parse tree containing triple patterns and logical relationships among the triple patterns. The parse tree and access methods create a data flow graph containing a plurality of triple pattern and access method pair nodes connected by a plurality of edges, and an optimal flow tree through the data flow graph is determined such that costs are minimized and all triple patterns in the semantic query are contained in the optimal flow tree. A structure independent execution tree defining a sequence of evaluation through the optimal flow tree is created and is transformed into a database structure dependent query plan. This is used to create an SQL query that is used to evaluate the semantic query over the RDF database.

Claims

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.

2. The method of claim 1, wherein the method further comprises:

using the query plan to create a structured query language query; and

using the structured query language query to evaluate the semantic query over the database.

3. The method of claim 1, wherein:

the optimal flow tree comprises a set of triple pattern and access method pair nodes and edges such that all triple patterns in the semantic query are contained in the optimal flow tree; and

using the data flow graph and costs estimates to determine the query plan further comprises;

creating an execution tree independent of a structure of the database, the execution tree comprising a sequence of evaluation of triple patterns in the optimal flow tree; and

transforming the execution tree into the query plan that exploits the structure of the database.

4. The method of claim 3, wherein:

the method further comprises expressing the semantic query as a query parse tree comprising a plurality of nodes, the nodes comprising the triple patterns from the semantic query and logical relationships among the triple patterns; and

creating the execution tree further comprises;

evaluating contents of each node in the parse tree sequentially starting with a root node in the parse tree for inclusion in the execution tree; and

determining whether the contents of a given node are to be added to the execution tree immediately or held for inclusion in the execution tree after contents of other nodes are added to the execution tree.

5. The method of claim 4, wherein determining whether the contents of a given node are to be added immediately further comprises adding contents of each node at a latest possible point in the execution tree upon determination that variables or operators in contents are required for subsequent stages in the execution tree.

6. The method of claim 1, wherein creating the data flow graph further comprises:

defining a root node in the data flow graph;

selecting an access method from the plurality of triple pattern and access method pair nodes;

identifying a triple pattern having a constant in at least one of a subject and an object that can be accessed by the selected access method and lacking any required variable, a required variable comprising a variable in the triple pattern that is required to be bound when evaluated by the selected access method by a prior triple pattern evaluation; and

connecting a first triple pattern and access method pair to the root node comprising the selected access method and the identified triple pattern.

7. The method of claim 6, wherein creating the data flow graph further comprises:

connecting subsequent triple pattern and access method pairs to the first triple pattern and access method pair by identifying a required variable in a subsequent triple pattern that is required to be bound by evaluation of the identified triple pattern when the subsequent triple pattern is evaluated by a subsequent selected access method.

8. The method of claim 7, wherein creating the data flow graph further comprises:

calculating for the cost estimates a cost for evaluating a given triple pattern by a given access method with respect to the statistics of the database; and

assigning the calculated cost to edges in the data flow graph associated with triple pattern and access pair nodes comprising the given triple pattern and the given access method.

9. A non-transitory computer-readable storage medium containing a computer-readable code that when read by a computer causes the computer to perform 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, 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.

10. The non-transitory computer-readable storage medium of claim 9, wherein the method further comprises:

using the query plan to create a structured query language query; and

using the structured query language query to evaluate the semantic query over the database.

11. The non-transitory computer-readable storage medium of claim 9, wherein:

the optical flow tree comprises a set of triple pattern and access method pair nodes and edges such that all triple patterns in the semantic query are contained in the optical flow tree; and

using the data flow graph and costs estimates to determine the query plan further comprises;

creating an execution tree independent of a structure of the database, the execution tree comprising a sequence of evaluation of triple patterns in the optimal flow tree; and

transforming the execution tree into the query plan that exploits the structure of the database.

12. The non-transitory computer-readable storage medium of claim 11, wherein:

the method further comprises expressing the semantic query as a query parse tree comprising a plurality of nodes, the nodes comprising the triple patterns from the semantic query and logical relationships among the triple patterns; and

creating the execution tree further comprises;

evaluating contents of each node in the parse tree sequentially starting with a root node in the parse tree for inclusion in the execution tree; and

determining whether the contents of a given node are to be added to the execution tree immediately or held for inclusion in the execution tree after contents of other nodes are added to the execution tree.

13. The non-transitory computer-readable storage medium of claim 12, wherein determining whether the contents of a given node are to be added immediately further comprises adding contents of each node at a latest possible point in the execution tree upon determination that variables or operators in contents are required for subsequent stages in the execution tree.

14. The non-transitory computer-readable storage medium of claim 9, wherein creating the data flow graph further comprises:

defining a root node in the data flow graph;

selecting an access method from the plurality of triple pattern and access method pair nodes;

identifying a triple pattern having a constant in at least one of a subject and an object that can be accessed by the selected access method and lacking any required variable, a required variable comprising a variable in the triple pattern that is required to be bound when evaluated by the selected access method by a prior triple pattern evaluation; and

connecting a first triple pattern and access method pair to the root node comprising the selected access method and the identified triple pattern.

15. The non-transitory computer-readable storage medium of claim 14, wherein creating the data flow graph further comprises:

connecting subsequent triple pattern and access method pairs to the first triple pattern and access method pair by identifying a required variable in a subsequent triple pattern that is required to be bound by evaluation of the identified triple pattern when the subsequent triple pattern is evaluated by a subsequent selected access method.

16. The non-transitory computer-readable storage medium of claim 15, wherein creating the data flow graph further comprises:

calculating for the cost estimates a cost for evaluating a given triple pattern by a given access method with respect to the statistics of the database; and

assigning the calculated cost to edges in the data flow graph associated with triple pattern and access pair nodes comprising the given triple pattern and the given access method.