автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Алгоритмы эффективной обработки MOLAP-кубов

Московский государственный университет имени М.В. Ломоносова

На правах рукописи

Кудрявцев Юрий Александрович

Алгоритмы эффективной обработки М01-АР-кубов

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

1 о ДЕН 2009

Москва - 2009

003487497

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук,

профессор

Марков А. С.

доктор физико-математических наук,

профессор

Машечкин И.В.

доктор физико-математических наук,

профессор

Кузнецов С.О.

Кафедра системного программирования -Южно-Уральский государственный университет

Защита состоится 18 декабря 2009 в 11 ч. 00 мин. на заседании диссертационного совета Д 501.001.44 Московского государственного университета имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ, С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ http://cs.msu.ru в разделе "Наука"-"Работа диссертационных советов" - 11Д 501.001.44"

Автореферат разослан "18" ноября 2009.

Учёный секретарь диссертационного совета профессор

Н.П. Трифонов

Общая характеристика работы. Актуальность темы.

Термин OLAP (Online Analytical Processing) был введен в 1993 Эдгаром Коддом ([Cod93]). Цель OLAP систем - предоставление пользователю возможности анализа больших объемов данных в интуитивно понятной форме. Кодд сформулировал 12 признаков OLAP-данных, и большинство современных OLAP средств отвечают этим постулатам. Однако 12 признаков в дальнейшем трансформировались в 4 ключевых определения, сформулированные Найджелом Пендзом (см. [Реп05] ), на которые теперь ссылаются при определении OLAP-систем.

FASMI-тест. OLAP-система должна быть:

• Fast - быстрой, обеспечивать почти мгновенный отклик на большинство запросов

• Shared - многопользовательской, должен существовать механизм контроля доступа к данным, а также возможность одновременной работы многих пользователей

• Multidimensional - многомерной, данные должны представляться в виде многомерных кубов.

• Information - данные должны быть полны с точки зрения аналитика, т.е. содержать всю необходимую информацию.

Окончательную формулировку термина предложила в 1995 группа исследователей во главе с Джимом Греем ([GBLP95] ), проанализировав создававшиеся тогда пользовательские приложения баз данных, и предложив расширение языка SQL - оператор CUBE. Этот оператор отвечает в SQL за создание многомерных кубов. Концепция многомерного представления данных является, наряду с моделью транзакций, одной из самых известных идей Кодда. В этой работе исследователи указали ряд эвристических рекомендаций по реализации новой структуры данных.

CUBE представляет собой обобщение операторов GROUP BY по всем возможным комбинациям измерений с разными уровнями агрегации дан-

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

Дальнейшее развитие OLAP-операций в SQL привело к тому, что в стандарт SQL'99 был включен набор операторов для работы с OLAP-данными (запросы grouping set, rollup by, cube by, window by, rank, rownum и пр.).

В реализации OLAP-приложений возникает ряд проблем, прежде всего связанных с экспоненциальным увеличением объема данных, которые необходимо хранить или рассчитывать.

OLAP-приложения делятся прежде всего по методу хранения данных

на:

• ROLAP, Relational OLAP - все данные куба (фактическая таблица + агрегаты) хранятся в реляционной таблице

• MOLAP, Multidimensional OLAP - и фактические данные, и агрегаты хранятся в многомерной бд

• HOLAP, Hybrid OLAP - фактические данные хранятся в реляционной таблице, агрегаты - в виде многомерных структур (многомерной БД)

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

В 1994 Майкл Стоунбрейкер и Сунита Сараваги ([GBLP95] ) предложили модель оценки выбора агрегированных представлений с учетом стоимости материализации и изменения скорости работы запросов. Пять лет спустя, Карлофф и Михаил ([GBLP95] ) показали сводимость этой задачи к

NP-трудной задаче упаковки, доказав тем самомым отсутствие оптимальных алгоритмов решения этой задачи.

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

Цель работы. Целью диссертационной работы является развитие новых алгоритмов расчета MOLAP-кубов для систем с полной материализацией, улучшение существующих результатов и оценка применимости параллельных вычислений к задаче расчета OLAP-кубов.

В соответствии с целью исследования были поставлены следующие задачи:

1. Выявить и описать методы построения OLAP-кубов не вошедшие в современные научные обзоры других исследователей, классифицировать методы;

2. Создать математическую модель, на базе которой оценить оптимальность методов

3. Использовать полученные математические результаты для создания более оптимального метода обработки OLAP-данных

4. Оценить применимость современной парадигмы параллельных вычислений над большими объемами данных Map/Reduce для задачи создания OLAP-кубов

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

Научная новизна работы. Следующие особенности работы определяют её научную новизну:

1. проведен анализ существующих алгоритмов обработки MOLAP-кубов, выделены следующие группы алгоритмов - синтаксические, семантические и аппроксимирующие. Для каждой из групп приведены примеры наилучших, на момент написания работы, алгоритмов

и указаны условия, в рамках которых применение этих алгоритмов является оптимальным (см главу 3). На основе результатов анализа разработана формальная математическая модель OLAP данных на базе теории решеток. Для предложенной модели с учётом классов эквивалентности доказана оптимальность представления OLAP-кубов замкнутыми решетками по введенному отношению покрытия, показана эквивалентность представления кубов замкнутыми решетками и разбиения решетки куба на классы эквивалентности по отношению покрытия, предложенному в алгоритме Quotient Cube. При этом доказана оптимальность алгоритма Quotient Cube (см главу 4).

2. для задачи создания замкнутых решеток OLAP-кубов или же Quotient СиЬе-решеток предложен алгоритм, использующий парадигму Map/Reduce. Предложенный алгоритм, в отличие от уже существующих линейных алгоритмов, может эффективно использовать многомашинные кластеры и многоядерные серверы, что позволяет существенно увеличить объем обрабатываемых данных и уменьшить время расчетов, см главу 5.

3. создан прототип алгоритма на технологиях Apache Hadoop (многомашинный кластер, см [KMSB08] ) и Standord Phoenix (использование map/reduce для многопроцессорных серверов, см [RRP+07]), проведены эксперименты, показывающие преимущества данного алгоритма по отношению к уже существующим, см главу 5.

Теоретическая и практическая ценность. Разработана математическая модель представления OLAP-кубов, использующая формализм теории решеток. На базе этой модели доказана оптимальность представления куба замкнутыми решетками. Приведен новый параллельных алгоритм вычисления замкнутых кубов на базе парадигмы Map/Reduce вычислений. Полученный алгоритм апробирован на экспериментальных данных, показана эффективность метода.

Апробация работы. Результаты диссертации докладывались и обсуждались на следующих конференциях и семинарах:

1. Трижды на семинаре московской секции ACM SIGMOD (2005, 2007, 2008)

2. Международной конференции 'Бизнес-Информатика', Звенигород, 2007

3. Дважды на конференции 'Корпоративные Базы Данных', Москва, 2007, 2009

4. Конференции 'Бизнес-Аналитика на современном предприятии', Москва, 2008

5. Конференции 'Advances in Databases, Knowledge, and Data Applications', Канкун, Мексика, 2009

6. Конференции Syrcodis, Москва, 2006

7. На семинаре 'Проблемы современных информационно-вычислительных систем' под управлением Васенина ВА. 2008

8. Неоднократно на семинаре 'Технологии баз данных' под управлением Кузнецова С.Д. и Маркова A.C., Москва, 2004-2008

9. На семинаре 'Математические модели информационных технологий' под управлением Кузнецова С.О., ГУ-ВШЭ, 2008

Публикации. Содержание диссертации изложено в работах [1-5]. Объем и структура работы. Диссертация содержит 142 страницы текста, состоит из введения, четырех глав, библиографии.

Содержание работы.

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

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

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

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

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

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

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

Регион Продукт Время года Продажи

R1 книги Весна 9

R1 Кда Осень 3

R2 книги Осень 6

d

Размер куба данных определяется по формуле f|(ci + 1) , где d -

г=1

количество измерений ("столбцов"), q - размерность измерения, т.е. количество различных значений кортежей по этому измерению. +1 отвечает за "значение"ALL, агрегирующее все возможные значения измерения.

В главе 2 дано более подробное описание задачи. Анализ различных алгоритмов построения MOLAP-кубов приведен в третьей главе. Подробно рассмотрен семантический алгоритм Quotient Cube, оптимальность представления которого доказывается в главе 4.

Таблица 2. Куб для таблицы 1. Агрегирующая функция - AVG.

Регион Продукт Время года AVG (Продажи)

R1 книги Весна 9

R1 Еда Осень 3

R2 книги Осень 6

R1 книги ALL 9

Rl j ALL Весна 9

ALL книги Весна 9

W2 ALL ALL б

ALL Еда ALL 3

ALL ALL Весна 9

ALL ALL ALL 6

Для доказательства оптимальности Quotient-решетки в четвертой главе сформулировано описание OLAP-куба в терминах теории решеток. При этом вводятся следующие определения:

Определение 1. Многомерное пространство Space(r) = {хлеоМА] U ALL) U {0,0,... ,0}}, где х - декартово произведение, {0,0,..., 0} - нулевой кортеж.

Vs € Space(r),s - многомерный кортеж. Для куба из примера (см. таблицу 1) получаем следующее многомерное пространство:

{(R1,книги,весна), (R1,еда,осень), (R2,книги,осень),(R1,еда,весна),.... (ALL,еда,осень), (Rl,ALL,весна),..., (ALL,ALL,ALL)} -■- всего 28 кортежей.

Введем отношение обобщения/специализации на Space(r) обозначаемое >д.

Определение 2. Отношение порядка >д и, v £ Space(r) _ ( MA e Д u[/l] С u[A]

^ — 9 ^ — I

I e противном случае v = {0,0,..., 0}

Если u, v € Space(r), u>gv тогда и обобщает v в Space(r). Для куба из примера (см. таблицу 1): (ALL,efla,oceHb)>s(Rl,еда,осень), (ALL,ALL,ALL)>9(ALL,еда,осень).

Операторы, создающие новые кортежи: сумма (+) и произведение

Определение 3. Сумма двух кортежей - наименьший кортеж, обобщающий оба операнда, и, V е Б расе {г)

Для примера из таблицы 1, (R2,еда,осень) + (Rl,ALL,осень) = (ALL,ALL,осень)

Определение 4. Произведение двух кортежей - наибольший кортеж, уточняющий оба операнда.

Пусть УЛ £ D, z[A] = и{А\ Л v[A}. Тогда u,v G Space(r)

Например, (ALL,еда,осень) • (Rl,ALL,осень) = (R1,еда,осень) Введя определения Space(r), >g и операторы + и • мы можем дать определение решетки куба.

Определение 5. Решетка куба

Пусть г - отношение базы данных над DUM. Чум CL(r) = {Space(r), >g} - решетка, в которой пересечение и объединение вводятся следующим образом:

{CL(r), >g, Л, V} - решетка куба.

В заданных терминах, решетка для алгоритма Quotient Cubes (см описание в главе 3) определяется следующим образом:

Определение 6. Quotient решетка куба

Пусть CL(r) - решетка куба(см. определение 5), и =cov ~~ отношение эквивалентности. Quotient решетка куба QCLR(r) = (CL(r)/ =cov,^)-Для двух классов эквивалентности А,Ве QCLR(r),A >z В если За €

t = u + v<*VAeD, t[A} =

и{А], если и[А\ = v[A] ALL , в противном случае

t = z если ->3A б D\z[A] = {0} {0,0,..., 0} , е противном случае

VT С CL(r), AT = +tcTt VT С CL{r), VT = .tcrt

A,3b£B\a >gb.

Минимальной решеткой, с точки зрения классов эквивалентности является замкнутая решетка. В четвертой главе приведено доказательство эквивалентности Quotient решетки и замкнутой решетки. Таким образом, Quotient Cubes алгоритм является оптимальным по количеству хранимых замкнутых классов алгоритмом хранения OLAP-кубов.

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

Алгоритм создания замкнутого MOLAP-куба

С учетом стремительного роста объема данных, которые необходимо обрабатывать, распараллеливание программ остается единственно возможным вариантом реализации вычислительно сложных задач, например создания графа web-страниц и ранжирования их. Учитывая этот факт, группа инженеров в Google, создала новую библиотеку Map-Reduce (см [DG06] и [Lam08]), которая сейчас широко используется для новых приложений, создаваемых в компании, вместо старых подходов к написанию параллельных программ на "чистом"С++.

Map/Reduce парадигма базируется на представлении необходимых вычислений в виде последовательности 2х функций: тар и reduce. При этом функция тар применяется ко всем входным данным и каждому входному значению сопоставляет пару (ключ, /тар(элемент исходных данных)). Функция reduce применяется к множеству пар содержащим одинаковый ключ и возвращает пару (ключ, /reduce (множество результатов fmap с таким же ключом)). Подобные операции были введены в языке LISP, где тар применялся ко всем элементам списка, a reduce (или в некоторых других функциональных языках, fold) "сворачивает"список, применяя агрегирующую функцию над всеми элементами.

В пятой главе приведено подробное описание Map/Reduce подхода и кратко описаны основные реализации.

Основной задачей алгоритма создания Quotient куба является вычисление замыкания (или покрытия) каждой ячейки куба и вычисление таким образом классов эквивалнентности. Мы используем Map-Reduce функции для обхода решетки куба поочередно сверху-вниз и снизу-вверх, что позволяет рано обнаруживать некоторые типы замкнутых классов и избегать

таким образом ненужных вычислений. Промежуточные результаты (текущие нижние грани) мы храним в распределенном кэше. Описание в псевдокоде приведено в 1.

_Псевдокод № 1. Вычисление замкнутого куба_

compute_closed_cube(data d, distributed cache dc, number of dimensions D): for i in [1..D/2J:

{ if map(d, D-i, dc) О 0 {reduce(d, D-i , dc)}

else cube is computed

if map(d, i, dc) О 0 {reduce(d, i, dc)}

else cube is computed}

closed classes from dc are transformed into QC-Тгее for query processing.

Если в результате map фазы не генерируются новые ячейки - значит все замкнутые классы уже вычислены и вычисления можно завершить. Шаги алгоритма:

1. 1ый шаг вниз, все верхние грани с supp — 1 записываются как паттерны замкнутых классов, т.е. если (а\, *, *) имеет supp — 1, то записывается класс (a\,bi, ci), (ai, *, *) и ячейки, содержащие а\ в дальнейших шагах не порождаются

2. 1ый шаг вверх, все верхние грани с supp >= 2 записываются в промежуточное хранилище

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

4. 2ой шаг вверх, аналогично 2, только supp >= 2. Дублирующихся верхних граней ячеек с supp=2 порождено не будет, они попадут в паттерны, полученные на шаге 3

5. Зий шаг вниз, аналогично 3 и т.д.

Листинги шар и reduce функций в псевдокоде представлены в 2 и 3. _Псевдокод К8 2. Map функция _

map(data d, level L, distributed cache dc):

for each cell c in d {

c_aggr = generate_aggregate_cells (c , L) for each aggr_celi In c_aggr: {if for each ubound in dc[classes_upper_bounds]

(aggrc * ubound = {0,0,...,0}) then output (aggrc.l)}

}

Функция generate_aggregate_cells генерирует все возможные агрегаты заданного уровня для указанной ячейки. Например, для первого уровня, она порождает набор ячеек, в которых одна из координат заменена значением ALL.

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

_Псевдокод № 3. Reduce функция_

reduce(map_output, level L, distributed cache dc): for each ( cell , support) in map^output {resulting_support = sum of map emited supports if (resulting_support = (D - L + 1))

{if exists lbound ,lbound_support in dc| closed_classes_lowerbounds] (cell >= lbound) and (lbound_support = resulting_support) {dc[closed_classes] = { cell ,ubound)} else

{dc[closed_classes_upperbounds)+= (cell , resulting_support)}

}

else if resulting_support > 1

{if exists ubound , ubound_support in dc[closed_classes_upperbounds] (ubound >= cell) and (ubound_support = resulting_support) {dc[ closed_classes ] = (cell ,ubound)} else

{dc [ closed_classes_lowerbounds]+= (cell , resulting_support)}}

}

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

Рассмотрим работу алгоритма на примере для данных таблицы 1. Шаги алгоритма:

1. Первый шаг сверху-вниз порождает ячейки Зего уровня (с двумя координатами, равными All). При этом все верхние грани с support = 1 записываются в dc[closed_classes_upperbounds]. Таким образом записываются (R2,A11, All), (all,еда,all) и (all,all,весна), т.к. их support равен 1.(all,all,осень),(all,книги,all) и (Rl,all,all) записываются как потенциальные нижние грани, вместе с их значением support.

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

Описанный алгоритм реализован на Apache Hadoop и запускаемых в виде Map задач на серверах копий M/R библиотеки Stanford Phoenix для создания локальных кубов.

В этой конфигурации общий алгоритм построения куба состоит из следующих фаз (см рисунок 1):

1. Распределение данных на Hadoop File System

2. Запуск локальных Phoenix в Hadoop Streaming как map задачи

3. Получение наборов классов эквивалентности Quotient Cube

4. Формирование локального QC-TVee на каждом Hadoop-сервере

Обработка запросов состоит из (см схему 2):

1. Запуска запроса в виде тар задачи на Hadoop - обращение к каждому локальному Phoenix кубу

2. Агрегации полученных результатов в reduce фазе

Основные результаты работы:

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

• разработана формальная математическая модель OLAP данных на базе теории решеток, на введенной модели доказана оптимальность (с точки зрения классов эквивалентности) представления OLAP-кубов замкнутыми решетками по введенному отношению покрытия

• для задачи создания замкнутых решеток OLAP-кубов предложен алгоритм, использующий парадигму Map/Reduce.

• создан прототип алгоритма на технологиях Apache Hadoop (многомашинный кластер) и Stanford Phoenix (использование map/reduce для многопроцессорных серверов), проведены эксперименты, показывающие преимущества данного алгоритма по отношению к уже существующим.

Рис. 1. Схема обработки кубов

Л,- ' »

^ Запуск'кластере серверов,

Запуск легального создания куб»

Мер-сервер

Ззяусклочапкного аадакнвкува

КЬр-сяревр

О-шагов, где О-число уровней решетки куйа

Мм-ис уж»расчи»«нных «и предыдущих зв»жнутых <мее*. «зтерый порождал, м нужно

Рис. 2. Схема обработки запросов к кубам

............................................—...................... . .....................

Локальный Ч

ЗЭМ«Л/1«йЙ

куС

\ \

Мар-серевр |

Локнг>ьиыа замкнутый куС

\

Мар-жомр

Список публикаций по теме диссертации

1. 'Applying Map-Reduce Paradigm for Parallel Closed Cube Computation', Kuznetsov Sergei, Kudryavcev Yury, Advances in Databases, Knowledge, and Data Applications, DBKDA '09, pages 62 - 67

2. 'Математическая модель OLAP-кубов', Кузнецов С.Д., Кудрявцев Ю.А.,'Программирование', №5 2009

3. 'OLAP-технологии: обзор решаемых задач и исследований', Ю.Кудрявцев, Бизнес-Информатика, апрель 2008, Междисциплинарный научно-практический журнал, Госудаственный Университет — Высшая Школа Экономики, страницы 66-79, апрель 2008

4. 'Efficient algorithms for MOLAP data storage and query processing', Yuri Kudryavcev, Syrcodis, 2006 Сборнике тезисов конференции Syrcodis 2006

5. Сборнике работ молодых ученых факультета ВМиК МГУ 2005 (работа награждена дипломом второй степени)

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 16.11.2009 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 75 экз. Заказ 628. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

1 Введение б

§ 1 Объект исследования и актуальность темы.

§ 2 Цели и задачи исследования

§ 3 Научная новизна.

§ 4 Положения, выносимые на защиту.

§ 5 Апробация результатов работы.

§ 6 Содержание работы.

2 OLAP

2.1 История Задачи

§ 1 12 Признаков OLAP Данных.

§ 2 FASMI тест.

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

§ 1 Пример.

§ 2 Измерения.

§ 3 Иерархии и агрегирование.

2.3 Виды запросов к кубам.

§ 1 Точечные запросы (Point queries).

§ 2 Интервальные запросы. (Range queries).

§ 3 Обратные запросы. (Iceberg queries).

§ 4 Intelligent Roll-Up запросы.

2.4 Хранение и эффективный расчет OLAP-кубов.

§ 1 Представление нулевых данных.

§ 2 Взрыв данных

§ 3 Материализация представлений

2.5 Общие стратегии вычисления кубов.

§ 1 Способы хранения.

§ 2 Классификация алгоритмов хранения MOLAP-данных

2.6 OLAP и статистические базы данных.

3.1 Требования к многомерным моделям данных.

3 Анализ существующих алгоритмов

3.2 Алгоритм Dwarf.

§ 1 Виды избыточностей структуры куба.

§ 2 Структура куба.

§ 3 Выполнение различных типов запросов.

§ 4 Сложность

§ 5 Виды сжатия.

§ 6 Вывод.

3.3 Многопозиционное агрегирование массивов для вычисления кубов.

§ 1 Пример Вычислений.

3.4 Аппроксимирующие алгоритмы.

§ 1 Вейвлеты.

3.5 Алгоритм Bottom-Up Computation.

3.6 Алгоритм Star-Cubing.

3.7 Condensed Cube.

3.8 Quotient Cube.

§ 1 Разбиение на классы ячеек.

§ 2 QC-Trees.

§ 3 Выполнение различных типов запросов.

4.1 Некоторые определения из теории решеток.

§ 1 Частично-упорядоченное множество, решетка.

§ 2 Описание решеток. Изомофизм решеток. Оператор замыкания.

4 Математическая модель OLAP-данных

4.2 Математическая модель OLAP-кубов.

§ 1 Общие определения. Меры, измерения, операторы в многомерном пространстве.

§ 2 Операторы в Space(r).

§ 3 Классы эквивалентности решетки куба.

§ 4 Замыкания и замкнутые решетки кубов.

5.1 Map-Reduce: парадигма параллельных вычислений.

§ 1 Map/Reduce на многопроцессорных машинах.

§ 2 Map/Reduce и OLAP.

5 Алгоритм вычисление замкнутых кубов с использованием

Map-Reduce

5.2 Предложенный алгоритм.

§ 1 Общий подход к вычислениям

§ 2 Алгоритм создания замкнутого MOLAP-куба на многопроцессорном сервере.

§ 3 Результаты экспериментов.

§ 1. Объект исследования и актуальность темы

Термин OLAP (Online Analytical Processing) был введен в 1993 Эдгаром Коддом [Cod93]. Цель OLAP систем - облегчение анализа данных. Кодд сформулировал 12 признаков OLAP-данных, и большинство современных OLAP средств отвечают этим постулатам. Однако 12 признаков в дальнейшем трансформировались в 4 ключевых определения, сформулированные Найджелом Пендзом (см. [РепОБЬ]), на которые теперь ссылаются при определнии OLАР-систем.

FASMI-тест. OLAP-система должна быть:

• Fast - быстрой, обеспечивать почти мгновенный отклик на большинство запросов

• Shared - многопользовательской, должен существовать механизм контроля доступа к данным, а также возможность одновременной работы многих пользователей

• Multidimensional - многомерной, данные должны представляться в виде многомерных кубов.

• Information - данные должны быть полны с точки зрения аналитика, т.е. содержать всю необходимую информацию.

Окончательную формулировку термина предложила в 1995 группа исследователей во главе с Джимом Греем [GBLP95], проанализировав создававшиеся тогда пользовательские приложения баз данных, и предложив расширение языка SQL - оператор CUBE. Этот оператор отвечает в SQL за создание многомерных кубов. Концепция многомерного представления данных является, наряду с моделью транзакций, одной из самых известных идей Кодда. В этой работе исследователи указали ряд эвристических рекомендаций по реализации новой структуры данных.

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

Дальнейшее развитие OLAP-операций в SQL привело к тому, что в стандарт SQL'99 был включен набор операторов для работы с OLAP-данными (запросы grouping set, rollup by, cube by, window by, rank, rownum и пр.).

В реализации подобных OLAP-приложений возникает ряд проблем, прежде всего связанных с экспоненциальным увеличением объема данных, которые необходимо хранить или рассчитывать.

6. Заключение

Рассматриваемая тема актуальна и востребована. Существует большое число промышленных систем, использующих различные идеи и методы работы с OLAP-данными. Тема анализа данных сейчас актуальна в связи с возрастанием объема хранящихся данных. И создание инструментов, призванных помочь пользователю анализировать данные, - актуальное направление научных исследований. Результаты работы

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

• разработана формальная математическая модель OLAP данных на базе теории решеток, на введенной модели доказана оптимальность (с точки зрения классов эквивалентности) представления OLAP-кубов замкнутыми решетками по введенному отношению покрытия

• для задачи создания замкнутых решеток OLAP-кубов предложен алгоритм, использующий парадигму Map/Reduce.

• создан прототип алгоритма на технологиях Apache Hadoop (многомашинный кластер) и Stanford Phoenix (использование map/reduce для многопроцессорных серверов), проведены эксперименты, показывающие преимущества данного алгоритма по отношению к уже существующим.

Апробация результатов работы Основные результаты работы докладывались и обсуждались на следующих конференциях:

1. Конференции Syrcodis, Москва, 2006

2. Трижды на семинаре московской секции ACM SIGMOD (2005, 2007, 2008)

3. 1ой международной конференции 'Бизнес-Информатика', Зеленоград, 2007

4. Дважды на конференции 'Корпоративные Базы Данных', Москва, 2007, 2009

5. На семинаре 'Проблемы современных информационно-вычислительных систем' под управлением Васенина В.А. 2008

6. Неоднократно на семинаре 'Технологии баз данных' под управлением Кузнецова С.Д. и Маркова A.C., Москва, 2004-2008

7. Конференции 'Бизнес-Аналитика на современном предприятии', Москва, 2008

8. Конференции 'Advances in Databases, Knowledge, and Data Applications', Канкун, Мексика, 2009

Основные научные результаты работы опубликованы в:

1. 'Applying Map-Reduce Paradigm for Parallel Closed Cube Computation', Kuznetsov Sergei, Kudryavcev Yury, Advances in Databases, Knowledge, and Data Applications, DBKDA '09, pages 62 - 67

2. 'Математическая модель OLAP-кубов', Кузнецов С.Д., Кудрявцев ЮА.,'Программирование', №5 2009

3. 'Efficient algorithms for MOLAP data storage and query processing', Yuri Kudryavcev, Syrcodis, 2006 Сборнике тезисов конференции Syrcodis 2006

4. 'OLАР-технологии: обзор решаемых задач и исследований', Ю.Кудрявцев, Бизнес-Информатика, апрель 2008, Междисциплинарный научно-практический журнал, Госудаственный Университет — Высшая Школа Экономики, страницы 66-79, апрель 2008

5. Сборнике работ молодых ученых факультета ВМиК МГУ 2005 (работа награждена дипломом второй степени)

1. JI.65. Фукс JI. Частично упорядоченные линейные системы. Мир, 1965.

2. Г.81. Гретцер Г. Общая теория решеток. Мир, 1981.

3. Г.84. Биркгоф Г. Теория решеток. Наука, 1984.

4. AFEA06. Shah Arun, Novy Robert F., Ertl, and Robert A. Allocation measures and metric calculations in star schema multi-dimensional data warehouse. United States Patent 7,080,090, July 2006.

5. AS94. Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules. In Jorge B. Bocca, Matthias Jarke, and

6. Carlo Zaniolo, editors, Proc. 20th Int. Conf. Very Large Data Bases, VLDB, pages 487-499. Morgan Kaufmann, 12-15 1994.

7. BDJ+05. Douglas Burdick, Prasad Deshpande, T. S. Jayram, Raghu Ramakrishnan, and Shivakumar Vaithyanathan. Olap over uncertain and imprecise data. In VLDB, pages 970-981, 2005.

8. BGJ06. Michael H. Bohlen, Johann Gamper, and Christian S. Jensen.

9. Multi-dimensional aggregation for temporal data. In EDBT, pages 257-275, 2006.

10. BR99. Kevin Beyer and Raghu Ramakrishnan. Bottom-up computation of sparse and iceberg cubes. In SIGMOD, 1999.

11. BW01. Daniel Barbara and Xintao Wu. Loglinear-based quasi cubes. Journal of Intelligent Information Systems, 2001.

12. BYR08. Ricardo Baeza-Yates and Raghu Ramakrishnan. Data challenges at yahoo! In EDBT '08: Proceedings of the 11th international conference on Extending database technology, pages 652-655, New York, NY, USA, 2008. ACM.

13. Cas04. Alain Casali. Mining borders of the difference of two datacubes. In DaWaK, 2004.

14. CCL03a. Alain Casali, Rosine Cicchetti, and Lotfi Lakhal. Cube lattices: a framework for multidimensional data mining. 2003.

15. CCL03b. Alain Casali, Rosine Cicchetti, and Lotfi Lakhal. Extracting semantics from data cubes using cube transversals and closures. In SIGKDD, 2003.

16. CCLN06. Alain Casali, Rosine Cicchetti, Lotfi Lakhal, and Noel Novelli.1.ssless reduction of datacubes. In DEXA, pages 409-419, 2006.

17. CCLR05a. Bee-Chung Chen, Lei Chen, Yi Lin, and Raghu Ramakrishnan.

18. Prediction cubes. In VLDB '05: Proceedings of the 31st international conference on Very large data bases, pages 982-993. VLDB Endowment, 2005.

19. CCLR05b. Bee-Chung Chen, Lei Chen, Yi Lin, and Raghu Ramakrishnan. Prediction cubes. In VLDB, pages 982-993, 2005.

20. Cel06. Joe Celko. Analytics and OLAP in SQL. Morgan Kaufmann, 2006.

21. CNCL07. Alain Casali, Sébastien Nedjar, Rosine Cicchetti, and Lotfi Lakhal.

22. Convex cube: Towards a unified structure for multidimensional databases. In DEXA, pages 572-581, 2007.

23. DERC01. Raghu Dehne, Todd Eavis, and Andrew Rau-Chaplin. Coarse grained parallel on-line analytical processing (olap) for data mining. In ICCS, pages 589-598, 2001.

24. DG04. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. OSDI '04, pages 137-150, 2004.

25. DMT+05. Burdick Doug, Deshpande Prasad M., Jayram T.S., Ramakrishnan Raghu, and Vaithyanathan Shivakumar. Olap over uncertain and imprecise data. In VLDB, 2005.

26. DPJ03. Curtis E. Dyreson, Torben Bach Pedersen, and Christian S.

27. Jensen. , Incomplete information in multidimensional databases. In Multidimensional databases: problems and solutions, pages 282309. IGI Publishing, Hershey, PA, USA, 2003.

28. Ear94. Robert J. Earle. Method and apparatus for storing and retrieving multi-dimensional data in computer memory. United States Patent 5,359,724, October 1994.

29. Eav03. Todd Eavis. Parallel relational olap. PhD thesis, Dalhousie University, Halifax, Nova Scotia, 2003. Adviser-Andrew Rau-Chaplin.

30. GBLP95. Jim Gray, Adam Bosworth, Andrew Layman, and Hamid Pirahesh.

31. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Microsoft Lab, 1995.

32. GC97. Sanjay Goil and Alok Choudhary. High performance olap and data mining on parallel computers. Center of Parallel and Distributed Computing Technical Report TR-97-05, 1997.

33. GGL03. Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. Thegoogle file system. SIGOPS Oper. Syst. Rev., 37(5):29-43, December 2003.

34. GM05. Himanshu Gupta and Inderpal Singh Mumick. Selection of views to materialize in a data warehouse. IEEE Transactions on Knowledge and Data Engineering, 17(l):24-43, 2005.

35. GRP06. Matteo Golfarelli, Stefano Rizzi, and Andrea Proli. Designing what-if analysis: towards a methodology. In DOLAP '06: Proceedings of the 9th ACM international workshop on Data warehousing and OLAP, pages 51-58, New York, NY, USA, 2006. ACM Press.

36. HFL+08. Bingsheng He, Wenbin Fang, Qiong Luo, Naga K. Govindaraju, and Tuyong Wang. Mars: A mapreduce framework on graphics processors. In PACT08: IEEE International Conference on Parallel Architecture and Compilation Techniques 2008, 2008.

37. HRU96. Venky Harinarayan, Anand Rajaraman, and Jeffrey Ulman. Implementing data cubes efficiently. SIGMOD, 1996.1. Kim.1. KL05.

38. Aaron Kimball. Google: Cluster computing and mapreduce:lecture 5 graph algorithms.

39. Owen Kaser and Daniel Lemire. Attribute value reordering for efficient hybrid olap. Elsevier Science, 2005.

40. KM99. H.J. Karloff and M. Mihail. On the complexity of view-selection problem. In PODS, 1999.

41. KMSB08. Aaron Kimball, Sierra Michels-Slettvet, and Christophe Bisciglia.

42. Cluster computing for web-scale data processing. In SIGCSE '08:

43. Proceedings of the 39th SIGCSE technical symposium on Computer science education, pages 116-120, New York, NY, USA, 2008. ACM.

44. Laks V.S. Lakshmanan and Mark Gyssens. A foundation for multidimensional databases. In VLDB, 1996.

45. G04. Xiaolei Li, Jiawei Han, and Hector Gonzalez. High-dimensional olap: A minimal cubing approach. In VLDB, 2004.

46. W03. Xiaolei Li, Dong Xin Jiawei, and Benjamin W. Wah. Star-cubing: Computing iceberg cubes by top-down and bottom-up integration. In VLDB, 2003.

47. Z03a. Laks V.S. Lakshmanan, Jian Peiz, and Yan Zhao. Qctrees: An efficient summary structure for semantic olap. In SIGMOD, 2003.

48. Z03b. Laks V.S. Lakshmanan, Jian Peiz, and Yan Zhaoy. Socqet: Semantic olap with compressed cube and summarization. In SIGMOD, 2003.

49. MMR91. F.M. Malvestuto, M. Moscarini, and M. Rafanelli. Suppressing marginal cells to protect sensitive information in a two-dimensional statistical table. ACM, 1991.

50. MPWOO. Soroush Momen-Pour and Alan Wagner. Parallel partitioned-cube algorithm. In PDPTA, 2000.

51. MVSV03. Andreas Maniatis, Panos Vassiliadis, Spiros Skiadopoulos, and Yannis Vassiliou. Advanced visualization for olap. In DOLAP '03,2003.

52. MVSV04. Andreas Maniatis, Panos Vassiliadis, Spiros Skiadopoulos, and Yannis Vassiliou. CPM: A cube presentation model for olap. 6th ACM International Workshop on Data Warehousing and OLAP,2004.

53. NCCL07. Sébastien Nedjar, Alain Casali, Rosine Cicchetti, and Lotfi Lakhal.

54. Emerging cubes for trends analysis in olapdatabases. In Song et al. SEN07., pages 135-144.

55. Pas02. Mosha Pasumansky. Multidimensional data ordering. United States Patent 6,460,026, October 2002.

56. Pen05a. Nigel Pendse. Olapreport: Database explosion, 2005.

57. Pen05b. Nigel Pendse. Olapreport: What is olap?, 2005.

58. PJ99a. Torben Bach Pedersen and Christian S. Jensen. Multidimensional data modeling for complex data. In ICDE, pages 336-345, 1999.

59. PJ99b. Torben Bach Pedersen and Christian S. Jensen. Multidimensional data modeling for complex data. In ICDE, pages 336-345, 1999.

60. PJ01. Torben Bach Pedersen and Christian S. Jensen. Multidimensional database technology. IEEE Computer, 34(12):40-46, 2001.

61. PJ05. Torben Bach Pedersen and Christian S. Jensen. Multidimensional databases. In The Industrial Information Technology Handbook, pages 1-13. 2005.

62. PJD99. Torben Bach Pedersen, Christian S. Jensen, and Curtis E.

63. Dyreson. Supporting imprecision in multidimensional databases using granularities. In SSDBM, pages 90-101, 1999.

64. PJD00. Torben Bach Pedersen, Christian S. Jensen, and Curtis E. Dyreson.

65. The treescape system: Reuse of pre-computed aggregates over irregular olap hierarchies. In VLDB, pages 595-598, 2000.

66. PJD01. Torben Bach Pedersen, Christian S. Jensen, and Curtis E. Dyreson.

67. Pre-aggregation for irregular olap hierarchies with the treescape system. In ICDE Demo Sessions, pages 1-3, 2001.

68. PK02. Jeffery S. Pinard and Katheryn Kemper. System for managing accounting information in a multi-dimensional database. United States Patent 6,397,195, May 2002.

69. Pro02. Anthony Charles Proctor. Apparatus and method for compound on-line analytical processing in databases. United States Patent 6,490,593, December 2002.

70. Pu05. Ken Q. Pu. Modeling, querying and reasoning about olap databases: A functional approach. DOLAP, 2005.

71. Raf03. Maurizio Rafanelli, editor. Multidimensional Databases: Problems and Solutions. Idea Group Publishing, 2003.

72. RP02. Srinivasan Sundar Raghavan and Rama Murthy Penumarti.

73. Dynamic recursive build for multidimensional databases and methods and apparatus thereof. United States Patent 6,405,208, June 2002.

74. SDRK02. Yannis Sismanis, Antonios Deligiannakis, Nick Roussopoulos, and Yannis Kotidis. Dwarf: Shrinking the petacube. In VLDB, 2002.

75. SEN07. II Yeal Song, Johann Eder, and Tho Manh Nguyen, editors.

76. Data Warehousing and Knowledge Discovery, 9th International Conference, DaWaK 2007, Regensburg, Germany, September 37, 2007, Proceedings, volume 4654 of Lecture Notes in Computer Science. Springer, 2007.

77. SGA97. Sunita Sarawagi, Ashish Gupta, and Rakesh Agrawal. Modeling multidimensional databases. IBM Research Report, 1997.

78. SHX04. Zheng Shao, Jiawei Han, and Dong Xin. Mm-cubing: Computing iceberg cubes by factorizing the lattice space. In Proceedings of the 16th International Conference on Scientific and Statitistical Database Management (SSDBM'), 2004.

79. SIA05. SI AM International Data Mining Conference. Cross Table Cubing: Mining Iceberg Cubes from Data Warehouses, April 2005.

80. SKK. Timos Sellis, Nikos Karayannidis, and Yannis Kouvaras. Cube file: A file structure for hierarchically clustered olap cubes.

81. SN06. Arun Shah and Robert F. Novy. Analytical server including metrics engine. United States Patent 7,031,953, April 2006.

82. SNE06. Arun Shah, Robert F. Novy, and Robert A. Ertl. Non-additive measures and metric calculation. United States Patent 7,072,897, July 2006.

83. SR04. Yannis Sismanis and Nick Roussopoulos. The polynomial complexity of fully materialized coalesced cubes. In VLDB, 2004.

84. SS94. Sunita Sarawagi and Michael Stonebreaker. Efficient organization of large multidimensional arrays. In Eleventh International Conference on Data Engeneering, 1994.

85. SS01. Sunita Sarawagi and Gayatri Sathe. Intelligent rollups in multidimensional olap data. In VLDB, 2001.

86. SV97. Timos Sellis and Panos Vassiliadis. A survey on logical models for olap databases. 1997.

87. Tho02. Erik Thomsen. OLAP Solutions: Building Multidimensional Information Systems Second Edition. Wiley Computer Publishing John Wiley & Sons, Inc., 2002.

88. TN01. Thomas R. Tortolani and Koorosh M. Nouri. Method and apparatus for accessing multidimensional data. United States Patent 6,317,750, November 2001.

89. VMB98. J. S. Vitter, Wang M., and B.Iyer. Data cube approximation and histograms via wavelets. In CIKM, 1998.

90. WFLY02. Wei Wang, Jianlin Feng, Hongjun Lu, and Jeffrey Xu Yu.

91. Condensed cube: An effective approach to reducing data cube size. In ICDe, 2002.

92. XSHL06. Dong Xin, Zheng Shao, Jiawei Han, and Hongyan Liu. C-cubing: Efficient computation of closed cubes by aggregation-based checking, icde, 0:4, 2006.

93. YJA03. Ge Yang, Ruoming Jin, and Gagan Agrawal. Implementing data cube construction using a cluster middleware: algorithms, implementation experience, and performance evaluation. Future Gener. Comput. Syst., 19(4):533-550, 2003.

94. ZDN97. Yihong Zhao, Prasad M. Deshpande, and Jeffrey F. Naughton.

95. An array-based algorithm for simultaneous multidimensional aggregates. In SIGMOD, pages 159-170, 1997.

96. Zha03. Yan Zhao. Quotient cube and qc-tree: Efficient summarizations for semantic olap, 2003.