Storing multidimensional data in a relational database management system

• US 6,636,870 B2
• Filed: 08/30/2002
• Issued: 10/21/2003
• Est. Priority Date: 10/25/1999
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Roccaforte, Raymond
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US10/232,581
• Publication Number:
  US 20030055832A1
• Time in Patent Office: 417 Days
• Field of Search: 707/100, 707/102, 707/104, 707/101, 707/2, 707/3, 707/10, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/958 Data cubes
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

Techniques are provided which address the problems associated with the conventional approaches for storing multidimensional data in a relational database system. According to technique, the many foreign key values of each row in the fact table are mapped to and replaced by a “replacement” value. A mapping function is provided that derives a replacement value from any given combination of foreign key values, and an inverse mapping function is provided to reproduce the combination of foreign key values given the replacement value. A mapping function is selected such that the foreign key value combinations of multidimensional values that are conceptually related to each other map to values that are close to each other. The rows in the fact table are then stored within the fact table in the sorted order, thus causing values that are conceptually related to each other to be stored physically near each other within the fact table. Various techniques are provided for generating the replacement value from the foreign key values by subdividing the multidimensional cube that contains all of the multidimensional values into smaller sub-cubes that are referred to as tiles. Variations on the tiling mechanism are provided. According to one approach, the cube is sub-divided into tiles based on the members of a particular level of a hierarchical dimension. According to another tiling approach, the tiles themselves may be subdivided into smaller tiles to create a hierarchy of tiles.

Claims

1. A method for generating a replacement value associated with a data cell of a multidimensional cube representing multidimensional data stored in relational tables, the method comprising the steps of:

generating a tile position value that represents a position of a tile in which the cell resides relative to other tiles within the multidimensional cube;

generating a local position value that represents a position of the cell relative to other cells within the tile in which the cell resides; and

generating a replacement value based on the tile position value and the local position value.

2. The method of claim 1, wherein the step of generating a replacement value comprises:

generating a single tile number based on the tile position value; and

generating a single offset number based on the local position value.

3. The method of claim 2, further comprising the step of:

storing within a single row of an index-only table, at least particular cell value associated with the data cell, and the single tile number associated with the particular cell value.

4. The method of claim 1, further comprising the step of:

representing the tile and zero or more other tiles that are associated with a particular range of dimension key values as a key-range partition of a fact table associated with the multidimensional data.

5. The method of claim 1, wherein the step of generating a tile position value comprises the step of:

generating a tile position value that includes a tile coordinate value for each dimension associated with the two or more dimension key values, wherein each tile coordinate value q_j is equal to

6. The method of claim 5, wherein the step of generating a replacement value includes the step of generating a single tile number based on the tile position value, and wherein the step of generating a single tile number includes the step of:

generating a tile number equal to

7. The method of claim 1, wherein the step of generating a local position value includes the step of:

generating a local position value that includes a local coordinate value for each dimension associated with the two or more dimension key values, wherein each local coordinate value r_j is equal to

8. The method of claim 7, wherein the step of generating a replacement value includes the step of generating a single offset based on the local position value, and wherein the step of generating a single offset includes the step of:

generating an offset equal to

9. A method for manipulating multidimensional data in relational tables, the method comprising the steps of:

maintaining a fact table for storing cell values that are associated with a plurality of dimensions;

receiving a request to store a particular cell value that is associated with a particular set of dimension key values, the particular set of dimension key values including one dimension key value for each of the plurality of dimensions;

generating a tile position that represents a position of a tile in which the particular cell value resides relative to other tiles within a multidimensional cube representing the multidimensional data;

generating a local position that represents a position of the particular cell value relative to other cells within the tile in which the cell resides;

generating a replacement value based on the tile position value and the local position value; and

storing within the fact table the particular cell value, and the replacement value in association with the particular cell value.

10. The method of claim 9, further comprising the step of:

maintaining metadata in a dictionary indicating that a mapping exists between the particular cell that contains the particular cell value and the replacement value.

11. The method of claim 9, wherein a plurality of cell values and associated replacement values are stored within the fact table, the method further comprising the steps of:

receiving a query that includes a join predicate on the fact table;

extracting cell values contained in the fact table;

mapping replacement values associated with respective cell values to respective associated sets of dimension key values;

expressing the predicate in terms of one or more associated sets of dimension key values; and

applying the predicate to the multidimensional data according to the query.

12. The method of claim 9, wherein the step of generating a replacement value includes:

generating a single tile number based on the tile position; and

generating a single offset number based on the local position.

13. The method of claim 12, wherein a plurality of cell values and associated replacement values are stored with the fact table, the method comprising the steps of:

receiving a query that includes a join predicate on the fact table;

extracting cell values contained in the fact table;

mapping replacement values associated with respective cell values to respective associated sets of dimension key values; and

expressing the predicate in terms of one or more associated sets of dimension key values; and

applying the predicate to the multidimensional data according to the query.

14. A computer-readable medium carrying one or more sequences of instructions for generating a replacement value associated with a data cell of a multidimensional cube representing multidimensional data stored in relational tables, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

generating a tile position value that represents a position of a tile in which the cell resides relative to other tiles within the multidimensional cube;

generating a local position value that represents a position of the cell relative to other cells within the tile in which the cell resides; and

generating a replacement value based on the tile position value and the local position value.

15. The computer-readable medium of claim 14, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of generating a replacement value by performing the step of:

generating a single tile number based on the tile position value; and

generating a single offset number based on the local position value.

16. The computer-readable medium of claim 15, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

storing within a single row of an index-only table, at least a particular cell value associated with the data cell, and the single tile number associated with the particular cell value.

17. The computer-readable medium of claim 14, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

representing the tile and zero or more other tiles that are associated with a particular range of dimension key values as a key-range partition of a fact table associated with the multidimensional data.

18. The computer-readable medium of claim 14, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of generating a tile position value by performing the step of:

generating a tile position value that includes a tile coordinate value for each dimension associated with the two or more dimension key values, wherein each tile coordinate value q_j is equal to

19. The computer-readable medium of claim 18, wherein the step of generating a replacement value includes the step of generating a single tile number based on the tile position value, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of generating a single tile number by performing the step of:

generating a tile number equal to

20. The computer-readable medium of claim 14, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of generating a local position value by performing the step of:

generating a local position value that includes a local coordinate value for each dimension associated with the two or more dimension key values, wherein each local coordinate value r_j is equal to

21. The computer-readable medium of claim 20, wherein the step of generating a replacement value includes the step of generating a single offset based on the local position value, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of generating a single offset by performing the step of:

generating an offset equal to

22. A computer-readable medium carrying one or more sequences of instructions for manipulating multidimensional data in relational tables, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

maintaining a fact table for storing cell values that are associated with a plurality of dimensions;

receiving a request to store a particular cell value that is associated with a particular set of dimension key values, the particular set of dimension key values including one dimension key value for each of the plurality of dimensions;

generating a tile position that represents a position of a tile in which the particular cell value resides relative to other tiles within a multidimensional cube representing the multidimensional data;

generating a local position that represents a position of the particular cell value relative to other cells within the tile in which the cell resides;

generating a replacement value based on the tile position value and the local position value; and

storing within the fact table the particular cell value, and the replacement value in association with the particular cell value.

23. The computer-readable medium of claim 22, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

maintaining metadata in a dictionary indicating that a mapping exists between the particular cell that contains the particular cell value and the replacement value.

24. The computer-readable medium of claim 22, wherein a plurality of cell values and associated replacement values are stored within the fact table, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a query that includes a join predicate on the fact table;

extracting cell values contained in the fact table;

mapping replacement values associated with respective cell values to respective associated sets of dimension key values;

expressing the predicate in terms of one or more associated sets of dimension key values; and

applying the predicate to the multidimensional data according to the query.

25. The computer-readable medium of claim 22, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of generating a replacement value by performing the steps of:

generating a single tile number based on the tile position; and

generating a single offset number based on the local position.

26. The computer-readable medium of claim 25, wherein a plurality of cell values and associated replacement values are stored with the fact table, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a query that includes a join predicate on the fact table;

extracting cell values contained in the fact table;

mapping replacement values associated with respective cell values to respective associated sets of dimension key values; and

expressing the predicate in terms of one or more associated sets of dimension key values; and

applying the predicate to the multidimensional data according to the query.