Классика баз данных - статьи
Алгоритмы динамического программирования были также
Алгоритмы динамического программирования были также предложены для конструирования оптимальных гистограмм для (иерархических) запросов с диапазонами над OLAP-данными []. Для многомерного случая проблема определения оптимальной гистограммы NP-полна, поэтому было предложено несколько приблизительных методов [].
В другой интересной работе были предложены алгоритмы для определения оптимальных наборов гистограмм (в противоположность к определению отдельных гистограмм), основанные на ожидаемой рабочей нагрузке []. Эта работа фокусируется на v-оптимальных гистограммах, но ее результаты равно применимы и к другим ограничениям разделения.
Однако даже при существовании эффективных алгоритмов вычисления статическим гистограммам свойственных возрастающие ошибки в промежутках между вычислениями. Более того, статические гистограммы вообще непригодны в среде потоков данных, поскольку отсутствует возможность сохранения поступающих данных и повторного их анализа. В связи с этим в нескольких работах предлагались различные подходы к поддержке динамических/адаптивных/самонастраивающихся гистограмм, которые изменяются при обновлении данных, оставаясь конкурентоспособными со статическими гистограммами. Среди этих работ мы отметим одну по поводу гистограмм, основанных на ограничениях разделения equi-depth и compressed [], одну для v-оптимальных гистограмм [] и одну для гистограмм, основанных на (линейных) сплайнах []. Имеется также исследовательская работа, фокусирующаяся на потоках данных, в которой поддерживается набросок (соединенного) распределения данных потока, на основе которого может быть сконструирована эффективная многомерная гистограмма []; в экспериментах использовались гистограммы STHoles, но в принципе метод можно применить и к другим классам диаграмм.
Другой подход к динамическому конструированию гистограмм, изучавшийся в прошлом, основывается на механизмах обратной связи запросов, в которых учитываются реальные размеры результатов запросов для динамического обновления гистограмм, так что обеспечиваемые ими оценки близки к действительности.
