Multiple dimensioned database architecture using semi-structured data

• US 9,311,349 B2
• Filed: 06/04/2011
• Issued: 04/12/2016
• Est. Priority Date: 01/07/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: FoundationDB, LLC (Apple Inc.)
• Inventors: Herrnstadt, Ori
• Primary Examiner(s): Kim, Taelor
• Application Number:
  US13/153,407
• Publication Number:
  US 20120036167A1
• Time in Patent Office: 1,774 Days
• Field of Search: 707/769, 707600-674, 707790-812, 707821-899
• US Class Current: 1/1
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A database management system stores data form a plurality of logical tables as independent copies in different format. In one specific example the system organizes tables into table groups and de-normalizes the table in each table group. It also organizes data in a second format including vertical column containers that store all the data for one attribute, there being one column container for each table and each attribute within that table. The receipt of a query causes the system to develop a query plan that can interact with either or both of the container sets.

Claims

1. A method, comprising:

forming at least one table group from different tables included in a logical database, wherein the at least one table group;

comprises a root table and one or more related tables, and

defines a physical storage structure in a memory unit adapted to maintain data objects from the root table and the one or more related tables, wherein the data objects are co-located and stored consecutively within the memory unit in accordance with the physical storage structure;

aggregating the data objects from the root table and the one or more related tables to form a composite entity;

storing the composite entity in the memory unit in accordance with the physical storage structure; and

responsive to a query, sequentially accessing and providing the data objects from the root table and the one or more related tables in accordance with the composite entity.

2. The method of claim 1, wherein the composite entity conforms to a structured interchange data format.

3. The method of claim 2, wherein the structured interchange format is Extensible Markup Language (XML).

4. The method of claim 1, wherein the data objects are XML objects that conform to an XML schema.

5. The method of claim 4, wherein the at least one table group is formed based on the XML schema.

6. The method of claim 1, wherein the query is an XML query.

7. A non-transitory computer readable storage medium configured to store instructions that, when executed by a processor included in a computing device, cause the processor to carry out steps that include:

forming at least one table group from different tables included in a logical database, wherein the at least one table group;

comprises a root table and one or more related tables, and

defines a physical storage structure in a memory unit adapted to maintain data objects from the root table and the one or more related tables, wherein the data objects are co-located and stored consecutively within the memory unit in accordance with the physical storage structure;

aggregating the data objects from the root table and the one or more related tables to form a composite entity;

storing the composite entity in the memory unit in accordance with the physical storage structure; and

responsive to a query, sequentially accessing and providing the data objects from the root table and the one or more related tables in accordance with the composite entity.

8. The non-transitory computer readable storage medium of claim 7, wherein the composite entity conforms to a structured interchange data format.

9. The non-transitory computer readable storage medium of claim 8, wherein the structured interchange format is Extensible Markup Language (XML).

10. The non-transitory computer readable storage medium of claim 7, wherein the data objects are XML objects that conform to an XML schema.

11. The non-transitory computer readable storage medium of claim 10, wherein the at least one table group is formed based on the XML schema.

12. The non-transitory computer readable storage medium of claim 7, wherein the query is an XML query.

13. A computing device, comprising:

a processor configured to cause the computing device to carry out steps that include;

forming at least one table group from different tables included in a logical database, wherein the at least one table group;

comprises a root table and one or more related tables, and

defines a physical storage structure in a memory unit adapted to maintain data objects from the root table and the one or more related tables, wherein the data objects are co-located and stored consecutively within the memory unit in accordance with the physical storage structure;

aggregating the data objects from the root table and the one or more related tables to form a composite entity;

storing the composite entity in the memory unit in accordance with the physical storage structure; and

responsive to a query, sequentially accessing and providing the data objects from the root table and the one or more related tables in accordance with the composite entity.

14. The computing device of claim 13, wherein the composite entity conforms to a structured interchange data format.

15. The computing device of claim 14, wherein the structured interchange format is Extensible Markup Language (XML).

16. The computing device of claim 13, wherein the data objects are XML objects that conform to an XML schema.

17. The computing device of claim 16, wherein the at least one table group is formed based on the XML schema.