Carleton University
Technical Report TR-99-01
January 1999
TR-99-01: Rectangular Attribute Cardinality Map: A New Histogram-like Technique for Query Optimization
B. John Oommen & Murali Thiyagarajah
Abstract
Current database systems utilize histograms to approximate frequency distributions of attribute values of relations. These are used to efficiently estimate query result sizes and access plan costs. Even though they have been is use for nearly two decades, there has been no significant mathematical techniques (othert than those used in statistics for traditional histogram approximations) to study them. In this paper, we introduce a new histogram-like approximation strategy, called the Rectangular Attribute Cardinality Map (R-ACM), that aims to approximate the density of the underlying attribute values using the philosophies of numerical integration.