Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Обучение от Mail.Ru Group.
Онлайн-университет
для программистов с
гарантией трудоустройства.
Набор открыт!
2008 г.

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

Юрий Кудрявцев, факультет ВМиК МГУ

Вперед: Quotient Cube Выше: Семантические алгоритмы Назад: Семантические алгоритмы   Содержание

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) — кортеж, который является единственным, формирующим агрегирующие отношения.

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

Определение 5.1   Пусть $ SD$ — набор измерений. $ SD \in \{D1, D2, D3,\ldots, Dn\}$ . Если $ r$ — единственный кортеж в разбиении , образованом по $ SD$ , то $ r$ - базовый единичный кортеж по $ SD$ , и $ SD$ — синглетное множество для $ r$ .

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

Вперед: Quotient Cube Выше: Семантические алгоритмы Назад: Семантические алгоритмы   Содержание

Новости мира IT:

Архив новостей

Последние комментарии:

Релиз ядра Linux 4.14  (6)
Пятница 17.11, 16:12
Apple запустила Pay Cash (2)
Четверг 09.11, 21:15
Loading

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...