Method, apparatus and programmed medium for approximating the data cube and obtaining approximate answers to queries in relational databases

摘要

A novel and unique method of approximating the data cube and summarizing database data in order to provide quick and approximate answers to aggregate queries by precomputing a summary of the data cube using histograms and answering queries using the substantially smaller summary. A unique method according to the present invention provides for identifying accurate histogram classes and distributing the space among the histograms on various sub-cubes such that the errors are minimized, while at the same time computer resources are maximized.