Method and apparatus for optimizing the evaluation of semantic web queries

摘要

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.

主权项

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.