Классика баз данных - статьи
Первое появление
Насколько нам известно, первое предложение по использованию гистограмм для аппроксимирования распределений данных в системе баз данных появилось в PhD-диссертации Куи (Kooi) []. Его предложение состояло в непосредственном заимствовании из статистик простейшей формы гистограммы, в которой множество значений разбивалось на диапазоны одинаковой длины, т.е. диаграммы с одинаковой шириной (equi-width histogram). Следовательно, в терминах таксономии из разд. точкой входа гистограмм в мир баз данных явился сериальный класс равных сумм (equi-sum(V,S)), где ограничение разделения equi-sum требует, чтобы суммы значений параметра источника (в данном случае - протяженности) были для каждого бакета одними и теми же. Внутри каждого бакета значения и частоты аппроксимировались на основе предположений о непрерывности значений и равномерности распределения частот.
Гистограммы с одинаковой шириной представляли собой существенное усовершенствование предположения о равномерном распределении для всего множества значений (т.е., по существу, гистограммы с единственным бакетом), на котором в то время основывались практические системы. Поэтому они были быстро внедрены сначала в коммерческую версию СУБД Ingres, а потом и в другие СУБД.
