Multiple dimensioned database architecture supporting table groups

• US 8,312,020 B2
• Filed: 06/04/2011
• Issued: 11/13/2012
• Est. Priority Date: 01/07/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Akiban Technologies, Inc. (Apple Inc.)
• Inventors: Herrnstadt, Ori
• Primary Examiner(s): Badawi, Sherief
• Application Number:
  US13/153,405
• Publication Number:
  US 20120030245A1
• Time in Patent Office: 528 Days
• Field of Search: 707/752, 707/748, 707/737, 707/802
• US Class Current: 707/737
• 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 non-transitory computer-readable storage medium storing a computer readable program of computer instructions, wherein the computer readable program when executed on a computer causes the computer to carry out operations to transform information in a data dictionary into one or more table groups, the operations comprising:

(a) constructing a directional graph comprising a set of one or more nodes, and one or more links among the one or more nodes, wherein a node is associated with a table in the data dictionary, and wherein a link is associated with a directional edge corresponding to a link between a primary key and a foreign key in the data dictionary;

(b) defining one or more root nodes, wherein a root node is a node in the directional graph to which no directional edges are directed;

(c) assigning an order of importance to the one or more root nodes, and

(d) processing the one or more root nodes into the one or more table groups by the following sub-steps;

(i) determining whether there are any more root nodes to process;

(ii) if so, for a root node of highest importance, following the directional edges from that root node to all connected nodes to identify a table group associated with that root node;

(iii) removing from the directional graph the nodes and directional edges associated with the table group identified in sub-step (ii); and

(iv) repeating sub-steps (i)-(iii) until there are no more root nodes to process.

2. The non-transitory computer-readable storage medium as described in claim 1 wherein a lookup table in the data dictionary is a reference table containing one or more key attribute values that are linked to other data in the data dictionary and that do not change frequently.

3. The non-transitory computer-readable storage medium as described claim 2 further including deleting one or more lookup edges in the directional graph constructed in operation (a), wherein a lookup edge is a directional edge between a first and second node in the directional graph, at least one of the first and second nodes corresponding to a lookup table in the data dictionary.

4. The non-transitory computer-readable storage medium as described in claim 1 where the one or more root nodes are assigned an order of importance based upon an expected or measured update access frequency.

5. The non-transitory computer-readable storage medium as described in claim 1 wherein a directional edge corresponds to a relationship associating information among tables within the table group identified.

6. The non-transitory computer-readable storage medium as described in claim 1 wherein the directional graph is constructed in response to an update event.

7. The non-transitory computer-readable storage medium as described in claim 6 wherein the update event is one of:

a creation, a deletion or update of a table, a relationship or an attribute in the data dictionary.

8. The non-transitory computer-readable storage medium as described in claim 1 wherein the table group identified includes one root table and at least one other table related thereto, each table in the table group being characterized as having columns of attributes and rows of data.