Query constraint encoding with type-based state machine

• US 9,177,017 B2
• Filed: 09/27/2010
• Issued: 11/03/2015
• Est. Priority Date: 09/27/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: De Smet, Bart, Meijer, Henricus Johannes Maria
• Primary Examiner(s): Das, Chameli
• Application Number:
  US12/890,870
• Publication Number:
  US 20120079464A1
• Time in Patent Office: 1,863 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 8/427 Parsing

Abstract

A query specified in a source programming language can be analyzed as a function of a type-based state machine that encodes query constraints of a target programming language. The type-based state machine can encode such constraints as types representing states and methods representing transitions between states or types.

Claims

1. A method of query analysis, comprising:

employing at least one processor configured to execute computer-executable instructions stored in memory to perform the following acts;

analyzing a query specified with a source programming language with respect to constraints of a target query programming language to determine validity of the query at compile time with a type-based state machine, wherein the type-based state machine is generated as a function of the target query programming language by encoding the constraints of the target query programming language in terms of data types as states and methods as transitions between the states.

2. The method of claim 1 further comprises generating the type-based state machine automatically from target programming-language semantics.

3. The method of claim 2 further comprises generating the type-based state machine from one of a grammar or type rules.

4. The method of claim 2 further comprises limiting computational complexity of the type-based state machine as a function of a parameter.

5. The method of claim 1 further comprises signaling an error upon detection of one or more invalid query operators or an invalid pattern of query operators.

6. The method of claim 5 further comprises signaling the error during query specification.

7. The method of claim 1 further comprises signaling an error upon detection of a failure to specify a minimal query.

8. The method of claim 1 further comprises suggesting valid query operators as the query is specified as a function of the type-based state machine.

9. A query analysis system, comprising:

a processor coupled to a memory the processor configured to execute the following computer-executable components stored in the memory;

a first component configured to validate a language-integrated query at compile time against a target query programming language with a type-based state machine, wherein the type-based state machine is generated as a function of a the target query programming language so that constraints of the target query language are encoded in terms of data types as states and methods as transitions between the states.

10. The system of claim 9, the type-based state machine encodes a portion of a grammar.

11. The system of claim 9, the type-based state machine encodes more constraints than provided by a grammar.

12. The system of claim 9, the type-based state machine captures a type system of the target query language.

13. The system of claim 9, the type-based state machine encodes a minimal query.

14. The system of claim 9, the first component is configured to signal an error upon detection one or more invalid query operators of an invalid pattern of query operators.

15. The system of claim 9 further comprises a second component configured to provide suggestions for code completion as a function of the type-based state machine.

16. The system of claim 9 further comprises a second component configured to generate the type-based state machine from a grammar automatically.

17. A computer-readable storage medium having instructions stored thereon that enable at least one processor to perform a method upon execution of the instructions, the method comprising:

generating a type-based state machine as a function of a target query programming language by encoding constraints of the target query programming language in terms of data types as states and methods as transitions between the states; and

validating a query specified with a source programming language at compile time with the type-based state machine.

18. The computer-readable storage medium of claim 17, the method further comprises generating the state machine from a grammar of the target query programming language.

19. The computer-readable storage medium of claim 17, the method further comprises limiting size or complexity of the state machine as a function of a parameter.

20. The computer-readable storage medium of claim 17, the method further comprises encoding a type system of the query programming language in the state machine.

21. A computer-readable storage medium having instructions stored thereon that enable at least one processor to perform the following act:

analyzing a query specified with a source programming language with respect to constraints of a target query programming language to determine validity of the query at compile time with a type-based state machine, wherein the type-based state machine is generated as a function of the target query programming language by encoding the constraints of the target programming language in terms of data types as states and methods as transitions between the states.