Method and apparatus for optimizing the evaluation of semantic web queries

• US 9,535,950 B2
• Filed: 01/27/2016
• Issued: 01/03/2017
• 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:
  US15/007,370
• Publication Number:
  US 20160140172A1
• Time in Patent Office: 342 Days
• 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 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.