Обзор алгоритмов MOLAP. Общие стратегии вычисления кубов

2008 г.

Обзор алгоритмов MOLAP

Вперед: OLAP и статистические базы данных Выше: Введение. Анализ задачи Назад: Хранение и эффективный расчет OLAP-кубов Содержание

Подразделы

Общие стратегии вычисления кубов

Вне зависимости от метода хранения (ROLAP, MOLAP), существует набор приемов, позволяющих уменьшить время создания и обработки запросов к OLAP-кубам.

Сортировка, хеширование, группировка
Во время вычисления куба агрегируются кортежи (или ячейки), имеющие одинаковые значения по всем измерениям (так называемые дубликаты), поэтому важно использовать сортировки и группировать данные, чтобы упростить вычисление подобных агрегатов. К примеру, если необходимо посчитать общие продажи по регионам, продуктам, времени года, то более эффективно сортировать кортежи по регионам, затем по по дням и группировать по продуктам. Эффективной реализации подобных операций с большими объемами данных посвящено немало работ в области баз данных. Используемые в этой области алгоритмы могут быть адаптированы для вычислений кубов.
Подобный подход может быть также расширен до разделяемых сортировок (т.е. использованию отсортированных результатов для создания многих подкубов, что позволяет распределить затраты на сортировку) или до разделяемого партиционирования (т.е. разделения затрат на партиционирование при использовании хэширования).
Одновременная агрегирование и кэширование промежуточных результатов
Эффективнее создавать подкубы высоких уровней из подкубов низких уровней, нежели из базовой таблицы. Более того,одновременное вычисление агрегатов может позволить сократить дорогостоящие операции обращения к жестким дискам.
К примеру, для расчета продаж по регионам мы используем промежуточные результаты, полученные при расчете подкуба более низкого уровня продаж по регионам, по дням. Расширение подобного подхода может привести к теории амортизированных чтений (т.е. вычислению максимального количества подкубов за одно обращение к диску).
Агрегирование от наименьшего подкуба-потомка при наличие многих подкубов-потомков
При вычислении подкуба высокого порядка часто более эффективно использовать наименьший из уже рассчитанных подкубов-потокомков.
К примеру, для расчета куба продаж по регионам при условии наличия 2-х рассчитанных подкубов (по регионам и годам, и по регионам и продуктам), очевидно, эффективнее использовать куб по регионам и годам, так как он содержит меньше ячеек.
Использование леммы Apriori при создании кубов типа айсберг
Это правило, используемое при создании кубов типа айсберг, гласит: " Если указаная ячейка не удовлетворяет условию, накладываемому на минимальное значение меры, то ни один из ее потомков не удовлетворяет условию". Этот факт был доказан в [3] и широко применяется в алгоритмах data mining.
При вычислении кубов типа айсберг существенную роль играет выбор условия на меру, которому должны удовлетворять ячейки, чтобы быть включенными в куб. Типичным айсберг-условием является минимальное значение, ячейки с мерой ниже которого исключаются при расчете (например, сумма продаж и количество купленных продуктов). В подобной ситуации условие Apriori может быть использовано для сокращения объема обрабатываемых данных. Например, если количество продаж в ячейке меньше минимально необходимого, то ни в одном из детей этой ячейки количество продаж указанный порог не превысит. Однако нужно отметить, что данное условие верно только для дистрибутивных агрегирующих функций (см. Агрегирующие функции, меры и формулы).

Таким образом, сокращение размера куба — насущная задача создателей OLAP-приложений. Еще одним важным ограничением является требование сохранения семантики отношений обобщения/специализации (roll-up/drill-down). Отбрасывая это требование, многие алгоритмы достигают хороших результатов, но восстановление этих отношений в дальнейшем либо невозможно, либо трудно вычислимо, что существенно ограничивает возможность их применения.

Способы хранения

ROLAP (Relational OLAP)

— данные, включающие в себя все возможные агрегации, хранятся в реляционных таблицах. Все запросы пользователя транслируются в SQL-операторы выборки из данной таблицы.

Плюсы данного подхода: все данные хранятся внутри одной СУБД в одном формате.

Минусы данного подхода: чрезмерное увеличение объема таблицы данных для куба и сложности пересчета агрегированных значений при изменениях начальных данных.

MOLAP (Multidimensional OLAP)

— все данные хранятся в многомерной базе данных или в специальном формате, определенном создающим и обрабатывающим OLAP-приложением. Все запросы пользователя транслируются в запросы многомерной выборки (MDX, Express 4Gl и др).

Плюсы данного подхода: все данные хранятся в многомерных структурах, что существенно повышает скорость обработки запросов.

Минусы данного подхода: данные куба ''оторваны'' от базовой таблицы, необходимы специальные инструменты для формирования кубов и их пересчета в случае изменения базовых значений.

HOLAP (Hybrid OLAP)

— базовые данные хранятся в реляционной таблице, агрегированные — в многомерной структуре.

Данный метод пытается совмещать достоинства предыдущих, будучи избавленным от их недостатков, но по скорости он проигрывает MOLAP, а также не достигается целостное хранение данных. Возрастают затраты на поддержку и определение типа хранения для подкубов.

Классификация алгоритмов хранения MOLAP-данных

В дальнейшем, мы будем называть

синтаксическими: — алгоритмы, осуществляющие только синтаксические преобразования данных;
семантическими: — алгоритмы, преобразующие внутреннюю структуру куба;
аппроксимирующими: — алгоритмы, основанные на некоторых средних приближениях значений данных, для которых значение ячейки не всегда совпадает с фактической таблицей.
aлгоритмы вычисления Iceberg-кубов: — выделим данный класс аппроксимирующих алгоритмов