Анализ вычислительной сложности решения задач агрегирования данных в Olap-гиперкубах

Размещено на http://www.allbest.ru/

АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ РЕШЕНИЯ ЗАДАЧ АГРЕГИРОВАНИЯ ДАННЫХ В OLAP-ГИПЕРКУБАХ

А.Б. Афанасьев

А.А. Ахрем

А.В. Бодров (alexey.bodrov@yandex.ru)

Институт Системного Анализа РАН, Москва



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

сложность вычислительный гиперкуб



Введение

В настоящее время все большую популярность приобретают системы многомерного оперативного анализа данных (OLAP-системы). Несмотря на то, что теоретических исследований и практических работ по данной тематике накопилось достаточно много, все еще есть проблемы, требующие детальной проработки. Например, так называемый эффект «взрыва данных» [Потгитер, 2004], разреженность данных, проблемы с производительностью при анализе динамически меняющихся данных и прочие.

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

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

Для решения проблемы «взрыва данных» предлагается так называемый алгоритм формирования подкубов [Ho и др., 2008]. Суть его заключается в том, что оперативно формируются подкубы с агрегатами. При нехватке места на диске удаляются те подкубы, которые используются редко. Это заключение делается на основе оценки статистики обращения к подкубам. В результате работы этого алгоритма во внешней памяти постоянно находится массив подкубов, к которым происходит наиболее частое обращение, что дает прирост производительности системы.

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



1. Агрегация

1.1 Определение и математическое описание агрегации

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

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

Обозначим некоторое множество агрегатов через A_l1…li…lm, где l_i {0,1}: выделим также такое подмножество порядковых номеров

I₀ = {i_k | i_k I & l_ik = 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 по i-ой размерности будем понимать оператор, преобразующий множество агрегатов, которым в том числе может являться множество исходных данных, в другое множество агрегатов, уровень иерархии которого в i-ой размерности на единицу меньше по сравнению с исходным множеством, так что

A(i, A_l1…li…lm) = A_{l1…li*…lm},

где l_i* = max{0, l_i - 1}.

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

Утверждение 1.1. Уровень детализации результирующего множества на единицу меньше уровня детализации исходного множества.

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

A(i, A_{l1…l(i-1),0, l(i+1)…lm}) = A_{l1… l(i-1),0, l(i+1)…lm}.

Утверждение 1.3. Множество агрегатов A_l1…li…lm может быть получено из различных исходных множеств на единицу большего уровня детализации при воздействии оператора агрегирования по различным размерностям:

A_l1…li…lm = {A(i, A_{l1…li-1…lm}) | i =1…m & l_i=0…l_i*-1}.

1.2 Вычислительная сложность агрегации

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

Введем обозначение C(i, A_l1…li…lm) для вычислительной сложности агрегирования множества A_l1…li…lm по i-ой размерности.

Дальнейшие рассуждения будем вести для случая с тремя простыми размерностями. N, M, T - множества мер соответствующих размерностей, количество мер в каждой из размерностей n_n = |N|, n_m = |M|, n_t = |T|, меры этих размерностей будем обозначать соответственно m_n, m_m, m_t.

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

C(1, A₁₁₁) = (n_n-1)n_mn_t.

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

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

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

A₀₀₁ = A(1, A₁₀₁) агрегирование множества A₁₀₁ по размерности N;

A₀₀₁ = A(2, A₀₁₁) агрегирование множества A₀₁₁ по размерности M.

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

C(1, A₁₀₁) = (n_n1)n_t C(2, A₀₁₁) = (n_m1)n_t.

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

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

Предположим, что задан гиперкуб H_n многомерных данных, имеющий n>2 размерностей. Допустим, что для решения некоторой задачи (некоторого класса задач) на H_n используется подмножество K_n(m) гиперкуба H_n, образованное данными с m(m<n) размерностями с фиксированными значениями. Предположим дополнительно, что сложность решения задачи на H_n допускает следующие оценки:

M(n ,a)=n^a; (2.1)

A(m, n, a)<m^a; (2.2)

B(n-m, n, a)<(n-m)^a; (2.3)

где M - сложность решения исходной задачи на гиперкубе H_n;

A, B - сложности решения задачи на подмножествах K_n(m) и H_n\K_n(m) соответственно;

m(m<n) - фиксированное натуральное число;

a(a>1) - коэффициент сложности решения исходной задачи на гиперкубе H_n.

Справедливо следующее предложение.

Утверждение 2.1.

Величины A, B, M удовлетворяют неравенству

A + B < M. (2.4)

Для доказательства утверждения 2.1 нам потребуется следующая лемма.

Лемма 2.1.

Пусть даны числа x, y, удовлетворяющие неравенствам:

0<x<1, 0<y<1; x^a1+y^b1<1, a₁>0, b₁>0. (2.5)

Тогда для любых чисел c₁>a₁, d₁>b₁ выполнено соотношение:

x^c1+y^d1<1.

Доказательство леммы 2.1.

Для чисел x, y, c₁, d₁ имеют место неравенства:

x^c1 = x^c1-a1*x^a1<x^a1; (2.6)

y^d1 = y^d1-b1*y^b1<y^b1. 2.7)

Используя (2.5)-(2.7), окончательно получаем, что

x^c1+y^d1<x^a1+y^b1<1,

что и требовалось доказать.

Доказательство утверждения 2.1.

Принимая во внимание неравенства (2.1) - (2.3), находим, что

A+B<m^a+(n m)^a; (2.8)

M = n^a. (2.9)

Так как a>1, m/n+(1-m/n)=1, то, применяя результат леммы 2.1 при a₁=b₁=1, c₁=d₁=a, будем иметь

n^a*[(m/n)^a+(1 m/n)^a]<n^a=M. (2.10)

Из цепочки неравенств (2.10) окончательно заключаем, что A+B<M, что и требовалось установить.

Утверждение 2.1 полностью доказано.

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

При m=1 из неравенства (2.4) утверждения 2.1 заключаем, что

A+B<1+(n1)^a<n^a=M. (2.11)

Из неравенства (2.11) находим, что при m=1 (т.е., когда фиксируется лишь одна размерность гиперкуба данных H_n) справедливы соотношения:

(A+B)*M^-1<n^-a*(1+(n1)^a)=n^-a+(11/n)^a. (2.12)

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

Допустим теперь, что сложности A, B, M удовлетворяют оценкам:

A(m, n, a) = A(p, n, a) =p^a*n^a; (2.13)

B(n-m, n,a)=B((1-p),n,a)=(1-p)a*n^a; (2.14)

M(n,a)=n^a, (2.15)

где m=pn, p=const, 0<p<1, a=const, a>1.

Для сложностей A, B, M в данном случае справедливо следующее утверждение.

Утверждение 2.2.

Сложности A, B, M при любых значения p, 0<p<1, удовлетворяют неравенству

M*2^1-a<A+B. (2.16)

Доказательство.

Используя (2.13) - ( 2.15), находим, что

A+B=[p^a+(1p)^a]*n^a=s(p)*M, (2.17)

где s(p) ? p^a+(1 p)a.

Для функции s(p) справедливо следующее соотношение

s(p)>2^1-a (2.18)

для любых p, 0<p<1; a>1.

Для доказательства (2.18) найдем сначала точку минимума p_min функции (2.18). Точка p_min должна удовлетворять следующей системе неравенства [Зорич, 1981]:

ds/dр(p^min)=a[p_min^a-¹ (1 p_min)^a-1]=0; (2.19)

d²s/dр²(p_min)=a(a1)[p_min^a-2+(1 p_min)^a-2]>0.

Нетрудно показать, что система алгебраических неравенств (2.19) имеет единственное решение p_min:

p_min = 1/2 (2.20)

Используя (2.17), (2.20), находим, что

s(p_min) = s(1/2) = 2^-a+2^-a = 2^1-a. (2.21)

Принимая во внимание (2.17), (2.21), окончательно получаем, что

A+B = n^a*s(p) > n^a*s(p_min) = 2^1-a*n^a = 2^1-a*M,

что и требовалось доказать.

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

Рассмотрим наконец случай, когда сложности A, B, M удовлетворяют соотношениям:

A=A(m,n,b)=m^b;

B=B(n-m,n,c)<(n-m)^c;

M=M(n,c)=n^c,

где m=l*n, 0<l<1, b=const, c=const, c>b.

Этот случай описывает ситуацию, при которой размерности гиперкуба Hn отличаются по сложности.

В данной ситуации при больших значениях натурального параметра n будем иметь:

A+B=m^b+(n-m)^c=[(m/n)^b*n^b-c+(1-m/n)^c]*n^c=[l^b*n^b-c+(1-l)^c]*n^c=(1l)^c*M. (2.22)

Из цепочки соотношений (2.22) заключаем, что:

а) сложность решения декомпозированного варианта задачи на гиперкубе многомерных данных H_n уменьшается по сравнению со сложностью традиционного переборного метода ее решения в (1-l)-^c раз;

б) коэффициент уменьшения сложности k=(1-l)^c является монотонно убывающей функцией своих аргументов l,c:

K(l',c') > k(l'',c'') при l''>l', c''>c', (0<l<1).

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



3. Пример оценки коэффициентов сложности

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

Ниже приведены результаты оценки коэффициентов относительной сложности на примере гиперкубовой структуры для многомерного анализа учетных данных по продажам иномарок в России за период с 2001 по 2009 годы. Подсчет коэффициентов относительной сложности проводится по всем возможным слоям каждой размерности гиперкуба (рис 1.). В качестве размерностей по осям куба отложены: Страна, Компания, иерархия Класс-Модель, а метрики или анализируемые показатели числа продаж расположены в ячейках куба. Общее число ячеек куба составляет 3499.

Рис. 1. Гиперкуб и подкуб

На рисунке 2 представлены все подкубы для размерности Класс. Для каждого значения размерности найдено число сканированных ячеек, которое изменяется для данной размерности в диапазоне от 147 до 783. Коэффициенты относительной сложности определяются отношениями этих чисел к общему числу ячеек куба.

Рис. 2. Число записей по членам размерности Класс

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

Табл. 1. Коэффициенты относительной сложности

Наименование размерности	Число членов размерности	Диапазон значений детального уровня	Диапазон коэффициентов относительной сложности
Страна	15	4 - 789	0,0011 - 0,2254
Класс	11	147 - 783	0,042 - 0,2237
Компания	90	1 - 147	0,00028 - 0,042
Факты	3499	-	-



Заключение

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

Благодарности. Работа выполнена при финансовой поддержке РФФИ (проект № 10-01-00674).



Список литературы

[Ho и др., 2008] Ho Kuo-Wei and Chen Huei-Huang. OLAP Query Processing via Subcubes. - Feng Chia University, 2008.

[Зорич, 1981] Зорич В.А. Математический анализ. - М.: Наука, 1981.

[Потгитер 2004] Потгитер Йохан. Масштабируемость OLAP-данных. http://citcity.ru/11158/

[Хрусталев, 2002] Хрусталёв Е.М. Агрегация данных в OLAP-кубах. http://www.olap.ru/home/mut.asp

Размещено на Allbest.ru

...