QUERY CONSTRAINT ENCODING WITH TYPE-BASED STATE MACHINE

• US 20120079464A1
• Filed: 09/27/2010
• Published: 03/29/2012
• Est. Priority Date: 09/27/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: De Smet, Bart, Meijer, Henricus Johannes Maria
• Granted Patent: US 9,177,017 B2
• Time in Patent Office: Days
• US Class Current: 717/143
• 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 at compile time as a function of a type-based state machine that encodes query constraints of a target programming language.

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 as a function of a type-base state machine that encodes semantics of supported query operations for a target query language.

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 medium having instructions stored thereon that enable at least one processor to perform the following acts:

generating a state machine that captures supported query operations of a query language from a grammar.

18. The computer-readable medium of claim 17 further comprises generating a type-based state machine from the grammar wherein states are encoded as types and transitions between states are encoded as methods.

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

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