Method and apparatus for optimizing the evaluation of semantic web queries

Patent metadata

Field	Value
Publication number	US-9535950-B2
Application number	US-201615007370-A
Country	US
Kind code	B2
Filing date	Jan 27, 2016
Priority date	Apr 3, 2013
Publication date	Jan 3, 2017
Grant date	Jan 3, 2017

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.

First claim

What is claimed is:

1. A method for optimizing semantic web queries, the method comprising:
receiving a semantic web query over a database, the semantic web query comprising a plurality of triple patterns;
determining an optimal flow tree for a data flow graph through a parse tree for the semantic web query;
creating a query plan in SPARQL for the semantic web query using the parse tree and the optimal flow tree, the query plan in SPARQL comprising an execution tree for the semantic web query;
translating the query plan in SPARQL to an SQL query plan by:
transforming the execution tree into an equivalent entity-oriented storage query plan; and using the entity-oriented storage query plan to create the SQL query; and
using the SQL query plan to evaluate the semantic query over the database;
wherein the method further comprises building the parse tree to include a plurality of query triple nodes for the plurality of triple patterns and a plurality of relationship nodes for relationships among the plurality of triple patterns;
wherein the method further comprises computing the data flow graph through the parse tree to include a plurality of data flow graph nodes, each data flow graph node comprising a given triple pattern and an access method, and a plurality of edges between data flow graph nodes, each edge indicating a shared variable between triple patterns in a given pair of data flow graph nodes.

2. The method of claim 1 , wherein determining the optimal flow tree further comprises determining the optimal flow tree through the data flow graph that minimizes costs and that traverses all triple patterns in the semantic web query.

3. The method of claim 1 , wherein: creating the query plan in SPARQL further comprises creating a storage-independent query plan in SPARQL; and translating the query plan in SPARQL to the SQL query plan comprises translating the storage-independent query plan in SPARQL to a storage specific SQL query plan.

4. The method of claim 1 , wherein the entity-oriented storage comprises a ranked resource description framework storage.

5. The method of claim 1 , wherein: the execution tree for the semantic web query comprises an access method and an execution node for each triple pattern in the semantic web query; and transforming the execution tree for the semantic web query into an equivalent entity-oriented storage query plan comprises merging execution nodes for triple patterns having at least one of a common subject and a common object into merged plan nodes.

6. The method of claim 5 , wherein each merged plan node comprises a plurality of triple patterns and forms a star-query.

7. The method of claim 6 , wherein transforming the execution tree for the semantic web query into an equivalent entity-oriented storage query plan further comprises identifying merged plan nodes having star-queries affected by spills.

8. The method of claim 5 , wherein transforming the execution tree for the semantic web query into an equivalent entity-oriented storage query plan further comprises merging execution nodes referring to a common entity, having a common access method and producing star-queries that are not affected by spills.

9. The method of claim 5 , wherein transforming the execution tree for the semantic web query into an equivalent entity-oriented storage query plan further comprises merging execution nodes only for which equivalent SQL statements exist for the merged plan nodes.

10. 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 web query over a database, the semantic web query comprising a plurality of triple patterns; determining an optimal flow tree for a data flow graph through a parse tree for the semantic web query;
creating a query plan in SPARQL for the semantic web query using the parse tree and the optimal flow tree, the query plan in SPARQL comprising an execution tree for the semantic web query;
translating the query plan in SPARQL to an SQL query plan by:
transforming the execution tree into an equivalent entity-oriented storage query plan; and
using the entity-oriented storage query plan to create the SQL query; and
using the SQL query plan to evaluate the semantic query over the database;
wherein the method further comprises building the parse tree to include a plurality of query triple nodes for the plurality of triple patterns and a plurality of relationship nodes for relationships among the plurality of triple patterns;
wherein the method further comprises computing the data flow graph through the parse tree to include a plurality of data flow graph nodes, each data flow graph node comprising a given triple pattern and an access method, and a plurality of edges between data flow graph nodes, each edge indicating a shared variable between triple patterns in a given of data flow graph nodes.

11. The non-transitory computer-readable medium of claim 10 , wherein determining the optimal flow tree further comprises determining the optimal flow tree through the data flow graph that minimizes costs and that traverses all triple patterns in the semantic web query.

12. The non-transitory computer-readable medium of claim 10 , wherein: creating the query plan in SPARQL further comprises creating a storage-independent query plan in SPARQL; and translating the query plan in SPARQL to the SQL query plan comprises translating the storage-independent query plan in SPARQL to a storage specific SQL query plan.

13. The non-transitory computer-readable medium of claim 10 , wherein: the execution tree for the semantic web query comprises an access method and an execution node for each triple pattern in the semantic web query; and transforming the execution tree for the semantic web query into an equivalent entity-oriented storage query plan comprises merging execution nodes for triple patterns having at least one of a common subject and a common object into merged plan nodes.

14. The non-transitory computer-readable medium of claim 13 , wherein each merged plan node comprises a plurality of triple patterns and forms a star-query.

15. The non-transitory computer-readable medium of claim 14 , wherein transforming the execution tree for the semantic web query into an equivalent entity-oriented storage query plan further comprises identifying merged plan nodes having star-queries affected by spills.

16. The non-transitory computer-readable medium of claim 13 , wherein transforming the execution tree for the semantic web query into an equivalent entity-oriented storage query plan further comprises merging execution nodes referring to a common entity, having a common access method and producing star-queries that are not affected by spills and merging execution nodes only for which equivalent SQL statements exist for the merged plan nodes.

Assignees

• IBM

Inventors

• Bornea Mihaela Ancuta
• Dolby Julian Timothy
• Kementsietsidis Anastasios
• Srinivas Kavitha

Classifications

• G06F17/30466

  Physics · mapped topic

• G06F17/30442 Primary

  Physics · mapped topic

• G06F17/30958

  Physics · mapped topic

• G06F17/30463

  Physics · mapped topic

• G06F17/30657

  Physics · mapped topic