ПРО ЗВ'ЯЗОК МІЖ ТАБЛИЧНОЮ АЛГЕБРОЮ НЕСКІНЧЕННИХ ТАБЛИЦЬ ТА МУЛЬТИМНОЖИННОЮ ТАБЛИЧНОЮ АЛГЕБРОЮ

ПРО ЗВ'ЯЗОК МІЖ ТАБЛИЧНОЮ АЛГЕБРОЮ НЕСКІНЧЕННИХ ТАБЛИЦЬ ТА МУЛЬТИМНОЖИННОЮ ТАБЛИЧНОЮ АЛГЕБРОЮ ІМГлушко ПРО ЗВ'ЯЗОК МІЖ ТАБЛИЧНОЮ АЛГЕБРОЮ НЕСКІНЧЕННИХ ТАБЛИЦЬ ТА МУЛЬТИМНОЖИННОЮ ТАБЛИЧНОЮ АЛГЕБРОЮ 56C12304E7402D2C4C23FF6D0E45C439 GROBID - A machine learning software for extracting information from scholarly documents

Дана робота є продовженням робіт, присвячених актуальній проблемі розробки теоретичної основи табличних баз даних, в якості якої виступають табличні алгебри. Розглядається питання про зв'язок між табличною алгеброю нескінченних таблиць та мультимножинною табличною алгеброю. Враховуючи той факт, що 1-мультимножини є аналогами звичайних множин, виникає питання, чи є таблична алгебра нескінченних таблиць підалгеброю мультимножинної табличної алгебри. Ця проблема і досліджується у даній роботі. Застосовуючи теоретико-множинні та логіко-алгебраїчні методи, встановлено, що таблична алгебра нескінченних таблиць не утворює підалгебру мультимножинної табличної алгебри, бо не є замкненою відносно деяких операцій сигнатури мультимножинної табличної алгебри. У роботі встановлено, що це за операції. Ключові слова. Реляційні бази даних, таблична алгебра нескінченних таблиць, мультимножинна таблична алгебра.

Данная работа является продолжением работ, посвященных актуальной проблеме разработки теоретической основы табличных баз данных, в качестве которой выступают табличные алгебры. Рассматривается вопрос о связи между табличной алгеброй бесконечных таблиц и мультимножественной табличной алгеброй. Учитывая тот факт, что 1-мультимножества являются аналогами обычных множеств, возникает вопрос, является ли табличная алгебра бесконечных таблиц подалгеброй мультимножественной табличной алгебры. Эта проблема и исследуется в этой работе. Применяя теоретико-множественные и логико-алгебраические методы, установлено, что табличная алгебра бесконечных таблиц не образует подалгебру мультимножественной табличной алгебры, потому что не является замкнутой относительно некоторых операций сигнатуры мультимножественной табличной алгебры. В работе установлено, что это за операции. Ключевые слова. Реляционные базы данных, табличная алгебра бесконечных таблиц, мультимножественная табличная алгебра.

This article is a continuation of the works devoted to the actual problem of the development of the theoretical basis of the table databases. The question of the relationship between table algebra of infinite tables and multiset table algebra is considered. Considering the fact that 1multisets are analogues of ordinary sets, the question arises, is whether table algebra of infinite tables a subalgebra of multiset table algebra. This paper is devoted to this issue. Applying the theorem-plural and logical-algebraic methods found that this is not the case. The table algebra of infinite tables does not form subalgebra of multiset table algebra, since it is not closed in relation to some signature operations of multiset table algebra. These operations are determined.

Вступ

Уточнення реляції в термінах іменних множин було здійснене В.Н. Редьком, Ю.Й. Броною, Д.Б. Буєм, С.А. Поляковим [1]. Традиційно під реляцією розуміється скінченна множина рядків, і автори враховують це обмеження, проте, як правило, математичні твердження про властивості уточнень реляційних операцій залишаються вірними і для нескінченних реляцій. Так, детальний аналіз доведень у [1] показує, що властивість скінченності таблиць в багатьох випадках не використовується. Тому в роботі [2] було здійснено узагальнення, яке полягає в тому, що надалі під реляцією розуміється довільна множина односхемних рядків, зокрема, нескінченна. Також введено до розгляду мультимножинну табличну алгебру, яка є мультимножинним аналогом табличної алгебри, тобто поняття реляції уточнюється, використовуючи поняття мультимножини, зокрема нескінченної [2]. Беручи до уваги, що 1-мультимножини є аналогами звичайних множин, постає питання чи є таблична алгебра нескінченних таблиць підалгеброю мультимножинної табличної алгебри. Цьому питанню й присвячена дана робота. ).

Таблична алгебра нескінченних таблицьТаблицею схеми R є пара R t, , де t -множина (зокрема, нескінченна) рядків вказаної схеми R . Надалі через   1 , R t будемо позначати першу компоненту пари R t, , тобто множину t . Множину усіх рядків (таблиць) схеми R позначимо ) (R S (відповідно) (R T ), а множину всіх рядків (таблиць) -S (відповідно T ). Таким чином,  A ) (   R R S S ,   )) ( ( | , ) ( T R S P t R t R   ,  A T T   R R) ( , де ) ( X P - булеан множини X .

У роботі [2]

                   , A , ,, , , , , , 2 1 12 2 1 , , , , , , \ , , P p R R R X R R R R R R R X R p R R R P Rt  

-сигнатура,  , P -множини параметрів. Сигнатура містить аналоги теоретико-множинних операцій (об'єднання, перетин, різницю) та спеціальні операції (селекцію, проекцію, з'єднання, ділення, перейменування та активне доповнення).

Мультимножинна таблична алгебра

Дамо означення основних понять мультимножинної табличної алгебри на основі монографії [2]. Як і раніше, A -множина атрибутів, D -універсальний домен. Довільна скінченна множина атрибутів

A  R -це схема. Рядком схеми R називається іменна множина на парі R , D , проекція якої за першою компонентою рівна R . Множина всіх рядків схеми R позначається ) (R S , а множина всіх рядків -S . Поняття таблиці задається як пара 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   -     інакше; , 0 , dom якщо ), ( ) (     d d d для всіх D d  .

Мультимножина називається порожньою і позначається як m  , якщо її основа -порожня множина.

Мультимножини, областю значень яких є порожня множина або одноелементна множина вигляду {1}, називаються 1-мультимножинами.

У роботі [1]

'єднання R All  , перетину R All  і різниці R All \ . Розглянемо кожну операцію окремо. Позначимо через ) ( 1 1 t  і ) ( 1 2 t  -основи 1-мультимножин 1 1 t та 1 2 t відповідно. Тоді R t t R t R t All R All , , , 1 2 1 1 1 2 1 1    , де R t , 1 1 , ). ( , 1 2 R T R t  Основа мультимножини 1 2 1 1 t t All

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

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

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

               ); ( ) ( якщо , 2 ), ( \ ) ( або ) ( \ ) ( якщо , 1 ) , ( 1 2 1 1 1 1 1 2 1 2 1 1 1 2 1 1 t t s t t s t t s t t s Occ All   де ) ( ) ( 1 2 1 1 t t s     . В результаті 1 2 1 1 t t All  буде мультимножиною загального вигляду, а не 1- мультимножиною.

Отже, множина T не замкнута відносно операції об'єднання R All  . З'ясуємо, чи замкнена множина T відносно інших операцій сигнатури мультимножинної табличної алгебри   ,

P . Множина T є замкненою відносно перетину: ) ( ) ( ) ( : R Т R Т R Т R All    , причому R t t R t R t All R All , , , 1 2 1 1 1 2 1 1    , де R t , 1 1 , ). ( , 1 2 R T R t  Основа мультимножини 1 2 1 1 t t All  дорівнює перетину основ 1-мультимножин таблиць-аргментів: ) ( ) ( ) ( 1 2 1 1 1 2 1 1 t t t t All       , а кількість дублікатів рядка визначається як  1 ) , ( ), , ( min ) , ( 1 2 11 1 2 1 1   t s Occ t s Occ t t s Occ де ) ( \ ) ( 1 2 1 1 t t s    .

В результаті отримаємо, що

1 2 1 1 \ t t All є 1-мультимножиною і ) ( , \ 1 2 1 1 R T R t  R t R t R p , , 1 ,    , де ) ( , 1 R T R t  .

Основа мультимножини результуючої таблиці визначається як:

} ) ( ) ( | { ) ( 1 true s p t s s t        ,

де  ~ -узагальнена рівність (тобто обидві частини або одночасно не визначені або одночасно визначені і рівні [4]).

В залежності від значення предиката на рядку s усі дублікати цього рядка або входять до мультимножини отриманої таблиці, або ні:

, 1 ) , ( ) , ( 1    t s Occ t s Occ де ) (t s    . Тому t є 1-мультимножиною і ) ( , R T R t  

. Отже, множина T замкнена відносно операції селекції.

Нехай

A  X -скінченна множина атрибутів. З'ясуємо чи замкнена множина T відносно операції проекції за множиною атрибутів X . Отже,   X R t R t R X  , , 1 ,    , де ) ( , 1 R T R t  . Основа мультимножини t визначається як )} ( | | { ) ( 1 t s X s t      .

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

        s X s t s t s Occ t s Occ | ), (1 1 )1 ,R R  . Маємо, 2 1 2 1 2 , 1 1 1 , , , 2 1 R R t R t R t R R     , де ), ( , 1 1 1 1 R T R t  ) ( , 2 2 1 2 R T R t 2

. Змістовно кажучи, кожний рядок з

Дамо означення основних понять табличної алгебри нескінченних таблиць на основі монографії [2]. Розглянемо дві множини: A -множину атрибутів і D -універсальний домен. Довільна (скінченна) множина атрибутів A  R називається схемою. Рядком схеми R називається іменна множина на парі R , D , проекція якої за першою компонентою рівна R (тобто по суті розглядається функція вигляду D  R s :

зв'язок між табличною алгеброю нескінченних таблиць та мультимножинною табличною алгеброюоперації над мультимножинами визначено в термінах характеристичних функцій. Автори вводять операції об'єднання 1  , перетину 1  , різниці 1 \ мультимножин, що будують 1-мультимножини, основи яких отримуються відповідно теоретико-множинними об'єднанням, перетином та різницею основ мультимножин-аргументів, та операції об'єднання Dist , що будує 1-мультимножину, основа якої збігається з основою вихідної мультимножини та вводиться аналог повного образу для мультимножин. 'ясуємо чи є таблична алгебра нескінченних таблиць підалгеброю мультимножинної табличної алгебри.Про Для цього припустимо, що таблицею табличної алгебри нескінченних таблиць є параt , 1R, де 1 t -1-множина(зокрема, нескінченна) рядків вказаної схеми R . У цьому випадку очевидно, що множина всіх таблицьтабличної алгебри нескінченних таблиць T є підмножиною множини всіх таблиць мультимножинної табличної алгебри  ,   T .Тепер з'ясуємо чи замкнена множина T відносно кожної операції сигнатури мультимножинноїтабличної алгебри P .  ,Почнемо з теоретико-множинних операцій: об,  операцію()

All  , перетину All  , різниці All \ мультимножин, які будують мультимножини загального вигляду. Також задано операцію декартового з'єднання мультимножин З

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

R Rs ,  . А кількість дублікатів рядка у результуючій таблиці задається рівністю

All



, де

Оскільки кожен рядок, що входить як в таблицю R t , 1 1 , так і в таблицю R t , 1 2 має кількість входжень рівну одиниці, то мінімальна кількість дублікатів цього рядка в таблиці

Кількість дублікатів знаходиться так:

Оскільки кількість дублікатів при перейменуванні не змінюється з огляду на ін'єктивність функції

Оскільки після застосування операції проекції до 1-мультимножини, ми не обов'язково отримаємо 1мультимножину, то результат різниці мультимножини та 1-мультимножини дасть мультимножину. Отже, множина T не замкнена відносно операції активного доповнення.

Таким чином, множина всіх таблиць табличної алгебри нескінченних таблиць T замкнена відносно операцій перетину, різниці, селекції, з'єднання та перейменування і не замкнена відносно об'єднання, проекції та активного доповнення. Отже, таблична алгебра нескінченних таблиць не утворює підалгебру мультимножинної табличної алгебри.

Висновки

Дана стаття є продовженням робіт присвячених актуальній проблемі розвитку теоретичної основи табличних баз даних. Основна увага в роботі зосереджена на питанні чи є таблична алгебра нескінченних таблиць підалгеброю мультимножинної табличної алгебри. Застосовуючи теоретико-множинні та логікоалгебраїчні методи встановлено, що це не так. Таблична алгебра нескінченних таблиць не утворює підалгебру мультимножинної табличної алгебри, бо не є замкненою відносно об'єднання, проекції та активного доповнення.

Література

Relational Databases: Table Algebras and SQL-like Language VNRedko 2001 Publishing house Academperiodica Kyiv Calculi and extensions of table algebras signature DBuy IMGlushko Nizhyn M. Gogol 2016 NDU im Multisets theory and its applications JABogatyreva A Thesis Submitted of the Requirements of the Kyiv National Taras Shevchenko University for the Degree of Doctor of Philosophy

Location

2011 Kyiv National Taras Shevchenko University Computability. An introduction to recursive function theory NCutland 1983 Myr Moscow ПроАвтора Глушко Ірина Миколаївна, кандидат фіз.-мат. наук, доцент кафедри інформаційних технологій та аналізу даних Ніжинського державного університету імені Миколи Гоголя. Кількість наукових публікацій в українських виданнях -приблизно 70. Кількість наукових публікацій в зарубіжних виданнях -8 вул. Графська 2. E-mail: