Method and Apparatus for Optimizing the Evaluation of Semantic Web Queries

• US 20160140172A1
• Filed: 01/27/2016
• Published: 05/19/2016
• Est. Priority Date: 04/03/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bornea, Mihaela Ancuta, Dolby, Julian Timothy, Kementsietsidis, Anastasios, Srinivas, Kavitha
• Granted Patent: US 9,535,950 B2
• Time in Patent Office: 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 inputs, the inputs comprising;

a semantic query over a resource description framework database, the semantic query comprising a plurality of hierarchically nested graph patterns, each graph pattern comprising at least one triple pattern comprising a subject, an object and predicate connecting the subject to the object;

statistics describing data in the resource description framework database; and

a plurality of access methods comprising alternative methods for evaluating each triple pattern;

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

creating a data flow graph, the data flow graph comprising a plurality of triple pattern and access method pair nodes connected by a plurality of edges representing dependencies among execution of the triple patterns;

determining an optimal flow tree through the data flow graph, the optimal flow comprising 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;

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

transforming the execution tree into a query plan that exploits the structure of the resource description framework database;

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

using the structured query language query to evaluate the semantic query over the resource description framework database.

2. The method of claim 1, wherein the semantic query comprises a SPARQL query and the query plan comprises a SPARQL query plan.

3. The method of claim 1, wherein the statistics comprise a total number of triples in the resource description framework database, average number of triples per subject, average number of triples per object, an identification of at least one of uniform resource identifiers and literals that appear in a greatest number of triples or combinations thereof.

4. The method of claim 1, wherein the plurality of access methods comprise access a triple patters by subject, access a triple pattern by object, conduct a full scan or combinations thereof.

5. The method of claim 1, wherein the logical relationships among triple patterns in the query parse tree comprise at least one of AND, OR, UNION and OPTIONAL.

6. The method of claim 1, wherein each edge in the plurality of edges in the data flow graph denotes a first triple pattern producing a variable required in either an object or a subject of a second triple pattern.

7. 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 access methods;

identifying a triple pattern having a constant in at least one of the subject and the 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.

8. The method of claim 7, 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.

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

calculating a cost of evaluating for a evaluating a given triple pattern by a given access method with respect to the statistics of the resource description framework 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.

10. The method of claim 1, 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 the statistics of the resource description framework database for a triple pattern and access pair node associated with that edge; and

the step of determining the optimal flow tree further comprises determining and optimal flow tree such that the edges in the optimal flow tree comprise a minimum cumulative cost.

11. The method of claim 1, wherein 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.

12. The method of claim 11, 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.

13. The method of claim 1, wherein transforming the execution tree into a query plan further comprises merging triple patterns having at least one of a common subject and common object into a single node in the query plan.

14. The method of claim 13, wherein:

the query plan comprises a plurality of nodes; and

using the query plan to create the structured query language query comprises creating a structured query language query for each node on the query plan.

15. The method of claim 1, the method further comprises communicating results of the structured query language query evaluation of the semantic query.

16. A 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 inputs, the inputs comprising;

a semantic query over a resource description framework database, the semantic query comprising a plurality of hierarchically nested graph patterns, each graph pattern comprising at least one triple pattern comprising a subject, an object and predicate connecting the subject to the object;

statistics describing data in the resource description framework database; and

a plurality of access methods comprising alternative methods for evaluating each triple pattern;

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

creating a data flow graph, the data flow graph comprising a plurality of triple pattern and access method pair nodes connected by a plurality of edges representing dependencies among execution of the triple patterns;

determining an optimal flow tree through the data flow graph, the optimal flow comprising 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;

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

transforming the execution tree into a query plan that exploits the structure of the resource description framework database;

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

using the structured query language query to evaluate the semantic query over the resource description framework database.

17. The computer-readable storage medium of claim 16, 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 access methods;

identifying a triple pattern having a constant in at least one of the subject and the 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;

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

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.

18. The computer-readable storage medium of claim 16, 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 the statistics of the resource description framework database for a triple pattern and access pair node associated with that edge; and

the step of determining the optimal flow tree further comprises determining and optimal flow tree such that the edges in the optimal flow tree comprise a minimum cumulative cost.

19. The computer-readable storage medium of claim 16, wherein creating the execution tree further comprises:

evaluating contents of each node in the parse tree sequentially starting with a root node in thee 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;

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.

20. The computer-readable storage medium of claim 16, wherein:

transforming the execution tree into a query plan further comprises merging triple patterns having at least one of a common subject and common object into a single node in the query plan, the query plan comprising a plurality of nodes; and

using the query plan to create the structured query language query comprises creating an structured query language query for each node on the query plan.