Розглядається таблична алгебра нескінченних таблиць. Сигнатура табличної алгебри нескінченних таблиць поповнена зовнішніми множинними операціями. Задано формальну математичну семантику цих операцій і наведено приклади їх застосування. Ключові слова: реляційні бази даних, таблична алгебра нескінченних таблиць, зовнішнє об'єднання, зовнішня різниця, зовнішній перетин. Рассматривается табличная алгебра бесконечных таблиц. Сигнатура табличной алгебры бесконечных таблиц пополнена внешними множественными операциями. Задано формальную математическую семантику этих операций и приведены примеры их применения. Ключевые слова: реляционные базы данных, табличная алгебра бесконечных таблиц, внешнее объединение, внешняя разница, внешнее пересечение. 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.
• попарное равенство известных значений сохраняется для тех атрибутов таблицы S , которые соответствуют атрибутам таблицы Т .
По сути, вводится бинарное отношение на декартовом произведении таблиц S×T. Детальный анализ этого отношения и приведенных в [3, 4] примеров показывает, что отношение близкого аналога совпадает с отношением совместимости строк. Поэтому при задании внешних множественных операций используется именно отношение совместимости двух строк. Табличная алгебра бесконечных таблиц указанной схемы 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 , R1⊗,R2, ÷RR1 , Rtξ ,R , ~ R ⎬ 2 ⎭ X ,R,R1,R2⊆A – сигнатура, P, Ξ – множество параметров. Операции сигнатуры задано в работе [2]. Внешние множественные операции
Зададим формальную математическую семантику внешних множественных операции табличной алгебры бесконечных таблиц.
Рассмотрим две таблицы t1, R1 и t2 , R2 , причем R1 I R2 ≠ ∅ . Для обозначения отсутствующих значений в результирующей таблице используется особый элемент универсального домена NULL . Обозначим через sR,NULL константную строку схемы R вида sR,NULL : R → {NULL} , которая присваивает всем атрибутам своей схемы значение NULL .
Пусть ϕ :T (R1) × T (R2 ) →~ T (R1 U R2 ) – некоторая частичная бинарная операция на множестве таблиц, причем выполняется включение (ϕ ( t1, R1 , t2 , R2 ))1 ⊆ ⎛⎜⎝ t1, R1 R1⊗,R2 t2 , R2 ⎞⎟⎠ для всех t1, R1 , t2 , R2 ∈ domϕ . 1 Отметим, что операции внешних соединений Cj (декартово соединение), ⊗ (естественное соединение),
R1,R2 R1,R2 (соединение за атрибутами A1,..., An ), (соединение за предикатом p ) именно такие.
⊗ p,R1,R2 Зафиксируем таблицы t1, R1 , t2 , R2
с области определения операции ϕ . Тогда таблица t1, R1 предполагает следующее представление: где
t1, R1 = t1 Iϕt2 , R1 U R1 t1 ϕ−t2 , R1 , t1 Iϕt2 , R1 = {s1 | s1 ∈ t1 ∧ ∃s2 (s2 ∈ t2 ∧ s1 U s2 ∈ (ϕ ( t1, R1 , t2 , R2 ))1 )}, R1 , t1 ϕ−t2 , R1 = {s1 | s1 ∈ t1 ∧ ∀s2 (s2 ∈ t2 ⇒ s1 U s2 ∉ (ϕ ( t1, R1 , t2 , R2 ))1 )}, R1 . t1 Iϕt2 , R1 Другими словами, строки из таблицы используются при формировании результата соединения, а строки из таблицы t1 ϕ−t2 , R1
не используются. Аналогичное представление таблицы t2 , R2 получим, заменив роли таблиц t1, R1 , t2 , R2 в представлении таблицы t1, R1 .
Зададим операции внешнего объединения, внешней разницы и внешнего пересечения. Для всех операций схема результирующей таблицы равна объединению схем таблиц-аргументов.
Определение 1. Внешним объединением (outer union) таблиц схем R1 и R2 называется бинарная параметрическая операция вида
\UR1,R2 / 1 : T (R1) × T (R2 ) → T (R1 U R2 ) , = ⎜⎝⎛ t1, R1 R1⊗,R2 t2 , R2 ⎟⎠⎞ U R1UR2 t1 −⊗ t2 , R1 R1,⊗R2\R1 {sRN2U\RL1L}, R2 \ R1 U R1 UR2
R1,R2 t2 ⊗− t1, R2 R2,⊗R1\R2 {sRN1U\LRL2 }, R1 \ R2 ,
R2,R1
Таким образом, результирующая таблица содержит строки, полученные в результате всяких объединений совместимых строк таблиц-аргументов, и строк первой и второй таблиц, которые не используются при формировании результата соединения, пополненные значением NULL для обозначения отсутствующих значений.
Нужно отметить, что операция внешнего объединения является частичным случаем операции полного внешнего соединения, когда операция ϕ является операцией внутреннего природного соединения. Пример 1. Рассмотрим табл. 1 и 2: Спортсмены, R1 со схемой R1 = {Фамилия, Имя, Группа, Факультет, Год_р} и Отличники, R2
со схемой R2 = {Фамилия, Имя, Группа, Форма_обуч}. Определим Спортсмены, R1 \ U R1,R2 / Отличники, R2 .
Таблица 1. Спортсмены Результатом выполнения операции внешнего объединения данных таблиц является табл. 3 из схемой R3 = {Фамилия, Имя, Группа, Факультет, Год_р, Форма_обуч}.
Таблица 3. Внешнее объединение Как видно из примера 2 операция внешней разницы не коммутативная, что является естественным, то есть
t1, R1 \ \ R1,R2 / t2 , R2 ≠ t2 , R2 \ \ R2,R1 / t1, R1 .
Если при определении операции внешнего пересечения (outer intersection) \IR1,R2 / таблиц t1, R1 и t2 , R2 применить рассуждения, использованные при определении предыдущих двух внешних множественных операций, то получим, что данная операция совпадает с операцией внутреннего естественного соединения ⊗ .
R1,R2 Пример 3. В результате применения операции внешнего пересечения таблиц Отличники, R2 получим табл. 6. Спотсмены, R1 и Таблица 6. Внешнее пересечение
2. Покажем сначала включение ( t1, R \\R,R/ t2 , R )1 ⊆ t1 \ t2 . Пусть s ∈ ( t1, R \\R,R/ t2 , R )1 , тогда ⎛ ⎞ s ∈ ⎜⎜ t1 −⊗ t2 , R ⊗ {ε },∅ ⎟⎟ = t1 −⊗ t2 учтено, что {ε } = tε единица за соединением [1]. Отсюда s ∈ t1, R и ⎝ R,R R,∅ ⎠1 R,R ∀s2 (s2 ∈ t2 ⇒ ¬(s ≈ s2 )) . рефлексивное). Пришли к противоречию с установленным утверждением, что ¬(s ≈ s2 ) для всех s2 ∈ t2 . Так как s ∈ t1 и s ∉ t2 имеем s ∈ t1 \ t2 .
Покажем обратное включение. Пусть s ∈ t1 \ t2 , тогда s ∈ t1 и s ∉ t2 , следовательно, s ∉ t1 I t2 . Пусть (другими словами, ∀s'(s'∈ t2 ⇒ ¬(s'≈ s)) ) и s ∈ t1 . Таким образом, s ∈ ( t1, R \\R,R/ t2 , R )1 . ∃s'∈ t2 и s' ≈ s , тогда, поскольку схемы таблиц-аргументов равны, то отношение совместимости переходит в равенство, то есть s' = s , а это противоречит предположению. Следовательно, ∀s'(s'∈ t2 ⇒ s'Us ∉ t1 I t2 ) 3. Докажем третье равенство используя цепочку равенств:
( t1, R \UR,R / t2 , R )1 = ⎛ ⎞ ⎞ = ⎜⎜⎛⎝ t1, R R⊗,R t2 , R ⎟ U R t1 ⊗− t2 , R ⊗ {ε }, ∅ U R t2 ⊗− t1, 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 . Выводы
Данная работа посвящена актуальной проблеме развития теоретической основы табличных баз данных, в качестве которой выступают табличные алгебры. Табличные алгебры построены на основе хорошо известных реляционных алгебры Кодда и существенно их обобщают. Основное внимание сосредоточено на определении формальной математической семантике внешних множественных операции табличной алгебры бесконечных таблиц. В качестве идеологического, теоретического и концептуального базиса в работе используются принципы и положения школы композиционного программирования академика НАН Украины В.Н. Редько.