Expressive grouping for language integrated queries

• US 8,713,015 B2
• Filed: 04/23/2008
• Issued: 04/29/2014
• Est. Priority Date: 04/23/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vick, Paul A., Meijer, Henricus Johannes Maria
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): BIBBEE, JARED M
• Application Number:
  US12/107,840
• Publication Number:
  US 20090271382A1
• Time in Patent Office: 2,197 Days
• Field of Search: 707/4, 707/718, 707/737, 707/760
• US Class Current: 707/737
• CPC Class Codes: G06F 16/2433 Query languages
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/3331 Query processing
• CPC Class Codes: G06F 16/3332 Query translation

Abstract

Standard group operators afford expressive grouping across collections of various types for employment by a number of programming languages. The operators can leverage positional information to facilitate grouping of sequential/ordered input data. Groups can also include more than one input element. Additionally or alternatively, the operators can enable multi-level grouping such as nested or hierarchical grouping. In accordance with one aspect, the group operators can be employed in conjunction with language-integrated queries.

Claims

1. A computer system, comprising at least one processor coupled to at least one computer-readable storage medium storing instructions executable by the at least one processor to implement:

an application component including computer executable functionality;

a group component configured to facilitate execution of each of a positional, multi-member, and multi-level group operator specified by the application component, positional group operators being operators for which position within an ordering of one or more elements affects results of the operators, multi-member operators being operators that can cause a specific element to concurrently occupy a plurality of groups, multi-level group operators being operators that can cause a first group to be nested within a second group; and

an injector component configured to identify a reference to a group operator in the group component, fetch functionality corresponding to the identified group operator from the group component and inject the functionality into the application component to produce new executable grouping functionality, the injector component being configured to identify, fetch, and inject when the application component is encoded in any of a plurality of program languages.

2. The system of claim 1, wherein

the group operator comprises an accumulator component configured to accumulate an intermediate result of a grouping operation and, based on the intermediate result, facilitate the avoidance of a further, redundant grouping operation, and

the accumulator component is configured to be passed as a function to the group operator.

3. The system of claim 2, wherein the function includes a continuation function to cause the group operator to return the intermediate result instead of returning one or more groups.

4. The system of claim 1, wherein the group operator is executable across different data sources.

5. The system of claim 1, wherein the group operator is executable across an ordered set of data.

6. The system of claim 1, wherein the group operator is configured to divide elements into groups upon identification of an element that satisfies a predicate.

7. The system of claim 1, wherein the group operator is configured to, when at least one element not satisfying a predicate appears prior in the ordering to at least one element satisfying the predicate, divide elements into groups based upon the ordering, beginning each group with an initial element in the ordering or an element that is immediately subsequent to any element that satisfies a predicate, and terminating each group with a next element in the ordering that satisfies the predicate.

8. The system of claim 1, wherein the group operator is configured to create a new group upon determination that a next element is of a different value than a previous element.

9. The system of claim 1, wherein the group component is configured to facilitate execution of the positional, multi-member, and multi-level group operators.

10. The system of claim 1, the group operator comprising an accumulator component configured to accumulate intermediate results and output a final result to avoid generation of groups from in-memory representations thereof.

11. A data interaction method, comprising:

obtaining at least a portion of a computer program expressed in a query comprehension syntax;

identifying a plurality of references to a plurality of query group operators in the portion of the computer program, the plurality of query group operators including a positional group operator, a multi-member group operator, and a multi-level group operator, positional group operators being operators for which position within an ordering of one or more elements affects results of the operators, multi-member operators being operators that can cause a specific element to be concurrently included in a plurality of groups, multi-level group operators being operators that can cause a first group to be nested within a second group;

mapping the identified plurality of query group operators to one or more standard group operators; and

inserting the one or more standard group operators into the referencing computer program to enable grouping of ordered data as part of a data query operation,

wherein the computer program is encoded in any of a plurality of program languages.

12. The method of claim 11, further comprising:

performing positional grouping using a plurality of inserted standard group operators, including, for an input sequence;

creating groups for each sub-sequence that starts with a particular value;

terminating a group when an element with a predetermined property is encountered;

creating a new group when a key selector of a next value returns a new value; and

allowing elements to concurrently be members of different groups.

13. The method of claim 11, further comprising inserting the one or more standard group operators into the referencing computer program at one of a compile time or a run time.

14. The method of claim 13, further comprising grouping input data as a function of position of the input data in the ordering.

15. The method of claim 13, further comprising injecting input elements into more than one group concurrently.

16. The method of claim 13, further comprising:

constructing nested groupings.

17. The method of claim 13, further comprising:

passing intermediate results to an accumulation function in memory to provide a desired result and avoid group construction.

18. A computer-readable storage medium storing instructions that, if executed by a computing device, cause the computing device to perform operations comprising:

scanning a computer program coded in any one of a plurality of programming languages;

based on the scanning, identifying grouping functionality for grouping sequences of data independent of the programming language; and

injecting the grouping functionality into the computer program to facilitate sequence-based grouping in conjunction with a language-integrated query, the grouping functionality including a positional group operator, a multi-member group operator, and a multi-level group operator, positional group operators being operators for which position within an ordering of one or more elements affects results of the operators, multi-member operators being operators that can cause a specific element to be concurrently included in a plurality of groups, multi-level group operators being operators that can cause a first group and a second group to be grouped within a third group while preserving the separateness of the first group and the second group.

19. The computer-readable storage medium of claim 18, the grouping functionality including adding sequence elements to more than one group.

20. The computer-readable storage medium of claim 18, the grouping functionality including performing hierarchical grouping.