Агрегация данных в OLAP-кубах

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

1. Введение

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

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

2. Основные понятия многомерной модели данных

Прежде, чем мы перейдем непосредственно к вопросам агрегации данных, напомним основные понятия многомерной модели данных, характерной для OLAP- систем. Дело в том что, на данный момент нет общепризнанной точки зрения на многомерную модель представления данных. Конечно, принципиальных различий в существующих взглядах нет, однако с точки зрения, например, терминологии некоторые разногласия имеются. Мы в данной статье будем ориентироваться на вариант, предлагаемый компанией «Microsoft».

Итак, основными понятиями многомерной модели данных являются:

• Показатель — это величина (обычно числового типа), которая собственно и является предметом анализа. Это, например, объём продаж некоторого товара, или выручка от продаж товара. Один OLAP-куб может обладать одним или несколькими показателями.
• Измерение (dimension) — это множество объектов одного или нескольких типов, организованных в виде иерархической структуры и обеспечивающих информационный контекст числового показателя. Измерение принято визуализировать в виде ребра многомерного куба.
• Объекты, совокупность которых и образует измерение, называются членами измерений (members). Члены измерений визуализируют как точки или участи, откладываемые на осях гиперкуба. Например, временное измерение: Дни, Месяцы, Кварталы, Годы — наиболее часто используемые в анализе, могут содержать следующие члены: 8 мая 2002 года, май 2002 года, 2-ой квартал 2002 года и 2002 год.
  Как уже было сказано, объекты в измерениях могут быть различного типа, например «производители» — «марки автомобиля» или «годы» — «кварталы». Эти объекты должны быть организованы в иерархическую структуру так, чтобы объекты одного типа принадлежали только одному уровню иерархии. Но об этом чуть позже.
• Ячейка (cell) — атомарная структура куба, соответствующая конкретному значению некоторого показателя. Ячейки при визуализации располагаются внутри куба и здесь же принято отображать соответствующее значение показателя.

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

 Рис. 1 Куб c тремя измерениями

Заметим, что, в отличие от измерений, не все значения показателей должны иметь и имеют реальные значения. Например, Менеджер Петров в 1994 г. мог еще не работать в фирме, и в этом случае все значения Показателя Объем продаж за этот год будут иметь неопределенные, «пустые» значения.

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

Существуют следующие типы иерархий:

• Сбалансированные (balanced) — иерархии, в которых число уровней определено её структурой и неизменно, и каждая ветвь иерархического дерева содержит объекты каждого из уровней. Каждому производителю автомобилей может соответствовать несколько марок автомобилей, а каждой марке — несколько моделей автомобилей, поэтому можно говорить о трёхуровневой иерархии этих объектов. В этом случае на первом уровне иерархии располагаются производители, на втором — марки, а на третьем — модели.
  Как нетрудно понять, что для формирования сбалансированной иерархии необходимо наличие связи «один-ко-многим» между объектами менее детального уровня по отношению к объектам более детального уровня. В принципе каждый уровень сбалансированной иерархии можно представить как отдельное простое измерение, но тогда эти измерения окажутся зависимыми, в значит неизбежно повышение разреженности куба.
• Несбалансированные (unbalanced) — иерархии, в которых число уровней может быть изменено, и каждая ветвь иерархического дерева может содержать объекты, принадлежащие не всем уровням, только нескольким первым. Необходимо заметить, что все объекты несбалансированной иерархии принадлежат одному типу. Типичный пример несбалансированной иерархии — иерархия типа «начальник-подчиненный», где все объекты имеют один и тот же тип — «Сотрудник».
• Неровные (balanced) — иерархии, в которых число уровней определено её структурой и постоянно, однако в отличие от сбалансированной иерархии некоторые ветви иерархического дерева могут не содержать объекты какого-либо уровня. Иерархии такого вида содержат такие члены, логические «родители» которых не находятся на непосредственно вышестоящем уровне. Типичным примером является географическая иерархия, в которой есть уровни «Страны», -Штаты — и «Города», но при этом в наборе данных имеются страны, не имеющие штатов или регионов между уровнями «Страны» и «Города».

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

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

3. Частичная и полная агрегация

Степень агрегации куба вычисляется как:

(1)

где a — реальное количество агрегированных значений показателей, a* — максимально возможное количество агрегатных значений исходных данных куба.

При выводе формул для a и a* сначала будем разбирать простые случаи с двумя-тремя измерениями, а затем перейдём к обобщённому варианту. То же самое касается и уровней иерархии в измерениях: сначала рассматриваются случаи простых измерений (с одним уровнем), а затем на примере измерений с несколькими уровнями выводится обобщённая формула. Такой подход позволяет легче понять процесс получения агрегатных значений показателей, поскольку читателю легче представить себе двух и трёхмерное пространство, сем пространства большей размерности.

3.1 Случай простых измерений

Для начала исследуем случай с тремя простыми измерениями. Для большей наглядности рассмотрим пример учёта объёма продаж автомобилей. Структура многомерного куба будет включать в себя следующие объекты:

• Один показатель: число проданных автомобилей,
• Три измерения:
  • менеджеры по продажам (ось oM),
  • модели автомобилей (ось oC),
  • временное измерение с единицей «месяц» (ось oT).

 Рис. 2 Трёхмерный OALP-куб с простыми измерениями; стрелки показывают направление агрегации.

Обозначим С, М, T — множества членов соответствующих измерений «модели автомобилей», «менеджеры», «месяцы». Обозначим также количество членов в каждом из измерений n_с = |С|, n_m = |М|, n_t = |T|. Члены этих измерений будем обозначать соответственно m_c, m_m, m_t.

Для получения агрегированных значений в разрезе менеджеров и месяцев мы должны просуммировать первоначальные значения показателей по всем моделям для каждой комбинации (m_t, m_m) менеджеров и месяцев. На рис.2 направление агрегирования обозначено стрелкой 1. Нетрудно понять, что количество агрегированных таким образом значений равно n_mn_t . Можно представить, что агрегированные таким образом значения показателей располагаются на плоскости (oM, oT)

Аналогично рассуждая, получим число агрегатов для всех комбинаций m_c, m_t) при суммировании показателей по всем членам измерения «менеджеры». Оно равно ncnt.

Количество агрегатов для всех комбинаций (m_c, m_m) при агрегации по временному измерению равно n_m n_c.

Теперь необходимо получить число агрегатов в разрезе членов одного из измерений. Очевидно, что количество таких агрегатов равно числу членом соответствующего измерения n_m, n_c и n_t.

Учитывая значение полного агрегата, определяющее в нашем случае суммарный объём продаж по всем моделям, менеджерам и всему временному периоду, получим суммарное количество всех агрегатов:

a* = n_mn_c + n_cn_t + n_mn_t + n_c + n_m + n_t + 1

Для дальнейших рассуждений введём новые обозначения. Допустим, имеем m измерений с n_i количество членов в i-ом измерении, где i = 1..m. Упорядочим некоторым образом существующие измерения и сопоставим каждому измерению порядковый номер i в соответствии с указанной сортировкой. Обозначим множество таких порядковых номеров I, так что m = | I |.

Обозначим некоторое множество агрегатов через A_l1-li-lm , где liЕ{0,1}: выделим также такое подмножество порядковых номеров I⁰= {i_k | i_kEI & li_k= 0 }, k = 1-p, p<= m. Тогда будем считать A_l1-li-lm — множество агрегатов, полученных агрегированием по всем членам тех измерений, порядковый номер которых iЕI⁰.

Тогда A_1-1, где индексы во всех позициях равны 1, является множеством исходных данных; A_0-0, где индексы во всех позициях равны 0, содержит единственное значение полного агрегата.

Упорядоченную последовательность l₁,?,l_i,?,l_m , соответствующую множеству агрегатов A_l1-li-lm, будем называть состоянием агрегации.

Введем понятие уровня детализации l = l₁+?+l_i+?+l_m. Очевидно, разные состояния агрегации, а, следовательно, и множества агрегатов могут соответствовать одному и тому же уровню детализации.

Обозначим количество агрегатов множества A_l1-li-lm, как a_l1-li-lm = |A_l1-li-lm|.

Для нашего трёхмерного случая с учётом того, что i(C)=1, i(M)=2, i(T)=3 —порядковые номера измерений, получим

a₀₁₁= n_mn_t a₁₀₁= n_cn_t a₁₁₀= n_cn_m a₀₀₁= n_t a₀₁₀= n_m a₁₀₀= n_c,

тогда a* = a₀₁₁+ a₁₀₁+ a₁₁₀ + a₀₀₁+ a₀₁₀ + a₁₀₀ + a₀₀₀.

Легко понять, что количество агрегатов, полученных агрегированием по некоторым измерениям, равно произведению числа членов всех остальных измерений, то есть

(2)

Очевидно, что количество всевозможных агрегатов равно сумме a_l1-li-lm при всевозможных вариантов последовательности l₁,?,l_i,?,l_m, исключая множество исходных данных . Нетрудно понять, что таких вариантов всего 2^m -1.

С другой стороны при агрегации исходных данных по всевозможным k измерениям, где k E {1,?,m}, мы получаем некоторую совокупность множеств агрегации с одним и тем же уровнем детализации, равным l = m — k. Обозначим эту совокупность A^l, с количеством агрегатов a^l. Для расчёта количества множеств агрегации A_l1-li-lm в A^m-k нам необходимо в индексе посчитать количество вариантов размещения k нулей по m позициям. Это случай сочетания k элементов по m, равный C^k_m. Таким образом,

, где |I₀| = k. Легко понять, что
, поэтому формула расчёта полного числа агрегатов с учётом (2) может быть представлена следующим образом

(3)

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

Гораздо более простую с точки зрения представления и вычисления формулу можно получить, используя свойство, вытекающее из (2):

A_{l1-li-1 1 li+1-lm} = n_i A_{l1-li-1 0 li+1-lm}

Тогда получим следующее

 

Исключая число исходных данных, получим

(4)

3.2 Случай иерархических измерений

Теперь рассмотрим случай, когда для i-го измерения существует l_i* уровней иерархии.

Обозначим n_ij — количество членов в j-ом уровне i-го измерения, так что n_{i j1?} n_{i j2} при j1 меньше j2; общее количество членов i-го измерения как n_i, так что  .

Упорядочивая измерения некоторым образом, получим последовательность измерений D₁,…,D_i,…,D_m , где i — порядковый номер измерения. Обозначим множество таких номеров I.

Определим последовательность чисел 1₁,?,l_i,?,l_m таких, что 1_i = 0…l_i*, как состояние агрегации. Тогда A_l1-li-lm — множество агрегатов, полученных агрегированием исходных данных до li-го уровня каждого из m измерений, a_l1-li-lm = |A_l1-li-lm|. Как и случае с простыми измерениями, обозначим подмножество порядковых номеров I⁰= { i_k | i_kО_I & l_ik= 0 }, k=1-p, p<= m.

Уровень иерархии с нулевым номером 1_i = 0 можно ассоциировать с абстрактным корневым уровнем, содержащим всегда единственный член (n_i0 =1), который, как правило, не имеет соответствия реальному объекту предметной области. В таком случае агрегацию по всем членам i-го измерения можно интерпретировать, как агрегацию до корневого уровня i-го измерения.

Как и в случае с простыми измерениями, назовем уровнем детализации, соответствующее множеству агрегатов A_l1-li-lm число l = l₁+?+l_i+?+l_m.

Рассмотрим двухмерный случай со следующей структурой:

• Показатели: число проданных автомобилей,
• Измерения:
  • временное измерение (ось oT): квартал — месяц — день,
  • функциональная единица (ось oU): салоны продаж — менеджеры.

Пусть количество членов временного измерения (T) превышает количество членов измерения функциональных единиц (U) Тогда

• T = D₁, U= D₂;
• l₁* = 3, l₂* = 2;
• общее число членов измерения T и U равно соответственно n₁ и n₂;
• количество кварталов, месяцев и дней во временном измерении равно соответственно n₁₁, n₁₂ и n₁₃;
• количество салонов и менеджеров равно соответственно n₁₁ и n₂₂;
• количество исходных данных равно n₁₃ n₂₂.

 Рис 3 Двухмерный случай с иерархическими измерениями

Нетрудно понять, что количество агрегатов:

• в разрезе месяцев и менеджеров a₂₂= n₁₂ n₂₂,
• в разрезе дней и салонов продаж a₃₁= n₁₃ n₂₁,
• в разрезе только дней a₃₀= n₁₃,
• в разрезе месяцев и салонов продаж a₂₁=n₁₂ n₂₁,
• в разрезе кварталов и менеджеров a₁₂= n₁₁ n₂₂,
• в разрезе только месяцев a₂₀= n₁₂,
• в разрезе кварталов и салонов продаж a₁₁= n₁₁ n₂₁,
• в разрезе только менеджеров a₀₂= n₂₂,
• в разрезе только салонов продаж a₀₁= n₂₁.
• в разрезе только кварталов a₁₀= n₁₁,
• полный агрегат a₀₀= 1.

Таким образом

a* = n₁₂ n₂₂ + n₁₃ n₂₁+ n₁₃+ n₁₂ n₂₁+ n₁₁ n₂₂+ n₁₂+ n₁₁ n₂₁+ n₂₂, + n₂₁ + n₁₁ + 1.

Из определения A_l1-li-lm следует, что

(5а),

что является общим случаем относительно формулы (2). Учитывая, что n_i0 = 1, получим более простую формулу

(5б)

Из (5б) получим соотношение между мощностями с различными уровнями детализации

n_i,l_i-k a_l1-li-lm = n_i,l_i al_1«li-k»lm (6) , где l_i = k-l_i*.

Общее количество всех агрегатов получается суммированием числа агрегатов множеств A_l1-li-lm, определяемых всевозможными состояниями агрегации. Число комбинаций l₁,?,l_i,?,l_m без учёта комбинации, соответствующей исходным данным, равно произведению (l₁*+1)? (l_i*+1)? (l_m*+1) — 1. Тогда с учётом (5б) получим количество всевозможных агрегатов:

&nbsp

где каждое слагаемое представляет уникальное произведение числа членов измерений.

Получим более удобную с точки зрения вычисления формулу количества всевозможных агрегатов. Для этого свойством

 

следующим из (6). Рассмотрим сумму всевозможных al1-li-lm.

 

 

Исключая множество исходных данных, и учитывая, что  , получим

 

Как нетрудно заметить, формула (8) представляет обобщённый вид формулы (4).

4. Оператор агрегирования

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

 

Из определения оператора агрегирования следует:

• Уровень детализации результирующего множества на единицу меньше уровня детализации исходного множества.
• Множество агрегатов, соответствующих корневому уровню i-го измерения, неизменно при воздействии оператора агрегации по i-му измерению.

 

• Множество агрегатов Al1-li-lm может быть получено из различных исходных множеств на единицу большего уровня детализации при воздействии оператора агрегирования по различным измерениям.

 

5. Вычислительные затраты на агрегирование

Под вычислительными затратами на выполнение агрегации некоторого множества значений показателей (агрегированных или исходных) до определенного результирующего множества агрегатов будем понимать количество элементарных операций суммирования, которые необходимо осуществить для получения результирующего множества. Будем обозначать затраты на выполнение агрегирования множества A_l1-li-lm по i-му измерению, как C(A(_i, A_l1-li-lm)) или более коротко
C(i, A_l1-li-lm).

Очевидно, что C(i, A_{l1-l(i-1),0, l(i+1)-lm}) = 0

Ещё раз обратимся к вышеописанному случаю с тремя простыми измерениями. Для формирования множества агрегатов A₀₁₁ для каждой комбинации менеджеров и месяцев необходимо просуммировать исходные значения показателей по направлению стрелки 1 (рис. 2) n_c-1 раз. Таким образом, с учётом того, что i(C) =1, i(M)=2, i(T) =3 — порядковые номера измерений, затраты на выполнение агрегирования A(1, A₁₁₁) = A₀₁₁ определяются как C(1, A₁₁₁) = (n_c — 1)n_mn_t.

Аналогично при формировании множеств агрегатов A₁₀₁ и A₁₁₀ на основании исходных значений показателей получим соответственно затраты

C(2, A₁₁₁) = n_c n_t (n_m — 1) и C(2, A₁₁₁) = n_c n_m (n_t ?1).

Получение множества A₀₀₁ согласно третьему заключению из определения оператора агрегации возможно двумя способами:

• A₀₀₁ = A(1, A_{1 01}) агрегирование множества A₁₀₁ по измерению моделей автомобилей (по стрелке 4);
• A₀₀₁ = A(2, A₀₁₁) агрегирование множества A₀₁₁ по измерению менеджеров (по стрелке 5);

Очевидно, что затраты на эти операции различны и равны соответственно

C(1, A₁₀₁) = (n_c-1)n_t, и C(2, A₀₁₁) = (n_m-1)n_t.

Эту неоднозначность при оценке затрат при формировании множества агрегатов мы обсудим ниже.

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

Утверждение 1 Пусть существует иерархия с l* уровнями, где n_l — количество членов на l-ом уровне и n_l<=n_l+1 l = 1-l*-1. Тогда количество элементарных операций суммирования значений показателя, соответствующих l+1-му уровню, с целью получения агрегированных значений показателя l-го уровня равно n_l+1 — n_l.

В нашем примере с двумя иерархическими (рис. 3) измерениями для получения агрегированных значений показателя по каждой комбинации менеджеров и месяцев (А₂₂) необходимо провести агрегацию множества исходных A₃₂ данных по временному измерению А₂₂ = A(1, A₃₂). Для этой операции необходимо для каждого менеджера просуммировать значения показателя по дням с целью получения показателя по месяцам (согласно утверждению) n₁₃ — n₁₂ раз. Таким образом,

C(1, A₃₂) = (n₁₃ — n₁₂)n₂₂ = n₁₃ n₂₂ — n₁₂ n₂₂ = a₃₂ — a₂₂.

Аналогично затраты на агрегацию значений показателя в разрезе менеджеров и кварталов по временному измерению с целью получения агрегатов только по менеджерам равны

C(1, A₁₂) = (n₁₁ — n₁₀) n₂₂ = (n₁₁ — 1) n₂₂ = n₁₁ n₂₂ — n₂₂ = a₁₂ = a₀₂,

Обобщая выше описанные примеры, заключим, что при суммировании множеств агрегатов по i-му измерению с li-го на li-1 уровень необходимо для каждой комбинации из членов текущих уровней всех остальных m-1 измерений провести n_i,li — n_i,li-1 элементарных операций суммирования. Таким образом, получаем

 

Используя (5а) и (6), преобразуем эту формулу в вид, который нам понадобится в дальнейших рассуждениях.

 

6. Процедуры формирования агрегатов

Множество агрегатов можно ассоциировать с вершинами сетевого графа. Начальной вершиной такого графа является множество исходных данных, конечной — значение полного агрегата (рис. 4)

 
Рис.4 Представление множества агрегатов в виде сетевого графа

В любое множество агрегатов A_l1-li-lm (l_i E {0,- l_i*-1}) можно непосредственно перейти из другого множества A_l1-li+1-lm, произведя операцию агрегирования по i-му измерению. При этом необходимо произвести соответствующие вычислительные затраты, откладываемые на рёбрах графа.

Можем также высказать следующее утверждение.

Утверждение 2 В любую вершину графа A_l1-li-lm можно попасть из другой вершины A_l1?-li?-lm, если хотя бы одно из неравенств l_i?=> l_i , i = 1-m выполняется строго.

6.1 Процедура предварительного формирования агрегатов

Теперь перейдём непосредственно к процедуре предварительного формирования агрегатных значений исходных данных куба известной структуры так, чтобы степень агрегации рассматриваемого куба достигла значения ?. Для этого согласно (1) необходимо сформировать a=aa* агрегатов. Ниже описаны основные моменты, характеризующие процедуру предварительного формирования агрегатов.

Принцип «от детального к общему». Очевидно, что процедуру формирования агрегированных значений показателей необходимо начинать с формирования агрегатов, соответствующих большей степени детализации. Будем считать, что формирование агрегатов l-го уровня детализации невозможно без получения всевозможных агрегатов l+1-го уровня детализации.

Принцип минимальных затрат. Как же было сказано ранее, расчёт множества агрегатов A_l1-li-lm может быть возможен нескольким способами:

A_l1-li-lm = {A(_{i, Al1«li-1»lm}) | i = 1-m & l_i= 0-l_i* — 1},

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

Распределение агрегатов между множествами одного уровня детализации. Рассмотрим совокупность множеств агрегации A^l, соответствующих уровню детализации l ( l=1-1*). Допустим, к настоящему моменту все множества большей степени детализации, чем l, сформированы и общее их количество равно a?. Обозначим множество всех агрегатов уровня l как a^l. В зависимости от заданной для текущего куба степени агрегации возможны следующие варианты дальнейшего поведения.

• Оцениваемое суммарное количество агрегатов, соответствующих уровню детализации большей или равной l, не превышает разрешённого количества агрегатов а, определяемого заданной степенью детализации, т.е. a?+ aⁱ <= a. В этом случае полностью формируются все множества агрегатов A_l1-li-lm, соответствующих уровню детализации l.
• Оцениваемое суммарное количество агрегатов, соответствующих уровню детализации большей или равной l, превышает разрешённое количество агрегатов а, определяемое заданной степенью детализации, т.е. a?+ a^l > a. Поскольку нет оснований для определения приоритетов и предпочтений среди множеств агрегатов l-го уровня, логично равноценно распределить остаточное количество агрегатов по этим множествам. Равноценность предполагает распределение остаточного количества агрегатов среди множеств l-го уровня детализации в прямой пропорции максимально возможному количеству их элементов a_l1-li-lm, так что реальное количество агрегатов множества A_l1-li-lm вычисляется как

 

Правило, по которому определяется, какие из агрегатов в каждом множестве A_l1-li-lm формируются, а какие нет, не регламентируется, так что формируемые агрегаты выбираются случайным образом.

Описанная процедура, возможно, и обеспечивает минимальные вычислительные затраты на её выполнение, но она далеко не оптимальна по отношению к множествам формируемых агрегатов. Для пояснения этого факта рассмотрим процедуру оперативного формирования агрегатов.

6.2 Процедура оперативного формирования агрегатов

Будем понимать под процедурой оперативного формирования агрегатов процедуру получения результирующего набора агрегатов при выполнении пользовательского запроса. При расчёте результирующего набора агрегатов будут использоваться подходящие предварительно сформированные агрегированные значения показателей. Если результирующий набор агрегатов предварительно сформирован, то затраты на оперативное формирование агрегатов равны 0.

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

Пусть в результате процедуры предварительно формирования агрегатов получили всевозможные множества минимального уровня детализации l. Пусть в результате необходимо сформировать множество агрегатов A_l?1,?,l-m уровня детализации l?, l?< l. Необходимо на основании одного из множеств A_l1,?,lm l-го уровня получить результирующее множество. При этом:

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

 
Рис.5. Предварительное и оперативное формирование агрегатов в сетевой модели

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

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

Итак, мы формально описали механизм агрегации данных OLAP-куба. В результате чего:

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

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

Автор: Хрусталёв Е.М.
Алеф Консалтинг & Софт