GROUP JOINS TO NAVIGATE DATA RELATIONSHIPS

• US 20080243764A1
• Filed: 03/29/2007
• Published: 10/02/2008
• 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
• Granted Patent: US 7,899,840 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• 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 component that acquires a plurality of data collections; and

a join component that combines data across the collections in accordance with a query and returns a hierarchical result.

2. The system of claim 1, the join component employs a hash join to efficiently combine data.

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

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

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

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

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

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

9. The system of claim 1, further comprises a component that infers a join from an abbreviated query syntax.

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

11. A method of traversing data collections, comprising:

acquiring a query identifying a one to many relationship amongst an inner and outer data collection;

selecting data from the collections in accordance with the query; and

returning selected data in a nested format.

12. The method of claim 11, further comprising identifying join keys for each data collection.

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

14. The method of claim 13, 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.

15. The method of claim 11, further comprising flattening the nested results.

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

17. The method of claim 11, further comprising performing an inner join.

18. The method of claim 11, further comprising performing an outer join.

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

means for receiving a language integrated query expression; and

means for joining data across two or more collections in accordance with the query expression and returning a nested result.

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