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

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


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

  • Сортировка, хеширование, группировка

    Во время вычисления куба агрегируются кортежи (или ячейки), имеющие одинаковые значения по всем измерениям (так называемые дубликаты), поэтому важно использовать сортировки и группировать данные, чтобы упростить вычисление подобных агрегатов. К примеру, если необходимо посчитать общие продажи по регионам, продуктам, времени года, то более эффективно сортировать кортежи по регионам, затем по по дням и группировать по продуктам. Эффективной реализации подобных операций с большими объемами данных посвящено немало работ в области баз данных. Используемые в этой области алгоритмы могут быть адаптированы для вычислений кубов.

    Подобный подход может быть также расширен до разделяемых сортировок (т.е. использованию отсортированных результатов для создания многих подкубов, что позволяет распределить затраты на сортировку) или до разделяемого партиционирования (т.е. разделения затрат на партиционирование при использовании хэширования).

  • Одновременная агрегирование и кэширование промежуточных результатов

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

    К примеру, для расчета продаж по регионам мы используем промежуточные результаты, полученные при расчете подкуба более низкого уровня продаж по регионам, по дням. Расширение подобного подхода может привести к теории амортизированных чтений (т.е. вычислению максимального количества подкубов за одно обращение к диску).

  • Агрегирование от наименьшего подкуба-потомка при наличие многих подкубов-потомков

    При вычислении подкуба высокого порядка часто более эффективно использовать наименьший из уже рассчитанных подкубов-потокомков.

    К примеру, для расчета куба продаж по регионам при условии наличия 2-х рассчитанных подкубов (по регионам и годам, и по регионам и продуктам), очевидно, эффективнее использовать куб по регионам и годам, так как он содержит меньше ячеек.


  • Использование леммы Apriori при создании кубов типа айсберг

    Это правило, используемое при создании кубов типа айсберг, гласит: " Если указаная ячейка не удовлетворяет условию, накладываемому на минимальное значение меры, то ни один из ее потомков не удовлетворяет условию". Этот факт был доказан в [3] и широко применяется в алгоритмах data mining.

    При вычислении кубов типа айсберг существенную роль играет выбор условия на меру, которому должны удовлетворять ячейки, чтобы быть включенными в куб. Типичным айсберг-условием является минимальное значение, ячейки с мерой ниже которого исключаются при расчете (например, сумма продаж и количество купленных продуктов). В подобной ситуации условие Apriori может быть использовано для сокращения объема обрабатываемых данных. Например, если количество продаж в ячейке меньше минимально необходимого, то ни в одном из детей этой ячейки количество продаж указанный порог не превысит. Однако нужно отметить, что данное условие верно только для дистрибутивных агрегирующих функций (см. ).


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


    Содержание раздела