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

Condensed Cube


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

. Тогда результирующий куб будет содержать

кортежей:

где
.

Так как в отношении содержится только один кортеж, все

. Следовательно, можно физически хранить только один кортеж

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

Этот алгоритм обладает рядом следующих отличительных черт.

  • ''Сжатый куб'' (Condensed Cube) не сжимается. Следовательно, несмотря на то, что он обладает меньшим размером по сравнению с полным кубом, это не влияет на выполнение запросов (он не требует разархивирования перед обработкой запросов).

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

  • ''Сжатый куб'' содержит абсолютно точные агрегирующие значения в отличие от различных аппроксимирующих методов.

  • ''Сжатый куб'' удовлетворяет базовым требованиям к OLAP-данным и поддерживает все OLAP приложения в отличие от методов, предлагающих уменьшение размера кубов за счет ограничения возможных запросов.

    Ключевым понятием этого алгоритма является ''базовый единичный кортеж'' (Base Single Tuple) — кортеж, который является единственным, формирующим агрегирующие отношения.

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

    Определение 5.1   Пусть



    — набор измерений.


    . Если


    — единственный кортеж в разбиении , образованом по


    , то


    - базовый единичный кортеж по


    , и


    — синглетное множество для


    . Далее, делается вывод, что если кортеж является базовым единичным кортежем по


    , то он является базовым единичным кортежем для любого ''надмножества''


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


    -


    . При этом на всех разбиениях из


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


    этой ячейки и, анализатор запросов учитывает данную информацию при обработке.

    Вперед: Quotient Cube

    Выше: Семантические алгоритмы

    Назад: Семантические алгоритмы

     


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






    Главная сайта