Queries that constrain multiple dimensions simultaneously are difficult to express, in both Structured Query Language (SQL) and multidimensional languages. Moreover, they can be inefficient. We introduce the diamond cube operator to facilitate the expression and computation of one such important class of multidimensional query, and we define the resulting cube to be a diamond.;The diamond cube operator identifies an important cube such that all remaining attributes are strongly related. For example, suppose a company wants to close shops and terminate product lines, whilst meeting some profitability constraints simultaneously over both products and shops. The diamond operator would identify the maximal set of products and shops that satisfy those constraints.;We determine the complexity of computing diamonds and investigate how pre-computed materialised views can speed execution. Views are defined by the parameter k associated with each dimension in every data cube. We prove that there is only one k1, k2,...,kd-diamond for a given cube. By varying the ki's we get a collection of diamonds for a cube and these diamonds form a lattice.;We also determine the complexity of discovering the most-constrained diamond that has a non-empty solution. By executing binary search over theoretically-derived bounds, we compute such a diamond efficiently.;Diamonds are defined over data cubes where the measures all have the same sign. We prove that the more general case---computing a diamond where measures include both positive and negative values---is NP-hard.;Finding dense subcubes in large data is a difficult problem. We investigate the role that diamonds play in the solution of three NP-hard problems that seek dense subcubes: Largest Perfect Cube, Densest Cube with Limited Dimensions and Heaviest Cube with Limited Dimensions.;We are interested in processing large data sets. We validated our algorithms on a variety of freely-available and synthetically-generated data cubes, whose dimensionality range from three to twenty-seven. Most of the cubes contain more than a million facts, and the largest has more than 986 million facts. We show that our custom implementation is more than twenty-five times faster, on a large data set, than popular database engines.
展开▼
