Patent US6636870B2 successfully refreshed from Google Patents.
US6636870B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Storing multidimensional data in a relational database management system
Assignee: Oracle International Corp
•
Filing: 2002-08-30
•
Granted: 2003-10-21
•
Expires: 2022-08-30
Abstract
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.
Inventors
- 👤 Raymond Roccaforte
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:44
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/20; G06F16/28; G06F16/283; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/954; Y10S707/957; Y10S707/958; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99941; Y10S707/99942; Y10S707/99943; Y10S707/99944; Y10S707/99945; Y10S707/99948
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
94 words
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.
Claim 2
Independent Claim
94 words
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.
Claim 3
Dependent Claim
38 words
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.
Claim 4
Dependent Claim
41 words
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.
Claim 5
Dependent Claim
44 words
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.
Claim 6
Dependent Claim
95 words
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 x j DIV T j ; wherein x j represents a respective global coordinate position of the cell within a respective dimension j; and wherein T j represents a number of dimension key values spanned by the tile along the respective dimension j.
Claim 7
Dependent Claim
92 words
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 sum( N− 1, 1, p 1 * . . . *p j *q [j+1] +q j +1; wherein q j represents a tile coordinate value associated with a respective dimension j; and wherein p j represents a number of pages along dimension j.
Claim 8
Dependent Claim
95 words
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 x j MOD T j ; wherein x j represents a respective global coordinate position of the cell within a respective dimension j; and wherein T j represents a number of dimension key values spanned by the tile along the respective dimension j.
Claim 9
Dependent Claim
78 words
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 sum( N− 1, 1, T 1 * . . . T j r [j+1] )+ r j +1; wherein r j represents a local coordinate value associated with a respective dimension j.
Claim 10
Independent Claim
161 words
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.
Claim 11
Independent Claim
161 words
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.
Claim 12
Dependent Claim
35 words
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.
Claim 13
Dependent Claim
92 words
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.
Claim 14
Dependent Claim
36 words
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.
Claim 15
Dependent Claim
92 words
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.
Claim 16
Dependent Claim
122 words
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.
Claim 17
Dependent Claim
122 words
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.
Claim 18
Dependent Claim
65 words
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.
Claim 19
Dependent Claim
64 words
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.
Claim 20
Dependent Claim
66 words
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.
Claim 21
Dependent Claim
119 words
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 x j DIV T j ; wherein x j represents a respective global coordinate position of the cell within a respective dimension j; and wherein T j represents a number of dimension key values spanned by the tile along the respective dimension j.
Claim 22
Dependent Claim
117 words
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 sum( N− 1, 1, p 1 * . . . *p j *q [j+1] )+ q j +1; wherein q j represents a tile coordinate value associated with a respective dimension j; and wherein p j represents a number of pages along dimension j.
Claim 23
Dependent Claim
119 words
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 x j MOD T j ; wherein x j represents a respective global coordinate position of the cell within a respective dimension j; and wherein T j represents a number of dimension key values spanned by the tile along the respective dimension j.
Claim 24
Dependent Claim
102 words
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 sum( N− 1, 1, T 1 * . . . T j *r [j+1] )+ r j +1; wherein r j represents a local coordinate value associated with a respective dimension j.
Claim 25
Dependent Claim
189 words
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.
Claim 26
Dependent Claim
189 words
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.
Claim 27
Dependent Claim
57 words
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.
Claim 28
Dependent Claim
113 words
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.
Claim 29
Dependent Claim
63 words
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.
Claim 30
Dependent Claim
114 words
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.
References Cited (Backward Citations)
US5359724A
Cited
US6161105A
Cited
US5848408A
Cited
US5978788A
Cited
US6122636A
Cited
US5940818A
Cited
US5943668A
Cited
US5926818A
Cited
US5905985A
Cited
US6205447B1
Cited
US5918232A
Cited
US6189004B1
Cited
US6212524B1
Cited
US6212515B1
Cited
US6163774A
Cited
US6282544B1
Cited
US6484179B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-10-20 | 2007-04-21 | 2007-10-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-10-20 | 2011-04-21 | 2011-10-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-10-20 | 2015-04-21 | 2015-10-21 | $7700.00 | Window Closed / Lapsed |