Method and system for performing range-sum queries on a data cube

• US 5,799,300 A
• Filed: 12/12/1996
• Issued: 08/25/1998
• Est. Priority Date: 12/12/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Srikant, Ramakrishnan, Ho, Ching-Tien
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): HO, RUAY L
• Application Number:
  US08/764,564
• Time in Patent Office: 621 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/100, 707/200, 707/503, 707/504, 345/342, 364/282.1, 364/282.3, 1/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method for performing a range-sum query in a database, in which the data is represented as a multi-dimensional data cube, is disclosed. The method comprises the steps of: selecting a subset of the dimensions of the data cube; computing a set of prefix-sums along the selected dimensions, based on the aggregate values in the cube corresponding the queried ranges; and generating a range-sum result based on the computed prefix-sums. Two d-dimensional arrays A and P are used for representing the data cube and the prefix-sums of the data cube, respectively. By maintaining the prefix-sum array P of the same size as the data cube, all range queries for a given cube can be answered in constant time, irrespective of the size of the sub-cube circumscribed by a query, using the inverse binary operator of the SUM operator. Alternatively, only auxiliary information for any user-specified fraction of the size of the d-dimensional data cube is maintained, to minimize the required system storage. The answer to a range query may now require access to some cells of the data cube in addition to the auxiliary information, but the average time complexity is still reduced significantly.

Claims

1. A method for performing a range-sum query in a database in which data include a plurality of attributes and are represented as a d-dimensional data cube having a plurality of cells, the dimensions of the data cube corresponding respectively to the attributes, each cell having an aggregate value of the corresponding data attribute values, and the range-sum query including a range of values for each data attribute, the method comprising the steps of:

selecting a subset of the dimensions of the data cube;

computing a plurality of prefix-sums along the selected dimensions, based on the aggregate values corresponding to the ranges of values of the data attributes; and

generating a range-sum result based on the data represented by the computed prefix-sums.

2. The method as recited in claim 1, wherein the range-sum query corresponds to a d-dimensional region of the data cube.

3. The method as recited in claim 1, wherein the range-sum query is based on an aggregate binary operator for which an inverse aggregate binary operator exists, the operators being operational on the data of the database.

4. The method as recited in claim 1, wherein:

the data cube is represented as a d-dimensional array A;

the computed prefix-sums are represented as a d-dimensional array P, the arrays A and P each having n₁ ×

n₂ ×

. . .×

n_d cells, where d is the number of dimensions of the data cube; and

the step of computing a plurality of prefix-sums includes the step of calculating;

##EQU9## where 1≦

x_j ≦

n_j, 1≦

j≦

d, and n_j is the size of dimension j of the arrays A and P.

5. The method as recited in claim 4, wherein the step of computing a plurality of prefix-sums includes the steps of:

performing one-dimensional prefix-sums along dimension 1 of the array A for all the cells in the array A;

storing the one-dimensional prefix-sums of the array A into an array P₁ ;

for i=2 to d;

(a) performing one-dimensional prefix-sums along dimension i of array P_i-1 ; and

(b) storing the one-dimensional prefix-sums of the array P_i-1 into an array P_i ; and

assigning array P_d to the prefix-sum array P.

6. The method as recited in claim 5, wherein:

the data cube includes a plurality of d-dimensional blocks each having b₁ ×

b₂ ×

. . .×

b_d cells, where b_i '"'"'s, for i=1 to d, are predetermined block factors; and

the method further comprises the steps of;

(a) for each block,

(i) summing up the aggregate values corresponding to all the cells in the block into a block sum; and

(ii) storing the block sum into one of the cells of the block, the array A of size n₁ ×

n₂ ×

. . .×

n_d now corresponding to a reduced array A'"'"' of size n₁ /b₁ ×

n₂ /b₂ ×

. . .×

n_d /b_d which includes the respective block sums for the blocks;

(b) executing the steps of performing and storing one-dimensional prefix-sums on the array A'"'"'; and

(c) outputting the prefix-sum array P as P'"'"'.

7. The method as recited in claim 6, wherein a subset of the block factors b_i '"'"'s, for 1≦

i≦

d, are equal to 1.

8. The method as recited in claim 6, wherein a subset of the block factors b_i '"'"'s, for 1≦

i≦

d, are equal to n_i.

9. The method as recited in claim 6, wherein the step of generating a range-sum result includes the steps of:

(i) for each dimension of the data cube, partitioning the range of values of the corresponding data attribute into three adjoining sub-ranges where the middle range is properly aligned with the blocks, the region of the data cube corresponding to the range-sum query thereby having 3^d disjoint sub-regions including an internal sub-region and 3^d -1 boundary sub-regions B_i '"'"'s;

(ii) computing a range-sum for the internal sub-region based on the array P'"'"';

(iii) computing a range-sum for each boundary sub-region B_i, based on the arrays P'"'"' and A; and

(iv) summing up the range-sums for all the 3^d sub-regions to arrive at the range-sum result.

10. The method for performing a range-sum query as recited in claim 9, wherein the step of computing a range-sum for each boundary sub-region B_i includes the step of summing up all the cells of the array A corresponding to B_i.

11. The method for performing a range-sum query as recited in claim 9, wherein the step of computing a range-sum for each boundary sub-region B_i includes the steps of:

computing a first sum from the cells of the array A which correspond to a superblock S_i of the boundary sub-region B_i, the superblock S_i being a minimum collection of the blocks that includes B_i ;

computing a second sum from the cells of the array A which correspond to a complementary region C_i of the boundary sub-region B_i, the complementary region C_i being the difference between the superblock S_i and the sub-region B_i ; and

subtracting the second sum from the first sum to arrive at the range-sum for the boundary sub-region B_i.

12. The method for performing a range-sum query as recited in claim 4, wherein the step of generating a range-sum result includes the step of calculating:

##EQU10## and the range of query for dimension i, for 1≦

i≦

d, is from l_i +1 to h_i, inclusively.

13. A computer program product for use with a computer system for performing a range-sum query in a database in which data include a plurality of attributes and are represented as a d-dimensional data cube having a plurality of cells, the dimensions of the data cube corresponding respectively to the attributes, each cell having an aggregate value of the corresponding data attribute values, and the range-sum query including a range of values for each data attribute, the computer program product comprising:

a computer-readable medium;

means, provided on the computer-readable medium, for directing the system to select a subset of the dimensions of the data cube;

means, provided on the computer-readable medium, for directing the system to compute a plurality of prefix-sums along the selected dimensions, based on the aggregate values corresponding to the ranges of values of the data attributes; and

means, provided on the computer-readable medium, for directing the system to generate a range-sum result based on the data represented by the computed prefix-sums.

14. The computer program product as recited in claim 13, wherein the range-sum query corresponds to a d-dimensional region of the data cube.

15. The computer program product as recited in claim 13, wherein the range-sum query is based on an aggregate binary operator for which an inverse aggregate binary operator exists, the operators being operational on the data of the database.

16. The computer program product as recited in claim 13, wherein:

the data cube is represented as a d-dimensional array A;

the computed prefix-sums are represented as a d-dimensional array P, the arrays A and P each having n₁ ×

n₂ ×

. . .×

n_d cells, where d is the number of dimensions of the data cube; and

the means for directing to compute a plurality of prefix-sums includes means, provided on the computer-readable medium, for directing the system to calculate;

##EQU11## where 1≦

x_j ≦

n_j, 1≦

j≦

d, and n, is the size of dimension j of the arrays A and P.

17. The computer program product as recited in claim 16, wherein the means for directing to compute a plurality of prefix-sums includes:

means, provided on the computer-readable medium, for directing the system to perform one-dimensional prefix-sums along dimension 1 of the array A for all the cells in the array A;

means, provided on the computer-readable medium, for directing the system to store the one-dimensional prefix-sums of the array A into an array P₁ ;

means, provided on the computer-readable medium, for directing the system, for i=2 to d;

(a) to perform one-dimensional prefix-sums along the dimension i of ii the array P_i-1 ; and

(b) to store the one-dimensional prefix-sums of the array P_i-1 into an array P_i ; and

means, provided on the computer-readable medium, for directing the system to assign array P_d to the prefix-sum array P.

18. The computer program product as recited in claim 17, wherein:

the data cube includes a plurality of d-dimensional blocks each having b₁ ×

b₂ ×

. . .×

b_d cells, where b_i '"'"'s, for i=1 to d, are predetermined block factors; and

the computer program product further comprises;

(a) for each block, means, provided on the computer-readable medium, for directing the system to;

(i) sum up the aggregate values corresponding to all the cells in the block into a block sum; and

(ii) store the block sum into one of the cells of the block, the array A of size n₁ ×

n₂ ×

. . .×

n_d now corresponding to a reduced array A'"'"' of size n₁ /b₁ ×

n₂ /b₂ ×

. . .×

n_d /b_d which includes the respective block sums for the blocks;

(b) means, provided on the computer-readable medium, for directing the system to perform and store one-dimensional prefix-sums on the array A'"'"'; and

(c) means, provided on the computer-readable medium, for directing the system to output the prefix-sum array P as P'"'"'.

19. The computer program product as recited in claim 18, wherein a subset of the block factors b_i '"'"'s, for 1≦

i≦

d, are equal to 1.

20. The computer program product as recited in claim 18, wherein a subset of the block factors b_i '"'"'s, for 1≦

i≦

d, are equal to n_i.

21. The computer program product as recited in claim 18, wherein the means for directing to generate a range-sum result includes:

(i) for each dimension of the data cube, means, provided on the computer-readable medium, for directing the system to partition the range of values of the corresponding data attribute into three adjoining sub-ranges where the middle range is properly aligned with the blocks, the region of the data cube corresponding to the range-sum query thereby having 3^d disjoint sub-regions including an internal sub-region and 3^d -1 boundary sub-regions B_i '"'"'s;

(ii) means, provided on the computer-readable medium, for directing the system to compute a range-sum for the internal sub-region based on the array P'"'"';

(iii) means, provided on the computer-readable medium, for directing the system to compute a range-sum for each boundary sub-region B_i, based on the arrays P'"'"' and A; and

(iv) means, provided on the computer-readable medium, for directing the system to sum up the range-sums for all the 3^d sub-regions to arrive at the range-sum result.

22. The computer program product as recited in claim 21, wherein the means for directing to compute a range-sum for each boundary sub-region B_i includes means, provided on the computer-readable medium, for directing the system to sum up all the cells of the array A corresponding to B_i.

23. The computer program product as recited in claim 21, wherein the means for directing to compute a range-sum for each boundary sub-region B_i includes:

means, provided on the computer-readable medium, for directing the system to compute a first sum from the cells of the array A which correspond to a superblock S_i of the boundary sub-region B_i, the superblock S_i being a minimum collection of the blocks that includes B_i ;

means, provided on the computer-readable medium, for directing the system to compute a second sum from the cells of the array A which correspond to a complementary region C_i of the boundary sub-region B_i, the complementary region C_i being the difference between the superblock S_i and the sub-region B_i ; and

means, provided on the computer-readable medium, for directing the system to subtract the second sum from the first sum to arrive at the range-sum for the boundary sub-region B_i.

24. The computer program product as recited in claim 16, wherein the means for directing to generate a range-sum result includes means, provided on the computer-readable medium, for directing the system to calculate:

##EQU12## and the range of query for dimension i, for 1≦

i≦

d, is from l_i +1 to h_i, inclusively.

25. A database system for performing a range-sum query in a database in which data include a plurality of attributes and are represented as a d-dimensional data cube having a plurality of cells, the dimensions of the data cube corresponding respectively to the attributes, each cell having an aggregate value of the corresponding data attribute values, and the range-sum query including a range of values for each data attribute, the system comprising:

means for selecting a subset of the dimensions of the data cube;

means for computing a plurality of prefix-sums along the selected dimensions, based on the aggregate values corresponding to the ranges of values of the data attributes; and

means for generating a range-sum result based on the data represented by the computed prefix-sums.

26. The system as recited in claim 25, wherein the range-sum query corresponds to a d-dimensional region of the data cube.

27. The system as recited in claim 25, wherein the range-sum query is based on an aggregate binary operator for which an inverse aggregate binary operator exists, the operators being operational on the data of the database.

28. The system as recited in claim 25, wherein:

the data cube is represented as a d-dimensional array A;

the computed prefix-sums are represented as a d-dimensional array P, the arrays A and P each having n₁ ×

n₂ ×

. . .×

n_d cells, where d is the number of dimensions of the data cube; and

the means for computing a plurality of prefix-sums includes means for calculating;

##EQU13## where 1≦

x_j ≦

n_j, 1≦

j≦

d, and n_j is the size of dimension j of the arrays A and P.

29. The system as recited in claim 28, wherein the means for computing a plurality of prefix-sums includes:

means for performing one-dimensional prefix-sums along dimension 1 of the array A for all the cells in the array A;

means for storing the one-dimensional prefix-sums of the array A into an array P₁ ;

for i=2 to d;

(a) means for performing one-dimensional prefix-sums along the dimension i of array P_i-1 ; and

(b) means for storing the one-dimensional prefix-sums of the array P_i-1 into an array P_i ; and

means for assigning array P_d to the prefix-sum array P.

30. The system as recited in claim 29, wherein:

the data cube includes a plurality of d-dimensional blocks each having b₁ ×

b₂ ×

. . .×

b_d cells, where b_i '"'"'s, for i=1 to d, are predetermined block factors; and

the system further comprises;

(a) for each block,

(i) means for summing up the aggregate values corresponding to all the cells in the block into a block sum; and

(ii) means for storing the block sum into one of the cells of the block, the array A of size n₁ ×

n₂ ×

. . .×

n_d now corresponding to a reduced array A'"'"' of size n₁ /b₁ ×

n₂ /b₂ ×

. . .×

n_d /b_d which includes the respective block sums for the blocks;

(b) means for executing the means for performing and means for storing one-dimensional prefix-sums on the array A'"'"'; and

(c) means for outputting the prefix-sum array P as P'"'"'.

31. The system as recited in claim 30, wherein a subset of the block factors b_i '"'"'s, for 1≦

i≦

d, are equal to 1.

32. The system as recited in claim 30, wherein a subset of the block factors b_i '"'"'s, for 1≦

i≦

d, are equal to n_i.

33. The system as recited in claim 30, wherein the means for generating a range-sum result includes:

(i) for each dimension of the data cube, means for partitioning the range of values of the corresponding data attribute into three adjoining sub-ranges where the middle range is properly aligned with the blocks, the region of the data cube corresponding to the range-sum query thereby having 3^d disjoint sub-regions including an internal sub-region and 3^d -1 boundary sub-regions B_i '"'"'s;

(ii) means for computing a range-sum for the internal sub-region based on the array P'"'"';

(iii) means for computing a range-sum for each boundary sub-region B_i, based on the arrays P'"'"' and A; and

(iv) means for summing up the range-sums for all the 3^d sub-regions to arrive at the range-sum result.

34. The system as recited in claim 33, wherein the means for computing a range-sum for each boundary sub-region B_i includes means for summing up all the cells of the array A corresponding to B_i.

35. The system as recited in claim 33, wherein the means for computing a range-sum for each boundary sub-region B_i includes:

means for computing a first sum from the cells of the array A which correspond to a superblock S_i of the boundary sub-region B_i, the superblock S_i being a minimum collection of the blocks that includes B_i ;

means for computing a second sum from the cells of the array A which correspond to a complementary region C_i of the boundary sub-region B_i, the complementary region C_i being the difference between the superblock S_i and sub-region B_i ; and

means for subtracting the second sum from the first sum to arrive at the range-sum for the boundary sub-region B_i.

36. The system as recited in claim 28, wherein the means for generating a range-sum result includes means for calculating:

##EQU14## and the range of query for dimension i, for 1≦

i≦

d, is from l_i +1 to h_i, inclusively.