Загальні стратегії обчислення кубів

Поза залежністю від методу зберігання (ROLAP, MOLAP), існує набір прийомів, що дозволяють зменшити час створення й обробки запитів до OLAP-Кубів.

1. Сортування, хешування, угруповання

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

2. Одночасне агрегування й хешування проміжних результатів

Ефективніше створювати підкуби високих рівнів з підкубів низьких рівнів, ніж з базової таблиці. Більш того, одночасне обчислення агрегатів може дозволити скоротити дорогі операції звертання до жорстких дисків.

Приміром, для розрахунку продажів по регіонах можна використовувати проміжні результати, отримані при розрахунку підкуба більш низького рівня продажів по регіонах, по днях.

3. Агрегування від найменшого підкуба-нащадка при наявність багатьох підкубів-нащадків

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

4. При створенні кубів типу айсберг можна використовувати наступне правило: «Якщо вказана комірка не задовольняє умові, що накладається на мінімальне значення міри, то жоден з її нащадків не задовольняє умові». Така умова може бути використана для скорочення об'єму оброблюваних даних. Однак дана умова вірна тільки для дистрибутивних агрегуючих функцій.

Параметри складаються із двох компонентів:

· чисельна характеристика факту, наприклад, ціна або дохід від продажів;

· формула, звичайно проста агрегативна функція, наприклад, сума MIN, MAX, AVG, COUNT, що може поєднувати кілька значень параметрів в одне. Але в деяких випадках можуть використовуватися й більш складні функції – дисперсії, середньоквадратичне відхилення й т.д.).

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

· Адитивні параметри можуть змістовним образом комбінуватися в будь-якому вимірі. Наприклад, має сенс підсумувати загальний обсяг продажів для продукту, місця розташування й часу, оскільки це не викликає накладення серед явищ реального світу, які генерують кожне із цих значень.

· Напівадитивні параметри, які не можуть комбінуватися в одному або декількох вимірах. Наприклад, підсумовування запасів по різних товарах і складам має сенс, але підсумовування запасів товарів у різний час безглуздо, оскільки той самий фізичний предмет може враховуватися кілька разів.

· Неадитивні параметри не комбінуються в будь-якому вимірі, звичайно тому, що обрана формула не дозволяє об'єднати середні значення низького рівня в середнім значенні більш високого рівня.

Адитивні й неадитивні параметри можуть описувати факти будь-якого роду, у той час як напівадитивні параметри, як правило, використовуються з миттєвими знімками.

Питання для самоперевірки

1. Як розраховується розмірність куба з агрегованими значеннями?

2. Які види агрегуючих функцій ви знаєте?

3. Перелічите види запитів до багатомірних кубів. Поясніть розходження між ними.

4. Що розуміється під «вибухом» даних?

5. Що втримується у вузлах графа, який представляє куб?

6. Поясніть зміст різних способів прискорення обробки даних багатомірного куба.

7. Які параметри називаються неадитивними?

8. У чому відмінність між неадитивними й напівадитивними параметрами?

Методичні вказівки до лекції:[3, с. 458–461].

Вправи

1. Задайте таблицю фактів, що містить у якості міри екзаменаційні оцінки студентів, із чотирма вимірами.

2. Оціните кількість значень у кожному вимірі із вправи 1. Розрахуйте розмір багатомірного куба з агрегованими значеннями для представлення фактичних даних.

3. Побудуйте граф для куба із вправи 3.

ЛЕКЦІЯ №8
Агреговані ЗНАЧЕННЯ ДЛЯ РІЗНИХ ВИДІВ ВИМІРІВ

Розглядаються наступні питання:

· поняття ступеня агрегації;

· розрахунок кількості агрегованих значень для простих вимірів;

· розрахунок кількості агрегованих значень для ієрархічних вимірів;

· обчислювальні витрати на агрегування;

· процедура попереднього формування агрегатів;

· процедура оперативного формування агрегатів.

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

Ступінь агрегації куба обчислюється як:

 ,                                                   (1)

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

При виводі формул для a і a* спочатку розберемо прості випадки із двома-трьома вимірами, а потім перейдемо до узагальненого варіанта. Те ж саме стосується й рівнів ієрархії у вимірах: спочатку розглянемо випадки простих вимірів (з одним рівнем), а потім на прикладі вимірів з декількома рівнями виведемо узагальнену формулу.

Прості виміри

Нехай є 3 прості виміри для обліку обсягу продажів деяких товарів. Структура багатомірного куба буде містити в собі наступні об'єкти (рис.11):

· Один показник: число проданих одиниць товару,

· Три виміри:

- менеджери по продажах (вісь oM),

- види товарів (вісь oC),

- часовий вимір з одиницею «місяць» (вісь oT).

Рис. 11. Тривимірний OALP-Куб із простими вимірами; стрілки показують напрямок агрегації.

Нехай Р, М, T – множини членів відповідних вимірів «види товарів», «менеджери», «місяці». Нехай кількість членів у кожному з вимірів n_Р = |Р|, n_m = |М|, n_t = |T|. Члени цих вимірів позначаються відповідно m_р, m_m, m_t.

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

Аналогічно міркуючи, одержимо число агрегатів для всіх комбінацій (m_р, m_t) при підсумовуванні показників по всіх членах виміру “менеджери”. Воно дорівнює n_рn_t.

Кількість агрегатів для всіх комбінацій (m_р, m_m) при агрегації по часовому вимірі дорівнює n_m n_р.

Тепер необхідно одержати число агрегатів у розрізі членів одного з вимірів. Очевидно, що кількість таких агрегатів дорівнює числу членів відповідного виміру n_m, n_рі n_t (стрілки 4, 5 і 6 відповідно).

З огляду на значення повного агрегату, що визначає в нашім випадку сумарний обсяг продажів по всіх видах товарів, менеджерам і всьому часовому періоду, сумарна кількість всіх агрегатів дорівнює:

a* = n_mn_р + n_рn_t + n_mn_t + n_р + n_m + n_t + 1

Нехай є m вимірів. Кожному виміру відповідає порядковий номер i,i = 1..m. Кожний вимір містить n_i членів.

Нехай – деяка множина агрегатів, де l_i=0, якщо по i-му вимірі виконується агрегування, інакше l_i=1.

Тоді A_1...1…1,де індекси у всіх позиціях рівні 1, є множиною  вхідних даних; A_0...0…0,де індекси у всіх позиціях рівні 0, містить єдине значення повного агрегату.

Упорядкована послідовність l₁,…,l_i,…,l_m,відповіднамножині агрегатів A_l1…li…lm,називається станом агрегації.

Рівнем деталізації називається число l = l₁+…+l_i+…+l_m... Очевидно, різні стани агрегації, а, отже, і множини агрегатів можуть відповідати тому самому рівню деталізації.

Нехай – це кількість агрегатів множини .

Для тривимірного випадку з урахуванням того, що i(Р)=1, i(M)=2, i(T)=3 – порядкові номери вимірів, одержимо

a₀₁₁= n_mn_t ; a₁₀₁= n_рn_t; a₁₁₀= n_рn_m; a₀₀₁= n_t; a₀₁₀= n_m; a₁₀₀= n_c

Тоді

a* = a₀₁₁+ a₁₀₁+ a₁₁₀ + a₀₀₁+ a₀₁₀ + a₁₀₀ + a₀₀₀.

Кількість агрегатів, отриманих агрегуванням по деяких вимірах, дорівнює добутку числа членів всіх інших вимірів, тобто

                                                    (2)

Кількість усіляких агрегатів дорівнює сумі при всіляких варіантах послідовності l₁,…,l_i,…,l_m,крім множини вхідних даних. Таких варіантів усього 2^m -1.

Формула розрахунку повного числа агрегатів з урахуванням (2) виглядає в такий спосіб

                                                 (3)

де  – кількість варіантів розміщення k нулів по m позиціях, тобто сполучення k елементів по m, – сума всіляких неповторюваних добутків кількості членів вимірів.

Більш просту формулу можна одержати, використовуючи властивість, що випливає з (2):

Тоді

Крім числа вхідних даних, одержимо

                                             (4)

Ієрархічні виміри

Нехай для i-го виміру існує l_i* рівнів ієрархії.

n_i,j – кількість членів в j-ом рівні i-го виміру, так що  при j₁<j₂; n_i – загальна кількість членів i-го виміру:

.

Зіставимо кожному виміру порядковий номер i.

– множина агрегатів, отриманих агрегуванням вхідних даних до l_i-го рівня кожного з m вимірів, l_i = 0...l_i*.

Послідовність чисел l₁,…,l_i,…,l_mназивається станом агрегації.

Рівень ієрархії з нульовим номером l_i = 0 можна асоціювати з абстрактним кореневим рівнем, що містить завжди єдиний член (n_i0 =1), який, як правило, не має відповідності реальному об'єкту предметної області. У такому випадку агрегацію по всіх членах i-го виміру можна інтерпретувати, як агрегацію до кореневого рівня i-го виміру.

Як і у випадку із простими вимірами, рівнем деталізації називається число l = l₁+…+l_i+…+l_m,відповіднемножині агрегатів .

Розглянемо двомірний випадок з наступною структурою (рис.12):

· Показники: число проданих одиниць товару,

· Виміри:

- вимір, що відповідає часу продажу (вісь oT): квартал - місяць - день,

- вимір, що відповідає місцю й продавцеві (вісь oU): салони продажів - менеджери.

Рис. 12. Двомірний випадок з ієрархічними вимірами

Нехай кількість членів часового виміру (T) перевищує кількість членів виміру місця (U). Тоді

- l₁* = 3, l₂* = 2;

- загальне число членів виміру T і U дорівнює відповідно n₁ і n₂;

- кількість кварталів, місяців і днів у часовому вимірі дорівнює відповідно n_1,1, n_1,2 і n_1,3;

- кількість салонів і менеджерів дорівнює відповідно n_1,1 і n_2,2;

- кількість вхідних даних дорівнює n_1,3 і n_2,2.

Відповідна кількість агрегатів дорівнює:

- у розрізі місяців і менеджерів a₂₂= n_1,2n_2,2,

- у розрізі днів і салонів продажів a₃₁= n_1,3n_2,1,

- у розрізі тільки днів a₃₀= n_1,3,

- у розрізі місяців і салонів продажів a₂₁=n_1,2n_2,1,

- у розрізі кварталів і менеджерів a₁₂= n_1,1n_2,2,

- у розрізі тільки місяців a₂₀= n_1,2,

- у розрізі кварталів і салонів продажів a₁₁= n_1,1n_2,1,

- у розрізі тільки менеджерів a₀₂= n_2,2,

- у розрізі тільки салонів продажів a₀₁= n_2,1.

- у розрізі тільки кварталів a₁₀= n_1,1,

- повний агрегат a₀₀= 1.

У такий спосіб

a* =a₃₁+a₃₀+a₂₂+a₂₁+a₂₀+a₁₂+a₁₂+a₁₀+a₀₂+a₀₁+a₀₀=

=n_1,2n_2,2 + n_1,3n_2,1+ n_1,3+ n_1,2n_2,1+ n_1,1n_2,2+ n_1,2+ n_1,1n_2,1+ n_2,2, + n_2,1 + n_1,1 + 1.

(перший індекс - вимір, другий індекс - рівень)

З визначення слідує, що

                                      (5а),

що є загальним випадком щодо формули (2). З огляду на те, що n_i,0 = 1, одержимо більш просту формулу

                                         (5б)

З (5б) виходить співвідношення між потужностями з різними рівнями деталізації

,                         (6)

де l_i = k…l_i*...

Загальна кількість всіх агрегатів виходить підсумовуванням числа агрегатів множин , обумовлених усілякими станами агрегації. Число комбінацій l₁,…,l_i,…,l_mбез урахування комбінації, що відповідає вхідним даним, дорівнює добутку (l₁*+1)…(l_i*+1)…(l_m*+1)–1... Тоді з урахуванням (5б) кількість усіляких агрегатів дорівнює:

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

Більш зручна з погляду обчислення формула кількості всіляких агрегатів може бути отримана із властивості

,

яка слідує з (6).

Сума всіляких дорівнює:

Крім множини вхідних даних, і з огляду на те, що  , одержимо

                                      (7)

Формула (7) представляє узагальнений вид формули (4).