Method and apparatus for storage and retrieval of information in compressed cubes

• US 20050065910A1
• Filed: 08/06/2004
• Published: 03/24/2005
• Est. Priority Date: 08/08/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Hopeman, A.A., Soylemez, Ekrem, Welton, Caleb
• Granted Patent: US 9,195,699 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

A method and data structure is described that builds summary information using processor time that is usually proportional to the size of input data and a depth of hierarchies for a plurality of attributes. The output of computation is stored in a smaller area by eliminating redundant storage and computation. An index is generated which includes tuples or rows that include lower bound values for each of the attributes, values of children of the lower bound values based on the hierarchies of the attributes, and coverage class indicators of the coverage classes of the children.

Claims

1. A method of generating an index for a body of data, said method comprising:

receiving a plurality of values associated with a plurality of respective attributes characterized by a plurality of respective hierarchies;

generating a plurality of entries in the index, the entries including a parent entry having a plurality of bounds associated respectively with the values and located at respective positions within the respective hierarchies;

determining a plurality of child positions, wherein one of the child positions is associated with one of the bounds of one of the parent entries and located at a first position in one of the respective hierarchies, and the one of the child positions is strictly included within the one of the bounds of the parent entry within the one of the respective hierarchies;

generating a plurality of child entries based on the parent entry, wherein one of the child entries includes a child bound that is located at a second position in one of the respective hierarchies and the child bound is strictly included within the one of the bounds within said one of the respective hierarchies; and

storing the one of the child positions in association with the parent entry and the one of the child entries.

2. A method according to claim 1, wherein each of the child entries includes a respective one of the child bounds that is located at a respective second position and the respective child bound is strictly included within a corresponding one of the bounds.

3. A method according to claim 2, further comprising:

storing each of the child positions in association with the parent entry and the respective one of the child bounds.

4. A method according to claim 1, wherein the parent entry of the index represents a first coverage class and one of the child entries represents a second coverage class.

5. A method according to claim 1, wherein the one of the child positions indicates a position in the one of the respective hierarchies that is located in a level in the one of the respective hierarchies that is adjacent to a level of location of the associated one of the bounds of the parent entry.

6. A method according to claim 1, wherein the generating the entries includes pushing up at least one of the respective hierarchies.

7. A method according to claim 6, wherein the determining the child positions includes determining the child positions based on said pushing up the at least one of the respective hierarchies.

8. A method according to claim 6, wherein the determining the child positions includes drilling down at least one of the respective hierarchies.

9. A method according to claim 8, wherein:

the drilling down is performed in an attribute drill down ordering on the respective attributes that is a reversal of an attribute pushup ordering of the respective attributes of a previously pushed up attribute, and

the drilling down is performed in a hierarchy drill down ordering that is a reversal of a hierarchy pushup ordering of the respective hierarchies utilized when pushing up the respective hierarchies.

10. A method according to claim 1, wherein the generating the child entries includes processing the associated at least one of the bounds and a plurality of child values, each located in a descendant level to the associated at least one of the bounds within the one of the respective hierarchies.

11. A method according to claim 1, wherein the determining the plurality of child positions includes processing the associated one of the bounds and a plurality of child values, each located in a descendant level to the associated one of the bounds within the one of the respective hierarchies.

12. A method according to claim 11, further comprising:

determining if the child positions associated with a parent bound match; and

if the child positions associated with the parent bound match, then replacing the parent bound with a value of the the child positions associated with the parent bound, wherein the plurality of bounds includes the parent bound included in one of the parent entries.

13. A method according to claim 1, wherein said storing the one of the child positions includes storing a supplemental entry with the one of the child positions, a first indicator of the one parent entry, and a second indicator of the one of the child entries.

14. A method according to claim 1, wherein one of the respective attributes includes a dimension of a multidimensional database, a column of a relational database table, or a field of a record, or said one of the respective hierarchies includes a predefined hierarchy or an implicit hierarchy.

15. A computer-readable medium bearing instructions for generating an index, said instructions being arranged, upon execution, to cause one or more processors to perform the steps of a method according to claim 1.

16. A computer-readable medium bearing an index for a body of data defined by a plurality of attributes, said attributes characterized by respective hierarchies, said index comprising:

a first indicator of a parent coverage class, wherein the parent coverage class specifies a plurality of parent bounds, each of the parent bounds located in one of the hierarchies characterizing the attributes;

a child position within one of the hierarchies for a corresponding one of the attributes, wherein the child position is strictly included in one of the parent bounds specified for the corresponding one of the attributes; and

a second indicator of a child coverage class, wherein the child coverage class specifies a plurality of child bounds, each of the child bounds located in one of the hierarchies characterizing the attributes.

17. A computer-readable medium according to claim 16, wherein the index further comprises the first indicator of the parent coverage class in association with the plurality of the parent bounds.

18. A computer-readable medium according to claim 17, wherein the index further comprises a measure associated with the parent coverage class.

19. A computer-readable medium according to claim 17, wherein:

a first instance of the first indicator, the child position, and the second indicator is stored in a first file structure, and

a second instance of the first indicator and the plurality of the parent bounds is stored in a second file structure other than the first file structure.

20. A computer-readable medium according to claim 19, wherein the first file structure includes one of a database table, a tree-structured index, and an index-only table.

21. A computer-readable medium according to claim 19, wherein the first file structure includes a plurality of separate file structures, each of the separate file structures corresponding to one of the attributes.

22. A computer-readable medium according to claim 16, wherein one of the child bounds in the child coverage class is included within the child position within the one of the hierarchies.

23. A computer-readable medium according to claim 16, wherein one of the attributes includes a dimension of a multidimensional database, a column of a relational database table, or a field of a record, and wherein one of the respective hierarchies includes a predefined hierarchy or an implicit hierarchy.

24. A method of searching for an item using an index for a body of data defined by a plurality of attributes, said attributes characterized by respective hierarchies, said method comprising:

comparing a value of the item in a first attribute with a first attribute lower bound value associated with a first node of the index; and

if the value of the item in the first attribute is lower in the hierarchy of the first attribute than the first attribute lower bound value associated with the first node of the index, performing the steps of;

determining whether a child value of the first attribute lower bound value associated with the first node of the index is included in a path from the value of the item in the first attribute to the first attribute lower bound value associated with the first node of the index based on the hierarchy of the first attribute, and

if the child value is included in the path, comparing the value of the item in the first attribute with a first attribute lower bound value associated with a second node of the index, based on an indicator of a coverage class associated with the child value included in the first node of the index.

25. A method according to claim 24, further comprising:

if the value of the item in the first attribute is at least as high in the hierarchy of the first attribute as the first attribute lower bound value associated with the second node of the index, performing the step of;

comparing the value of the item in a second attribute with a second attribute lower bound value associated with the second node of the index.

26. A method according to claim 25, wherein an ordering of the first attribute and the second attribute is determined as a reversal of an ordering of the respective hierarchies utilized in generating the index.

27. A method according to claim 25, further comprising, after said comparing the value of the item in the second attribute with the second attribute lower bound value associated with the second node of the index, the step of:

if the value of the item in the second attribute is a value other than values included in a path in the hierarchy of the second attribute as traversed by a drill path, returning a null value.

28. A method according to claim 24, wherein one of the attributes includes a dimension of a multidimensional database, a column of a relational database table, or a field of a record, and wherein one of the respective hierarchies includes a predefined hierarchy or an implicit hierarchy.

29. A computer-readable medium bearing instructions for searching, said instructions being arranged, upon execution, to cause one or more processors to perform the steps of a method according to claim 24.

30. A method of traversing a body of data defined by a plurality of attributes, said attributes characterized by respective hierarchies, using an index, said method comprising the steps of:

initializing an array on each one of the plurality of attributes based on a lower bound value of each attribute which is associated with a child node of a plurality of nodes included in the index, and a path from each lower bound value of the child node to a value of a parent node lower bound value in each of the respective hierarchies, wherein the child node is determined by accessing a child coverage class indicator associated with the parent node; and

generating a cross product of rows based on the array on each one of the plurality of attributes.

31. A method according to claim 30, wherein one of the attributes includes a dimension of a multidimensional database, a column of a relational database table, or a field of a record, and wherein one of the respective hierarchies includes a predefined hierarchy or an implicit hierarchy.

32. A method according to claim 30, further comprising:

before the step of initializing based on a lower bound value and a path from each lower bound value of the child node to the value of the parent node lower bound value, performing the step of;

initializing an array on each one of the plurality of attributes based on a lower bound value of each attribute for a start node of the index.

33. A method according to claim 30, further comprising drilling down based on each child coverage class indicator associated with the child node.

34. A method according to claim 33, wherein said drilling down is performed in an order that is determined as a reversal of an ordering of the respective hierarchies utilized in generating the index.

35. A method according to claim 30, further comprising:

receiving a set of query values associated with one of the attributes, and wherein said generating the cross product further comprises generating the cross product of rows based on the array on each one of the plurality of attributes and the set of query values.

36. A computer-readable medium bearing instructions for traversing a body of data, said instructions being arranged, upon execution, to cause one or more processors to perform the steps of a method according to claim 30.