Logo Host-telecom.com — профессиональный хостинг в Европе! Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

💰 Самые низкие цены на домены

🔒 Отличный хостинг на SSD c бесплатными SSL

💻 Огромнейший выбор dedicated выделенных серверов

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

VDS хостинг Облачный сервер в Нидерландах и Украине

Аренда виртуального сервера от $7.91

Партнёрская программа
$20 за клиента

Wildcard сертификаты от $74,97 в год.

Дешевые ssl сертификаты для домена

Sectigo сертификаты от $7,67 в год.

2008 г.

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

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

Вперед: Виды запросов к кубам Выше: Введение. Анализ задачи Назад: История Задачи   Содержание

Подразделы


Многомерные кубы, определение и свойства

Рассмотрим базовую (фактическую) таблицу $ r$ , на основе которой мы будем строить OLAP-куб. Множество атрибутов r условно делятся на 2 группы:

  1. Набор измерений (категорий, локаторов), которые служат критериями для анализа и определяют многомерное пространство OLAP-куба. За счет фиксации значений измерений получаются срезы (гиперплоскости) куба. Каждый срез представляет собой запрос к данным, включающий агрегации.

  2. Набор мер — функции, которые каждой точке пространства ставят в соответствие данные.

Из атрибутов $ r$ создаются измерения, содержащие проекцию r по атрибуту, с введенной иерархией (например, для таблицы, содержащей фактические данные по продажам магазина, возможно измерение ''Время'', содержащее иерархию вида ''Год-Месяц-Неделя-День''). Куб представляет собой декартово произведение измерений, где для каждого элемента произведения проставлен набор мер (существует проблема хранения неопределенных значений, подробнее см. Представление неопределенных данных). В кубе существуют отношения обобщения и специализации (roll-up/drill-down) по иерархиям измерений (подробнее об иерархиях см.  Иерархии и агрегирование). Ячейка высокого уровня иерархии может ''спускаться'' (drill-down) к ячейке низкого уровня (для  примера (R1, ALL, весна) может ''спуститься'' к ячейке (R1, книги, весна)) и наоборот, ''подняться'' (roll-up) (от (R1, книги, весна) к (R1, ALL, весна) по измерению ''продукты'').

Пример

Рассмотрим пример, который будет и в дальнейшем использоваться в рамках данной работы.

Таблица 1.1: Фактические данные для примера

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert c\vert}
\hline
Регион ...
...e
R1 & Еда & Осень & 3\\
\hline
R2 & книги & Осень & 6\\
\hline
\end{tabular}$



Таблица 1.2: Куб для 1.1. Агрегирующая функция — AVG.

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert c\vert}
\hline
Регион ...
...\
\hline
ALL& ALL& Весна& 9\\
\hline
ALL& ALL& ALL& 6\\
\hline
\end{tabular}$


Размер куба данных определяется по формуле $ \prod\limits_d (c_i + 1)$ , где $ d$ -измерения (''столбцы''), размерность измерения $ c_i$ — количество различных значений кортежей по этому измерению (Select Count(distinct dimension) from table), $ +1$ отвечает за значение $ ALL$, агрегирующее все возможные значения измерения.

Таким образом, при базовой таблице в 3 кортежа результирующий куб в простой реляционной таблице (называемой Binary Storage Footprint), в которой напрямую хранятся все агрегаты, занимает 27 кортежей.

Измерения

Измерения куба — набор доменов, по которым создается многомерное пространство. Важной особенностью OLAP-моделей является разделение измерений на локаторы (задающие точки) и меры (задающие значение). Как отмечается в [23], данное разделение может носить как условный, так и жесткий характер. В случае условного разделения измерения можно ''разворачивать'' как данные и как аналитику, создавая новую аналитику куба по продажам — ''количество продаж''. Таким образом, возрастает гибкость моделей и уровень абстракции. Однако данный подход, несмотря на свою привлекательность, сложен в реализации (для примера отметим необходимость создания оптимальных алгоритмов хранения абстрактных типов данных) и, насколько нам известно, нигде промышленно не реализован. Теоретически, вкупе с моделированием решеток кубов логикой предикатов первого порядка, абстрагирование понятия ''измерение'' дает очень интересные результаты.

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

Иерархии и агрегирование

Иерархичность данных — одно из важнейших свойств многомерных кубов. Иерархии призваны добавлять новые уровни в аналитическое пространство пользователя. Самым распространенным примером иерархии является ''день-неделя-месяц-год''. Соответственно, для уровней иерархии работают отношения обобщения и специализации (rollup/drilldown). Как правило, в научных работах рассматриваются простые примеры иерархий ''детальное значение — ALL'', однако, как мы увидим далее, подобного уровня детализации может быть недостаточно.

Все иерархии можно разбить на 2 типа, о которых пойдет речь ниже. Основой разбиения будет служить расстояние $ d$ от корня ( $ \{ALL,ALL,\ldots,ALL\}$ ) до листьев. В случае, если $ d = const$, иерархии называются уровневыми (leveled), иначе — несбалансированными (ragged).

Примеры типов иерархий:

Уровневые:
день-месяц-год; улица — город — страна
Несбалансированные:
Организационная диаграмма, различная группировка продуктов

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

Агрегирующие функции, меры и формулы

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

$\displaystyle f(x) = [\{f_{1,1},\ldots,f_{1,k_1}\},\ldots,\{f_{n,1},\ldots,f_{n,k_n}\}]
$

где $ x$ — точка куба, а $ f_{i,j}$ - $ j$ -ая функция агрегирования по $ i$ -ому измерению.

В [7] приведена следующая классификация агрегирующих функций с точки зрения сложности распараллеливания.

Дистрибутивные функции
позволяют разбивать входные данные и вычислять отдельные итоги, которые потом можно объединять.
Алгебраические функции
можно представить комбинацией из дистрибутивных функций (например, Average() можно представить как $ \frac {sum()} {count()})$
Холистические функции
невозможно вычислять на частичных данных или представлять каким-либо образом.

Эта классификация окажется полезной, когда мы будем рассматривать классы разбиения в алгоритме Quotient Cube (см. раздел Quotient Cube, работы [12],[11],[26]), в котором разбиение по покрытию применимо для дистрибутивных и алгебраических функций.

Вперед: Виды запросов к кубам Выше: Введение. Анализ задачи Назад: История Задачи   Содержание

хостинг Украина Виртуальный хостинг для сайта от $4,87

Регистрация домена от $2 в год

Партнерская программа – $20 за клиента

VPS с гибкой конфигурацией: за 1€

Мощные выделенные сервера: от 25€

Собственный Дата-Центр
Поддержка 24/7

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

ATLEX Выделенные серверы: в Европе / в России.

Виртуальные серверы: в Европе / в России.

Партнерская программа

Ваш сайт в 8 раз быстрее конкурентов. Хостинг от $2.95

VPS: SSD, KVM, бесплатные бэкапы и администрирование

Все необходимое для вашего сайта и лучшая техподдержка 24/7

хостинг сайтов ГиперХост — хостинг сайтов который Вы искали.

Виртуальный хостинг, Аренда VPS серверов, рация доменных имен, SSL сертификаты

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

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

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

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

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