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

摘要

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.