=Paper=
{{Paper
|id=Vol-1631/11-16
|storemode=property
|title=Outer Set Operations of Table Algebra of Infinite Tables
|pdfUrl=https://ceur-ws.org/Vol-1631/11-16.pdf
|volume=Vol-1631
|authors=Irina Glushko
|dblpUrl=https://dblp.org/rec/conf/ukrprog/Glushko16
}}
==Outer Set Operations of Table Algebra of Infinite Tables==
https://ceur-ws.org/Vol-1631/11-16.pdf
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
УДК 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 , а другая из Т ) имеют равные значения первичного ключа;
11
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
• попарное равенство известных значений сохраняется для тех атрибутов таблицы S , которые
соответствуют атрибутам таблицы Т .
По сути, вводится бинарное отношение на декартовом произведении таблиц S×T. Детальный анализ
этого отношения и приведенных в [3, 4] примеров показывает, что отношение близкого аналога совпадает с
отношением совместимости строк. Поэтому при задании внешних множественных операций используется
именно отношение совместимости двух строк.
Табличная алгебра бесконечных таблиц
Рассмотрим два множества: A – множество атрибутов и D – универсальный домен. Произвольное
(бесконечное) множество атрибутов R ⊆ A назовем схемой.
Рядком схемы R называется именное множество на паре R , D , проекция которого за первой
компонентой равна R (то есть, по сути, рассматривается функция вида s : R → D ).
Под таблицей схемы R понимаем пару t, R , где t – множество (в частности, бесконечное) строк
указанной схемы R . В дальнейшем как ( t , R )1 будем обозначать первую компоненту пары t, R , то есть
множество t .
Множество всех строк (таблиц) схемы R обозначим S (R ) (соответственно T (R ) ), а множество всех
строк (таблиц) – S (соответственно T ). Таким образом,
S = U S ( R ) , T ( R ) = { t , R | t ∈ P( S ( R))}, T = U T ( R ) ,
R⊆A R⊆A
где P( X ) – булеан множества X .
Под табличной алгеброй бесконечных таблиц понимаем (частичную параметрическую) алгебру
T, Ω P ,Ξ , где T – множество всех таблиц,
p∈P ,ξ ∈Ξ
⎧ ⎫
Ω P ,Ξ = ⎨U R , I R , \ R ,σ p , R , π X , R , ⊗ , ÷ RR1 , Rtξ ,R , ~ R ⎬
⎩ R ,
1 2R 2
⎭ X , R , R1 , R2 ⊆ A
– сигнатура, P , Ξ – множество параметров. Операции сигнатуры задано в работе [2].
Внешние множественные операции
Зададим формальную математическую семантику внешних множественных операции табличной алгебры
бесконечных таблиц.
Рассмотрим две таблицы t1 , R1 и t 2 , R2 , причем R1 I R2 ≠ ∅ . Для обозначения отсутствующих
значений в результирующей таблице используется особый элемент универсального домена NULL . Обозначим
через s R , NULL константную строку схемы R вида s R, NULL : R → {NULL} , которая присваивает всем атрибутам
своей схемы значение NULL .
~ T ( R U R ) – некоторая частичная бинарная операция на множестве таблиц,
Пусть ϕ : T ( R1 ) × T ( R2 ) → 1 2
причем выполняется включение (ϕ ( t1 , R1 , t 2 , R2 ))1 ⊆ ⎜ t1 , R1 ⊗ t 2 , R2 ⎟ для всех t1 , R1 , t 2 , R2 ∈ dom ϕ .
⎛ ⎞
⎝ R ,
1 2R ⎠1
Отметим, что операции внешних соединений Cj (декартово соединение), ⊗ (естественное соединение),
R1 ,R2 R1 ,R2
⊗ (соединение за атрибутами A1 ,..., An ), ⊗ (соединение за предикатом p ) именно такие.
A1 ,..., An , R1 , R2 p , R1 , R2
Зафиксируем таблицы t1 , R1 , t 2 , R2 с области определения операции ϕ . Тогда таблица t1 , R1
предполагает следующее представление:
t1 , R1 = t1 I t 2 , R1 U R1 t1 − t 2 , R1 ,
ϕ ϕ
где
(
t1 I t 2 , R1 = {s1 | s1 ∈ t1 ∧ ∃s2 s2 ∈ t 2 ∧ s1 U s2 ∈ (ϕ ( t1 , R1 , t 2 , R2 ))1 }, R1 ,
ϕ
)
(
t1 − t 2 , R1 = {s1 | s1 ∈ t1 ∧ ∀s 2 s 2 ∈ t 2 ⇒ s1 U s 2 ∉ (ϕ ( t1 , R1 , t 2 , R2 ))1 }, R1 .
ϕ
)
12
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
Другими словами, строки из таблицы t1 I t 2 , R1 используются при формировании результата
ϕ
соединения, а строки из таблицы t1 − t 2 , R1 не используются. Аналогичное представление таблицы t 2 , R2
ϕ
получим, заменив роли таблиц t1 , R1 , t 2 , R2 в представлении таблицы t1 , R1 .
Зададим операции внешнего объединения, внешней разницы и внешнего пересечения. Для всех операций
схема результирующей таблицы равна объединению схем таблиц-аргументов.
Определение 1. Внешним объединением (outer union) таблиц схем R1 и R2 называется бинарная
параметрическая операция вида
\ U R1 ,R2 / 1 : T ( R1 ) × T ( R2 ) → T ( R1 U R2 ) ,
причем
t1 , R1 \ U R1 , R2 / t 2 , R2 =
⎛ ⎞
= ⎜ t1 , R1 ⊗ t 2 , R2 ⎟ U R1U R2 t1 − t 2 , R1 ⊗ {s RNULL
2 \ R1
}, R2 \ R1 U R1 U R2 t 2 − t1 , R2 ⊗ {s RNULL
1 \ R2
}, R1 \ R2 ,
⎝ R ,
1 2R ⎠ ⊗
R1 , R2
R1 , R2 \ R1 ⊗
R2 , R1
R2 , R1 \ R 2
где t1 − t 2 , R1 = t1 − t 2 , R1 , а ϕ – операция внешнего естественного соединения и t1 , R1 ∈ T ( R1 ),
⊗ ϕ
R1 , R2
t 2 , R2 ∈ T ( R2 ) .
Таким образом, результирующая таблица содержит строки, полученные в результате всяких
объединений совместимых строк таблиц-аргументов, и строк первой и второй таблиц, которые не используются
при формировании результата соединения, пополненные значением NULL для обозначения отсутствующих
значений.
Нужно отметить, что операция внешнего объединения является частичным случаем операции полного
внешнего соединения, когда операция ϕ является операцией внутреннего природного соединения.
Пример 1. Рассмотрим табл. 1 и 2: Спортсмены, R1 со схемой R1 = {Фамилия, Имя, Группа,
Факультет, Год_р} и Отличники , R2 со схемой R2 = {Фамилия, Имя, Группа, Форма_обуч}. Определим
Спортсмены, R1 \ U R1 ,R2 / Отличники , R2 .
Таблица 1. Спортсмены
Фамилия Имя Группа Факультет Год_р
Баков Семен МИ-11 Физико-математический 1991
Бойко Иван МЕз-31 Физико-математический 1988
Кайдан Юлия Ип-16 Историко-юридический 1991
Мыкытюк Ирина Ан-12 Иностранных языков 1990
Наменко Алина Уаз-21 Филологический 1989
Таблица 2. Отличники
Фамилия Имя Группа Форма_обуч
Борода Игорь ПФ-41 Дневная
Бойко Иван МЕз-31 Заочная
Кайдан Юлия ИП-16 Дневная
Поданюк Павел СИ-11 Дневная
1
Для обозначения внешних множественных операций, как и Код используем знаки \, / , при этом указываем
еще схемы таблиц-аргументов.
13
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
Результатом выполнения операции внешнего объединения данных таблиц является табл. 3 из схемой
R3 = {Фамилия, Имя, Группа, Факультет, Год_р, Форма_обуч}.
Таблица 3. Внешнее объединение
Фамилия Имя Группа Факультет Год_р Форма_обуч
Баков Семен МИ-11 Физико-математический 1991 NULL
Бойко Иван МЕз-31 Физико-математический 1988 Заочная
Кайдан Юлия ИП-16 Историко-юридический 1991 Дневная
Мыкытюк Ирина АН-12 Иностранных языков 1990 NULL
Наменко Алина УАз-21 Филологический 1989 NULL
Борода Игорь ПФ-41 NULL NULL Дневная
Поданюк Павел СИ-11 NULL NULL Дневная
Для операции внешнего объединения имеет место равенство
t1 , R1 \ U R1 ,R2 / t 2 , R2 = t 2 , R2 \ U R2 ,R1 / t1 , R1 ,
которое аналогично коммутативности в силу коммутативности операции объединения U R1 ,R2 .
Определение 2. Внешней разницей (outer difference) таблиц схем R1 и R2 называется бинарная
параметрическая операция вида
\\ R1 , R2 / : T ( R1 ) × T ( R2 ) → T ( R1 U R2 ) ,
причем
⎛ ⎞
⎜ ⎟
t1 , R1 \ \ R1 ,R2 / t 2 , R2 = ⎜ t1 , R1 \ R1 t1 I t 2 , R1 ⎟ R ,⊗ {s RNull
2 \ R1
}, R2 \ R1 = t1 − t 2 , R1 ⊗ {s RNull
2 \ R1
}, R2 \ R1 ,
⎜ ⊗ ⎟ 1 2 1
R \ R ⊗ R1 , R2 \ R1
⎝ R1 , R2 ⎠ R1 , R2
где t1 , R1 ∈ T ( R1 ), t2 , R2 ∈ T ( R2 ) .
Таким образом, результирующая таблица содержит те строки первой таблицы, пополненные значением
NULL для обозначения отсутствующих значений, которые не используются при формировании результата
соединения.
Пример 2. Отыскать
Спортсмены, R1 \ \ R1 , R2 / Отличники , R2 и Отличники , R2 \ \ R2 , R1 / Спортсмены, R1 .
В результате получим соответственно табл. 4 и табл. 5.
Таблица 4. Внешняя разница Спортсмены, R1 \ \ R1 , R2 / Отличники , R 2
Фамилия Имя Группа Факультет Год_р Форма_обуч
Баков Семен МИ-11 Физико-математический 1991 NULL
Мыкытюк Ирина АН-12 Иностранных языков 1990 NULL
Наменко Аліна УАз-21 Филологический 1989 NULL
Таблица 5. Внешняя разница Отличники , R 2 \ \ R2 , R1 / Спортсмены, R1
Фамилия Имя Группа Факультет Год_р Форма_обуч
Борода Игорь ПФ-41 NULL NULL Дневная
Поданюк Павло СИ-11 NULL NULL Дневная
14
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
Как видно из примера 2 операция внешней разницы не коммутативная, что является естественным, то
есть
t1 , R1 \ \ R1 ,R2 / t 2 , R2 ≠ t 2 , R2 \ \ R2 ,R1 / t1 , R1 .
Если при определении операции внешнего пересечения (outer intersection) \ I R1 ,R2 / таблиц t1 , R1 и
t 2 , R2 применить рассуждения, использованные при определении предыдущих двух внешних
множественных операций, то получим, что данная операция совпадает с операцией внутреннего естественного
соединения ⊗ .
R1 ,R2
Пример 3. В результате применения операции внешнего пересечения таблиц Спотсмены, R1 и
Отличники , R2 получим табл. 6.
Таблица 6. Внешнее пересечение
Фамилия Имя Группа Факультет Год_р Форма_обуч
Бойко Иван МЕз-31 Физико-математический 1988 Заочна
Кайдан Юлия ИП-16 Историко-юридический 1991 Дневная
Теорема. Пусть схемы таблиц t1 , R1 и t 2 , R2 совпадают и равны R . Тогда выполняются равенства:
1) t1 , R \ I R ,R / t 2 , R = t1 , R I R t 2 , R ;
2) t1 , R \\ R ,R / t 2 , R = t1 , R \ R t 2 , R ;
3) t1 , R \ U R,R / t 2 , R = t1 , R U R t 2 , R .
Доказательство.
При доказательстве теоремы используется бинарное отношение совместимости строк:
def
s1 ≈ s2 ⇔ s1 | R' = s2 | R' , где R ' = R1 I R2 , а R1 , R2 – схемы строк s1 , s 2 соответственно. Здесь, s | X –
ограничение строки s за множеством атрибутов X, которое понимается стандартно:
s | X = s I ( X × D) = s I ( X × π 22 s) . Основное свойство отношения совместимости заключается в следующем:
s1 U s2 ∈ S ( R1 U R2 ) ⇔ s1 ≈ s2 [1].
Далее доказывается каждое из равенств.
⎛ ⎞
1. Доказательство следует из равенства ⎜ t1 , R ⊗ t 2 , R ⎟ = t1 I t 21 , то есть соединение таблиц
⎝ R , R ⎠1
одинаковых схем совпадает с их пересечением. Покажем это. Сначала установим включение
⎛ ⎞
t1 I t 2 ⊆ ⎜ t1 , R ⊗ t 2 , R ⎟ . Пусть s ∈ t1 I t 2 , то есть s ∈ t1 и s ∈ t 2 . Так как s = s U s и s ≈ s (отношение
⎝ R, R ⎠1
⎛ ⎞
совместимости ≈ – рефлексивно), то s ∈ ⎜ t1 , R ⊗ t 2 , R ⎟ . Покажем обратное включение. Пусть
⎝ R,R ⎠1
⎛ ⎞
s ∈ ⎜ t1 , R ⊗ t 2 , R ⎟ , тогда s = s1 U s2 для s1 ∈ t1 и s2 ∈ t 2 , причем s1 ≈ s2 . Учитывая, что π 12 s1 = π 12 s2 = π 12 s , а
⎝ R,R ⎠1
на односхемных строках совместимость переходит в равенство (так как схемы таблиц t1 , R1 и t 2 , R2
совпадают, то и таблица t1 , R ⊗ t 2 , R имеет ту же схему) имеем s = s1 = s2 , то есть s ∈ t1 I t 2 .
R,R
2. Покажем сначала включение ( t1, R \\ R,R / t2 , R )1 ⊆ t1 \ t2 . Пусть s ∈ ( t1 , R \\ R,R / t2 , R )1 , тогда
⎛ ⎞
s ∈ ⎜ t1 − t 2 , R ⊗ {ε }, ∅ ⎟ = t1 − t 2 учтено, что {ε } = tε единица за соединением [1]. Отсюда s ∈ t1 , R и
⎜ ⊗ R ,∅ ⎟ ⊗
⎝ R ,R ⎠1 R ,R
∀s2 (s2 ∈ t 2 ⇒ ¬( s ≈ s2 ) ) .
15
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine)
Покажем, что s ∉ t 2 от противного. Пусть s ∈ t 2 , тогда s ≈ s (ибо отношение совместимости
рефлексивное). Пришли к противоречию с установленным утверждением, что ¬( s ≈ s2 ) для всех s2 ∈ t 2 .
Так как s ∈ t1 и s ∉ t 2 имеем s ∈ t1 \ t 2 .
Покажем обратное включение. Пусть s ∈ t1 \ t 2 , тогда s ∈ t1 и s ∉ t 2 , следовательно, s ∉ t1 I t 2 . Пусть
∃s '∈ t 2 и s ' ≈ s , тогда, поскольку схемы таблиц-аргументов равны, то отношение совместимости переходит в
равенство, то есть s ' = s , а это противоречит предположению. Следовательно, ∀s ' (s '∈ t 2 ⇒ s 'U s ∉ t1 I t 2 )
(другими словами, ∀s ' (s '∈ t 2 ⇒ ¬( s ' ≈ s ) ) ) и s ∈ t1 . Таким образом, s ∈ ( t1 , R \\ R,R / t 2 , R )1 .
3. Докажем третье равенство используя цепочку равенств:
( t1 , R \U R,R / t2 , R )1 =
⎛ ⎞
⎛ ⎞
= ⎜ ⎜ t1 , R ⊗ t 2 , R ⎟ U R t1 − t 2 , R ⊗ {ε }, ∅ U R t 2 − t1 , R ⊗ {ε }, ∅ ⎟ =
⎜⎝ R,R ⎠ ⊗ R ,∅ ⊗ R ,∅ ⎟
⎝ R,R R ,R ⎠1
= ( t1 I t2 , R U R t1 \ t2 , R U R t2 \ t1 , R )1 = t1 U t2 .
Выводы
Данная работа посвящена актуальной проблеме развития теоретической основы табличных баз данных, в
качестве которой выступают табличные алгебры. Табличные алгебры построены на основе хорошо известных
реляционных алгебры Кодда и существенно их обобщают. Основное внимание сосредоточено на определении
формальной математической семантике внешних множественных операции табличной алгебры бесконечных
таблиц. В качестве идеологического, теоретического и концептуального базиса в работе используются
принципы и положения школы композиционного программирования академика НАН Украины В.Н. Редько.
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
16