ПРОГРАММИРОВАНИЕ, 2009, No 5, с. 26-36
- БАЗЫ ДАННЫХ ~
УДК 004.92+004.94
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ OLAP-КУБОВ
© 2009 г. С. Д. Кузнецов*, Ю. А. Кудрявцев**
* Институт системного программирования РАН 109004 Москва, ул. Солженицына, 25 ** Факультет вычислительной математики и кибернетики МГУ им. М.В. Ломоносова 119992 Москва, Воробьевы горы E-mail: kuzloc@ispras.ru, mail@ykud.com Поступила в редакцию 15.04.2008 г.
В 1993 году Э. Коддом была предложена концепция OLAP-систем (Online Analytical Processing), включающая в себя 12 правил представления данных пользователю. Подобные системы, как следует из названия, предназначены для анализа данных в интерактивном режиме. В связи с этим основной задачей OLAP-средств является представление больших объемов данных в виде, удобном для анализа конечными пользователями. Представление данных в виде многомерных кубов на сегодняшний день является de facto стандартом пользовательской работы с большими массивами данных.
В данной статье вводятся основные понятия OLAP-систем, которые затем формализуются с использованием математического аппарата теории решеток. В рамках введенной формализации доказывается оптимальность (с точки зрения объема хранимых элементов) представления OLAP-кубов замкнутыми решетками или эквивалентными им Quotient-решетками.
1. OLAP. БАЗОВЫЕ ПОНЯТИЯ И ТЕРМИНОЛОГИЯ
Термин OLAP (Online Analytical Processing) был введен в 1993 г. Эдгаром Коддом [1]. Цель OLAP-систем - облегчение решения задач анализа данных. Кодд сформулировал 12 признаков OLAP-данных, и большинство современных OLAP-средств отвечают этим постулатам. Однако 12 признаков в дальнейшем трансформировались в 4 ключевых определения, сформулированные Найджелом Пендзом (см. [2]), на которые теперь ссылаются при определении OLAP-систем.
FASMI-тест. OLAP-система должна быть:
• Fast - быстрой, обеспечивать почти мгновенный отклик на большинство запросов.
• Shared - многопользовательской, должен су-
ществовать механизм контроля доступа к данным, а также возможность одновременной работы многих пользователей.
• Multidimensional - многомерной, данные должны представляться в виде многомерных кубов.
• Information - данные должны быть полны с точки зрения аналитика, т.е. содержать всю необходимую информацию.
Большинство существующих OLAP-средств удовлетворяют всем этим признакам. Однако в реализации подобных приложений возникает ряд проблем, прежде всего связанных с увеличением объема данных, которые необходимо хранить.
В 1995 г. группа исследователей во главе с Джимом Греем [3], проанализировав создававшиеся тогда пользовательские приложения баз данных, предложила расширение языка SQL -оператор CUBE. Этот оператор отвечает в SQL за создание многомерных кубов. Концепция многомерного представления данных является, наряду с моделью транзакций, одной из самых известных идей Кодда. В этой работе исследовате-
ли указали ряд эвристических рекомендаций по реализации новой структуры данных.
CUBE представляет собой обобщение операторов GROUP BY по всем возможным комбинациям измерений с разными уровнями агрегации данных. Каждая сгруппированная таблица относится к группе ячеек, описываемых кортежами из измерений, по которым формируется куб. Оператор, расширяющий SQL, называется CUBE BY (синтаксис такой же, как и у GROUP BY).
В стандарт SQL'99 был включен набор операторов для работы с OLAP-данными (запросы grouping set, rollup by, cube by, window by, rank, rownum и пр.).
2. МНОГОМЕРНЫЕ КУБЫ, ОПРЕДЕЛЕНИЕ И СВОЙСТВА
Рассмотрим базовую (фактическую) таблицу r, на основе которой будет строиться OLAP-куб. Множество атрибутов r условно делят на 2 группы:
1. Набор измерений (категорий, локаторов), которые служат критериями для анализа и определяют многомерное пространство OLAP-куба. За счет фиксации значений измерений получаются срезы (гиперплоскости) куба. Каждый срез представляет собой запрос к данным, включающий агрегации.
2. Набор мер - функции, которые каждой точке пространства ставят в соответствие данные.
Из атрибутов r создаются измерения, содержащие проекцию r по атрибуту, с введенной иерархией (например, для таблицы, в которой хранятся фактические данные по продажам магазина, возможно наличие измерения под названием "Время", содержащего иерархию вида "Год-Месяц-Неделя-День"). Куб представляет собой декартово произведение измерений, где для каждого элемента произведения назначен набор мер. В кубе введены отношения обобщения и специализации (roll-up/drill-down) по иерархиям измерений (подробнее об иерархиях см. раздел 2.3). Ячейка высокого уровня иерархии может "спускаться" (drill-down) к ячейке низкого уровня
(для примера 2.1 (R1, ALL, весна) может "спуститься" к ячейке (R1, книги, весна)) и наоборот, "подняться" (roll-up) (от (R1, книги, весна) к (R1,ALL, весна) по измерению "продукты").
2.1. Пример
Рассмотрим пример, который будет в дальнейшем использоваться в этой статье.
Размер куба данных определяется по формуле
Ц(а + 1), где d - количество измерений ("столб-d
цов"), ci - размерность измерения, т.е. количество различных значений кортежей по этому измерению. Эквивалентный SQL-запрос: Select Count(distinct dimension) from cube-table)), +1 отвечает за "значение" ALL, агрегирующее все возможные значения измерения.
2.2. Измерения
Измерения куба - это набор доменов, по которым создается многомерное пространство. Важной особенностью OLAP-моделей является разделение измерений на локаторы (задающие точки) и меры (задающие значение). Как отмечено в [4], данное разделение может носить как условный, так и жесткий характер. В случае условного разделения измерения можно "разворачивать" как данные и как аналитики, создавая новую аналитику куба по продажам - "количество продаж". Таким образом, возрастает гибкость моделей и уровень абстракции. Однако этот подход, несмотря на свою привлекательность, сложен в реализации (в частности, отметим необходимость создания оптимальных алгоритмов хранения абстрактных типов данных) и, насколько нам известно, нигде промышленно не реализован. Теоретически, вкупе с моделированием решеток кубов логикой предикатов первого порядка, абстрагирование понятия "измерения" дает очень интересные результаты.
Локаторы куба отличаются иерархической структурой, и для получения значений мер на каждом уровне агрегирования вводятся агрегирующие функции.
2.3. Иерархии и агрегирование
Иерархичность данных - одно из важнейших свойств многомерных кубов. Иерархии призваны
КУЗНЕЦОВ, КУДРЯВЦЕВ Таблица 1. Фактические данные для примера
Таблица 2. Куб для таблицы 1. Агрегирующая функция - АУС
Регион Продукт Время года Продажи
R1 книги Весна 9
R1 Еда Осень 3
R2 книги Осень 6
Регион Продукт Время года AVG (Продажи)
R1 книги Весна 9
R1 Еда Осень 3
R2 книги Осень 6
R1 книги ALL 9
R1 ALL Весна 9
ALL книги Весна 9
R2 ALL ALL 6
ALL Еда ALL 3
ALL ALL Весна 9
ALL ALL ALL 6
добавлять новые уровни в аналитическое пространство пользователя. Самым распространенным примером иерархии является "день-неделя-месяц-год". Между элементами разных уровней иерархии существуют отношения обобщения и специализации (roll-up/drill-down).
Все иерархии можно разбить на 2 типа, о которых пойдет речь ниже. Основой разбиения будет служить расстояние d от корня ({ALL, ALL,.ALL}) до листьев. В случае, если d = const, - иерархии называются уровневыми (leveled), иначе - несбалансированными (ragged).
Примеры типов иерархий:
Уровневые: день - месяц - год; улица - город - страна.
Несбалансированные: Организационная диаграмма, различная группировка продуктов.
2.4. Агрегирующие функции, меры и формулы
Неотъемлемой частью OLAP-модели является задание функций агрегирования. Поскольку цель OLAP - создание многоуровневой модели
анализа, данные на уровнях, отличных от фактического, должны быть соответствующим образом агрегированы. Важно отметить, что по каждому измерению можно задавать собственную (и не одну) функцию агрегации. Таким образом, в случае куба с n измерениями функция агрегирования имеет вид:
f(x) = [{/i,b ••• f1,ki } ••• {fn,1, • ••, fn,k„ }],
где x - точка куба, а fij - j-ая функция агрегирования по i-му измерению.
В [5] приведена следующая классификация агрегирующих функций с точки зрения сложности распараллеливания.
Дистрибутивные функции позволяют разбивать входные данные и вычислять отдельные итоги, которые потом можно объединять.
Алгебраические функции возможно представить в виде комбинации из дистрибутивных функций ^например, Average() можно sum() \
представить как -— .
count() '
Рис. 1. Схема агрегирования данных для формирования куба. Таблица 3. Категории агрегирующих функций
Категория Примеры
Дистрибутивные Бпт(), СоппЬ(), Мгпгтпт(), Махгтпт()
Алгебраические Ауетаде(), Б1апЗ,ат^РеугаИоп(), Center-of-Mass(), МахЖ(), МтМ()
Холистические МвЛап(), Мо81_ЕтецпепЬ(), Капк()
Холистические функции невозможно вычислять на частичных данных или представлять каким-либо образом.
3. НЕКОТОРЫЕ ОПРЕДЕЛЕНИЯ ИЗ ТЕОРИИ РЕШЕТОК
Приведем некоторые необходимые в дальнейшем изложении определения из теории решеток. Определения приводятся по книге [6].
3.1. Частично-упорядоченное множество, решетка
Определение 1. Частично-упорядочен-ным множеством (чум) называется множество, на котором определено бинарное отношение
<, удовлетворяющее для всех х,у, г следующим правилам:
1. х < х (рефлексивность);
2. если х < у и у < х, то х = у (антисимметричность);
3. если х < у и у < г, то х < г (транизитив-ность).
Если для чум (А, <) верно, что Ух, у € А : х < у или у < х, то такое множество называется линейно-упорядоченным множеством, или цепью.
Пусть Н С Р и а € Р. Тогда а называется верхней границей подмножества Н, если Н < а для всех Н € Н. Верхняя граница а подмножества Н называется его верхней гранью или су-
премумом, если а < Ь для любой верхней границы Ь подмножества Н. Будем писать а = впрН или а = УН. Понятие нижней границы и нижней грани, или инфинума, вводятся аналогично; инфинум обозначается ги/Н или АН.
Определение 2. Чум (А, <) называется решеткой, если Ух, у е А существуют впр(х, у) и ги/(х
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.