Group joins to navigate data relationships

• US 7,899,840 B2
• Filed: 03/29/2007
• Issued: 03/01/2011
• Est. Priority Date: 03/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hejlsberg, Anders, Meijer, Henricus Johannes Maria, Torgersen, Mads, Warren, Matthew J., Kulkarni, Dinesh Chandrakant
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Shanmugasundaram; Kannan
• Application Number:
  US11/693,136
• Publication Number:
  US 20080243764A1
• Time in Patent Office: 1,433 Days
• Field of Search: 707/3, 707/769, 707/770, 707999001-999005
• US Class Current: 707/769
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

A group join query facilitates navigation of relationships (e.g., one-to-many or many-to-one) across a plurality of data collections. Such a query operator produces nested or hierarchical results that capture the arguments passed thereto. If desired, the nested results can be flattened to simulate conventional relational database results.

Claims

1. A data retrieval system, comprising:

a processor;

a component implemented by the processor that acquires a plurality of data collections, wherein the data collections are specified in accordance with a nested or hierarchical data model;

a join component configured to allow remote execution by a user that performs the following;

identifies a group join query from a query syntax, wherein the group join query comprises a query that is directed to at least two different data collections, the group join query being configured to combine data rows of the different data collections, the group join query comprising a group join operator that allocates and returns an enumerable object that captures one or more arguments passed to the group join operator, wherein the arguments specify functions that extract join key values from elements of both outer and inner sequences, and wherein a hash join is employed to combine the data of the two different data collections;

traverses the plurality of data collections to locate and combine data across the collections that satisfy one or more group join arguments of a query, wherein the data is automatically made available to the join component based on the group join arguments and wherein the join component preserves the order of any outer sequence elements and, for each outer sequence element, preserves the order of any matching inner sequence elements, wherein the traversal includes implementing a superset of inner joins and left outer joins which are each written in terms of grouped joins; and

based on the traversal, returns a hierarchical result;

a hash component that executes a hash join function over join keys of both the inner and the outer sequences, wherein the hash join modifies the group join to increase group join performance by combining outer and inner sequence elements;

an identifier component that discovers and identifies abbreviated queries among the group queries, wherein a join is inferred from the abbreviated query syntax; and

a translation component that receives identification information from the identifier component identifying abbreviated code and translates the abbreviated code into an expanded format for implementation by the join component.

2. The system of claim 1, one or more nested loops are employed by the join component to combine the data.

3. The system of claim 1, further comprising a presentation component that flattens the hierarchical result.

4. The system of claim 3, the presentation component inserts into the query another query including an operator that injects a value for missing values.

5. The system of claim 1, the query is a language integrated query expression.

6. The system of claim 5, the data collections are structured in accordance with an object-oriented data model.

7. The system of claim 6, the data collections are acquired from memory or an external source.

8. The system of claim 1, the join component performs an outer join.

9. A method of traversing data collections, comprising:

acquiring a query identifying a one to many relationship amongst an inner and outer data collection, wherein the inner and outer data collections are specified in accordance with a nested or hierarchical data model;

identifying a group join query from a query syntax, wherein the group join query comprises a query that is directed to at least two different data collections, the group join query being configured to combine data rows of the different data collections, the group join query comprising a group join operator that allocates and returns an enumerable object that captures one or more arguments passed to the group join operator, wherein the arguments specify functions that extract join key values from elements of both outer and inner sequences, and wherein a hash join is employed to combine the data of the two different data collections;

traversing the plurality of data collections in accordance with the query to locate and combine data across the collections that satisfy one or more group join arguments of a query, wherein the data is automatically made available to the join component based on the group join arguments and wherein the join component preserves the order of any outer sequence elements and, for each outer sequence element, preserves the order of any matching inner sequence elements, wherein the traversal includes implementing a superset of inner joins and left outer joins which are each written in terms of grouped joins;

executing a hash join function over join keys of both the inner and the outer sequences, wherein the hash join modifies the group join to increase group join performance by combining outer and inner sequence elements;

identifying one or more abbreviated queries among the group queries, wherein a join is inferred from the abbreviated query syntax;

receiving identification information identifying abbreviated code portions and translating the abbreviated code into an expanded format for implementation by the join component;

based on the traversal and the translated code, returning selected data in a nested format.

10. The method of claim 9, further comprising identifying join keys for each data collection.

11. The method of claim 10, further comprising collecting elements of the inner collection by their keys in a hash table.

12. The method of claim 11, further comprising:

generating a hash key for each element of the outer collection as a function of the associated join key; and

looking up corresponding inner elements in the hash table with the hash key.

13. The method of claim 9, further comprising flattening the nested results.

14. The method of claim 13, comprising inserting into the query another query including an operator that injects a value for missing values.

15. The method of claim 9, further comprising performing an inner join.

16. The method of claim 9, further comprising performing an outer join.

17. A system to navigate relationships amongst data collections, comprising:

a processing means;

a memory means;

means for receiving a language integrated query expression, wherein language integrated query expression is configured to query a plurality of data collections that are specified in accordance with a nested or hierarchical data model;

means for identifying a group join query from a query syntax, wherein the group join query comprises a query that is directed to at least two different data collections, the group join query being configured to combine data rows of the different data collections, the group join query comprising a group join operator that allocates and returns an enumerable object that captures one or more arguments passed to the group join operator, wherein the arguments specify functions that extract join key values from elements of both outer and inner sequences, and wherein a hash join is employed to combine the data of the two different data collections;

means for traversing the plurality of the plurality of data collections to locate and combine data across the plurality of data collections in accordance with the query expression, to satisfy one or more group join arguments of the query expression, wherein the data is automatically made available to the join component based on the group join arguments and wherein the join component preserves the order of any outer sequence elements and, for each outer sequence element, preserves the order of any matching inner sequence elements, wherein the traversal includes implementing a superset of inner joins and left outer joins which are each written in terms of grouped joins;

means for executing a hash join function over join keys of both the inner and the outer sequences, wherein the hash join modifies the group join to increase group join performance by combining outer and inner sequence elements;

means for identifying one or more abbreviated queries among the group queries, wherein a join is inferred from the abbreviated query syntax;

means for receiving identification information identifying abbreviated code portions and translating the abbreviated code into an expanded format for implementation by the join component; and

means for returning a nested result based on the traversal and the translated code.

18. The system of claim 17, further comprising a means for flattening the nested result to simulate relational database results.