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

Металлоконструкции в сопутствующей сантехнической услуге Новосибирск и пригороде.

Condensed Cube


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

$ r(a_1,a_2,…,a_n,aggr)$

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

$ 2^n$

кортежей:

$ (a_1,a_2,\ldots,a_n,V_1),(a_1,ALL,\ldots,ALL,V_2), (ALL,a_2,ALL,\ldots,ALL,V_3)\\ , \ldots,(ALL,\ldots,ALL,V_k), ~$
где
$ ~k =2^n$
.

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

$ V_i = aggr$

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

$ (a_1,a_2,a_3,\ldots,a_n,aggr)$

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

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

  1. ''Сжатый куб'' (Condensed Cube) не сжимается. Следовательно, несмотря на то, что он обладает меньшим размером по сравнению с полным кубом, это не влияет на выполнение запросов (он не требует разархивирования перед обработкой запросов).
  2. ''Сжатый куб'' полностью вычислен. В отличие от многих подходов, предлагающих лишь частичные вычисления подкубов, в данном подходе результатом является полностью вычисленный куб.
  3. ''Сжатый куб'' содержит абсолютно точные агрегирующие значения в отличие от различных аппроксимирующих методов.
  4. ''Сжатый куб'' удовлетворяет базовым требованиям к OLAP-данным и поддерживает все OLAP приложения в отличие от методов, предлагающих уменьшение размера кубов за счет ограничения возможных запросов.

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

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


Начало  Назад  Вперед



Книжный магазин