QUERY SUBMISSION PIPELINE USING LINQ

• US 20100114885A1
• Filed: 06/16/2009
• Published: 05/06/2010
• Est. Priority Date: 10/21/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Karkanias, Chris D., Bowers, Stuart M., Smith, Burton Jordan, Wecker, David Brian
• Granted Patent: US 8,285,708 B2
• Time in Patent Office: Days
• US Class Current: 707/736
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers

Abstract

Described is a technology comprising a query processing pipeline in which a SPARQL query is processed into an intermediate LINQ query, which is then processed by a LINQ provider. The LINQ provider decides which instructions correspond to flat database queries, and routes those instructions a database engine (e.g., SQL server) for querying a database. Other instructions are provided to a reasoning engine for processing, e.g., by performing a graph traversal and/or database queries. The pipeline may include a parser that parses the query into an abstract syntax tree, and an optimizer that processes the abstract syntax tree into a LINQ query, including by reordering LINQ instructions and/or associating a flag with each of the instructions that indicates whether to query the database or provide the instruction to a reasoning engine.

Claims

1. In a computing environment, a system comprising, a query processing pipeline, including a LINQ provider that processes LINQ instructions, in which for an instruction that corresponds to a flat query, the LINQ provider provides a query to a database engine for querying a database, and for other instructions, provides data corresponding to the other instructions to a reasoning engine for processing.

2. The system of claim 1 wherein the query processing pipeline includes a parser that parses a query of a first query language into an abstract syntax tree.

3. The system of claim 2 wherein the query comprises a SPARQL query.

4. The system of claim 1 wherein the query processing pipeline includes an optimizer that processes an abstract syntax tree into the LINQ instructions.

5. The system of claim 4 wherein the abstract syntax tree is provided by a parser, or wherein the abstract syntax tree is provided by a program compiler.

6. The system of claim 4 wherein the optimizer reorders the LINQ instructions.

7. The system of claim 4 wherein the optimizer associates a flag with the LINQ instructions, the flag including a value that indicates whether to query the database with a flat query for an instruction.

8. The system of claim 1 wherein the pipeline includes means for pivoting a query from being node-centric to being edge-centric.

9. The system of claim 8 further comprising means for reverting the pivoting of at least one predicate from being edge-centric to being node-centric.

10. In a computing environment, a method comprising, transforming a query in a first query language into a LINQ query, and processing the LINQ query into at least one query in another database language and LINQ instructions provided to a reasoning engine, the reasoning engine determining from the LINQ instructions whether results are found via graph traversal or via a query provided in the other database language.

11. The method of claim 10 wherein transforming the query in a first query language into the LINQ query comprises parsing the query in the first query language into an abstract syntax tree.

12. The method of claim 11 wherein transforming the query further comprises optimizing the abstract syntax tree into the LINQ query.

13. The method of claim 12 wherein optimizing the abstract syntax tree into the LINQ query comprises determining LINQ instructions from the abstract syntax tree, and reordering the LINQ instructions.

14. The method of claim 10 further comprising, associating data with each LINQ instruction that indicates whether to process that instruction via a flat database query or by graph traversal.

15. The method of claim 10 wherein the first query language comprises SPARQL, and wherein the second query language comprises SQL.

16. In a computing environment, a system comprising, a query processing pipeline, including a parser that parses a query of a first query language into an abstract syntax tree, an optimizer that processes the abstract syntax tree into a LINQ query, a LINQ provider that processes the LINQ query into at least one flat query for providing to a database engine in a second query language, or into LINQ instructions for providing to a reasoning engine, or both into at least one flat query for providing to a database engine in a second query language and into LINQ instructions for providing to a reasoning engine.

17. The system of claim 16 wherein the first query language comprises SPARQL, and wherein the second query language comprises SQL.

18. The system of claim 16 wherein the optimizer reorders instructions in the LINQ query.

19. The system of claim 16 wherein the optimizer associates a flag with at least some LINQ instructions corresponding to the LINQ query, the flag indicating whether to query the database with a flat query for an instruction.

20. The system of claim 16 wherein the pipeline includes means for pivoting a query from being node-centric to being edge-centric, and means for reverting the pivoting of at least one predicate from being edge-centric to being node-centric.