CONVERTING SPARQL QUERIES TO SQL QUERIES

• US 20090138437A1
• Filed: 11/26/2007
• Published: 05/28/2009
• Est. Priority Date: 11/26/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dua, Rajdeep S., Krishnamoorthy, Karthick, Kumar, Raman
• Granted Patent: US 7,818,352 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation

Abstract

RDF store database designs and efficient techniques for converting SPARQL queries to SQL queries are described that provide faster triplet access, and which can reduce the computational overhead and cost associated with storing large volumes of RDF metadata. In various embodiments RDF data can be stored in de-normalized tables tailored to provide efficient query and storage performance. The provided query conversion techniques provide reliable and efficient query performance.

Claims

1. A query conversion method for querying Resource Description Framework metadata stored in a relational database, the method comprising:

receiving a query substantially conforming to a Simple Protocol and Resource Description Framework Query Language, the query comprising a where clause, the where clause comprising a plurality of Resource Description Framework terms;

parsing the query; and

converting the query into a structured query language query by applying a conversion algorithm, wherein the structured query language query is configured to query a relational database storing data in at least one de-normalized table.

2. The method of claim 1, the method further comprising:

parsing the query to facilitate performing a pre-conversion setup task.

3. The method of claim 2, the method further comprising:

performing the pre-conversion setup task by generating a token list, the token list comprises a list of the plurality of Resource Description Framework terms of the where clause.

4. The method of claim 2, the where clause further comprises one or more triples, the method further comprising:

performing the pre-conversion setup task by creating a count of triples, the count of triples is the total number of the one or more triples.

5. The method of claim 2, the method further comprising:

performing the pre-conversion setup task by creating a list of variables to be selected by the query.

6. The method of claim 2, the method further comprising:

passing results of the pre-conversion setup task to the conversion algorithm.

7. The method of claim 1, the structured query language query having one or more structured query language query clauses, the method further comprising:

building the structured query language query by assembling the one or more structured query language query clauses into one or more associated string variables, from the plurality of Resource Description Framework terms.

8. The method of claim 7, the method further comprising:

assembling the one or more structured query language query clauses including assembling one or more of a FROM, WHERE, or a SELECT clause.

9. The method of claim 1, the method further comprising:

converting the query into a structured query language query by applying the conversion algorithm including determining a type for Resource Description Framework terms, wherein the type comprises one of a literal, uniform resource identifier, blank, or variable.

10. A computing device configured to perform the method of claim 1.

11. A database management system comprising computing means for performing the method of claim 1.

12. An apparatus that facilitates conversion of a Simple Protocol and Resource Description Framework Query Language query to a structured query language query, the apparatus comprising:

a conversion engine configured to receive a Simple Protocol and Resource Description Framework Query Language query, the query comprising a where clause, the where clause comprising a plurality of Resource Description Framework terms;

an algorithm component for converting the query into a structured query language query, wherein structured query language query is configured to query a relational database storing data in at least one de-normalized database table.

13. The apparatus of claim 12, the apparatus further comprising:

a parsing component configured to parse the query to facilitate performing a setup task prior to converting the query.

14. The apparatus of claim 13, the where clause further comprises one or more triples, the setup task includes one or more of generating a token list, creating a count of triples, or creating a list of variables to be selected by the query, the token list comprises a list of the plurality of Resource Description Framework terms of the where clause, and the count of triples is the total number of the one or more triples.

15. The apparatus of claim 13, the conversion engine is further configured to communicate information associated with the setup task to the algorithm component to facilitate converting the query into a structured query language query.

16. The apparatus of claim 12, the conversion engine is further configured to build the structured query language query by assembling one or more structured query language query clauses into one or more associated string variables, based in part on the plurality of Resource Description Framework terms.

17. A computer-readable medium having computer-executable instructions stored thereon for conversion of a Simple Protocol and Resource Description Framework Query Language query to a structured query language query, the computer-executable instructions comprising:

a first instruction set for receiving a query substantially conforming to a Simple Protocol and Resource Description Framework Query Language, the query comprising a where clause, the where clause comprising a plurality Resource Description Framework terms and one or more triples;

a second instruction set for parsing the query to perform setup tasks prior to query conversion, the setup task includes one or more of generating a token list, creating a count of triples, or creating a list of variables to be selected by the query, the token list comprises a list of the plurality of Resource Description Framework terms of the where clause, and the count of triples is the total number of the one or more triples; and

a third instruction set for applying conversion algorithm logic to convert the query into a structured query language query, wherein structured query language query is configured to query a relational database storing data in at least one de-normalized table.

18. The computer readable medium of claim 17, the third instruction set for applying conversion algorithm logic includes instructions for determining a type for Resource Description Framework terms, wherein the type comprises one of a literal, uniform resource identifier, blank, or variable.

19. The computer readable medium of claim 17, the third instruction set for applying conversion algorithm logic includes instructions for building the structured query language query by assembling one or more structured query language query clauses into one or more associated string variables.

20. The computer readable medium of claim 19, the one or more structured query language query clauses includes one or more of a FROM, WHERE, or a SELECT clause.