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

• US 5,890,151 A
• Filed: 05/09/1997
• Issued: 03/30/1999
• Est. Priority Date: 05/09/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Bruck, Jehoshua, Ho, Ching-Tien
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/853,750
• Time in Patent Office: 690 Days
• Field of Search: 707/5, 707/1, 707/2, 707/3, 707/4, 707/100, 707/200, 707/503, 707/504, 345/342, 364/282.1, 364/282.3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Disclosed is a method and system for performing a partial-sum query in a database in which the data is represented as a multi-dimensional data cube. The data cube is partitioned into multi-dimensional blocks. One or more covering codes are then selected for each block, and a group of partial-sums is computed for each block based on its covering codes. At query time, the query result is generated by combining the partial-sums for those blocks that intersect with the query subset. To improve the query response time and reduce system storage requirements, the covering codes are preferably augmented as single-weight extended covering codes or composition-extended covering codes. Also, a second partial-sum may also be computed for each block to efficiently find its partial sum, based on the block'"'"'s first partial-sums and the bit-position differences between selected codewords for the block and bit strings representing the cell indexes of the blocks intersecting with the query subset.

Claims

1. A method for performing a partial-sum query in a database represented as a d-dimensional data cube, the data cube having a plurality of cells each having a value and identified by an index, the partial-sum query corresponding to a subset I of the data cube, the method comprising the steps of:

partitioning the data cube into a plurality of d-dimensional blocks;

selecting at least one covering code for each block i of the data cube, each covering code having a code length that is a function of the size of the block i;

computing a plurality of first sums for the block i, based on the respective covering codes selected for the block i; and

generating a partial-sum result from the first sums corresponding to those blocks of the data cube that intersect with the subset I.

2. The method as recited in claim 1, wherein each dimension of the block i has a block length and corresponds to one of the covering codes selected for the block i.

3. The method as recited in claim 2, wherein the blocks of the data cube have the same block length in each dimension of the data cube.

4. The method as recited in claim 2, wherein the code length of each covering code for the block i is equal to a multiplication product of the respective block lengths of the block i in selected dimensions of the block i.

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

each of the covering codes for the block i includes a plurality of codewords; and

each first sum of the block i is based on a Cartesian product of selected codewords, each selected codeword being from the covering code for a respective dimension of the block i.

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

each codeword of each covering code for the block i includes a sequence of bits;

the cells in the block i are indexed by the bits of the codewords of the covering codes for the block i; and

each first sum of the block i includes a sum of the values of selected cells in the block i, where the bits indexing the selected cells, in the selected codewords, are all 1'"'"'s.

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

each codeword in the covering codes has a codeword length;

the covering codes for the block i are binary covering codes; and

the codewords of each binary covering code for the block i have the same codeword length.

8. The method as recited in claim 7, wherein:

the data cube is a one-dimensional array A; and

the method further comprises the steps of;

representing the indexes to the cells in each block i that intersects with the subset I as a binary bit string V_i ;

augmenting each binary covering code of the block i with all single-weight codewords, each single-weight codeword having a single "1" bit;

selecting a codeword W_j from the augmented code such that W_j has a smallest Hamming distance to the bit string V_i ;

computing a second sum for the block i based on a first sum F_j for the block i and a bit-position difference between W_j and V_i, the first sum F_j corresponding to the codeword W_j ; and

combining the second sums for all the blocks of the data cube that intersect with the subset I to generate the partial-sum result.

9. The method as recited in claim 8, wherein the step of computing a second sum includes the steps of:

initializing the second sum with the first sum F_j ;

adding the value in cell A x! to the second sum for all indexes x'"'"'s such that the x-th bit of the bit string V_i is "1" and the x-th bit of the codeword W_j is "0"; and

subtracting the value in cell A y! from the second sum for all indexes y'"'"'s such that the y-th bit of the bit string V_i is "0" and the y-th bit of the codeword W_j is "1".

10. The method as recited in claim 7, wherein:

the data cube is a one-dimensional array;

the indexes to the cells in each block i that intersects with the subset I are represented as a binary bit string V_i ; and

the method further comprises the steps of;

selecting a smallest subset S of codewords for the block i such that the bit string V_i can be derived from a combination of bit-wise additions and bit-wise subtractions of the codewords in the subset S;

computing a second sum for the block i based on a plurality of first sums F_j '"'"'s, where each first sum F_j corresponds to a codeword in the subset S; and

combining the second sums for all blocks of the data cube that intersect with the subset I to generate the partial-sum result.

11. The method as recited in claim 10, wherein the step of computing a second sum for the block i includes the steps of:

initializing the second sum to zero;

adding to the second sum those first sums corresponding to the codewords of the subset S that were used in the bit-wise additions for deriving the bit string V_i ; and

subtracting from the second sum those first sums corresponding to the codewords of the subset S that were used in the bit-wise subtractions for deriving the bit string V_i.

12. The method as recited in claim 7, wherein:

the data cube and the cell indexes are d-dimensional, where d>

1;

the d-dimensional indexes to the cells in each block i that intersects with the subset I are represented as a product of d binary bit strings V_z '"'"'s, where each bit string V_z corresponds to a data cube dimension z, for 1≦

z≦

d; and

the method further comprises the steps of;

augmenting each binary covering code of the block i with all single-weight codewords, each single-weight codeword having a single "1" bit;

for each block i and for each dimension z of the data cube, where 1≦

z≦

d, selecting a codeword W_z from the augmented code such that W_z has a smallest Hamming distance to the bit string V_z ;

computing a second sum for the block i based on a combination of the codeword W_z and a bit-position difference between W_z and V_z over all dimensions z,for 1≦

z≦

d; and

combining the second sums for all blocks of the data cube that intersect with the subset I to generate the partial-sum result.

13. The method as recited in claim 12, wherein the step of computing a second sum includes the steps of:

for each block i and for each dimension z of the data cube, where 1≦

z≦

d, selecting a smallest subset S_z of the codewords for the block i such that each bit string V_z can be derived from a combination of bit-wise additions and bit-wise subtractions of the codewords in S_z ; and

calculating the second sum for the block i based on a plurality of first sums F_z '"'"'s, each first sum F_z corresponding to a cross-product of d codewords each being from the subset S_z for the respective dimension z, where 1≦

z≦

d.

14. The method as recited in claim 13, wherein the step of calculating the second sum includes the steps of:

initializing the second sum to zero;

adding to the second sum those first sums F_z '"'"'s for the block i where the number of bit-wise codeword subtractions used to derive the respective bit string V_z is an even number; and

subtracting from the second sum those first sums F_z '"'"'s for the block i where the number of bit-wise codeword subtractions used to derive the respective bit string V_z is an odd number.

15. A computer program product for use with a computer system for performing a partial-sum query in a database, the database being represented as a d-dimensional data cube having a plurality of cells, each cell having a value and identified by an index, the partial-sum query corresponding to a subset I of the data cube, the computer program product comprising:

a computer-readable medium;

means, provided on the computer-readable medium, for directing the system to partition the data cube into a plurality of d-dimensional blocks;

means, provided on the computer-readable medium, for directing the system to select at least one covering code for each block i of the data cube, each covering code having a code length that is a function of the size of the block i;

means, provided on the computer-readable medium, for directing the system to compute a plurality of first sums for the block i, based on the respective covering codes selected for the block i; and

means, provided on the computer-readable medium, for directing the system to generate a partial-sum result from the first sums corresponding to those blocks of the data cube that intersect with the subset I.

16. The computer program product as recited in claim 15, wherein each dimension of the block i has a block length and corresponds to one of the covering codes selected for the block i.

17. The computer program product as recited in claim 16, wherein the blocks of the data cube have the same block length in each dimension of the data cube.

18. The computer program product as recited in claim 16, wherein the code length of each covering code for the block i is equal to a multiplication product of the respective block lengths of the block i in selected dimensions of the block i.

19. The computer program product as recited in claim 15, wherein:

each of the covering codes for the block i includes a plurality of codewords; and

each first sum of the block i is based on a Cartesian product of selected codewords, each selected codeword being from the covering code for a respective dimension of the block i.

20. The computer program product as recited in claim 19, wherein:

each codeword of each covering code for the block i includes a sequence of bits;

the cells in the block i are indexed by the bits of the codewords of the covering codes for the block i; and

each first sum of the block i includes a sum of the values of selected cells in the block i, where the bits indexing the selected cells, in the selected codewords, are all 1'"'"'s.

21. The computer program product as recited in 19, wherein:

each codeword in the covering codes has a codeword length;

the covering codes for the block i are binary covering codes; and

the codewords of each binary covering code for the block i have the same codeword length.

22. The computer program product as recited in claim 21, wherein:

the data cube is a one-dimensional array A;

the indexes to the cells in each block i that intersects with the subset I are represented as a binary bit string V_i ; and

the computer program product further comprises;

means, provided on the computer-readable medium, for directing the system to augment each binary covering code of the block i with all single-weight codewords, each single-weight codeword having a single "1" bit;

means, provided on the computer-readable medium, for directing the system to select a codeword W_j from the augmented code such that W_j has a smallest Hamming distance to the bit string V_i ;

means, provided on the computer-readable medium, for directing the system to compute a second sum for the block i based on a first sum F_j for the block i and a bit-position difference between W_j and V_i, the first sum F_j corresponding to the codeword W_j ; and

means, provided on the computer-readable medium, for directing the system to combine the second sums for all the blocks of the data cube that intersect with the subset I to generate the partial-sum result.

23. The computer program product as recited in claim 22, wherein the means for directing to compute a second sum includes:

means, provided on the computer-readable medium, for directing the system to initialize the second sum with the first sum F_j ;

means, provided on the computer-readable medium, for directing the system to add the value in cell A x! to the second sum for all indexes x'"'"'s such that the x-th bit of the bit string V_i is "1" and the x-th bit of the codeword W_j is "0"; and

means, provided on the computer-readable medium, for directing the system to subtract the value in cell A y! from the second sum for all indexes y'"'"'s such that the y-th bit of the bit string V_i is "0" and the y-th bit of the codeword W_j is "1".

24. The computer program product as recited in claim 21, wherein:

the data cube is a one-dimensional array;

the indexes to the cells in each block i that intersects with the subset I are represented as a binary bit string V_i ; and

the computer program product further comprises;

means, provided on the computer-readable medium, for directing the system to select a smallest subset S of the codewords for the block i such that the bit string V_i can be derived from a combination of bit-wise additions and bit-wise subtractions of the codewords in the subset S;

means, provided on the computer-readable medium, for directing the system to compute a second sum for the block i based on a plurality of first sums F_j '"'"'s where each first sum F_j corresponds to a codeword in the subset S; and

means, provided on the computer-readable medium, for directing the system to combine the second sums for all blocks of the data cube that intersect with the subset I to generate the partial-sum result.

25. The computer program product as recited in claim 24, wherein the means for directing to compute a second sum for the block i includes:

means, provided on the computer-readable medium, for directing the system to initialize the second sum to zero;

means, provided on the computer-readable medium, for directing the system to add to the second sum those first sums corresponding to the codewords of the subset S that were used in the bit-wise additions for deriving the bit string V_i ; and

means, provided on the computer-readable medium, for directing the system to subtract from the second sum those first sums corresponding to the codewords of the subset S that were used in the bit-wise subtractions for deriving the bit string V_i.

26. The computer program product as recited in claim 21, wherein:

the data cube and the cell indexes are d-dimensional, where d>

1;

the d-dimensional indexes to the cells in each block i that intersects with the subset I are represented as a product of d binary bit strings V_z '"'"'s, where each bit string V_z corresponds to a data cube dimension z, for 1≦

z≦

d ; and

the computer program product further comprises;

means, provided on the computer-readable medium, for directing the system to augment each binary covering code of the block i with all single-weight codewords, each single-weight codeword having a single "1" bit;

means, provided on the computer-readable medium, for directing the system to select, for each block i and for each dimension z of the data cube where 1≦

z≦

d , a codeword W_z from the augmented code such that W_z has a smallest Hamming distance to the bit string V_z ;

means, provided on the computer-readable medium, for directing the system to compute a second sum for the block i based on a combination of the codeword W_z and a bit-position difference between W_z and V_z over all dimensions z, for 1≦

z≦

d; and

means, provided on the computer-readable medium, for directing the system to combine the second sums for all blocks of the data cube that intersect with the subset I to generate the partial-sum result.

27. The computer program product as recited in claim 26, wherein the means for directing to compute a second sum includes:

means, provided on the computer-readable medium, for directing the system to select, for each block i and for each dimension z of the data cube where 1≦

z≦

d, a smallest subset S_z of the codewords for the block i such that each bit string V_z can be derived from a combination of bit-wise additions and bit-wise subtractions of the codewords in S_z ; and

means, provided on the computer-readable medium, for directing the system to calculate the second sum for the block i based on a plurality of first sums F_z '"'"'s, each first sum F_z corresponding to a cross-product of d codewords each being from the subset S_z for the respective dimension z, where 1≦

z≦

d.

28. The computer program product as recited in claim 27, wherein the means for directing to calculate the second sum includes:

means, provided on the computer-readable medium, for directing the system to initialize the second sum to zero;

means, provided on the computer-readable medium, for directing the system to add to the second sum those first sums F_z '"'"'s for the block i where the number of bit-wise codeword subtractions used to derive the respective bit string V_z is an even number; and

means, provided on the computer-readable medium, for directing the system to subtract from the second sum those first sums F_z '"'"'s for the block i where the number of bit-wise codeword subtractions used to derive the respective bit string V_z is an odd number.

29. A system for performing a partial-sum query in a database represented as a d-dimensional data cube, the data cube having a plurality of cells each having a value and identified by an index, the partial-sum query corresponding to a subset I of the data cube, the system comprising:

means for partitioning the data cube into a plurality of d-dimensional blocks;

means for selecting at least one covering code for each block i of the data cube, each covering code having a code length that is a function of the size of the block i;

means for computing a plurality of first sums for the block i, based on the respective covering codes selected for the block i; and

means for generating a partial-sum result from the first sums corresponding to those blocks of the data cube that intersect with the subset I.

30. The system as recited in claim 29, wherein each dimension of the block i has a block length and corresponds to one of the covering codes selected for the block i.

31. The system as recited in claim 30, wherein the blocks of the data cube have the same block length in each dimension of the data cube.

32. The system as recited in claim 30, wherein the code length of each covering code for the block i is equal to a multiplication product of the respective block lengths of the block i in selected dimensions of the block i.

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

each of the covering codes for the block i includes a plurality of codewords; and

each first sum of the block i is based on a Cartesian product of selected codewords, each selected codeword being from the covering code for a respective dimension of the block i.

34. The system as recited in claim 33, wherein:

each codeword of each covering code for the block i includes a sequence of bits;

the cells in the block i are indexed by the bits of the codewords of the covering codes for the block i; and

each first sum of the block i includes a sum of the values of selected cells in the block i, where the bits indexing the selected cells, in the selected codewords, are all 1'"'"'s.

35. The system as recited in claim 33, wherein:

each codeword in the covering codes has a codeword length;

the covering codes for the block i are binary covering codes; and

the codewords of each binary covering code for the block i have the same codeword length.

36. The system as recited in claim 35, wherein:

the data cube is a one-dimensional array A; and

the system further comprises;

means for representing the indexes to the cells in each block i that intersects with the subset I as a binary bit string V_i ;

means for augmenting each binary covering code of the block i with all single-weight codewords, each single-weight codeword having a single "1" bit;

means for selecting a codeword W_j from the augmented code such that W_j has a smallest Hamming distance to the bit string V_i ;

means for computing a second sum for the block i based on a first sum F_j for the block i and a bit-position difference between W_j and V_i, the first sum F_j corresponding to the codeword W_j ; and

means for combining the second sums for all the blocks of the data cube that intersect with the subset I to generate the partial-sum result.

37. The system as recited in claim 36, wherein the means for computing a second sum includes:

means for initializing the second sum with the first sum F_j ;

means for adding the value in cell A x! to the second sum for all indexes x'"'"'s such that the x-th bit of the bit string V_i is "1" and the x-th bit of the codeword W_j is "0"; and

means for subtracting the value in cell A y! from the second sum for all indexes y'"'"'s such that the y-th bit of the bit string V_i is "0" and the y-th bit of the codeword W_j is "1".

38. The system as recited in claim 35, wherein:

the data cube is a one-dimensional array;

the indexes to the cells in each block i that intersects with the subset I are represented as a binary bit string V_i ; and

the system further comprises;

means for selecting a smallest subset S of codewords for the block i such that the bit string V_i can be derived from a combination of bit-wise additions and bit-wise subtractions of the codewords in the subset S;

means for computing a second sum for the block i based on a plurality of first sums F_j '"'"'s, where each first sum F_j corresponds to a codeword in the subset S; and

means for combining the second sums for all blocks of the data cube that intersect with the subset I to generate the partial-sum result.

39. The system as recited in claim 38, wherein the means for computing a second sum for the block i includes:

means for initializing the second sum to zero;

means for adding to the second sum those first sums corresponding to the codewords of the subset S that were used in the bit-wise additions for deriving the bit string V_i ; and

means for subtracting from the second sum those first sums corresponding to the codewords of the subset S that were used in the bit-wise subtractions for deriving the bit string V_i.

40. The system as recited in claim 35, wherein:

the data cube and the cell indexes are d-dimensional, where d>

1;

the d-dimensional indexes to the cells in each block i that intersects with the subset I are represented as a product of d binary bit strings V_z '"'"'s, where each bit string V_z corresponds to a data cube dimension z, for 1≦

z≦

d ; and

the system further comprises;

means for augmenting each binary covering code of the block i with all single-weight codewords, each single-weight codewords having a single "1" bit;

means for selecting, for each block i and for each dimension z of the data cube, where 1≦

z≦

d , a codeword W_z from the augmented code such that W_z has a smallest Hamming distance to the bit string V_z ;

means for computing a second sum for the block i based on a combination of the codeword W_z and a bit-position difference between W_z and V_z over all dimensions z, for 1≦

z≦

d ; and

is means for combining the second sums for all blocks of the data cube that intersect with the subset I to generate the partial-sum result.

41. The system as recited in claim 40, wherein the means for computing a second sum includes:

means for selecting, for each block i and for each dimension z of the data cube, where 1≦

z≦

d , a smallest subset S_z of the codewords for the block i such that each bit string V_z can be derived from a combination of bit-wise additions and bit-wise subtractions of the codewords in S_z ; and

means for calculating the second sum for the block i based on a plurality of first sums F_z '"'"'s, each first sum F_z corresponding to a cross-product of d codewords each being from the subset S_z for the respective dimension z, where 1≦

z≦

d.

42. The system as recited in claim 41, wherein the means for calculating the second sum includes:

means for initializing the second sum to zero;

means for adding to the second sum those first sums F_z '"'"'s for the block i where the number of bit-wise codeword subtractions used to derive the respective bit string V_z is an even number; and

means for subtracting from the second sum those first sums F_z '"'"'s for the block i where the number of bit-wise codeword subtractions used to derive the respective bit string V_z is an odd number.