Cache ': техніка угрупування
Євген Каратаєв
В
цій статті розглянемо технічну частину угруповання даних. За базу
даних виберемо СУБД Cache ', оскільки в ній існує можливість самостійно
використовувати власні структури даних. Із загальних слів на тему
"навіщо" можна сказати, що типу такі завдання виникають при
складанні звітів, що це дуже важливо, не завжди зрозуміло, та інше. Всі
питання на тему "навіщо" надалі будемо опускати і займемося
питанням "як". А саме, як зробити так, щоб працювало, працювало
добре і щоб було зрозуміло, які можливості надає техніка
групування.
Операція
угруповання в базах SQL-типу оголошується опцією GROUP BY і часто
супроводжується опцією ORDER BY. Ті, хто мав справу з мовою SQL, напевно
приблизно уявляють, що це таке і до чого призводить. Ті ж, хто не
використовує мову SQL, мають з одного боку відсутність простого декларативного
оголошення своїх намірів, і, з іншого боку, набагато більшу гнучкість і
могутність, не обмежені нічим і ніякими реалізаціями та їх магічними
обмеженнями. Будемо слідувати другому варіанту - ручне програмування
операції угруповання, і розглянемо види групування та їх особливості, плюси і
мінуси.
Віддамо
належне методології і опишемо, в чому полягає операція групування.
Угрупування в загальних словах - це операція вибірки даних в такому вигляді, в
якому значення колонок розглядаються як критерій об'єднання строк
- Рядки з однаковими значеннями в групуються колонках об'єднуються в одну
рядок.
Покладемо,
що у нас є набір вихідних даних, на якому ми можемо провести
демонстрацію. Як приклад і в зв'язку з наближенням новим роком виберемо
умовну задачу "облік новорічних ялинкових іграшок". Покладемо, що в
нашому розпорядженні є кілька партій новорічних іграшок, які ми
розрізняємо по фігурі, за кольором і в кожній партії є певна кількість
однакових іграшок.
Створимо
тестові дані скриптом виду:
create (n)
s: '$ d (n)
n = 100
s: (n <1)
n =- n
k
^ group
n
i, color, colors, figure, figures, count
s
colors = "червоний золотий ~ ~ ~ синій зелений ~ срібний ~ жовтий"
s
figures = "кулька ~ шишка ~ сніжинка ~ білка ~ лебідь ~ рибка"
f
i = 1:1: n d
.
s color = $ p (colors ,"~",$ r (6) +1)
.
s figure = $ p (figures ,"~",$ r (6) +1)
.
s count = $ r (10) +1
.
s ^ group (i) = color_ "~" _figure_ "~" _count
q
Тут
i - це такий собі умовний номер партії. При групуванні по полях колір і фігура
частина рядків з їх однаковими значеннями об'єднуються в один рядок: якщо були
рядка
червоний
кулька 10
червоний
кулька 8
синій кулька
5
синій кульку 15
Те
при групуванні ми повинні отримати
червоний
кулька 10
8
синій кулька
5
15
Те
є з чотирьох вихідних отримали два вихідні, причому у вихідних рядках в
одне відділення потрапили від одного до декількох значень (кількість іграшок у
партії). Формально кажучи, ми можемо зробити з ними що хочемо, але оскільки мова
ведемо про угруповання, то в угрупованні прийнято з цих декількох значень,
що потрапляють в одну комірку, складати одне значення і приводити таким чином,
вихідні дані до класичного визначення таблиці з атомарними значеннями в
кожному осередку. Характер маніпулювання такими наборами з метою отримання
одного значення називається функцією групування. Найбільш часто зустрічаються
найпростіші - на зразок банального додавання в стовпчик або обчислення їх
кількості. У складніших випадках значення, що потрапили в одну клітинку, можуть
бути відсортовані за обраним критерієм, наприклад, за датою отримання партії,
з якої було взято це значення і в сукупності з датою одержання партії
може бути отримана наприклад середня швидкість надходження таких виробів. Взагалі
кажучи, ці функції групування становлять зовсім окремий найцікавіший
для прикладних фахівців клас задач, що знаходиться на стику задач класу OLAP
і Data Mining. У цій статті ми опустимо їх різноманітність і будемо користуватися
тільки найпростішої функцією - додавання в стовпчик, якої в SQL відповідає
функцій SUM. У наведеному вище прикладі запит на SQL виглядав би приблизно як
select color, figure, SUM (count)
from NewYearToys
group by color, figure
Зазвичай
спільно з угрупованням використовується операція сортування. Про неї ми скажемо
окремо пізніше. Сподіваюся, загальнотеоретичні відомості про угруповання, наведені
вище, повинні бути достатніми для її технічної реалізації.
Отже,
угруповання може бути класифікована за типом вибірки даних і по ширині
угруповання. За типом вибірки даних угруповання поділяється на угруповання з
орієнтацією на вибірку за допомогою функції $ ORDER і з орієнтацією на вибірку з
допомогою функції $ QUERY. По ширині угруповання поділ йде на нормальну і
широку.
Будемо
використовувати дані, згенеровані у вищенаведеному скрипті і розглянемо як
саме технічно виконати групування. Звернемо увагу на структуру
вихідних даних і зауважимо, що поєднання групуються полів для кожного рядка
утворює унікальне значення. Отже, в ієрархічних базах даних це
поєднання повинно стояти ліворуч від знаку рівності:
мінлива (групуються поле 1 ...
групуються поле 2 ...
групуються поле N) = набір
негруппірующіх полів
Тут
під таємничими символами і позначені відмінності типів угруповання - у разі
використання функції $ ORDER використовуємо конкатенацію значень групуються
полів, у разі використання функції $ QUERY використовуємо звичайні коми,
розглядаючи значення групуються полів як значення індексів
відповідного рівня.
Виконаємо
угруповання для функції $ QUERY:
GroupQ ()
;
group to use $ QUERY function
;
use SUM function
k
group
n
i, color, figure, count
s
i =""
f s i = $ o (^ group (i)) q: i = "" d
.
s color = $ p (^ group (i ),"~", 1)
.
s figure = $ p (^ group (i ),"~", 2)
.
s count = $ p (^ group (i ),"~", 3)
.
s group (color, figure) = count + $ G (group (color, figure), 0)
q
Тут
виконується прохід за вихідними даними, для наочності значення полів
зберігаються в окремих змінних, після чого виконується складання. Функція $ G
використовується для випадку, якщо це складання виконується перший раз. Замість складання
можемо використовувати будь-яку іншу функцію групування, але в нашому прикладі будемо
користуватися для простоти тільки одним складанням в стовпчик. Після того, як
дані згруповані у вигляді
group (color, figure) = SUM (count)
ми
можемо їх отримати одним проходом за допомогою функції $ QUERY:
WriteGroupedQ ()
d
QroupQ ()
n
color, figure, count, cf
s
cf = "group"
f s cf = $ Q (@ cf) q: cf = "" d
.
s color = $ qs (cf, 1)
.
s figure = $ qs (cf, 2)
.
s count = @ cf
.
w color,? 15, figure,? 30, count,!
q
Тут
значення полів виходять за допомогою функції $ QSUBSCRIPT. У разі використання
цього типу угруповання ми можемо використати кілька полів групування та
все одно зможемо отримати результат одним проходом. З метою створення
більш-менш формалізованої узагальненої функції ми можемо використовувати номери в
аргументах $ QS. Якщо їх отримувати з формальної специфікації запиту, то немає
необхідності організовувати вкладені цикли проходу за рівнями індексів.
Розглянемо
парний вищенаведеного метод групування, орієнтований на використання
функції $ ORDER:
GroupO ()
;
group to use $ ORDER function
;
use SUM function
k
group
n
i, color, figure, count
s
i =""
f s i = $ O (^ group (i)) q: i = "" d
.
s color = $ p (^ group (i ),"~", 1)
.
s figure = $ p (^ group (i ),"~", 2)
.
s count = $ p (^ group (i ),"~", 3)
.
s group (color_ $ C (10) _figure) =
count + $ G (group (color_ $ C (10) _figure), 0)
q
Тут
результат виходить у вигляді змінної з одним значенням індексу, в якому з
допомогою роздільників використовується символ $ C (10). Для отримання результату
угруповання можемо використовувати також тільки один прохід, але з використанням
функції $ ORDER:
WriteGroupedO ()
d
GroupO ()
n
color, figure, count, cf
s
cf =""
f s cf = $ O (group (cf)) q: cf = "" d
.
s color = $ P (cf, $ C (10), 1)
.
s figure = $ P (cf, $ C (10), 2)
.
s count = group (cf)
.
w color,? 15, figure,? 30, count,!
q
Тут
ми також можемо скласти узагальнену функцію угруповання, якщо отримаємо номери
полів з формального запиту та підставами їх у аргумент функції $ PIECE.
В
обох типах угруповання в правій частині може стояти не одне значення
негруппірующего поля, а декілька. Їх можна зберігати як у форматі з
роздільниками, так і в списочному вигляді. У наведеному прикладі використовувалося
тільки одне негруппірующее полі, тому в разі якщо їх декілька, код
слід відповідно підправити.
Відзначимо
плюси і мінуси обох методів групування. У першому випадку (орієнтація на
$ QUERY) результат видається в відсортованому вигляді, та порядок сортування
є індексним порядком. Яких-небудь додаткових пересортіровок вже не
потрібно. При цьому слід пам'ятати, що операція $ QS може зайняти більше
часу, ніж $ P у другому випадку. До того ж обов'язково слід скорегувати
код для випадку отримання в якості значення поля порожнього рядка. Наприклад,
завжди доповнювати рядок пробілом при групуванні і видалення цього пробілу при
видачу результату. У другому випадку, взагалі кажучи, отсортірованность
результату не гарантується і визначається вибраним символом - роздільником.
Якщо він менше пропуску, то результат буде відсортований. І, так само як у першій
випадку, слід доповнювати індексне значення певним символом на випадок отримання
угруповання тільки по одному полю і при можливості отримання в якості
значення поля порожнього рядка.
В
разі використання групіровкі, орієнтованої на функцію $ ORDER, результат,
звичайно, буде певним чином відсортований, але результат навряд чи буде
задовільним, оскільки буде застосовуватися індексний сортування до агрегату
полів, що є рядковий сортуванням. У разі використання нестрокових
(числових) значень полів слід приводити їх значення до рядків таким
чином, щоб сортування проводилася в правильному порядку, відповідному
типу даних. Наприклад, у випадку використання цілих чисел їх слід заміняти
приблизно як: число 123 замінюємо на рядок "00000123". Тобто
по-перше додаємо символ знака, по-друге доповнюємо нулями до деякої
обраної довжини. У разі використання дрібних чисел ситуація ускладнюється --
слід в рядок вносити символ знака числа, десятковий символ, дробову частина,
знак і величину порядку. Причому розташувати ці частини мають бути в порядку,
забезпечує саме строкову сортування. Після проведення угруповання з
такий сортуванням у функції візуалізації також слід провести відповідну
корекцію даних, щоб прибрати нагромадження доповнюють нулів.
Втім,
в ситуації з особливою трудомісткістю додатки полів з метою поєднання
угруповання з сортуванням ніщо не заважає виконати сортування у вигляді операції,
окремої від групування. Про це теж не слід забувати - сортування як
окрема операція може знадобитися в ситуації, коли слід виконати
сортування по негруппірующім полях.
Розглянемо
інший поділ угруповання - на нормальну і широку. Проблемою, яка породила
такий розподіл, є обмеженість довжини індексу. У нашому випадку це
важливо, оскільки в індексні значення пишуться значення полів. Яким би не
було магічне число цього обмеження, з метою ефективності реалізації СУБД
в кожній реалізації воно є. В окремих реалізаціях розмір індексу збігається
з величиною угруповання, в інших це дві різні величини, але в будь-якому разі
передбачаються обмеження на максимальну величину індексу і групуються
полів. Взагалі кажучи, в більшості випадків застосування нескладного і нескладної
аналізу двох вищенаведених способів групування цілком вистачає. Тому обидва
вони називаються нормальної угрупованням, оскільки в обох випадках ліворуч від
символу рівності стоять саме значення групуються полів.
Але
якщо все добре працює, то програмісти цим, як правило, не займаються, і
нас більше цікавить випадок, коли не працює. Або, у випадку з угрупованням,
стоїть питання - як провести групування в ситуації, коли величина
групуються полів не вмістилася в обмеження індексу.
В
цій ситуації допомагає умовна заміна значень полів на відповідні цим
значенням числові ідентифікатори. Скажімо, кольором червоний зіставляється число
1, кольором синій - 2 і так далі, після чого в групуванні беруть участь не
довгі поля типу назви організації, а короткі числа.
Ці
проміжні ідентифікатори значень повинні бути числами, для яких можна
задати, по-перше, взаємно однозначна відповідність між значенням і числом і,
по-друге, на наборі чисел має бути визначений порядок, відповідний
порядку значень полів. Виконуємо два проходи. У першому отримуємо список
значень групуються полів, що потрапили у вибірку, у другому проводимо власне
угруповання. При видачі результату використовуємо відображення числових значень на
значення полів. Зразковий код отримання списку значень:
WideGroup ()
k group, map
n i, color, figure, count
s i =""
f s i = $ O (^ group (i)) q: i = "" d
.
s color = $ p (^ group (i ),"~", 1)
.
s figure = $ p (^ group (i ),"~", 2)
.
; Save colors and figures into special lists
.
s map ( "color", color )=""
.
s map ( "figure", figure )=""
Після
цього в локальних змінних map містяться два списки з квітами та фігурами.
Відзначимо, що до повного проходу за результатами вибірки даних, що потрапили на
угрупування (у нашому випадку це O (^ group (i))) ми просто не можемо побудувати
сортованого списку числових ідентифікаторів значень, оскільки дані
приходять у свідомо несортоване вигляді.
Після
отримання списків значень групуються полів можемо побудувати відображення на
відповідні числові значення:
s color =""
f
s color = $ O (map ( "color", color))
q: color = "" d
.
; Map color to ordered number
.
s map ( "color", color) = $ I (map ( "color "))
.
; Map ordered number to color
.
s map ( "Ncolor", map ( "color", color)) = color
s
figure =""
f s figure = $ O (map ( "figure", figure))
q: figure = "" d
.
; Map figure to ordered number
.
s map ( "figure", figure) = $ I (map ( "figure "))
.
; Map ordered number to figure
.
s map ( "Nfigure", map ( "figure", figure)) = figure
Після
цього в локальних змінних map маємо відображення значень кольорів і фігур на
числа, причому числа завдяки використанню індексного сортування в
O (map ( "color", color)) і O (map ( "figure", figure)) впорядковані
в тому ж порядку. Після цього, використовуючи відображення значень на числа, можемо
провести широку угруповання:
n ncolor, nfigure
s
i =""
f s i = $ O (^ group (i)) q: i = "" d
.
s color = $ p (^ group (i ),"~", 1)
.
s figure = $ p (^ group (i ),"~", 2)
.
s ncolor = map ( "color", color)
.
s nfigure = map ( "figure", figure)
.
s count = $ p (^ group (i ),"~", 3)
.
s group (ncolor, nfigure) = count + $ G (group (ncolor, nfigure), 0)
q
Об'єднавши
зразки коду разом, отримаємо функцію, яка виконує широку угруповання.
Відзначимо, що ніякої оптимізації тут не доводилось, а отримання даних,
що потрапляють на групування, не всегла така проста операція, як просто
прохід по глобал. І, щоб не виконувати її двічі, має сенс у реальному коді
зберегти вибірку в тимчасовій глобал. І використовувати глобал для
групування і відображення групуються значень на числа. Оскільки даних
може виявитися настільки багато, що вони просто не помістяться в області даних
процесу.
При
виведення згрупованих даних випливає, звичайно ж, пам'ятати, що групували ми
не значення, а їх номери, тому використовуємо побудоване раніше відображення:
WriteWideGrouped ()
d
WideGroup ()
n
color, ncolor, figure, nfigure, count, cf
s
cf = "group"
f s cf = $ Q (@ cf) q: cf = "" d
.
s ncolor = $ qs (cf, 1)
.
s nfigure = $ qs (cf, 2)
.
s count = @ cf
.
s color = map ( "Ncolor", ncolor)
.
s figure = map ( "Nfigure", nfigure)
.
w color,? 15, figure,? 30, count,!
q
Складно
говорити про угруповання і не торкнутися угруповання з подитогамі. Наприклад,
отримання тієї ж угруповання, але в яку вставлені дані окремо за кольорами
безвідносно фігур іграшок, а також загальна величина. Нічого складного в цьому
немає. Звичайно ж, слід використати той же механізм групування, але для
кожного рядка писати підсумовування не тільки з рядком, ідентифікованої
групою полів, але й ідентифікованої спеціальним маркером подітога замість
що групуються поля. Наприклад, вибравши в якості маркера подітога символ $ C (11),
отримаємо групування з подитогамі по кольору:
; group to use $ QUERY function
;
use SUM function
k
group
n
i, color, figure, count
s
i =""
f s i = $ o (^ group (i)) q: i = "" d
.
s color = $ p (^ group (i ),"~", 1)
.
s figure = $ p (^ group (i ),"~", 2)
.
s count = $ p (^ group (i ),"~", 3)
.
s group (color, figure) = count + $ G (group (color, figure), 0)
.
s group (color, $ C (11)) = count + $ G (group (color, $ C (11)), 0)
q
Отримання
угруповання з подитогамі насправді не така проста операція. Не буду
приводити повністю код, що є правильним, зазначу лише, що слід
уважно поставитися до доповнень полів, щоб подитогі сортувалися
правильним чином. І при видачі результату в залежності від використаної
технології візуалізації давали розумне расположення подитогов.
Список літератури
Для
підготовки даної роботи були використані матеріали з сайту http://karataev.nm.ru/
