Method of calculating tuples for data cubes

• US 5,987,467 A
• Filed: 08/15/1997
• Issued: 11/16/1999
• Est. Priority Date: 08/15/1997
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.), Columbia University
• Original Assignee: AT&T Corporation (AT&T, Inc.), Columbia University
• Inventors: Srivastava, Divesh, Ross, Kenneth A.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US08/911,688
• Time in Patent Office: 823 Days
• Field of Search: 707/2, 707/3, 707/5, 707/6, 707/7, 707/100, 345/423
• 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: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and apparatus of calculating data cubes is shown in which a data set is partitioned into memory sized data fragments and cuboid tuples are calculated from the data fragments. A search lattice of the data cube is used as a basis for ordering calculations of lower dimensional cuboids in the data cube. Identification of a minimum number of paths through the lattice that is sufficient to traverse all nodes in the lattice is achieved by iteratively duplicating twice all paths in a lower dimensional space, distributing a new attribute to the first duplicate, moving end points from paths of the second duplicate to a corresponding path in the first duplicate and merging the first and second duplicates.

Claims

1. A method of constructing a data cube data structure from a data set, comprising the steps of:

partitioning the data set by a first attribute into a plurality of data fragments, and for each data fragment,

determining whether the size of the data fragment exceeds a predetermined threshold, and

when the size of the data fragment does not exceed the predetermined threshold, computing cuboid tuples from the data fragment according to;

sorting data of the data fragment by a first order of attributes, and

calculating tuples for all cuboid fragments indexed by a prefix of the first sort order.

2. The method of claim 1, further comprising steps of:

when the size of the data fragment exceeds the predetermined threshold, partitioning the data fragment according to a second attribute into a plurality of sub-fragments, and

for each sub-fragment,

determining whether the size of the sub-fragment exceeds the predetermined threshold, and

when the size of the sub-fragment does not exceed the predetermined threshold, computing cuboid tuples from the sub-fragment.

3. The method of claim 2, further comprising steps of:

when the size of a sub-fragment exceeds the predetermined threshold, recursively partitioning the sub-fragment by additional attributes into other data fragments until a size of each other data fragment does not exceed the predetermined threshold, and

for each other data fragment, computing cuboid tuples from the other data fragment.

4. The method of claim 1, wherein the computing step further comprises,

in the event that all tuples to be calculated from the data fragment are not calculated by the calculating step, recursively:

resorting the data fragment by additional sort orders of attributes, and

calculating tuples for all fragments indexed by prefixes of the additional sort orders until all fragments to be calculated from the data fragment are calculated.

5. The method of claim 4, wherein the sorting and resorting steps are performed to traverse a minimum number of paths through a search lattice of the data cube.

6. The method of claim 5, wherein the minimum number of paths are selected according to a method comprising the steps of:

counting out a number of dimensions equal to a number of dimensions of the data cube, and

for each counted dimension,

duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension,

distributing an attribute associated with the counted dimension to the first duplicate,

for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and

merging the paths of the first and second duplicate.

7. The method of claim 6, further comprising a step of, after all dimensions have been counted, reordering a prefix of each path in an order of end point of the path to first point of the path.

8. The method of claim 4, wherein the order of paths is chosen to possess a common prefix with a previous sort order.

9. The method of claim 1, further comprising steps of:

identifying a parent cuboid for a cuboid that remains to be calculated,

determining whether a size of the parent cuboid exceeds the predetermined threshold, and

in the event that the size of the parent cuboid exceeds the predetermined threshold,

partitioning the parent cuboid into second data fragments according to a second attribute,

for each second data fragment,

determining whether the size of the second data fragment exceeds the predetermined threshold, and

when the size of the second data fragment does not exceed the predetermined threshold, computing cuboid tuples from the second data fragment.

10. The method of claim 9, further comprising a step of in the event that the size of the parent cuboid does not exceed the predetermined threshold, calculating remaining cuboids from the parent cuboid.

11. The method of claim 10, wherein the step of calculating remaining cuboids comprises the steps of:

sorting the parent cuboid according to a first sort order,

computing uncalculated cuboids indexed by a prefix of the first sort order, and

iteratively;

resorting the parent cuboid according to additional sort orders, and

computing uncalculated cuboids indexed by a prefix of the additional sort orders until all cuboids are calculated.

12. The method of claim 11, wherein the sorting and resorting steps are performed to traverse a minimum number of paths through a search lattice of the data cube.

13. The method of claim 11, wherein the additional sort orders are chosen to possess a common prefix with a previous sort order.

14. A method of selecting a minimum number of paths necessary to traverse a search lattice of a data cube, comprising the steps of:

counting out a number of dimensions equal to a number of dimensions of the data cube, and

for each counted dimension,

duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension,

distributing an attribute associated with the counted dimension to the first duplicate,

for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and

merging the paths of the first and second duplicate; and

after all dimensions have been counted, reordering a prefix of each path in an order of end point of the path to first point of the path.

15. A data cube data structure constructed from a data set according to the method of:

partitioning the data set by a first attribute into a plurality of data fragments, and for each data fragment,

determining whether the size of the data fragment exceeds a predetermined threshold, and

when the size of the data fragment does not exceed the predetermined threshold, computing cuboid fragment tuples from the sorted data fragment according to;

sorting data of the data fragment by a first order of attributes,

calculating tuples for all cuboid fragments indexed by a prefix of the first sort order.

16. The data cube data structure of claim 15 wherein the method further comprises steps of:

when the size of the data fragment exceeds the predetermined threshold, partitioning the data fragment according to a second attribute into a plurality of sub-fragments, and

for each sub-fragment,

determining whether the size of the sub-fragment exceeds the predetermined threshold, and

when the size of the sub-fragment does not exceed the predetermined threshold, computing cuboid fragment tuples from the sub-fragment.

17. The data cube data structure of claim 16, wherein the method further comprises steps of:

when the size of a sub-fragment exceeds the predetermined threshold, recursively partitioning the sub-fragment by additional attributes into other data fragments until a size of each other data fragment does not exceed the predetermined threshold, and

for each other data fragment, computing cuboid fragment tuples from the other data fragment.

18. The data cube data structure of claim 15, wherein the computing step further comprises

in the event that all cuboid fragments to be calculated from the data fragment are not calculated by the calculating step, recursively:

resorting the data fragment by additional sort orders of attributes, and

calculating tuples for all cuboid fragments indexed by prefixes of the additional sort orders until all cuboid fragments to be calculated from the data fragment are calculated.

19. The data cube data structure of claim 18, wherein the sorting and resorting steps of the method are performed to traverse a minimum number of paths through a search lattice of the data cube.

20. The data cube data structure of claim 19, wherein the minimum number of paths are selected according to a sub-method comprising the steps of:

counting out a number of dimensions equal to a number of dimensions of the data cube, and

for each counted dimension,

duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension,

distributing an attribute associated with the counted dimension to the first duplicate,

for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and

merging the paths of the first and second duplicate.

21. The data cube data structure of claim 20, wherein the sub-method further comprises a step of, after all dimensions have been counted, reordering a prefix of each path in an order of end point of the path to first point of the path.

22. The data cube data structure of claim 21, further comprising a step of in the event that the size of the parent cuboid does not exceed the predetermined threshold, calculating remaining cuboids from the parent cuboid.

23. The data cube data structure of claim 18, wherein the additional sort orders are chosen to possess a common prefix with a previous sort order.

24. The data cube structure of claim 23, wherein the step of calculating remaining cuboids comprises the steps of:

sorting the parent cuboid according to a first sort order,

computing uncalculated cuboids indexed by a prefix of the first sort order,

recursively,

resorting the parent cuboid according to additional sort orders, and

computing uncalculated parent cuboids indexed by a prefix of the additional sort orders until all cuboids are calculated.

25. The data cube data structure of claim 24, wherein the sorting and resorting steps are performed to traverse a minimum number of paths through a search lattice of the data cube.

26. The data cube data structure of claim 24, wherein the additional sorts orders are chosen to possess a common prefix with a previous sort order.

27. The data cube data structure of claim 15 further comprising the steps of:

identifying a parent cuboid for an uncalculated cuboid;

determining whether a size of the parent cuboid exceeds the predetermined threshold, and

in the event that the size of the parent cuboid exceeds the predetermined threshold, partitioning the parent cuboid into second data fragments according to a second attribute,

for each second data fragment,

determining whether the size of the second data fragment exceeds the predetermined threshold, and

when the size of the second data fragment does not exceed the predetermined threshold, computing cuboid fragment tuples from the second data fragment.

28. A method of calculating a data cube from a data set, comprising the steps of:

identifying a minimum number of paths necessary to traverse a search lattice representing the data cube, wherein each of the minimum paths is characterized by a root node of the path, and

for each identified path, calculating the data cube from the data set indexed by each of the identified paths including, for each path;

sorting data of a cuboid that is a parent to the root node by a sort order identifying the path, and

calculating cuboids indexed by the sort order,

wherein tuples of each cuboid indexed by one of the minimum paths are calculated in unison.

29. A data cube data structure constructed from a data set according to the method of:

identifying a minimum number of paths necessary to traverse a search lattice representing the data cube, wherein each of the minimum paths is characterized by a root node of the path, and

calculating cuboids indexed by each of the identified paths including, for each path;

sorting data of a cuboid that is a parent to the root node by a sort order identifying the path, and

calculating cuboids indexed by the sort order,

wherein tuples of each cuboid indexed by one of the minimum paths are calculated in unison.

30. A method for performing a multiple attribute query on a data set in a memory, comprising the steps of:

determining whether a size of the data set exceeds a predetermined threshold;

when the size exceeds the predetermined threshold;

partitioning the data set by a first attribute into a plurality of data fragments, and

computing cuboid tuples from the data fragments according to;

sorting data of the data fragment by a first order of attributes,

calculating tuples for all cuboid fragments indexed by a prefix of the first sort order, and

identifying cuboid tuples responsive to the query.

31. The method of claim 30, wherein the attribute of partition is selected independently from the query.

32. The method of claim 30, wherein the computing step further, comprises

in the event that all tuples to be calculated from the data fragment are not calculated by the calculating step, recursively:

resorting the data fragment by additional sort orders of attributes, and

calculating tuples for all fragments indexed by prefixes of the additional sort orders until all fragments to be calculated from the data fragment are calculated.

33. The method of claim 32, wherein the sorting and resorting steps are performed to traverse a minimum number of paths through a search lattice of the data cube.

34. The method of claim 33, wherein the minimum number of paths are selected according to a method comprising the steps of:

counting out a number of dimensions equal to a number of dimensions of the data cube, and

for each counted dimension;

duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension,

distributing an attribute associated with the counted dimension to the first duplicate,

for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and

merging the paths of the first and second duplicate.

35. The method of claim 34, further comprising a step of, after all dimensions have been counted, reordering a prefix of each path in an order of end point of the path to first point of the path.

36. The method of claim 34, wherein an order of paths is chosen to possess a common prefix with a previous sort order.

37. Apparatus for performing a multiple attribute query on a data set, comprising:

a first memory for storing the data set,

a second memory that implements data storage and retrieval faster than the first memory, and

processor in communication with the first and second memories, wherein;

the processor determines whether the data set fits within the second memory,

when the data set does not fit within the second memory, the processor partitions the data set into a plurality of data fragments by a first attribute,

for each data fragment,

the processor loads the data fragment into the second memory, and

the processor computes cuboid tuples from the loaded data fragment according to;

sorting data of the data fragment by a first order of attributes,

calculating tuples for all cuboid fragments indexed by a prefix of

the first sort order

wherein certain of the computed cuboid tuples are responsive to the query.

38. Apparatus of claim 37, wherein the processor selects an attribute of partition independently from attributes defined in the query.

39. Apparatus of claim 37, wherein the processor further computes cuboid tuples according to,

in the event that all tuples to be calculated from the data fragment are not calculated by the calculating step, recursively:

resorting the data fragment by additional sort orders of attributes, and

calculating tuples for all fragments indexed by prefixes of the additional sort orders until all fragments to be calculated from the data fragment are calculated.

40. Apparatus of claim 39, wherein the processor performs the sorting and resorting steps to traverse a minimum number of paths through a search lattice of the data cube.

41. Apparatus of claim 40, wherein the processor selects the minimum number of paths according to the steps of:

counting out a number of dimensions equal to a number of dimensions of the data cube, and

for each counted dimension;

duplicating twice a set of paths of a search lattice for a data cube having one less dimension than the counted dimension,

distributing an attribute associated with the counted dimension to the first duplicate,

for each path in the second duplicate, moving an end point of the path to a corresponding path in the first duplicate, and

merging the paths of the first and second duplicate.