Мультимножини: основні поняття

Наведемо основні поняття мультимножин в термінах роботи [6]. Зафіксуємо деяку множину U . Мультимножина  включається у мультимножину  (    ), якщо:

      d d U d d U U              &  . Якщо    , то мультимножина  називається підмультимножиною мультимножини  , а мультимно- жина  -надмультимножиною мультимножини  . Очевидно, що порожня мультимножина є підмультимно- жиною будь-якої мультимножини (     ,  m ), а будь-яка мультимножина є своєю ж підмультимножиною (     , 

).

Мультимножинна таблична алгебра} { : NULL R s NULL R  .

Задамо поняття таблиці як пари R ,



, де перша компонента  -це довільна мультимножина, зокрема, нескінченна, а друга компонента R -схема таблиці.

Таким чином, кожній таблиці приписується певна схема. Множину всіх таблиць схеми R позначимо

) (R  , а множину всіх таблиць  A ) (     R R .

Позначимо

) ,

(  s Occ -кількість дублікатів (екземплярів) рядка s у мультимножині  . Домовимося му- льтимножину  записувати як } , ,..., { 1 1  k n k n s s , де ) , (  i i s Occ n  ,  , 2 , 1  i , а } , ,..., { ) ( 1  k s s    -основа мультимножин  . Під мультимножинною табличною алгеброю розуміємо алгебру    , , P , де  -множина всіх таб- лиць,                      , A , , ,, , , , , , , , 2 1 2 1

, , , , , \ , ,

P p R R R X R R R R R X R p R All R All R All P Rt   -сигнатура, P ,  -множини параметрів. Задамо операції. Під об'єднанням R All  (перетином R All  , різницею R All \ ) таблиць схеми R розуміється бінарна (параметрична) операція, отримана обмеженням однойменних операцій All  , All  , All \ над мульти- множинами на множину всіх таблиць схеми R .

Розглянемо кожну операцію окремо. Позначимо через

) ( 1   і ) ( 2   -основи мультимножин 1  та 2  відповідно. Таким чином, ) ( ) ( ) ( : R R R R All       , R R R All R All , , , 2 1 2 1        .

Основа мультимножини

2 1   All 

дорівнює об'єднанню основ мультимножин таблиць-аргументів:

) ( ) ( ) ( 2 1 2 1           All .

Дублікати рядків, які з'явилися після виконання операції, не вилучаються. Кількість дублікатів кожного рядка визначається за формулою:

                ); ( ) ( якщо ), , ( ) , ( ), ( \ ) ( якщо ), , ( ), ( \ ) ( якщо ), , ( ) , ( 2 1 2 1 1 2 2 2 1 1 2 1               s s Occ s Occ s s Occ s s Occ s Occ All де ) ( ) ( 2 1       s . ) ( ) ( ) ( : R R R R All       , причому R R R All R All , , , 2 1 2 1        .

Основа мультимножини

2 1   All 

дорівнює перетину основ мультимножин таблиць-аргментів:

) ( ) ( ) ( 2 1 2 1           All , а кількість дублікатів рядка визначається як   ) , ( ), , ( min ) , ( 2 1 2 1     s Occ s Occ s Occ All   , де ) ( ) ( 2 1       s . ) ( ) ( ) ( : \ R R R R All      , причому R R R All R All , \ , \ , 2 1 2 1      , де R , 1  , ). ( , 2 R R    Основа мультимножини 2 1 \   All визначається як ) , ( ) ( \ ) ( ) \ ( 2 1 2 1 2 1            C All  , де   ) , ( ) , ( ) ( ) ( | ) , ( 2 1 2 1 2 1       s Occ s Occ s s C         . Кількість дублікатів знаходиться так:             ), , ( якщо ), , ( ) , ( ), ( \ ) ( якщо ), , ( ) \ , ( 2 1 2 1 2 1 1 2 1          C s s Occ s Occ s s Occ s Occ All де   ) , ( ) ( \ ) ( 2 1 2 1         C s  . Нехай } , { : false true S p 

-частковий предикат на множині рядків. Під селекцією за предикатом p таблиць схеми R розуміється унарна часткова параметрична операція R p,  , яка таблиці зіставляє її підтабли- цю, що містить рядки, на яких предикат p істинний (крім того, предикат p має бути визначеним на всіх рядках таблиці-аргументу).

Отже,

) ( ) ( : , R R R p     ,   p dom R dom R p    ) ( | , ,    ,   R R R p , ' , ,     , де ) ( , R R    .

Областю означеності операції селекції є таблиці

) ( , R R    , які містять рядки ) (R S s  , на



, значеннями якої є таблиці схеми X R  , що складаються з обмежень за X рядків вихідних таблиць.

Отже,

) ( ) ( : , X R R R X      ,   X R R R X  , , ,      , де ) ( , R R    . Основа мультимножини   визначається як )} ( | | { ) (        s X s

. Дублікати рядків, які з'явилися після виконання операції, не вилучаються. Кількість дублікатів кожного рядка визначається за формулою:

        s X s s s Occ s Occ | ), ( ) , ( ) , (    , де ) (     s . Під з'єднанням таблиць схем 1 R , 2 R розуміється бінарна параметрична операція 2 1 ,R R  , значеннями якої є таблиці схеми 2 1 R R  , що складаються з усяких об'єднань сумісних рядків вихідних таблиць. Отже, ) ( ) ( ) ( : 2 1 2 1 , 2 1 R R R R R R        , 2 1 2 2 , 1 1 , , , 2 1 R R R R R R        , де ), ( , 1 1 1 R R    ) ( , 2 2 2 R R   

. Змістовно кажучи, кожний рядок з 1  з'єднується з кожним рядком із 2  , незалежно від того -дублікат це чи ні.

Основою мультимножини   є множина рядків

    2 1 2 1 2 2 1 1 2 1 ' ) ( ) ( | ' ) ( s s s s s s s s s s                   . Кількість дублікатів знаходиться так: ), , | ' ( ) , | ' ( ) , ' ( 2 2 1 1    R s Occ R s Occ s Occ    де ) ' ( '    s . Введемо операцію перейменування. Під перейменуванням таблиць схеми R розуміється унарна параме- трична операція R R ,   , де A A  :  -ін',   s A A s A s Rs 2 1 | ) ( ), ( ) (      , при- чому \domξ A id     . Схема R називається  -допустимою, якщо   ) \ ( ] [   dom R R  . Тут ] [R  -повний образ множини R відносно функції  . Множину таблиць схеми R , де схема R  -допустима позначимо ) (R   .

Під перейменуванням таблиць схеми R , що відповідає ін'єктивній частковій функції перейменування атрибутів A A  :

 , розуміється унарна параметрична операція R R ,   з областю означеності ) (R  

, значення якої задаються таким чином:

  ] [ ], [ , , R Rs R R R        , де ) (R     ,    \dom A id   , ] [  Rs -по- вний образ мультимножини  з основою ) (  відносно функції  Rs . Основою мультимножини ] [  Rs є повний образ множини ) (  відносно функції R Rs ,  . А кількість дублікатів рядка у результуючій таблиці задається рівністю   ) , ( ] [ ,    s Occ Rs s Occ   , де ) ( 1 s Rs s     , ) (     s .

Введемо операцію активного доповнення. Для цього введемо декілька допоміжних понять.

Активним доменом атрибута R A відносно таблиці R ,  називається таблиця   R D R A A , }, { ,     . Насиченням таблиці R ,  є таблиця       R R R C R A A A A A A R A n n n , ... , , }, { } { }, ,..., { } { }, { }, { 1 1 2 1 1          .

Під активним доповненням таблиці схеми R розуміється унарна параметрична операція R ~, яка таблиці зіставляє доповнення в її насиченні.

Отже, R ~:

) ( ) ( R R    ,     R R C R R All R , \ , , ~    , де ) ( , R R    .

Твердження. Мають місце наступні твердження: 1) будь-який вираз мультимножинної табличної алгебри можна замінити еквівалентним йому виразом, який використовує лише операції селекції, з'єднання, проекції, об'єднання, різниці та перейменування;

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

Агрегатні операції

Широко використовуваними агрегатними операціями є Sum , Avg , Min , Max , Count . Так, операція Sum розраховує суму значень у відповідному стовпці заданої таблиці, при цьому значення NULL ігноруються. Операція Avg визначає середнє арифметичне значень у відповідному стовпці заданої таблиці, при цьому значення NULL ігноруються. Операції Min та Max знаходять найменше та найбільше значення у відповідному стовпці заданої таблиці, при цьому значення NULL так само ігноруються. Операція Count визначає кількість значень, відмінних від NULL , у відповідному стовпці заданої таблиці. Операція

) ( Count визначає кількість рядків у заданій таблиці. Нехай ) ( , R R    , причому  -скінченна мультимножина і A -деякий атрибут схеми R , R A  . Позначимо через A  -мультимножину, яка містить всі елементи стовпця з атрибутом A таблиці R ,  . Тоді   , A A D  , де   R D R A A , , ,     -активний домен атрибута A відносно таблиці R ,  . Нехай } 2 ) ( | { 2 ' D ' D      m -сім'я всіх мультимножин, основи яких є скінченними підмножинами множини ' D ; тут D D  '

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

Задамо агрегатні операції Sum , Avg , Min , Max , Count . Їхніми аргументами є скінченні таблиці, а зна- ченнями -одноатрибутні таблиці з одним рядком. Загальна схема: спочатку на скінченній мультимножині визначаються функції сумування, взяття найменшого та найбільшого значення, визначення середнього арифметичного і кількості елементів, а потім ці функції переносяться на таблиці.

Під операцією агрегування

R A Sum , за атрибутом A (скінченних) таблиць схеми R , R A  , розуміється унарна параметрична операція вигляду }) ({ ) ( : , A R Sum R A    ,       } { , ) ( , , 1 , A Sum A R Sum A R A    , де ) ( , R R    , а Sum -функція, що повертає суму значень стовпця з атрибутом A таблиці R ,



(ці значення можуть повторюватися), які відрізняються від значення NULL , крім того, цей стовпець містить лише дані числового типу. Отже, Позначимо рядки:

                   {NULL} d A A A A A A NULL d d NULL NULL NULL Sum \ ) ( . } { \ ) ( якщо ), ( }; { ) ( якщо , ; ) ( якщо , ) (       Верхній індекс 1 вказує на те, що рядок } ) ( , { A Sum A  входить у результуючу таблицю лише один раз, тобто кількість дублікатів даного рядка дорівнює однин. Таким чином, NULL Sum m   ) ( , NULL NULL Sum n  }) ({ ,        k i i i n k n n d d d Sum k 1 1 , , 1  , в припущенні, що всі елементи i d відрізняються від елемента NULL . Для випадку порожньої таблиці R ,   операція агрегування R A Sum , застосовується так:       } { , , , 1 , A NULL A R Sum R A    .Приклад} 3 , ,4 , , 2 , , 4 , { 1         D C B A s , } 2 , ,3 , , 3 , , 4 , { 2         D C B A s , } 1 , ,3 , , 3 , , 3 , { 3         D C B A s , де ) ( , R R    , а