Классика баз данных - статьи
Нетрадиционные гистограммы
Временами встречались интересные работы, авторы которых не следовали общей таксономии гистограмм или определениям проблем гистограмм. В одной из этих работ предлагалось использовать дискретное косинусное преобразование (Discrete Cosine Transform, DCT) для сжатия всей многомерной гистограмм и хранить ее в сжатой форме []. Используется очень простое правило многомерного разделения (равномерная решетка на всем пространстве); пространство делится на большое число небольших бакетов, и затем информация бакетов сжимается с использованием DCT. Это позволяет сократить не только объем требуемой памяти, но и время оценки, поскольку необходимую информацию можно восстановить, интегрируя обратную функцию DCT.
Также имеется перспективное направление исследований, в котором гистограммы комбинируются с другими методами для обеспечения более высококачественных оценок, чем может обеспечить какой-либо метод в отдельности. В дополнение к нескольким таким комбинациям с применением взятия образцов, особенно интересный метод направлен на преодоление "проклятия размерности" (curse of dimensionality) путем определения решающих областей зависимости и независимости между измерениями в многомерных данных, фиксации их в статистической модели взаимодействий (например, нелинейной модели), которая затем может образовать основу для MHIST-гистограмм меньшей размерности, служащей для аппроксимации всего соединенного распределения данных [].
Наконец, имеется очень интересное отступление от традиций, когда гистограммы строятся на базовых отношениях, и оценки распределений данных промежуточных результатов запросов получаются путем соответствующих манипуляций над этими гистограммами []. В этой работе обсуждается возможность поддержки гистограмм на результатах сложных запросов, что оказывается в некоторых случаях довольно эффективным. Для демонстрации предлагаемого подхода в работе используются основные гистограммы SQL Server (по существу, основанные на maxdiff - см. разд. ), но основные результаты не зависят от конкретного класса гистограмм. Поскольку число потенциальных гистограмм сложных запросов гораздо больше числа гистограмм базовых отношений, соответственно более сложной является и проблема проектирования баз данных, когда решается, какие гистограммы следует конструировать. К счастью, для этих целей удается применить алгоритм, основанный на рабочей нагрузке.
