Розглянуто мультимножинну табличну алгебру. Сигнатура мультимножинної табличної алгебри поповнена агрегатними операціями. Задано формальну математичну семантику цих операцій та наведено приклади їх застосування. М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]. Разом з тим, в жодній із зазначених робіт не приділяється увага агрегатним операціям над таблицями мультимножинної табличної алгебри.
Мультимножини, областю значень яких є порожня множина або одноелементна множина вигляду {1}, називаються 1-мультимножинами. Дані мультимножини є аналогами звичайних множин.
Під рангом скінченної мультимножини розуміємо суму дублікатів елементів її основи
U U & d d U d d . Мультимножинна таблична алгебра Розглянемо дві множини: A – множину атрибутів і D – універсальний домен. Довільну скінченну множину атрибутів R A назвемо схемою.
Рядком схеми R називається іменна множина на парі R , D , проекція якої за першою компонентою рівна R (тобто по суті розглядається функція вигляду s : R D ). Множину всіх рядків схеми R позначимо S (R) , а множину всіх рядків – S . Для позначення відсутніх значень у таблиці використовується особливий NULL . Позначимо s NULL
R – константний рядок схеми
R , тобто елемент універсального домену s NULL : R {NULL} .
R
Задамо поняття таблиці як пари , R , де перша компонента – це довільна мультимножина, зокрема, нескінченна, а друга компонента R – схема таблиці.
Таким чином, кожній таблиці приписується певна схема. Множину всіх таблиць схеми R позначимо (R) , а множину всіх таблиць (R) .
RA Позначимо Occ(s, ) – кількість дублікатів (екземплярів) рядка s у мультимножині . Домовимося мультимножину записувати як {s1n1 ,..., sknk ,} , де ni Occ(si , ) , i 1,2, , а ( ) {s1,..., sk ,} – основа мультимножин .
Під мультимножинною табличною алгеброю розуміємо алгебру , P, , де – множина всіх таблиць, P, Al,lR , Al,lR , \ Al,lR , p,R , X ,R , R1,R2, Rt ,R , ~ R pP, – сигнатура, P , – множини параметрів. X ,R,R1,R2A Задамо операції. Під об’єднанням RAll (перетином All , різницею \ RAll ) таблиць схеми R розуміється R бінарна (параметрична) операція, отримана обмеженням однойменних операцій All , All , \ All над мультимножинами на множину всіх таблиць схеми R .
Розглянемо кожну операцію окремо. Позначимо через ( 1) і ( 2 ) – основи мультимножин 1 та 2 відповідно. Таким чином, RAll : (R) (R) (R) ,
R 1, R All 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, 1) Occ(s, 2 ), якщо s ( 1) ( 2 ); де s ( 1) ( 2 ) . а кількість дублікатів рядка визначається як
R RAll : (R) (R) (R) , причому 1, R All 2 , R 1 All 2 , R . Основа мультимножини 1 All 2 дорівнює перетину основ мультимножин таблиць-аргментів: ( 1 All 2 ) ( 1) ( 2 ) ,
Occ(s, 1 All 2 ) minOcc(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 ), де s ( 1) \ ( 2 ) C ( 1, 2 ) .
Нехай p : S ~ {true, false} – частковий предикат на множині рядків. Під селекцією за предикатом p таблиць схеми R розуміється унарна часткова параметрична операція p,R , яка таблиці зіставляє її підтаблицю, що містить рядки, на яких предикат p істинний (крім того, предикат p має бути визначеним на всіх рядках таблиці-аргументу).
Отже,
p,R : (R) ~ (R) , dom p,R , R | ( ) dom p, p,R , 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 2 , R2 , R1 R2 , : (R1) (R2 ) (R1 R2 ) , 1, R1 R1,R2
R1,R2 де 1, R1 (R1), 2 , R2 (R2 ) . Змістовно кажучи, кожний рядок з 1 з’єднується з кожним рядком із 2 , незалежно від того – дублікат це чи ні.
Основою мультимножини є множина рядків
( ) s'| s1s2 s1 ( 1) s2 ( 2 ) s1 s2 s' s1 s2 .
Кількість дублікатів знаходиться так: Occ(s', ) Occ(s'| R1, 1) Occ (s'| R2, 2 ), де s' ( ') .
Введемо операцію перейменування. Під перейменуванням таблиць схеми R розуміється унарна
параметрична операція R ,R , де : A ~ A – ін’єктивне відображення на множині атрибутів, що здійснює
перейменування атрибутів вихідних таблиць згідно з відображенням-параметром . Перейменувати таблицю означає
перейменувати атрибути її схеми, тобто перейменувати рядки таблиці. Перейменування рядків будемо
здійснювати відповідно до [
Нехай : A A – функція перейменування атрибутів. Під перейменуванням рядків, що відповідає функції перейменування атрибутів , розуміється відображення Rs : S S , Rs (s) ( A), s( A) | A 12s, причому idA\domξ .
Схема R називається -допустимою, якщо [R] (R \ dom ) . Тут [R] – повний образ множини R відносно функції . Множину таблиць схеми R , де схема R -допустима позначимо (R) . Під перейменуванням таблиць схеми R , що відповідає ін’єктивній частковій функції перейменування атрибутів : A ~ A , розуміється унарна параметрична операція R ,R з областю означеності (R) , значення якої задаються таким чином: R ,R , R Rs [ ],[R] , де (R) , id A\dom , Rs [ ] – повний образ мультимножини з основою ( ) відносно функції Rs .
Основою мультимножини Rs [ ] є повний образ множини ( ) відносно функції Rs ,R . А кількість дублікатів рядка у результуючій таблиці задається рівністю
Occs, Rs [ ] Occ(s, ) ,
DA, {A},R , R . де s Rs1(s) , s ( ) .
Введемо операцію активного доповнення. Для цього введемо декілька допоміжних понять. Активним доменом атрибута A R відносно таблиці , R називається таблиця Насиченням таблиці , R є таблиця
C , R {A1},R , R {A1},{A2}...{A1,...,An1},{An} {An},R , R .
Під активним доповненням таблиці схеми 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 DA, , де DA, A,R , R – активний домен атрибута A відносно таблиці , R . Нехай 2Dm' { | ( ) 2D'} – сім’я всіх мультимножин, основи яких є скінченними підмножинами множини D' ; тут D' D – підмножина універсального домену.
Нехай Num – числова підмножина універсального домену D , замкнена відносно додавання. Множина Num розширена включенням особливого елемента NULL , але при цьому операція додавання на випадок, коли хоча б один з аргументів є NULL не розширюється.
Задамо агрегатні операції Sum , Avg , Min , Max , Count . Їхніми аргументами є скінченні таблиці, а значеннями – одноатрибутні таблиці з одним рядком. Загальна схема: спочатку на скінченній мультимножині визначаються функції сумування, взяття найменшого та найбільшого значення, визначення середнього арифметичного і кількості елементів, а потім ці функції переносяться на таблиці.
Під операцією агрегування SumA,R за атрибутом A (скінченних) таблиць схеми R , A R , розуміється унарна параметрична операція вигляду
Sum A,R : (R) ({A}) , SumA,R , R A, Sum( A ) 1,{A} , де , 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 , Sumd1n1 ,, dknk dini , k i1 в припущенні, що всі елементи di відрізняються від елемента NULL .
Для випадку порожньої таблиці , R операція агрегування Sum A,R застосовується так:
SumA,R , R A, NULL 1,{A} .
Приклад 1. Серед студентів фізико-математичного факультету було проведено анонімне опитування на визначення рівня самооцінки. Проаналізовано відповіді 6 учасників вибраних довільним чином з кожного факультету. Дані відображені в таблиці ФМ , R , де R {A, B,C, D} (див. таблицю). Атрибути схеми R – це запитання, дані в таблицях – це відповіді студентів.
Запитання (атрибути):
A – чи турбуєтеся Ви за свій психічний стан? B – чи турбуєтеся Ви про своє майбутнє? C – чи боїтеся Ви виступати з промовою перед незнайомими людьми?
D – чи часто Ви робите помилки? Варіанти відповіді: 1 – часто; 2 – іноді; 3 – рідко; 4 – ніколи.
B 2 2 2 3 3 3
C 4 4 4 3 3 3
D 3 3 3 2 2 1 Таблиця s1 { A,4 , B,2 , C,4 , D,3 } , s2 { A,4 , B,3 , C,3 , D,2 } ,
s3 { A,3 , B,3 , C,3 , D,1 } , тоді ФМ {s13,s22 , s31} .
Тоді в результаті застосування операції агрегування Sum A,R до таблиці ФМ , R A, B,C, D отримаємо таблиці: за атрибутами Sum A,R {{A, 23}},{A} , SumB,R {{B, 15}},{B} ,
SumC,R {{C, 21}},{C} , SumD,R {{D, 14}},{D} .
Нехай ≤ – лінійний порядок на універсальному домені D . Під операцією агрегування MinA,R за атрибутом A (скінченних) таблиць схеми R , A R , розуміється унарна параметрична операція вигляду:
Min A,R : (R) ({A}) , де MinA,R , R A, Min( A ) 1, {A} , причому , R (R) , а Min – функція, що повертає найменше значення серед значень стовпця з атрибутом A таблиці , R , відмінних від значення NULL , тобто Min : 2mD D , NULL, якщо ( A ) ; Min( A ) NULL, якщо ( A ) {NULL};
min{d | d ( A ) \ {NULL}}, якщо ( A ) \ {NULL} .
Таким чином, Min(m ) NULL , Min({NULLn}) NULL , Min d1n1 ,, dknk min{d1,, dk } , в припущенні, що всі елементи di , i 1, k , відрізняються від елемента NULL .
Для випадку порожньої таблиці , R операція агрегування MinA,R застосовується так:
MinA,R t , R A, NULL 1,{A} .
Приклад 2. Розглянемо таблицю із приклада 1. Застосуємо операцію агрегування MinA,R до таблиці ФМ , R за атрибутами A, B,C, D отримаємо таблиці:
MinA,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}) , MaxA,R , R A, Max( A ) 1,{A} , де , R (R) , а Max – функція, що повертає найбільше значення серед значень стовпця з атрибутом A таблиці , R , відмінних від NULL , тобто Max : 2mD D , NULL, якщо ( A ) ; Max( A ) NULL, якщо ( A ) {NULL};
max{d | d ( A ) \ {NULL}}, якщо ( A ) \ {NULL} .
Таким чином, Max(m ) NULL , Max({NULLn}) NULL , Max d1n1 ,, dknk max{d1,, dk } , в припущенні, що всі елементи di , i 1, k , відрізняються від значення NULL .
Для випадку порожньої таблиці , R операція агрегування Max A,R застосовується так:
MaxA,R , R A, NULL 1,{A} .
Приклад 3. Застосуємо операцію агрегування MaxA,R до таблиці ФМ , R за атрибутами A, B,C, D отримаємо таблиці: MaxA,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 ) 1,{A} , де , R (R) , а Count – функція, що повертає кількість значень, відмінних від NULL , з урахуванням дублікатів, у стовпці з атрибутом A таблиці , R , тобто:
Count : 2mD Z , Count ( A )
A (d ) ; d( A)\{NULL} покладається за означенням, що сума порожньої множини доданків дорівнює нулю.
Таким чином, Count(m ) 0 , Count ({NULLn}) 0 , Countd1n1 ,, dknk n1 nk , в припущенні, що всі елементи di , i 1, k , відрізняються від елемента NULL .
Для випадку порожньої таблиці , R операція агрегування Count A,R застосовується так:
Count A,R , R A,0 1,{A} .
Приклад 4. Застосуємо операцію агрегування Count A,R до таблиці ФМ , R за атрибутами A, B,C, D отримаємо таблиці:
Count A,R {{A, 6}},{A} , CountB,R {{B, 6}},{B} ,
CountC,R {{C, 6}},{C} , CountD,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 1,{A} , де , R (R) , а Avg – функція, що повертає середнє арифметичне значення елементів стовпця з атрибутом A таблиці , R , які відрізняються від значення NULL , з урахуванням дублікатів, тобто:
Avg : 2mNum 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 , Avgd1n1 ,, dknk Sumd1n1 ,, dknk / Countd1n1 ,, dknk 1 k
dini , (n1 nk ) i1
Для випадку порожньої таблиці , R операція агрегування Avg A,R застосовується так:
Count A,R () : (R) ({A}) , Count A,R () , R A, 1,{A} , при цьому , R (R) , а – це ранг мультимножини .
Для випадку порожньої таблиці , R операція агрегування Count A,R () застосовується так: Під операцією агрегування Count A,R () (скінченних) таблиць схеми R розуміється унарна параметрична Приклад 6. Застосуємо операцію агрегування Count A,R () до таблиці ФМ , R за атрибутами A, B,C, D Приклад 5. Застосуємо операцію агрегування Avg A,R до таблиці ФМ , R за атрибутами A, B,C, D отриAvg A,R , R A, NULL 1,{A} .
23 6 21 6 Avg A,R {{A,
}},{A} , Avg B,R {{B, AvgC,R {{C, }},{C} , Avg D,R {{D, 15 6 14 6 }},{B} , }},{D} .
Count A,R () , R A, m 1,{A} A,0 1,{A} .
Count A,R () {{A, 6}},{A} , Count B,R () {{B, 6}},{B} ,
CountC,R () {{C, 6}},{C} , Count D,R () {{D, 6}},{D} .
Визначено формальну математичну семантику агрегатних операцій над таблицями як мультимножинами рядків однієї схеми, яка проілюстрована прикладами їх використання. Для заданих агрегатних операцій параметром виступає лише один атрибут, проте отримані результати можна розширити на випадки, коли параметром є деяка функція над рядком. Результати роботи можуть бути використані в теорії узагальнених табличних алгебр.