Storing multidimensional data in a relational database management system
First Claim
1. A method for storing 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, said particular set of dimension key values including one dimension key value stored in each of said plurality of dimensions;
generating a replacement value based on two or more dimension key values in said particular set of dimension key values; and
storing within said fact table said particular cell value; and
said replacement value in association with said particular cell value.
2 Assignments
0 Petitions
Accused Products
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.
296 Citations
44 Claims
-
1. A method for storing 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, said particular set of dimension key values including one dimension key value stored in each of said plurality of dimensions;
generating a replacement value based on two or more dimension key values in said particular set of dimension key values; and
storing within said fact table said particular cell value; and
said replacement value in association with said particular cell value.- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
the two or more dimension key values includes a particular dimension key value from a particular dimension;
the method further comprises the step of storing coordinate values within the dimension table associated with said particular dimension; and
the step of generating a replacement value includes generating a replacement value based on a coordinate value stored in said dimension table in association with said particular dimension key value.
-
-
4. The method of claim 1 wherein the step of storing said replacement value in association with said particular cell value is performed without storing said two or more dimension key values in association with said particular cell value.
-
5. The method of claim 4 further comprising the steps of:
-
reading the replacement value associated with said particular cell value from said fact table; and
determining that said two or more dimension key values are associated with said particular cell value based on said replacement value.
-
-
6. The method of claim 1 wherein the step of generating a replacement value includes generating the replacement value based on dimension key values that correspond to all dimension key values in said particular set of dimension key values.
-
7. The method of claim 1 wherein the step of generating a replacement value includes the steps of:
-
establishing a mapping between dimension key values in said plurality of dimensions and cells of a multidimensional cube;
subdividing said multidimensional cube into tiles;
determining which tile of said multidimensional cube contains a cell that corresponds to said particular cell value; and
generating said replacement value based on the tile that contains the cell that corresponds to said particular cell value.
-
-
8. The method of claim 7 wherein each row of the fact table corresponds to a tile of said multidimensional cube and stores:
-
data that identifies said tile; and
the particular cell values that correspond to cells in said tile.
-
-
9. The method of claim 7 wherein each row of the fact table corresponds to a cell value and stores data that identifies:
-
the tile that contains the cell associated with said cell value; and
a relative location of the cell within said tile.
-
-
10. The method of claim 7 wherein:
-
a particular dimension of said plurality of dimensions is hierarchical and includes a set of finest-level dimension values and a set of non-finest level dimension values; and
the step of subdividing said multidimensional cube into tiles includes subdividing said multidimensional cube into a first set of tiles based on a mapping between said dimension values in said set of finest-level dimension values and dimension values in said set of non-finest-level dimension values.
-
-
11. The method of claim 10 wherein:
-
said particular dimension includes a second set of non-finest level dimension values that have a coarser level of granularity than said set of finest-level dimension values; and
a finer level of granularity than said set of non-finest-level dimension values;
the step of subdividing said multidimensional cube into tiles includes subdividing each tile of said first set of tiles into a second set of tiles based on a mapping between said dimension values in said set of finest-level dimension values and dimension values in said second set of non-finest-level dimension values.
-
-
12. The method of claim 7 wherein the step of subdividing said multidimensional cube into tiles includes establishing fixed-width tiling ranges for a particular dimension of said plurality of dimensions.
-
13. The method of claim 12 wherein the step of subdividing said multidimensional cube into tiles further includes establishing fixed-width tiling ranges for a dimension of said plurality of dimensions other than said particular dimension.
-
14. A method for clustering multidimensional values in a relational database system, the method comprising the steps of:
-
maintaining a fact table for storing cell values that are associated with a plurality of dimensions;
establishing a mapping between dimension key values in said plurality of dimensions and cells of a multidimensional cube;
subdividing said multidimensional cube into tiles; and
selecting where to store each cell value within said fact table based on the tile of said multidimensional cube that contains the cell associated with said cell value. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22)
a particular dimension of said plurality of dimensions is hierarchical and includes a set of finest-level dimension values and a set of non-finest level dimension values; and
the step of subdividing said multidimensional cube into tiles includes subdividing said multidimensional cube into a first set of tiles based on a mapping between said dimension values in said set of finest-level dimension values and dimension values in said set of non-finest-level dimension values.
-
-
16. The method of claim 15 wherein:
-
said particular dimension includes a second set of non-finest level dimension values that have a coarser level of granularity than said set of finest-level dimension values; and
a finer level of granularity than said set of non-finest-level dimension values;
the step of subdividing said multidimensional cube into tiles includes subdividing each tile of said first set of tiles into a second set of tiles based on a mapping between said dimension values in said set of finest-level dimension values and dimension values in said second set of non-finest-level dimension values.
-
-
17. The method of claim 14 wherein the step of subdividing said multidimensional cube into tiles includes establishing fixed-width tiling ranges for a particular dimension of said plurality of dimensions.
-
18. The method of claim 17 wherein the step of subdividing said multidimensional cube into tiles further includes establishing fixed-width tiling ranges for a dimension of said plurality of dimensions other than said particular dimension.
-
19. The method of claim 14 wherein:
-
the step of subdividing said multidimensional cube into tiles includes the steps of subdividing said multidimensional cube into a first set of tiles based on a first criteria, and subdividing each tile of said first set of tiles into a second set of tiles based on a second criteria; and
the step of selecting where to store each cell value within said fact table is performed based on the tile of said first set of tiles that contains the cell associated with said cell value, and the tile of said second set of tiles that contains the cell associated with said cell value.
-
-
20. The method of claim 19 further comprising the steps of:
-
establishing a first set of clusters within said fact table, wherein each cluster in said first set of clusters corresponds to rows associated with a particular tile in said first set of tiles; and
establishing a second set of clusters within each cluster of said first set of clusters, wherein each cluster in said second set of clusters corresponds to rows associated with a particular tile in said second set of tiles.
-
-
21. The method of claim 14 wherein:
-
the method further comprises the step of assigning tile numbers to said tiles; and
the step of selecting where to store each cell value within said fact table includes storing rows in said fact table in sorted order based on said tile numbers.
-
-
22. The method of claim 21 wherein the step of assigning tile numbers to said tiles is performed using an assignment technique that assigns closely related tile numbers to tiles that reside at closely related positions within said multidimensional cube.
-
23. A computer-readable medium bearing instructions for storing multidimensional data in relational tables, the instructions including instructions for performing 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, said particular set of dimension key values including one dimension key value stored in each of said plurality of dimensions;
generating a replacement value based on two or more dimension key values in said particular set of dimension key values; and
storing within said fact table said particular cell value; and
said replacement value in association with said particular cell value.- View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35)
the two or more dimension key values includes a particular dimension key value from a particular dimension;
the computer-readable medium further comprises instructions for performing the step of storing coordinate values within the dimension table associated with said particular dimension; and
the step of generating a replacement value includes generating a replacement value based on a coordinate value stored in said dimension table in association with said particular dimension key value.
-
-
26. The computer-readable medium of claim 23 wherein the step of storing said replacement value in association with said particular cell value is performed without storing said two or more dimension key values in association with said particular cell value.
-
27. The computer-readable medium of claim 26 further comprising instructions for performing the steps of:
-
reading the replacement value associated with said particular cell value from said fact table; and
determining that said two or more dimension key values are associated with said particular cell value based on said replacement value.
-
-
28. The computer-readable medium of claim 23 wherein the step of generating a replacement value includes generating the replacement value based on dimension key values that correspond to all dimension key values in said particular set of dimension key values.
-
29. The computer-readable medium of claim 23 wherein the step of generating a replacement value includes the steps of:
-
establishing a mapping between dimension key values in said plurality of dimensions and cells of a multidimensional cube;
subdividing said multidimensional cube into tiles;
determining which tile of said multidimensional cube contains a cell that corresponds to said particular cell value; and
generating said replacement value based on the tile that contains the cell that corresponds to said particular cell value.
-
-
30. The computer-readable medium of claim 29 wherein each row of the fact table corresponds to a tile of said multidimensional cube and stores:
-
data that identifies said tile; and
the particular cell values that correspond to cells in said tile.
-
-
31. The computer-readable medium of claim 29 wherein each row of the fact table corresponds to a cell value and stores data that identifies:
-
the tile that contains the cell associated with said cell value; and
a relative location of the cell within said tile.
-
-
32. The computer-readable medium of claim 29 wherein:
-
a particular dimension of said plurality of dimensions is hierarchical and includes a set of finest-level dimension values and a set of non-finest level dimension values; and
the step of subdividing said multidimensional cube into tiles includes subdividing said multidimensional cube into a first set of tiles based on a mapping between said dimension values in said set of finest-level dimension values and dimension values in said set of non-finest-level dimension values.
-
-
33. The computer-readable medium of claim 32 wherein:
-
said particular dimension includes a second set of non-finest level dimension values that have a coarser level of granularity than said set of finest-level dimension values; and
a finer level of granularity than said set of non-finest-level dimension values;
the step of subdividing said multidimensional cube into tiles includes subdividing each tile of said first set of tiles into a second set of tiles based on a mapping between said dimension values in said set of finest-level dimension values and dimension values in said second set of non-finest-level dimension values.
-
-
34. The computer-readable medium of claim 29 wherein the step of subdividing said multidimensional cube into tiles includes establishing fixed-width tiling ranges for a particular dimension of said plurality of dimensions.
-
35. The computer-readable medium of claim 32 wherein the step of subdividing said multidimensional cube into tiles further includes establishing fixed-width tiling ranges for a dimension of said plurality of dimensions other than said particular dimension.
-
36. A computer-readable medium bearing instructions for clustering multidimensional values in a relational database system, the instructions including instructions for the steps of:
-
maintaining a fact table for storing cell values that are associated with a plurality of dimensions;
establishing a mapping between dimension key values in said plurality of dimensions and cells of a multidimensional cube;
subdividing said multidimensional cube into tiles; and
selecting where to store each cell value within said fact table based on the tile of said multidimensional cube that contains the cell associated with said cell value. - View Dependent Claims (37, 38, 39, 40, 41, 42, 43, 44)
a particular dimension of said plurality of dimensions is hierarchical and includes a set of finest-level dimension values and a set of non-finest level dimension values; and
the step of subdividing said multidimensional cube into tiles includes subdividing said multidimensional cube into a first set of tiles based on a mapping between said dimension values in said set of finest-level dimension values and dimension values in said set of non-finest-level dimension values.
-
-
38. The computer-readable medium of claim 37 wherein:
-
said particular dimension includes a second set of non-finest level dimension values that have a coarser level of granularity than said set of finest-level dimension values; and
a finer level of granularity than said set of non-finest-level dimension values;
the step of subdividing said multidimensional cube into tiles includes subdividing each tile of said first set of tiles into a second set of tiles based on a mapping between said dimension values in said set of finest-level dimension values and dimension values in said second set of non-finest-level dimension values.
-
-
39. The computer-readable medium of claim 36 wherein the step of subdividing said multidimensional cube into tiles includes establishing fixed-width tiling ranges for a particular dimension of said plurality of dimensions.
-
40. The computer-readable medium of claim 37 wherein the step of subdividing said multidimensional cube into tiles further includes establishing fixed-width tiling ranges for a dimension of said plurality of dimensions other than said particular dimension.
-
41. The computer-readable medium of claim 36 wherein:
-
the step of subdividing said multidimensional cube into tiles includes the steps of subdividing said multidimensional cube into a first set of tiles based on a first criteria, and subdividing each tile of said first set of tiles into a second set of tiles based on a second criteria; and
the step of selecting where to store each cell value within said fact table is performed based on the tile of said first set of tiles that contains the cell associated with said cell value, and the tile of said second set of tiles that contains the cell associated with said cell value.
-
-
42. The computer-readable medium of claim 41 further comprising instructions for performing the steps of:
-
establishing a first set of clusters within said fact table, wherein each cluster in said first set of clusters corresponds to rows associated with a particular tile in said first set of tiles; and
establishing a second set of clusters within each cluster of said first set of clusters, wherein each cluster in said second set of clusters corresponds to rows associated with a particular tile in said second set of tiles.
-
-
43. The computer-readable medium of claim 36 wherein:
-
the instructions further comprise instructions for assigning tile numbers to said tiles; and
the step of selecting where to store each cell value within said fact table includes storing rows in said fact table in sorted order based on said tile numbers.
-
-
44. The computer-readable medium of claim 43 wherein the step of assigning tile numbers to said tiles is performed using an assignment technique that assigns closely related tile numbers to tiles that reside at closely related positions within said multidimensional cube.
Specification