Query intermediate language method and system

• US 7,519,577 B2
• Filed: 06/23/2003
• Issued: 04/14/2009
• Est. Priority Date: 06/23/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Suver, Chris A., Brundage, Michael L.
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Gortayo; Dangelino N
• Application Number:
  US10/601,444
• Publication Number:
  US 20040267760A1
• Time in Patent Office: 2,122 Days
• Field of Search: 707/2, 707/3, 707/4, 707/100, 707/102, 707/1, 707/200, 715/513, 715/514
• US Class Current: 1/1
• CPC Class Codes: G06F 16/83 Querying
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer system and method generate a semantic representation of one or more XML language inquiries across relational and non-relational data sources. A semantic intermediate language representation explicitly describes the meaning of the one or more XML language inquiries. The semantic intermediate language may be a graph structure with nodes which describe the operations of the original query. Operators assigned to the nodes in the semantic graph allow an unambiguous definition of the original XML query. The semantic intermediate language may be used to perform XML queries over single or multiple data sources. A method includes receiving at least one inquiry, defining at least one node object for every operation within the received inquiry, translating each node object using operators, and generating a semantic representation from the operators.

Claims

1. A method for semantic representation of one or more XML language inquiries across relational and non-relational data sources, the method comprising:

receiving at least one XML language inquiry;

defining a plurality of nodes of a rooted graph structure which represents the at least one XML language inquiry, the rooted graph structure having at least one node object for every operation within the at least one XML language inquiry;

translating each of the at least one node objects using intermediate language operators represented by a unique corresponding node type and class, wherein there are multiple node types per class and one class per node type;

generating a semantic intermediate language representation having the rooted graph structure, wherein the semantic intermediate language representation explicitly describes a meaning of the one or more XML language inquiries, the semantic intermediate language representation including a tuple operator having three child nodes, the child nodes comprising a list of iterators that construct tuple space, a clause that filters the tuple space, and a clause that produces an outcome of the tuple space, wherein each iterator in the semantic intermediate language representation of a tuple node corresponds to one column in the tuple space, and wherein the semantic intermediate language representation decouples front-end language compilers from back-end query engines that use the semantic intermediate language representation, such that, when used in a compiler system having M front-front end languages and N back-end search engines, has a complexity of M plus N compiler implementations; and

effecting a partitioning of the at least one XML language inquiry by distributing one or more portions of the semantic intermediate language representation to corresponding query engines based upon a data source.

2. The method of claim 1, wherein the non-relational data sources comprise one or more of a text document, a spreadsheet, and a non-relational database.

3. The method of claim 1, wherein the generating step further comprises breaking down high level operations of the received inquiry into explicit parts.

4. The method of claim 3, wherein the explicit parts are common across multiple XML languages.

5. The method of claim 1, wherein the operators comprise one or more of special operators, data sources, literals, Boolean operators, sequence operators, arithmetic operators, string operators, value comparison operators, node comparison operators, tuple spaces, function definition and invocation, XML navigation, XML construction, XML property accessors, type operators, language specific operators, and data manipulation operators.

6. The method of claim 1, wherein the at least one XML language inquiry comprises one or more of an XML query language and an XML view definition language.

7. The method of claim 1, wherein the at least one XML language inquiry comprises one or more of an XPath, an XSLT, an XQuery, a DML, an OPath, and an Annotated Schema inquiry.

8. The method of claim 1, wherein the semantic intermediate language representation allows XML queries over XML views of relational data.

9. A semantics interpreter for expressing a meaning of one or more of an XML query and an XML view across multiple data sources, the interpreter comprising:

an input for receiving the one or more of an XML query and an XML view which form an inquiry;

a graph structure generator for defining node objects for every operation within the inquiry, wherein the inquiry is represented as a rooted graph;

a translator for assigning intermediate language operators for each node object, wherein the intermediate language operators break down operations of the inquiry into explicit parts, wherein each of the intermediate language operators is represented by a unique corresponding node type and class, and wherein there are multiple node types per class and one class per node type;

an output for providing the explicit parts as an intermediate language representation for expressing the meaning of the one or more of the XML query and the XML view, the intermediate language representation including a tuple operator having three child nodes, the child nodes comprising a list of iterators that construct tuple space, a clause that filters the tuple space, and a clause that produces an outcome of the tuple space, wherein each iterator in the intermediate language representation of a tuple node corresponds to one column in the tuple space, and wherein the intermediate language representation decouples front-end language compilers from back-end query engines that use the intermediate language representation, such that utilization of the intermediate language representation in the semantics interpreter, when used in a compiler system having M front-front end languages and N back-end search engines, has a complexity of M plus N compiler implementations; and

multiple query engines, each query engine corresponding to one or more portions of the intermediate language representation based upon a data source, wherein partitioning of the inquiry is effected by distributing at least one portion of the representation to the corresponding query engine.

10. The semantic interpreter of claim 9, wherein the multiple data sources comprise relational and non-relational data sources.

11. The semantic interpreter of claim 10, wherein the non-relational data sources comprise one or more of a text document, a spreadsheet, and a non-relational database.

12. The semantic interpreter of claim 9, wherein the operators comprise one or more of special operators, data sources, literals, Boolean operators, sequence operators, arithmetic operators, string operators, value comparison operators, node comparison operators, tuple spaces, function definition and invocation, XML navigation, XML construction, XML property accessors, type operators, language specific operators, and data manipulation.

13. The semantic interpreter of claim 9, wherein the explicit parts are common across multiple XML languages.

14. A computer-readable storage medium having computer-executable instructions for performing a method of intermediate language representation of a received inquiry, the computer-executable instructions comprising instructions for:

receiving one or more of an XML query and an XML view forming the received inquiry;

defining a plurality of node objects in a rooted graph structure which represents the at least one received inquiry, the graph structure having a node object for every operation within the received inquiry;

translating each node using intermediate language operators which break down operations of the received inquiry into explicit parts, wherein each of the intermediate language operators is represented by a unique corresponding node type and class, and wherein there are multiple node types per class and one class per node type;

generating instructions corresponding to the explicit parts forming an intermediate language representation for subsequent queries over one or more of relational and non-relational data sources, wherein the intermediate language representation comprises an explicit description of a meaning of the received inquiry, and wherein the intermediate language representation decouples front-end language compilers from back-end query engines that use the intermediate language representation, such that utilization of the intermediate language representation, when used in a compiler system having M front-front end languages and N back-end search engines, has a complexity of M plus N compiler implementations; and

effecting a partitioning of the inquiry by distributing one or more portions of the representation to corresponding query engines based upon the one or more data sources.

15. The computer-readable storage medium of claim 14, wherein the operators comprise one or more of special operators, data sources, literals, Boolean operators, sequence operators, arithmetic operators, string operators, value comparison operators, node comparison operators, tuple spaces, function definition and invocation, XML navigation, XML construction, XML property accessors, type operators, language specific operators, and data manipulation.

16. The computer-readable storage medium of claim 14, wherein the explicit parts are common across multiple XML languages.

17. The computer-readable storage medium of claim 14, wherein the received inquiry comprises one or more of an XML query language and an XML view definition language.

18. A computer system for generating a semantic representation of an inquiry, the computer system comprising:

a processor for executing computer instructions; and

at least one module comprising;

an input function for receiving one or more of an XML query and an XML view which forms the inquiry;

a graph structure generator for generating a rooted graph representing the inquiry and defining node objects for every operation within the inquiry;

a translator function for assigning intermediate language operators for each node object wherein the operators break down operations of the inquiry into explicit parts, wherein each of the intermediate language operators is represented by a unique corresponding node type and class, wherein there are multiple node types per class and one class per node type;

an output for providing the explicit parts as an intermediate language representation for expressing a meaning of the XML query and the XML view, wherein the intermediate language representation decouples front-end language compilers from back-end query engines that use the intermediate language representation, such that utilization of the intermediate language representation, when used in a compiler system having M front-front end languages and N back-end search engines, has a complexity of M plus N compiler implementations, wherein the at least one module comprises one or more software modules and one or more hardware modules, wherein the intermediate language representation includes a tuple operator having three child nodes, the child nodes comprising a list of iterators that construct tuple space, a clause that filters the tuple space, and a clause that produces an outcome of the tuple space, and wherein each iterator in the intermediate language representation of a tuple node corresponds to one column in the tuple space; and

effecting a partitioning of the inquiry by distributing one or more portions of the intermediate language representation to corresponding query engines based upon a data source.

19. The computer system of claim 18, wherein the operators comprise one or more of special operators, data sources, literals, Boolean operators, sequence operators, arithmetic operators, string operators, value comparison operators, node comparison operators, tuple spaces, function definition and invocation, XML navigation, XML construction, XML property accessors, type operators, language specific operators, and data manipulation.

20. The computer system of claim 18, wherein the explicit parts are common across multiple XML languages.