Outer Set Operations of Table Algebra of Infinite Tables

Table algebra of infinite tables is considered. The signature of table algebra of infinite tables is filled up with outer set operations. A formal mathematical semantics of these operations is defined.Problems in programming 2016; 2-3: 11-16

Збережено в:

Бібліографічні деталі
Дата:	2018
Автор:	Glushko, I.N.
Формат:	Стаття
Мова:	rus
Опубліковано:	Інститут програмних систем НАН України 2018
Теми:	relation databases table algebra of infinite tables outer union outer difference outer intersection UDC 004.655
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/175
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-175
record_format	ojs
resource_txt_mv	ppisoftskievua/de/8cb31449445d14cf24957563725a23de.pdf
spelling	pp_isofts_kiev_ua-article-1752024-04-28T13:09:54Z Outer Set Operations of Table Algebra of Infinite Tables Внешние множественные операции табличной алгебры бесконечных таблиц Зовнішні множинні операції табличної алгебри нескінченних таблиць Glushko, I.N. relation databases; table algebra of infinite tables; outer union; outer difference; outer intersection UDC 004.655 реляционные базы данных; табличная алгебра бесконечных таблиц; внешнее объединение; внешняя разница; внешнее пересечение УДК 004.655 реляційні бази даних; таблична алгебра нескінченних таблиць; зовнішнє об’єднання; зовнішня різниця; зовнішній перетин УДК 004.655 Table algebra of infinite tables is considered. The signature of table algebra of infinite tables is filled up with outer set operations. A formal mathematical semantics of these operations is defined.Problems in programming 2016; 2-3: 11-16 Рассматривается табличная алгебра бесконечных таблиц. Сигнатура табличной алгебры бесконечных таблиц пополнена внешними множественными операциями. Задано формальную математическую семантику этих операций и приведены примеры их применения.Problems in programming 2016; 2-3: 11-16 Розглядається таблична алгебра нескінченних таблиць. Сигнатура табличної алгебри нескінченних таблиць поповнена зовнішніми множинними операціями. Задано формальну математичну семантику цих операцій і наведено приклади їхзастосування.Problems in programming 2016; 2-3: 11-16 Інститут програмних систем НАН України 2018-07-06 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/175 10.15407/pp2016.02-03.011 PROBLEMS IN PROGRAMMING; No 2-3 (2016); 11-16 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2016); 11-16 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2016); 11-16 1727-4907 10.15407/pp2016.02-03 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/175/170 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2024-04-28T13:09:54Z
collection	OJS
language	rus
topic	relation databases table algebra of infinite tables outer union outer difference outer intersection UDC 004.655
spellingShingle	relation databases table algebra of infinite tables outer union outer difference outer intersection UDC 004.655 Glushko, I.N. Outer Set Operations of Table Algebra of Infinite Tables
topic_facet	relation databases table algebra of infinite tables outer union outer difference outer intersection UDC 004.655 реляционные базы данных табличная алгебра бесконечных таблиц внешнее объединение внешняя разница внешнее пересечение УДК 004.655 реляційні бази даних таблична алгебра нескінченних таблиць зовнішнє об’єднання зовнішня різниця зовнішній перетин УДК 004.655
format	Article
author	Glushko, I.N.
author_facet	Glushko, I.N.
author_sort	Glushko, I.N.
title	Outer Set Operations of Table Algebra of Infinite Tables
title_short	Outer Set Operations of Table Algebra of Infinite Tables
title_full	Outer Set Operations of Table Algebra of Infinite Tables
title_fullStr	Outer Set Operations of Table Algebra of Infinite Tables
title_full_unstemmed	Outer Set Operations of Table Algebra of Infinite Tables
title_sort	outer set operations of table algebra of infinite tables
title_alt	Внешние множественные операции табличной алгебры бесконечных таблиц Зовнішні множинні операції табличної алгебри нескінченних таблиць
description	Table algebra of infinite tables is considered. The signature of table algebra of infinite tables is filled up with outer set operations. A formal mathematical semantics of these operations is defined.Problems in programming 2016; 2-3: 11-16
publisher	Інститут програмних систем НАН України
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/175
work_keys_str_mv	AT glushkoin outersetoperationsoftablealgebraofinfinitetables AT glushkoin vnešniemnožestvennyeoperaciitabličnojalgebrybeskonečnyhtablic AT glushkoin zovníšnímnožinníoperacíítabličnoíalgebrineskínčennihtablicʹ
first_indexed	2024-09-16T04:07:29Z
last_indexed	2024-09-16T04:07:29Z
_version_	1818568143739551744
fulltext	Теоретичні та методологічні основи програмування © И.М. Глушко, 2016 ISSN 1727-4907. Проблеми програмування. 2016. № 2–3. Спеціальний випуск 11 УДК 004.655 ВНЕШНИЕ МНОЖЕСТВЕННЫЕ ОПЕРАЦИИ ТАБЛИЧНОЙ АЛГЕБРЫ БЕСКОНЕЧНЫХ ТАБЛИЦ И.М. Глушко Розглядається таблична алгебра нескінченних таблиць. Сигнатура табличної алгебри нескінченних таблиць поповнена зовнішніми множинними операціями. Задано формальну математичну семантику цих операцій і наведено приклади їх застосування. Ключові слова: реляційні бази даних, таблична алгебра нескінченних таблиць, зовнішнє об’єднання, зовнішня різниця, зовнішній перетин. Рассматривается табличная алгебра бесконечных таблиц. Сигнатура табличной алгебры бесконечных таблиц пополнена внешними множественными операциями. Задано формальную математическую семантику этих операций и приведены примеры их применения. Ключевые слова: реляционные базы данных, табличная алгебра бесконечных таблиц, внешнее объединение, внешняя разница, внешнее пересечение. Table algebra of infinite tables is considered. The signature of table algebra of infinite tables is filled up with outer set operations. A formal mathematical semantics of these operations is defined. Key words: relation databases, table algebra of infinite tables, outer union, outer difference, outer intersection. Введение Системы управления базами данных (СУБД) в настоящее время используются практически во всех сферах человеческой деятельности, связанных с сохранением и обработкой информации. Прогресс, достигнутый в области технологий баз данных, в значительной степени базируется на реляционной модели, предложенной Э. Коддом в 70-х годах ХХ в. Суть реляционного подхода составляет понятие реляции. Уточнение реляции в терминах именных множеств было совершено В.Н. Редько, Ю.И. Броной, Д.Б. Буем, С.А. Поляковым [1]. При таком уточнении рассматривается один универсальный домен, что позволяет исследовать общие свойства табличных манипуляций, не вводя к рассмотрению несущественные детали, и упростить рассуждения. В работе [2] введено к рассмотрению табличную алгебру бесконечных таблиц, которая является обобщением табличной алгебры предложенной в [1] и, в свою очередь, существенно обобщает классическую реляционную алгебру Кодда. Обобщение заключается в том, что под реляцией понимается произвольное множество односхемных строк, в частности, бесконечное, при этом каждой таблице приписывается определенная схема. В ходе развития коммерческих реляционных СУБД возникла потребность в использовании дополнительных операций, в частности, операций внутренних и внешних соединений, операции полусоединения, внешних множественных операций, агрегатных операций. Остановимся более подробно на внешних множественных операциях. Всем хорошо известны операции внешних соединений, которые позволяют учесть строки таблиц-аргументов, которые не попали в результат исходного внутреннего соединения. Кроме операций внешних соединений выделяют "внешние" версии других операторов реляционной алгебры, в частности объединения, пересечения и разности [3, 4]. Elmasri R. и Navathe S. описывают операцию внешнего объединения (outer union) таблиц [4]. Операция используется для объединения строк двух таблиц, схемы которых различны. Данные таблицы должны быть частично совместимы по объединению, то есть некоторые атрибуты должны быть одинаковы для обеих таблиц. Предполагается, что список одинаковых атрибутов содержит ключ для обеих таблиц. Строки, которые имеют тот же ключ в исходных таблицах, представлены в результирующей таблице только один раз и имеют значение для каждого атрибута. Атрибуты, которые являются различными для данных таблиц, тоже входят в схемы, а строки, не имеющие значения для этих атрибутов, пополняются значением Null. В книге в качестве примера рассмотрено внешнее объединение двух таблиц: STUDENT (Name, SSN, Department, Advisor) и FACULTY (Name, SSN, Department, Rank). В результате получаем таблицу R (Name, SSN, Department, Advisor, Rank), в которую включены все строки обеих таблиц. Строки таблицы STUDENT имеют значение Null для атрибута Rank, а строки таблицы FACULTY имеют значение Null для атрибута Advisor. Строка, которая в обеих таблицах имеет одинаковые значения для атрибутов Name, SSN, Department, будет иметь значение для всех атрибутов, то есть для атрибутов Name, SSN, Department, Advisor, Rank. Кодд Э. [10] кроме операции внешнего объединения, задает также операции внешнего пересечения (outer set intersection) и внешней разницы (outer set difference). При этом вводится понятие, которое является более общим за понятие равенства строк – понятие близкого аналога (close counterpart). Строка таблицы S является близким аналогом строки таблицы Т , если выполняются условия: • таблицы S и Т имеют одинаковые первичные ключи; • две строки (одна из S , а другая из Т ) имеют равные значения первичного ключа; Теоретичні та методологічні основи програмування 12 • попарное равенство известных значений сохраняется для тех атрибутов таблицы S , которые соответствуют атрибутам таблицы Т . По сути, вводится бинарное отношение на декартовом произведении таблиц S×T. Детальный анализ этого отношения и приведенных в [3, 4] примеров показывает, что отношение близкого аналога совпадает с отношением совместимости строк. Поэтому при задании внешних множественных операций используется именно отношение совместимости двух строк. Табличная алгебра бесконечных таблиц Рассмотрим два множества: A – множество атрибутов и D – универсальный домен. Произвольное (бесконечное) множество атрибутов AR назовем схемой. Рядком схемы R называется именное множество на паре R , D , проекция которого за первой компонентой равна R (то есть, по сути, рассматривается функция вида DRs : ). Под таблицей схемы R понимаем пару Rt, , где t – множество (в частности, бесконечное) строк указанной схемы R . В дальнейшем как   1 , Rt будем обозначать первую компоненту пары Rt, , то есть множество t . Множество всех строк (таблиц) схемы R обозначим )(RS (соответственно )(RT ), а множество всех строк (таблиц) – S (соответственно T ). Таким образом,  A )(   R RSS ,  ))((\|,)(T RSPtRtR  ,  A )(TT   R R , где )(XP – булеан множества X . Под табличной алгеброй бесконечных таблиц понимаем (частичную параметрическую) алгебру  ,,T P , где T – множество всех таблиц,             , A,,, , , ,,, 21 1 2 21 ~,,,,,,\,, Pp RRRX RR R R RR RXRpRRRP Rt – сигнатура, ,P – множество параметров. Операции сигнатуры задано в работе [2]. Внешние множественные операции Зададим формальную математическую семантику внешних множественных операции табличной алгебры бесконечных таблиц. Рассмотрим две таблицы 11,Rt и 22 ,Rt , причем 21 RR  . Для обозначения отсутствующих значений в результирующей таблице используется особый элемент универсального домена NULL . Обозначим через NULLRs , константную строку схемы R вида }{:, NULLRs NULLR  , которая присваивает всем атрибутам своей схемы значение NULL . Пусть )( ~ )()(: 2121 RRRR TTT  – некоторая частичная бинарная операция на множестве таблиц, причем выполняется включение    1 22 , 1112211 ,,,,, 21        RtRtRtRt RR  для всех dom,,, 2211 RtRt . Отметим, что операции внешних соединений 21,RR Cj (декартово соединение), 21,RR  (естественное соединение), 211 ,,,..., RRAA n  (соединение за атрибутами nAA ,...,1 ), 21,, RRp  (соединение за предикатом p ) именно такие. Зафиксируем таблицы 2211 ,,, RtRt с области определения операции  . Тогда таблица 11,Rt предполагает следующее представление: 12112111 ,,, 1 RttRttRt R    , где     11221121222111121 },,,,\|{, RRtRtsstsstssRtt     ,     11221121222111121 },,,,\|{, RRtRtsstsstssRtt     . Теоретичні та методологічні основи програмування 13 Другими словами, строки из таблицы 121 ,Rtt   используются при формировании результата соединения, а строки из таблицы 121 ,Rtt   не используются. Аналогичное представление таблицы 22 ,Rt получим, заменив роли таблиц 11,Rt , 22 ,Rt в представлении таблицы 11,Rt . Зададим операции внешнего объединения, внешней разницы и внешнего пересечения. Для всех операций схема результирующей таблицы равна объединению схем таблиц-аргументов. Определение 1. Внешним объединением (outer union) таблиц схем 1R и 2R называется бинарная параметрическая операция вида /\ 21,RR 1 )()()(: 2121 RRRR TTT  , причем 22,11 ,/\, 21 RtRt RR ,}{,,, 12 121 2,1 21 21 \ \, 12122 , 11 NULL RR RRR RR RR sRttRtRt RR          2112 \ RRRR  212 1,2 \, 212 , RRR Rtt RR   21\ \},{ 21 RRsNULL RR , где 121121 ,, 2,1 RttRtt RR    , а  – операция внешнего естественного соединения и ),(, 111 RRt T )(, 222 RRt T . Таким образом, результирующая таблица содержит строки, полученные в результате всяких объединений совместимых строк таблиц-аргументов, и строк первой и второй таблиц, которые не используются при формировании результата соединения, пополненные значением NULL для обозначения отсутствующих значений. Нужно отметить, что операция внешнего объединения является частичным случаем операции полного внешнего соединения, когда операция  является операцией внутреннего природного соединения. Пример 1. Рассмотрим табл. 1 и 2: 1,RСпортсмены со схемой 1R = {Фамилия, Имя, Группа, Факультет, Год_р} и 2, RОтличники со схемой 2R = {Фамилия, Имя, Группа, Форма_обуч}. Определим 1,RСпортсмены /\ 21,RR 2, RОтличники . Таблица 1. Спортсмены Фамилия Имя Группа Факультет Год_р Баков Семен МИ-11 Физико-математический 1991 Бойко Иван МЕз-31 Физико-математический 1988 Кайдан Юлия Ип-16 Историко-юридический 1991 Мыкытюк Ирина Ан-12 Иностранных языков 1990 Наменко Алина Уаз-21 Филологический 1989 Таблица 2. Отличники Фамилия Имя Группа Форма_обуч Борода Игорь ПФ-41 Дневная Бойко Иван МЕз-31 Заочная Кайдан Юлия ИП-16 Дневная Поданюк Павел СИ-11 Дневная 1 Для обозначения внешних множественных операций, как и Код используем знаки /\, , при этом указываем еще схемы таблиц-аргументов. Теоретичні та методологічні основи програмування 14 Результатом выполнения операции внешнего объединения данных таблиц является табл. 3 из схемой 3R = {Фамилия, Имя, Группа, Факультет, Год_р, Форма_обуч}. Таблица 3. Внешнее объединение Фамилия Имя Группа Факультет Год_р Форма_обуч Баков Семен МИ-11 Физико-математический 1991 NULL Бойко Иван МЕз-31 Физико-математический 1988 Заочная Кайдан Юлия ИП-16 Историко-юридический 1991 Дневная Мыкытюк Ирина АН-12 Иностранных языков 1990 NULL Наменко Алина УАз-21 Филологический 1989 NULL Борода Игорь ПФ-41 NULL NULL Дневная Поданюк Павел СИ-11 NULL NULL Дневная Для операции внешнего объединения имеет место равенство 11,2222,11 ,/\,,/\, 1221 RtRtRtRt RRRR   , которое аналогично коммутативности в силу коммутативности операции объединения 21,RR . Определение 2. Внешней разницей (outer difference) таблиц схем 1R и 2R называется бинарная параметрическая операция вида )()()(:/\\ 2121, 21 RRRRRR TTT  , причем              12\ \, 1211122,11 \},{,\,,/\\, 12 121 2,1 121 RRsRttRtRtRt Null RR RRR RRR RR  12\ \, 121 \},{, 12 121 2,1 RRsRtt Null RR RRR RR   , где ),(, 111 RRt T )(, 222 RRt T . Таким образом, результирующая таблица содержит те строки первой таблицы, пополненные значением NULL для обозначения отсутствующих значений, которые не используются при формировании результата соединения. Пример 2. Отыскать 2,1 ,/\\, 21 RОтличникиRСпортсмены RR и 1,2 ,/\\, 12 RСпортсменыRОтличники RR . В результате получим соответственно табл. 4 и табл. 5. Таблица 4. Внешняя разница 2,1 ,/\\, 21 RОтличникиRСпортсмены RR Фамилия Имя Группа Факультет Год_р Форма_обуч Баков Семен МИ-11 Физико-математический 1991 NULL Мыкытюк Ирина АН-12 Иностранных языков 1990 NULL Наменко Аліна УАз-21 Филологический 1989 NULL Таблица 5. Внешняя разница 1,2 ,/\\, 12 RСпортсменыRОтличники RR Фамилия Имя Группа Факультет Год_р Форма_обуч Борода Игорь ПФ-41 NULL NULL Дневная Поданюк Павло СИ-11 NULL NULL Дневная Теоретичні та методологічні основи програмування 15 Как видно из примера 2 операция внешней разницы не коммутативная, что является естественным, то есть 11,2222,11 ,/\\,,/\\, 1221 RtRtRtRt RRRR  . Если при определении операции внешнего пересечения (outer intersection) /\ 21,RR таблиц 11,Rt и 22 ,Rt применить рассуждения, использованные при определении предыдущих двух внешних множественных операций, то получим, что данная операция совпадает с операцией внутреннего естественного соединения 21,RR  . Пример 3. В результате применения операции внешнего пересечения таблиц 1,RСпотсмены и 2, RОтличники получим табл. 6. Таблица 6. Внешнее пересечение Фамилия Имя Группа Факультет Год_р Форма_обуч Бойко Иван МЕз-31 Физико-математический 1988 Заочна Кайдан Юлия ИП-16 Историко-юридический 1991 Дневная Теорема. Пусть схемы таблиц 11,Rt и 22 ,Rt совпадают и равны R . Тогда выполняются равенства: 1) RtRtRtRt RRR ,,,/\, 212,1   ; 2) RtRtRtRt RRR ,\,,/\\, 212,1  ; 3) RtRtRtRt RRR ,,,/\, 212,1   . Доказательство. При доказательстве теоремы используется бинарное отношение совместимости строк: '\|'\| 2121 RsRsss def  , где 21' RRR  , а 21, RR – схемы строк 21,ss соответственно. Здесь, Xs \| – ограничение строки s за множеством атрибутов X , которое понимается стандартно: )()D(\| 2 2sXsXsXs   . Основное свойство отношения совместимости заключается в следующем: 212121 )( ssRRSss   [1]. Далее доказывается каждое из равенств. 1. Доказательство следует из равенства 121 1 2 , 1 ,, ttRtRt RR        , то есть соединение таблиц одинаковых схем совпадает с их пересечением. Покажем это. Сначала установим включение 1 2 , 121 ,,        RtRttt RR  . Пусть 21 tts  , то есть 1ts и 2ts . Так как sss  и ss  (отношение совместимости  – рефлексивно), то 1 2 , 1 ,,        RtRts RR . Покажем обратное включение. Пусть 1 2 , 1 ,,        RtRts RR , тогда 21 sss  для 11 ts  и 22 ts  , причем 21 ss  . Учитывая, что sss 2 12 2 11 2 1   , а на односхемных строках совместимость переходит в равенство (так как схемы таблиц 11, Rt и 22 , Rt совпадают, то и таблица RtRt RR ,, 2 , 1  имеет ту же схему) имеем 21 sss  , то есть 21 tts  . 2. Покажем сначала включение   2112,1 \,/\\, ttRtRt RR  . Пусть   12,1 ,/\\, RtRts RR , тогда 21 1 , 21 ,, },{, ttRtts RRRR R             учтено, что  t}{ единица за соединением [1]. Отсюда Rts ,1 и  )( 2222 sstss  . Теоретичні та методологічні основи програмування 16 Покажем, что 2ts от противного. Пусть 2ts , тогда ss  (ибо отношение совместимости рефлексивное). Пришли к противоречию с установленным утверждением, что )( 2ss  для всех 22 ts  . Так как 1ts и 2ts имеем 21 \ tts . Покажем обратное включение. Пусть 21 \ tts , тогда 1ts и 2ts , следовательно, 21 tts  . Пусть 2' ts и ss ' , тогда, поскольку схемы таблиц-аргументов равны, то отношение совместимости переходит в равенство, то есть ss ' , а это противоречит предположению. Следовательно,  212 ''' ttsstss   (другими словами,  )'('' 2 sstss  ) и 1ts . Таким образом,   12,1 ,/\\, RtRts RR . 3. Докажем третье равенство используя цепочку равенств:    12,1 ,/\, RtRt RR             ,}{,,, , 212 , 1 ,  R R RR RttRtRt RR          1 , 12 },{, ,  R R Rtt RR  =  1 2 1 2, \ ,R Rt t R t t R 2 1 1 21 \ ,t t R t t . Выводы Данная работа посвящена актуальной проблеме развития теоретической основы табличных баз данных, в качестве которой выступают табличные алгебры. Табличные алгебры построены на основе хорошо известных реляционных алгебры Кодда и существенно их обобщают. Основное внимание сосредоточено на определении формальной математической семантике внешних множественных операции табличной алгебры бесконечных таблиц. В качестве идеологического, теоретического и концептуального базиса в работе используются принципы и положения школы композиционного программирования академика НАН Украины В.Н. Редько. 1. Редько В.Н., Брона Ю.Й., Буй Д.Б. та ін. Реляційні бази даних: табличні алгебри та SQL-подібні мови – К.: Видавничий дім "Академперіодика", 2001. – 198 с. 2. Глушко І.М. Таблична алгебра нескінченних (скінченних) таблиць // Матеріали 9-ї Міжнародної конференції "Теоретичні та прикладні аспекти побудови програмних систем" (3-7 грудня 2012 р., м. Київ). – К.; 2012. – С. 83–87. 3. Codd E.F. The Relational Model for Database Management: Version 2. – Addison-Wesley, 1990. – 541 р. 4. Elmasri R., Navathe S. Fundamental of Database Systems: [3rd Edition] – Addison-Wesley, 2000. – 893 p. References 1. REDKO, V.N. et al. (2001) Relational Databases: Table Algebras and SQL-like Language. Kyiv: Publishing house Academperiodica. 2. GLUSHKO, І.М. (2012) Table Algebra of infinite (finite) tables. In International conference Theoretical and Applied Aspects of Program Systems Development. Kyiv, 3rd to 7th Decemder 2012. Kyiv. P. 83–87. 3. CODD, E.F. (1990) The Relational Model for Database Management: Version 2. Addison-Wesley. 4. ELMASRI, R. & NAVATHE, S. (2000) Fundamental of Database Systems. Addison-Wesley. Об авторе: Глушко Ирина Николаевна, кандидат физико-математических наук, доцент кафедры Прикладной математики, информатики и образовательных измерений. Количество научных публикаций в украинских изданиях – 50. Количество научных публикаций в иностранных изданиях – 5. http://orcid.org/0000-0003-2549-5356. Место работы автора: Нежинский государственный университет имени Николая Гоголя, 16600, Украина, Черниговская обл., г. Нежин, ул. Крапивянского 2. Е-mail: iryna.glushko@ndu.edu.ua, glushkoim@gmail.com mailto:iryna.glushko@ndu.edu.ua mailto:glushkoim@gmail.com

Outer Set Operations of Table Algebra of Infinite Tables

Репозитарії

Схожі ресурси