=Paper=
{{Paper
|id=Vol-1843/166-173
|storemode=property
|title=Формальна семантика агрегатних операцій мультимножинної табличної алгебри
(A formal semantics of aggregate operations of multiset table algebra)
|pdfUrl=https://ceur-ws.org/Vol-1843/166-173.pdf
|volume=Vol-1843
|authors=Irina Glushko
|dblpUrl=https://dblp.org/rec/conf/ukrprog/Glushko14
}}
==Формальна семантика агрегатних операцій мультимножинної табличної алгебри
(A formal semantics of aggregate operations of multiset table algebra)==
https://ceur-ws.org/Vol-1843/166-173.pdf
Proceedings of the 8th International Conference of Programming UkrPROG’2014 (Kyiv, Ukraine)
УДК 004.655
ФОРМАЛЬНА СЕМАНТИКА АГРЕГАТНИХ ОПЕРАЦІЙ
МУЛЬТИМНОЖИННОЇ ТАБЛИЧНОЇ АЛГЕБРИ
І.М. Глушко
Ніжинський державний університет імені Миколи Гоголя,
16600, Ніжин, вул. Кропив’янського 2,
glushkoim@gmail.com
Розглянуто мультимножинну табличну алгебру. Сигнатура мультимножинної табличної алгебри поповнена агрегатними операція-
ми. Задано формальну математичну семантику цих операцій та наведено приклади їх застосування.
Мultiset table algebra is considered. The signature of multiset table algebra is filled up with aggregate operations. A formal mathematical
semantics of these operations is defined.
Вступ
Реляційна модель даних на сьогодні широко використовується як у наукових дослідженнях в базах да-
них, так і на практиці. У формальному визначенні, запропонованому Е. Коддом [1], дана модель базується на
множинах кортежів, тобто не дозволяє дублікати кортежів у відношенні. Багато мов, орієнтованих на роботу з
базами даних, вимагають реляційну модель даних з мультимножинною семантикою (multi-set semantics) тому,
що, по-перше, відношення, які дозволяють дублікати, корисні в багатьох прикладних областях, де об'єкти-
дублікати можуть існувати; по-друге, в реляційній моделі даних видалення дублікатів після виконання операцій
проекції та об’єднання передбачає злиття однакових елементів або здійснення інших трудомістких дій.
Питанню використання мультимножин в базах даних приділяли увагу Paul W.P.J. Grefen та Rolf A. de By
[2], G. Lamperti, M. Melchiori, M. Zanella [3], Г. Гарсіа-Моліна, Дж. Ульман, Дж. Уидом [4], A. Silbeschatz,
H. Korth, S. Sudarshan [5], Д.Б. Буй, С.А. Поляков, Ю.Й. Брона, В.Н. Редько [6]. Разом з тим, в жодній із зазна-
чених робіт не приділяється увага агрегатним операціям над таблицями мультимножинної табличної алгебри.
Мультимножини: основні поняття
Наведемо основні поняття мультимножин в термінах роботи [6]. Зафіксуємо деяку множину U . Під му-
льтимножиною з основою U будемо розуміти відображення вигляду : U N , де N {1,2,...} – множина
натуральних чисел.
Нехай D – універсум елементів основ мультимножин, тоді булеан P(D) – універсум основ мультимно-
жин. Під характеристичною функцією мультимножини розуміємо функцію вигляду : D Z , значення
якої задається наступною кусковою схемою:
(d ), якщо d dom ,
(d )
0, інакше;
для всіх d D , де Z – множина цілих невід’ємних чисел..
Мультимножина називається порожньою і позначається як m , якщо її основа – порожня множина.
Мультимножини, областю значень яких є порожня множина або одноелементна множина вигляду {1},
називаються 1-мультимножинами. Дані мультимножини є аналогами звичайних множин.
Домовимося мультимножину з основою {d1 ,..., d k } записувати як {d1n1 ,..., d knk } , де ni – кількість дуб-
лікатів (екземплярів) елемента d i у мультимножині , i 1,..., k .
Під рангом скінченної мультимножини розуміємо суму дублікатів елементів її основи
dU
(d ) , де U – основа мультимножини . Зрозуміло, що m 0 .
Мультимножина включається у мультимножину ( ), якщо:
U U & d d U d d .
Якщо , то мультимножина називається підмультимножиною мультимножини , а мультимно-
жина – надмультимножиною мультимножини . Очевидно, що порожня мультимножина є підмультимно-
жиною будь-якої мультимножини ( m , ), а будь-яка мультимножина є своєю ж підмультимножиною
( , ).
166
Proceedings of the 8th International Conference of Programming UkrPROG’2014 (Kyiv, Ukraine)
Мультимножинна таблична алгебра
Розглянемо дві множини: A – множину атрибутів і D – універсальний домен. Довільну скінченну мно-
жину атрибутів R A назвемо схемою.
Рядком схеми R називається іменна множина на парі R , D , проекція якої за першою компонентою рі-
вна R (тобто по суті розглядається функція вигляду s : R D ). Множину всіх рядків схеми R позначимо
S (R) , а множину всіх рядків – S . Для позначення відсутніх значень у таблиці використовується особливий
елемент універсального домену NULL . Позначимо s RNULL – константний рядок схеми R , тобто
s RNULL : R {NULL} .
Задамо поняття таблиці як пари , R , де перша компонента – це довільна мультимножина, зокрема,
нескінченна, а друга компонента R – схема таблиці.
Таким чином, кожній таблиці приписується певна схема. Множину всіх таблиць схеми R позначимо
(R) , а множину всіх таблиць ( R) .
RA
Позначимо Occ( s, ) – кількість дублікатів (екземплярів) рядка s у мультимножині . Домовимося му-
n n
льтимножину записувати як {s1 1 ,..., s k k ,} , де ni Occ( si , ) , i 1,2, , а ( ) {s1 ,..., s k ,} – основа
мультимножин .
Під мультимножинною табличною алгеброю розуміємо алгебру , P , , де – множина всіх таб-
pP ,
лиць, P , All, R , All, R , \ All, R , p , R , X , R , , Rt , R , ~ R – сигнатура, P , – множини параметрів.
R ,
1 2R X , R , R1 , R2 A
Задамо операції. Під об’єднанням RAll (перетином RAll , різницею \ RAll ) таблиць схеми R розуміється
бінарна (параметрична) операція, отримана обмеженням однойменних операцій All , All , \ All над мульти-
множинами на множину всіх таблиць схеми R .
Розглянемо кожну операцію окремо. Позначимо через ( 1 ) і ( 2 ) – основи мультимножин 1 та 2
відповідно. Таким чином,
RAll : ( R ) ( R ) ( R ) , 1 , R RAll 2 , R 1 All 2 , R .
Основа мультимножини 1 All 2 дорівнює об’єднанню основ мультимножин таблиць-аргументів:
( 1 All 2 ) ( 1 ) ( 2 ) .
Дублікати рядків, які з’явилися після виконання операції, не вилучаються. Кількість дублікатів кожного
рядка визначається за формулою:
Occ( s, 1 ), якщо s ( 1 ) \ ( 2 ),
Occ( s, 1 All 2 ) Occ( s, 2 ), якщо s ( 2 ) \ ( 1 ),
Occ( s, ) Occ( s, ), якщо s ( ) ( );
1 2 1 2
де s ( 1 ) ( 2 ) .
RAll : ( R ) ( R ) ( R ) , причому 1 , R RAll 2 , R 1 All 2 , R .
Основа мультимножини 1 All 2 дорівнює перетину основ мультимножин таблиць-аргментів:
( 1 All 2 ) ( 1 ) ( 2 ) ,
а кількість дублікатів рядка визначається як
Occ( s, 1 All 2 ) min Occ( s, 1 ), Occ( s, 2 ) , де s ( 1 ) ( 2 ) .
\ RAll : ( R ) ( R ) ( R ) , причому 1 , R \ RAll 2 , R 1 \ All 2 , R , де 1 , R , 2 , R ( R ).
Основа мультимножини 1 \ All 2 визначається як ( 1 \ All 2 ) ( 1 ) \ ( 2 ) C ( 1 , 2 ) , де
C ( 1 , 2 ) s | s ( 1 ) ( 2 ) Occ ( s, 1 ) Occ ( s, 2 ) .
Кількість дублікатів знаходиться так:
Occ( s, 1 ), якщо s ( 1 ) \ ( 2 ),
Occ( s, 1 \ All 2 )
Occ( s, 1 ) Occ( s, 2 ), якщо s C ( 1 , 2 ),
167
Proceedings of the 8th International Conference of Programming UkrPROG’2014 (Kyiv, Ukraine)
де s ( 1 ) \ ( 2 ) C ( 1 , 2 ) .
Нехай p : S ~ {true, false} – частковий предикат на множині рядків. Під селекцією за предикатом p
таблиць схеми R розуміється унарна часткова параметрична операція p, R , яка таблиці зіставляє її підтабли-
цю, що містить рядки, на яких предикат p істинний (крім того, предикат p має бути визначеним на всіх ряд-
ках таблиці-аргументу).
Отже,
p , R , R | ( ) dom p , p , R , R ' , R ,
~ ( R) , dom
p , R : ( R)
де , R ( R ) .
Областю означеності операції селекції є таблиці , R ( R ) , які містять рядки s S (R) , на яких пре-
дикат-параметр селекції p визначений. Надалі розглядаємо тільки предикати-параметри вигляду
p( s ) true p( s ( A1 ),..., s ( Am )) true , де p – предикат на універсальному домені, а атрибути A1 ,..., Am нале-
жать схемі рядка s .
Основа мультимножини результуючої таблиці визначається як: ( ) {s | s ( ) p ( s ) ~ true} , де ~
–
узагальнена рівність (тобто обидві частини або одночасно не визначені або одночасно визначені і рівні).
В залежності від значення предиката на рядку s усі дублікати цього рядка або входять до мультимножи-
ни отриманої таблиці, або ні: Occ( s, ) Occ( s, ), де s ( ' ) . Зазначимо, що операція селекції не породжує
нові дублікати рядка.
Нехай X A – скінченна множина атрибутів. Під проекцією за множиною атрибутів X таблиць схеми
R розуміється унарна параметрична операція X , R , значеннями якої є таблиці схеми R X , що складаються з
обмежень за X рядків вихідних таблиць.
Отже, X , R : ( R ) ( R X ) , X , R , R , R X , де , R ( R ) .
Основа мультимножини визначається як ( ) {s | X | s ( )} .
Дублікати рядків, які з’явилися після виконання операції, не вилучаються. Кількість дублікатів кожного
рядка визначається за формулою:
Occ( s, ) Occ( s, ) , де s ( ) .
s ( ),
s| X s
Під з’єднанням таблиць схем R1 , R2 розуміється бінарна параметрична операція , значеннями якої є
R1 ,R2
таблиці схеми R1 R2 , що складаються з усяких об’єднань сумісних рядків вихідних таблиць.
Отже,
: ( R1 ) ( R2 ) ( R1 R2 ) , 1 , R1 2 , R2 , R1 R2 ,
R1 , R2 R1 , R2
де 1 , R1 ( R1 ), 2 , R2 ( R2 ) . Змістовно кажучи, кожний рядок з 1 з’єднується з кожним рядком із
2 , незалежно від того – дублікат це чи ні.
Основою мультимножини є множина рядків
( ) s ' | s1s 2 s1 ( 1 ) s 2 ( 2 ) s1 s 2 s ' s1 s 2 .
Кількість дублікатів знаходиться так: Occ( s ' , ) Occ( s ' | R1 , 1 ) Occ ( s ' | R2 , 2 ), де s' ( ' ) .
Введемо операцію перейменування. Під перейменуванням таблиць схеми R розуміється унарна параме-
~ A – ін’єктивне відображення на множині атрибутів, що здійснює перейме-
трична операція R , R , де : A
нування атрибутів вихідних таблиць згідно з відображенням-параметром . Перейменувати таблицю означає
перейменувати атрибути її схеми, тобто перейменувати рядки таблиці. Перейменування рядків будемо здійс-
нювати відповідно до [6].
Нехай : A A – функція перейменування атрибутів. Під перейменуванням рядків, що відповідає фун-
кції перейменування атрибутів , розуміється відображення Rs : S S , Rs ( s) ( A), s( A) | A 12 s , при-
чому id A\domξ .
Схема R називається -допустимою, якщо [ R ] ( R \ dom ) . Тут [R] – повний образ множини
R відносно функції . Множину таблиць схеми R , де схема R -допустима позначимо (R ) .
168
Proceedings of the 8th International Conference of Programming UkrPROG’2014 (Kyiv, Ukraine)
Під перейменуванням таблиць схеми R , що відповідає ін’єктивній частковій функції перейменування
~ A , розуміється унарна параметрична операція R
атрибутів : A , R з областю означеності (R ) , значен-
ня якої задаються таким чином: R , R , R Rs [ ],[ R] , де (R ) , id A\dom , Rs [ ] – по-
вний образ мультимножини з основою ( ) відносно функції Rs .
Основою мультимножини Rs [ ] є повний образ множини ( ) відносно функції Rs , R . А кількість
дублікатів рядка у результуючій таблиці задається рівністю
Occ s , Rs [ ] Occ ( s, ) ,
де s Rs1 ( s ) , s ( ) .
Введемо операцію активного доповнення. Для цього введемо декілька допоміжних понять.
Активним доменом атрибута A R відносно таблиці , R називається таблиця
D A, { A},R , R .
Насиченням таблиці , R є таблиця
C , R { A1}, R , R ... { An }, R , R .
{ A1},{ A2 } { A1 ,..., An 1},{ An }
Під активним доповненням таблиці схеми R розуміється унарна параметрична операція ~ R , яка таблиці
зіставляє доповнення в її насиченні.
Отже, ~ R :
( R) ( R) , ~ R , R C , R \ RAll , R , де , R ( R ) .
Твердження. Мають місце наступні твердження:
1) будь-який вираз мультимножинної табличної алгебри можна замінити еквівалентним йому виразом,
який використовує лише операції селекції, з’єднання, проекції, об’єднання, різниці та перейменування;
2) будь-який вираз мультимножинної табличної алгебри, який містить лише скінченні таблиці можна за-
мінити еквівалентним йому виразом, який використовує сталі таблиці з єдиним атрибутом і єдиним рядком,
операції селекції, з’єднання, проекції, об’єднання, різниці й перейменування.
Агрегатні операції
Широко використовуваними агрегатними операціями є Sum , Avg , Min , Max , Count . Так, операція
Sum розраховує суму значень у відповідному стовпці заданої таблиці, при цьому значення NULL ігнорують-
ся. Операція Avg визначає середнє арифметичне значень у відповідному стовпці заданої таблиці, при цьому
значення NULL ігноруються. Операції Min та Max знаходять найменше та найбільше значення у відповід-
ному стовпці заданої таблиці, при цьому значення NULL так само ігноруються. Операція Count визначає
кількість значень, відмінних від NULL , у відповідному стовпці заданої таблиці. Операція Count () визначає
кількість рядків у заданій таблиці.
Нехай , R ( R ) , причому – скінченна мультимножина і A – деякий атрибут схеми R , A R .
Позначимо через A – мультимножину, яка містить всі елементи стовпця з атрибутом A таблиці , R . Тоді
A D A, , де D A, A, R , R – активний домен атрибута A відносно таблиці , R . Нехай
2D ' D'
m { | ( ) 2 } – сім’я всіх мультимножин, основи яких є скінченними підмножинами множини D' ; тут
D' D – підмножина універсального домену.
Нехай Num – числова підмножина універсального домену D , замкнена відносно додавання. Множина
Num розширена включенням особливого елемента NULL , але при цьому операція додавання на випадок, коли
хоча б один з аргументів є NULL не розширюється.
Задамо агрегатні операції Sum , Avg , Min , Max , Count . Їхніми аргументами є скінченні таблиці, а зна-
ченнями – одноатрибутні таблиці з одним рядком. Загальна схема: спочатку на скінченній мультимножині ви-
значаються функції сумування, взяття найменшого та найбільшого значення, визначення середнього арифмети-
чного і кількості елементів, а потім ці функції переносяться на таблиці.
Під операцією агрегування Sum A, R за атрибутом A (скінченних) таблиць схеми R , A R , розуміється
унарна параметрична операція вигляду
169
Proceedings of the 8th International Conference of Programming UkrPROG’2014 (Kyiv, Ukraine)
Sum A, R : ( R ) ({ A}) , Sum A, R , R A, Sum( ) ,{A} ,
A
1
де , R ( R ) , а Sum – функція, що повертає суму значень стовпця з атрибутом A таблиці , R (ці зна-
чення можуть повторюватися), які відрізняються від значення NULL , крім того, цей стовпець містить лише
дані числового типу. Отже,
NULL, якщо ( A ) ;
Sum( A ) NULL, якщо ( A ) {NULL};
d A (d ), якщо ( A ) \ {NULL} .
d ( A ) \{NULL}
Верхній індекс 1 вказує на те, що рядок { A, Sum( A ) } входить у результуючу таблицю лише один раз,
тобто кількість дублікатів даного рядка дорівнює однин.
Таким чином,
Sum( m ) NULL , Sum ({ NULLn }) NULL , Sum d1n1 ,, d knk d i ni ,
k
i 1
в припущенні, що всі елементи d i відрізняються від елемента NULL .
Для випадку порожньої таблиці , R операція агрегування Sum A, R застосовується так:
Sum A, R , R A, NULL ,{A} .
1
Приклад 1. Серед студентів фізико-математичного факультету було проведено анонімне опитування на
визначення рівня самооцінки. Проаналізовано відповіді 6 учасників вибраних довільним чином з кожного фа-
культету. Дані відображені в таблиці ФМ , R , де R { A, B, C , D} (див. таблицю). Атрибути схеми R – це за-
питання, дані в таблицях – це відповіді студентів.
Запитання (атрибути):
A – чи турбуєтеся Ви за свій психічний стан?
B – чи турбуєтеся Ви про своє майбутнє?
C – чи боїтеся Ви виступати з промовою перед незнайомими людьми?
D – чи часто Ви робите помилки?
Варіанти відповіді:
1 – часто;
2 – іноді;
3 – рідко;
4 – ніколи.
Таблиця
A B C D
4 2 4 3
4 2 4 3
4 2 4 3
4 3 3 2
4 3 3 2
3 3 3 1
Позначимо рядки:
s1 { A,4 , B,2 , C ,4 , D,3 } , s 2 { A,4 , B,3 , C ,3 , D,2 } ,
s3 { A,3 , B,3 , C ,3 , D,1 } ,
170
Proceedings of the 8th International Conference of Programming UkrPROG’2014 (Kyiv, Ukraine)
тоді ФМ {s13 ,s 22 , s13 } .
Тоді в результаті застосування операції агрегування Sum A, R до таблиці ФМ , R за атрибутами
A, B, C , D отримаємо таблиці:
Sum A, R {{ A, 23}}, { A} , Sum B , R {{B, 15}}, {B} ,
SumC , R {{C , 21}}, {C} , Sum D , R {{D, 14}}, {D} .
Нехай ≤ – лінійний порядок на універсальному домені D . Під операцією агрегування Min A, R за атрибу-
том A (скінченних) таблиць схеми R , A R , розуміється унарна параметрична операція вигляду:
Min A, R : ( R ) ({ A}) , де Min A, R , R A, Min( ) , {A} ,
A
1
причому , R ( R ) , а Min – функція, що повертає найменше значення серед значень стовпця з атрибутом
A таблиці , R , відмінних від значення NULL , тобто Min : 2 mD D ,
NULL, якщо ( A ) ;
Min( A ) NULL, якщо ( A ) {NULL};
min{d | d ( ) \ {NULL}}, якщо ( ) \ {NULL} .
A A
n n
Таким чином, Min( m ) NULL , Min ({ NULLn }) NULL , Min d1 1 ,, d k k min{d1 ,, d k } , в припу-
щенні, що всі елементи d i , i 1, k , відрізняються від елемента NULL .
Для випадку порожньої таблиці , R операція агрегування Min A, R застосовується так:
Min A, R t , R A, NULL ,{A} .
1
Приклад 2. Розглянемо таблицю із приклада 1. Застосуємо операцію агрегування MinA, R до таблиці
ФМ , R за атрибутами A, B , C , D отримаємо таблиці:
Min A, R {{ A, 3}}, { A} , MinB , R {{B, 2}},{B} ,
MinC , R {{C , 3}},{C} , MinD , R {{D, 1}}, {D} .
Під операцією агрегування Max A, R за атрибутом A (скінченних) таблиць схеми R , A R , розуміється
унарна параметрична операція вигляду:
Max A, R : ( R ) ({ A}) , Max A, R , R A, Max( ) ,{A} ,
A
1
де , R ( R ) , а Max – функція, що повертає найбільше значення серед значень стовпця з атрибутом A
таблиці , R , відмінних від NULL , тобто Max : 2 mD D ,
NULL, якщо ( A ) ;
Max( A ) NULL, якщо ( A ) {NULL};
max{d | d ( ) \ {NULL}}, якщо ( ) \ {NULL} .
A A
n n
Таким чином, Max( m ) NULL , Max ({ NULLn }) NULL , Max d1 1 ,, d k k max{d1 ,, d k } , в припу-
щенні, що всі елементи d i , i 1, k , відрізняються від значення NULL .
Для випадку порожньої таблиці , R операція агрегування Max A, R застосовується так:
Max A,R , R A, NULL ,{A} .
1
Приклад 3. Застосуємо операцію агрегування Max A, R до таблиці ФМ , R за атрибутами A, B , C , D
отримаємо таблиці:
171
Proceedings of the 8th International Conference of Programming UkrPROG’2014 (Kyiv, Ukraine)
Max A, R {{ A, 4}}, { A} , MaxB , R {{B, 3}},{B} ,
MaxC , R {{C , 4}},{C} , MaxD , R {{D, 3}},{D} .
Зазначимо, що функції Min та Max визначають найменший або найбільший елемент основи мульти-
множини A серед елементів основи, відмінних від NULL , тому порівнянність особливого елемента NULL з
рештою елементів універсального домену в даному випадку неістотна.
Під операцією агрегування Count A, R за атрибутом A (скінченних) таблиць схеми R , A R , розумієть-
ся унарна параметрична операція вигляду:
Count A, R : ( R ) ({ A}) , Count A, R , R A, Count ( ) ,{A} ,
A
1
де , R ( R ) , а Count – функція, що повертає кількість значень, відмінних від NULL , з урахуванням дуб-
лікатів, у стовпці з атрибутом A таблиці , R , тобто:
Count : 2 D
m Z , Count ( A ) A (d ) ;
d ( A ) \{NULL}
покладається за означенням, що сума порожньої множини доданків дорівнює нулю.
n n
Таким чином, Count ( m ) 0 , Count ({ NULLn }) 0 , Count d1 1 ,, d k k n1 nk , в припущенні, що
всі елементи d i , i 1, k , відрізняються від елемента NULL .
Для випадку порожньої таблиці , R операція агрегування Count A, R застосовується так:
Count A, R , R A,0 ,{A} .
1
Приклад 4. Застосуємо операцію агрегування Count A,R до таблиці ФМ , R за атрибутами A, B, C , D
отримаємо таблиці:
Count A, R {{ A, 6}}, { A} , Count B , R {{B, 6}},{B} ,
Count C , R {{C , 6}}, {C} , Count D , R {{D, 6}}, {D} .
Припустимо, що числова підмножина Num універсального домену замкнена відносно (часткової опера-
~ Num . Довизначимо операцію ділення так, що коли перший агрумент дорівнює
ції) ділення / : Num Num
NULL , то функція приймає значення NULL .
Під операцією агрегування Avg A, R за атрибутом A (скінченних) таблиць схеми R , A R , розуміється
унарна параметрична операція вигляду:
Avg A, R : ( R ) ({ A}) , Avg A, R , R A, Avg ,{A} ,
A
1
де , R ( R ) , а Avg – функція, що повертає середнє арифметичне значення елементів стовпця з атрибутом
A таблиці , R , які відрізняються від значення NULL , з урахуванням дублікатів, тобто:
Avg : 2 mNum Num , Avg ( A ) Sum( A ) / Count ( A ) .
Таким чином, з означення випливають рівності
Avg ( m ) Sum( m ) / Count ( m ) NULL / 0 NULL ,
Avg ({ NULLn }) Sum ({ NULLn }) / Count ({ NULLn }) NULL / 0 NULL ,
Avg d1n1 ,, d knk Sum d1n1 ,, d knk / Count d1n1 ,, d knk (n 1 n ) d n ,k
i 1
i i
1 k
в припущенні, що всі елементи d i відрізняються від елемента NULL .
Для випадку порожньої таблиці , R операція агрегування Avg A, R застосовується так:
172
Proceedings of the 8th International Conference of Programming UkrPROG’2014 (Kyiv, Ukraine)
Avg A, R , R A, NULL , { A} .
1
Приклад 5. Застосуємо операцію агрегування Avg A,R до таблиці ФМ , R за атрибутами A, B, C , D отри-
маємо таблиці
23 15
Avg A, R {{ A, }}, { A} , Avg B , R {{B, }}, {B} ,
6 6
21 14
Avg C , R {{C , }}, {C} , Avg D , R {{D, }}, {D} .
6 6
Під операцією агрегування Count A, R () (скінченних) таблиць схеми R розуміється унарна параметрична
операція вигляду:
Count A, R () : ( R ) ({ A}) , Count A, R () , R A, ,{A} ,
1
при цьому , R ( R ) , а – це ранг мультимножини .
Для випадку порожньої таблиці , R операція агрегування Count A, R () застосовується так:
Count A, R () , R A, m ,{A} A,0 ,{A} .
1 1
Приклад 6. Застосуємо операцію агрегування Count A,R () до таблиці ФМ , R за атрибутами A, B, C , D
отримаємо таблиці:
Count A, R () {{ A, 6}}, { A} , Count B , R () {{B, 6}},{B} ,
Count C , R () {{C , 6}}, {C} , Count D , R () {{D, 6}}, {D} .
Висновки
Визначено формальну математичну семантику агрегатних операцій над таблицями як мультимножинами
рядків однієї схеми, яка проілюстрована прикладами їх використання. Для заданих агрегатних операцій параме-
тром виступає лише один атрибут, проте отримані результати можна розширити на випадки, коли параметром є
деяка функція над рядком. Результати роботи можуть бути використані в теорії узагальнених табличних алгебр.
1. Codd E.F. A Relational Model of Data for Large Shared Data Banks / E.F. Codd // Comm. of ACM. – 1970.– 13, N 6. – P. 377–387.
2. Grefen Paul W.P.J., Rolf A. De By A Multi-Set Extended Relational Algebra. A Formal Approach to a Practical Issue // 10th International
Conference on Data Engineering, ICDE, February 14-18, 1994, Houston, TX, USA. – 1994. – Р. 80–88.
3. Lamperti G., Melchiori M., Zanella M. On Multisets in Database Systems // Multiset Processing: Mathematical, Computer Science, and
Molecular Computing Points of View, number 2235 in Lecture Notes in Computing Since. – Berlin: Springer-Verlag. – 2001. – P. 147–215.
4. Garcia-Molina H. Database Systems: The Complete Book: [2nd Edition] / H. Garcia-Molina, J.D. Ullman, J. Widom. – Prentice Hall, 2008. –
1119 p.
5. Silbeschatz A., Korth H., Sudarshan S. Database System Concepts – McGraw-Hill, 2011. – 1376 p.
6. Редько В.Н., Брона Ю.Й., Буй Д.Б., Поляков С.А. Реляційні бази даних: табличні алгебри та SQL-подібні мови. – Київ: Видавничий дім
"Академперіодика", 2001. – 198 с.
173