Method and system for performing range max/min queries on a data cube

• US 5,926,820 A
• Filed: 02/27/1997
• Issued: 07/20/1999
• Est. Priority Date: 02/27/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Megiddo, Nimrod, Ho, Ching-Tien
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/808,046
• Time in Patent Office: 873 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/200, 707/503, 707/504
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method for performing a range max/min query in a database, in which the data is represented as a multi-dimensional data cube, is disclosed. The method comprises the steps of: partitioning the data cube into multi-level multi-dimensional blocks which are represented by a tree structure; determining the index to the maximum or minimum value for each block; generating a range max/min result from the values of the cells selected from the cells in the query region Q, and the cells referenced by the indexes at the nodes corresponding to the cells in the query region Q, using the tree structure and determined cell indexes. A branch-and-bound method is used to repeatedly reduce the size of the query region from a cell within the region, based on sub-trees whose roots are cells in the region. To further improve the method performance, one or more reference arrays may also be used to quickly traverse the tree in determining the max/min cell indexes.

Claims

1. A method for performing a range max/min query in a database represented as a d-dimensional data cube having a plurality of cells, each cell having a value and identified by an index, the range max/min query corresponding to a region Q of the data cube, the method comprising the steps of:

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

representing the blocks as a multi-level tree structure having a plurality of nodes, the n-level nodes of the tree corresponding respectively to the n-level blocks;

for each block, determining the index of a cell with a max/min value among the cells in the block;

storing the determined cell indexes for the blocks into the corresponding nodes; and

generating a range max/min result from the values of the cells selected from the cells in the query region Q and the cells referenced by the indexes at the nodes corresponding to the cells in the query region Q.

2. The method as recited in claim 1, wherein the step of generating a range max/min result includes the steps of:

(a) identifying a node x of the tree where the node x corresponds to a smallest block that includes the query region Q; and

(b) repeatedly reducing the size of the region Q to determine a cell having the range max/min result, based on the cell indexes from selected nodes of a sub-tree of the tree, the sub-tree having a root node that is the same as the identified node x.

3. The method as recited in claim 2, wherein:

the tree includes a root node branching into multiple levels of internal nodes and terminates with a plurality of leaf nodes, the leaf nodes corresponding to the cells of the data cube, the root and internal nodes each having a plurality of child nodes; and

the step of reducing the size of Q includes the steps of;

(a) initializing a variable u with the index of any cell in the query region Q;

(b) determining whether the value of a cell indexed by x_i, where x_i is the index stored at node x, is larger than the value of a cell indexed by the variable u and whether the cell indexed by x_i is within the query region Q;

(c) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is within the query region Q, then updating the variable u with the index x_i ;

(d) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is outside the query region Q, then for each child node z of node x where the block corresponding to node z intersects with Q, executing steps (b)-(e) with node x being substituted by node z; and

(e) returning the value of u as the range-max/min result.

4. The method as recited in claim 3, wherein the step of executing steps (b)-(e) includes the steps of:

first, executing the steps (b)-(e) for each child node m of node x, with node x being substituted by node m, where the block corresponding to node m is included in the query region Q;

next, executing the steps (b)-(e) for each child node n of node x, with node x being substituted by node n, where the block corresponding to node n intersects Q, but not completely included in Q, and the cell referenced by the index at node n is within the query region Q; and

lastly, executing the steps (b)-(e) for each child node p of node x, with node x being substituted by node p, where the block corresponding to node p intersects Q, but not completely included in Q, and the cell referenced by the index at node p is outside the query region Q.

5. The method as recited in claim 1 further comprising the steps of:

selecting at least one level of the blocks;

for each selected block level, creating at least one reference array R based on at least one of the block dimensions; and

wherein the step of generating a range min/max result is based on the reference arrays Rs.

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

the tree includes a root node branching into multiple levels of internal nodes and terminates with a plurality of leaf nodes, the leaf nodes corresponding to the cells in the data cube, the root and internal nodes each having a plurality of child nodes;

the method further includes the step, for each subset of child nodes y of a node x where the blocks corresponding to the nodes y are within the query region Q, of identifying the index to a cell with a maximum value among the cells referenced by the subset of nodes, based on the reference arrays Rs; and

the step of generating a range max/min result includes the steps of;

(a) identifying a node x of the tree where the node x corresponds to a smallest block that includes the query region Q; and

(b) repeatedly reducing the size of the region Q to determine a cell having the range max/min result, based on the cell indexes referenced by the nodes of a sub-tree of the tree, the sub-tree having a root node that is the same as the identified node x.

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

the step of reducing the size of Q includes the steps of;

(a) initializing a variable u with the index of any cell in the query region Q;

(b) determining whether the value of a cell indexed by x_i, where x_i is the index stored at node x, is larger than the value of a cell indexed by the variable u and whether the cell indexed by x_i is within the query region Q;

(c) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is within the query region Q, then updating the variable U with the index x_i ;

(d) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is outside the query region Q, then for each child node z of node x where the block corresponding to node z intersects with Q, executing steps (b)-(e) with node x being substituted by node z; and

(e) returning the value of u as the range-max/min result.

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

the step of determining the index includes the step of identifying, for each block, the indexes of the cells whose values are equal to or greater than those of remaining cells in the block, the identified indexes being in an order; and

the generation of the range max/min result is based on the values of the cells referenced by the ordered indexes.

9. The method as recited in claim 8, wherein the step of generating a range max/min result includes the steps of:

(a) identifying a node x of the tree where the node x corresponds to a smallest block that includes the query region Q; and

(b) repeatedly reducing the size of the region Q to determine a cell having the range max/min result, based on the cell indexes referenced by the nodes of a sub-tree of the tree, the sub-tree having a root node that is the same as the identified node x.

10. A method for performing a range max/min query in a database represented by a d-dimensional array A having a plurality of cells, each cell having a value and identified by an index, the range max/min query corresponding to a region Q of the array A, the method comprising the steps of:

precomputing at least one d-dimensional reference array R of the same size as the array A, each member R i! of R referencing an index i of the array A such that j is closest to i with respect to a predetermined distance function and direction, and referencing an out-of-bound index of A if no such j exists;

generating a range max/min result from the values of the cells selected from those in the query region Q, based on the precomputed reference arrays Rs.

11. The method as recited in claim 10, wherein the step of generating a max/min result includes the steps of:

initializing a variable u with the index of any cell in the query region Q;

traversing a reference array R starting from a member of R corresponding to a cell in the query region Q until all cells in Q have been covered, the coverage being based on the predetermined distance function and direction;

updating the variable u with the index of each cell of R being considered during the step of traversing; and

returning the last value of u as the range max/min result.

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

the reference arrays R are one-dimensional; and

the step of traversing includes the step of traversing the reference array R from a lower bound of the query range until immediately before an upper bound of the query range or the out-of-bound index is found.

13. A computer program product for use with a computer system for performing a range max/min query in a database represented as a d-dimensional data cube having a plurality of cells, each cell having a value and identified by an index, the range max/min query corresponding to a region Q 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 multi-level d-dimensional blocks;

means, provided on the computer-readable medium, for directing the system to represent the blocks as a multi-level tree structure having a plurality of nodes, the n-level nodes of the tree corresponding respectively to the n-level blocks;

means, provided on the computer-readable medium, for directing the system to determine, for each block, the index of a cell with a max/min value among the cells in the block;

means, provided on the computer-readable medium, for directing the system to store the determined cell indexes for the blocks into the corresponding nodes; and

means, provided on the computer-readable medium, for directing the system to generate a range max/min result from the values of the cells selected from the cells in the query region Q and the cells referenced by the indexes at the nodes corresponding to the cells in the query region Q.

14. The computer program product as recited in claim 13, wherein the means for directing to generate a range max/min result includes:

(a) means, provided on the computer-readable medium, for directing the system to identify a node x of the tree where the node x corresponds to a smallest block that includes the query region Q; and

(b) means, provided on the computer-readable medium, for directing the system to repeatedly reduce the size of the region Q to determine a cell having the range max/min result, based on the cell indexes from selected nodes of a sub-tree of the tree, the sub-tree having a root node that is the same as the identified node x.

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

the tree includes a root node branching into multiple levels of internal nodes and terminates with a plurality of leaf nodes, the leaf nodes corresponding to the cells of the data cube, the root and internal nodes each having a plurality of child nodes; and

the means for directing to reduce the size of Q includes means, provided on the computer-readable medium, for directing the system to perform the steps of;

(a) initializing a variable u with the index of any cell in the query region Q;

(b) determining whether the value of a cell indexed by x_i, where x_i is the index stored at node x, is larger than the value of a cell indexed by the variable u and whether the cell indexed by x_i is within the query region Q;

(c) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is within the query region Q, then updating the variable u with the index x_i ;

(d) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is outside the query region Q, then for each child node z of node x where the block corresponding to node z intersects with Q, executing steps (b)-(e) with node x being substituted by node z; and

(e) returning the value of u as the range-max/min result.

16. The computer program product as recited in claim 15, wherein the step of executing steps (b)-(e) includes the steps of:

first, executing the steps (b)-(e) for each child node m of node x, with node x being substituted by node m, where the block corresponding to node m is included in the query region Q;

next, executing the steps (b)-(e) for each child node n of node x, with node x being substituted by node n, where the block corresponding to node n intersects Q, but not completely included in Q, and the cell referenced by the index at node n is within the query region Q; and

lastly, executing the steps (b)-(e) for each child node p of node x, with node x being substituted by node p, where the block corresponding to node p intersects Q, but not completely included in Q, and the cell referenced by the index at node p is outside the query region 0.

17. The computer program product as recited in claim 13 further comprising:

means, provided on the computer-readable medium, for directing the system to select at least one level of the blocks;

means, provided on the computer-readable medium, for directing the system to create, for each selected block level, at least one reference array R based on at least one of the block dimensions; and

wherein the range min/max result is generated based on the reference arrays Rs.

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

the tree includes a root node branching into multiple levels of internal nodes and terminates with a plurality of leaf nodes, the leaf nodes corresponding to the cells in the data cube, the root and internal nodes each having a plurality of child nodes;

the computer program product further comprises, for each subset of child nodes y of a node x where the blocks corresponding to the nodes y are within the query region Q, means provided on the computer-readable medium for directing the system to identify the index to a cell with a maximum value among the cells referenced by the subset of nodes, based on the reference arrays Rs; and

the means for directing to generate a range max/min result includes;

(a) means, provided on the computer-readable medium, for directing the system to identify a node x of the tree where the node x corresponds to a smallest block that includes the query region Q; and

(b) means, provided on the computer-readable medium, for directing the system to repeatedly reduce the size of the region Q to determine a cell having the range max/min result, based on the cell indexes referenced by the nodes of a sub-tree of the tree, the sub-tree having a root node that is the same as the identified node x.

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

the means for directing to determine the index includes means, provided on the computer-readable medium, for directing the system to identify, for each block, the indexes of the cells whose values are equal to or greater than those of remaining cells in the block, the identified indexes being in an order; and

the generation of the range max/min result is based on the values of the cells referenced by the ordered indexes.

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

the means for directing to generate a range max/min result includes;

(a) means, provided on the computer-readable medium, for directing the system to identify a node x of the tree where the node x corresponds to a smallest block that includes the query region Q; and

(b) means, provided on the computer-readable medium, for directing the system to repeatedly reduce the size of the region Q to determine a cell having the range max/min result, based on the cell indexes referenced by the nodes of a sub-tree of the tree, the sub-tree having a root node that is the same as the identified node x.

19. The computer program product as recited in 18, wherein the means for directing to reduce the size of Q includes means, provided on the computer-readable medium, for directing the system to perform the steps of:

(a) initializing a variable u with the index of any cell in the query region Q;

(b) determining whether the value of a cell indexed by x_i, where x_i is the index stored at node x, is larger than the value of a cell indexed by the variable u and whether the cell indexed by x_i is within the query region Q;

(c) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is within the query region Q, then updating the variable u with the index x_i ;

(d) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is outside the query region Q, then for each child node z of node x where the block corresponding to node z intersects with Q, executing steps (b)-(e) with node x being substituted by node z; and

(e) returning the value of u as the range-max/min result.

22. A computer program product for performing a range max/min query in a database represented by a d-dimensional array A having a plurality of cells, each cell having a value and identified by an index, the range max/min query corresponding to a region Q of the array A, the computer program product comprising:

means, provided on the computer-readable medium, for directing the system to precompute at least one d-dimensional reference array R of the same size as the array A, each member R i! of R referencing an index j of the array A such that j is closest to i with respect to a predetermined distance function and direction, and referencing an out-of-bound index of A if no such j exists;

means, provided on the computer-readable medium, for directing the system to generate a range max/min result from the values of the cells selected from those in the query region Q, based on the precomputed reference arrays Rs.

23. The computer program product as recited in claim 22, wherein the means for directing to generate a max/min result includes:

means, provided on the computer-readable medium, for directing the system to initialize a variable u with the index of any cell in the query region Q;

means, provided on the computer-readable medium, for directing the system to traverse a reference array R starting from a member of R corresponding to a cell in the query region Q until all cells in Q have been covered, the coverage being based on the predetermined distance function and direction;

means, provided on the computer-readable medium, for directing the system to update the variable u with the index of each cell of R being considered during the step of traversing; and

means, provided on the computer-readable medium, for directing the system to return the last value of u as the range max/min result.

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

the reference arrays R are one-dimensional; and

the means for directing to traverse includes means, provided on the computer-readable medium, for directing the system to traverse the reference array R from a lower bound of the query range until immediately before an upper bound of the query range or the out-of-bound index is found.

25. A database system for performing a range max/min query in a database represented as a d-dimensional data cube having a plurality of cells, each cell having a value and identified by an index, the range max/min query corresponding to a region Q of the data cube, the system comprising:

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

means for representing the blocks as a multi-level tree structure having a plurality of nodes, the n-level nodes of the tree corresponding respectively to the n-level blocks;

for each block, means for determining the index of a cell with a max/min value among the cells in the block;

means for storing the determined cell indexes for the blocks into the corresponding nodes; and

means for generating a range max/min result from the values of the cells selected from the cells in the query region Q and the cells referenced by the indexes at the nodes corresponding to the cells in the query region Q.

26. The system as recited in claim 25, wherein the means for generating a range max/min result includes:

(a) means for identifying a node x of the tree where the node x corresponds to a smallest block that includes the query region Q; and

(b) means for repeatedly reducing the size of the region Q to determine a cell having the range max/min result, based on the cell indexes referenced by the nodes of a sub-tree of the tree, the sub-tree having a root node that is the same as the identified node x.

27. The system as recited in claim 26, wherein:

the tree includes a root node branching into multiple levels of internal nodes and terminates with a plurality of leaf nodes, the leaf nodes corresponding to the cells of the data cube, the root and internal nodes each having a plurality of child nodes; and

the means for reducing the size of Q includes;

(a) means for initializing a variable u with the index of any cell in the query region Q;

(b) means for determining whether the value of a cell indexed by x_i, where x_i is the index stored at node x, is larger than the value of a cell indexed by the variable U and whether the cell indexed by x_i is within the query region Q;

(c) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is within the query region Q, then means for updating the variable u with the index x_i ;

(d) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is outside the query region Q, then for each child node z of node x where the block corresponding to node z intersects with Q, means for recursively operating the means in (b)-(e) with node x being substituted by node z; and

(e) means for returning the value of u as the range-max/min result.

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

the recursively operating means first operates for each child node m of node x, with node x being substituted by node m, where the block corresponding to node m is included in the query region Q;

the recursively operating means next operates for each child node n of node x, with node x being substituted by node n, where the block corresponding to node n intersects Q, but not completely included in Q, and the cell referenced by the index at node n is within the query region Q; and

the recursively operating means finally operates for each child node p of node x, with node x being substituted by node p, where the block corresponding to node p intersects Q, but not completely included in Q, and the cell referenced by the index at node p is outside the query region Q.

29. The system as recited in claim 25 further comprising:

means for selecting at least one level of the blocks;

for each selected block level, means for creating at least one reference array R based on at least one of the block dimensions; and

wherein the range min/max result is generated based on the reference arrays Rs.

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

the tree includes a root node branching into multiple levels of internal nodes and terminates with a plurality of leaf nodes, the leaf nodes corresponding to the cells in the data cube, the root and internal nodes each having a plurality of child nodes;

the method further includes, for each subset of child nodes y of a node x where the blocks corresponding to the nodes y are within the query region Q, means for identifying the index to a cell with a maximum value among the cells referenced by the subset of nodes, based on the reference arrays Rs; and

the means for generating a range max/min result includes;

(a) means for identifying a node x of the tree where the node x corresponds to a smallest block that includes the query region Q; and

(b) means for repeatedly reducing the size of the region Q to determine a cell having the range max/min result, based on the cell indexes referenced by the nodes of a sub-tree of the tree, the sub-tree having a root node that is the same as the identified node x.

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

the means for reducing the size of Q includes;

(a) means for initializing a variable u with the index of any cell in the query region Q;

(b) means for determining whether the value of a cell indexed by x_i, where x_i is the index stored at node x, is larger than the value of a cell indexed by the variable u and whether the cell indexed by x_i is within the query region Q;

(c) if the value of the cell indexed by x_i is larger than the value of the cell indexed by u and the cell indexed by x_i is within the query region Q, then means for updating the variable u with the index x_i ;

(d) if the value of the cell indexed by x_i is larger than the value of the cell indexed by U and the cell indexed by x_i is outside the query region 0, then for each child node z of node x where the block corresponding to node z intersects with Q, means for recursively operating the means (b)-(e) with node x being substituted by node z; and

(e) means for returning the value of u as the range-max/min result.

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

the means for determining the index includes means for identifying, for each block, the indexes of the cells whose values are equal to or greater than those of remaining cells in the block, the identified indexes being in an order; and

the generation of the range max/min result is based on the values of the cells referenced by the ordered indexes.

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

the means for generating a range max/min result includes;

(a) identifying a node x of the tree where the node x corresponds to a smallest block that includes the query region Q; and

(b) repeatedly reducing the size of the region Q to determine a cell having the range max/min result, based on the cell indexes referenced by the nodes of a sub-tree of the tree, the sub-tree having a root node that is the same as the identified node x.

34. A system for performing a range max/min query in a database represented by a d-dimensional array A having a plurality of cells, each cell having a value and identified by an index, the range max/min query corresponding to a region Q of the array A, the system comprising:

means for precomputing at least one d-dimensional reference array R of the same size as the array A, each member R i! of R referencing an index j of the array A such that j is closest to i with respect to a predetermined distance function and direction, and referencing an out-of-bound index of array A if no such j exists;

means for generating a range max/min result from the values of the cells selected from those in the query region Q, based on the precomputed reference arrays Rs.

35. The system as recited in claim 34, wherein the means for generating a max/min result includes:

means for initializing a variable u with the index of any cell in the query region Q;

means for traversing a reference array R starting from a member of R corresponding to a cell in the query region Q until all cells in Q have been covered, the coverage being based on the predetermined distance function and direction;

means for updating the variable u with the index of each cell of R being considered during the traverse of R; and

means for returning the last value of u as the range max/min result.

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

the reference arrays R are one-dimensional; and

the means for traversing includes means for traversing the reference array R from a lower bound of the query range until immediately before an upper bound of the query range or the out-of-bound index is found.