Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Конференция «Технологии управления данными 2018»
СУБД, платформы, инструменты, реальные проекты.
29 ноября 2018 г.
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:

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

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

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
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...