О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения
В работе найдены необходимые и достаточные условия, при которых в табличных алгебрах операция насыщения дистрибутивна относительно операций объединения и пересечения таблиц. Приведены примеры, иллюстрирующие данные критерии. В роботi знайдено необхiднi та достатнi умови, за яких у табличних алгебрах...
Saved in:
| Published in: | Труды Института прикладной математики и механики |
|---|---|
| Date: | 2013 |
| Main Author: | |
| Language: | Russian |
| Published: |
Інститут прикладної математики і механіки НАН України
2013
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/124169 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения / А.С. Сенченко // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2013. — Т. 26. — С. 197-204. — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-124169 |
|---|---|
| record_format |
dspace |
| spelling |
Сенченко, А.С. 2017-09-21T16:23:34Z 2017-09-21T16:23:34Z 2013 О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения / А.С. Сенченко // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2013. — Т. 26. — С. 197-204. — Бібліогр.: 2 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/124169 004.655 В работе найдены необходимые и достаточные условия, при которых в табличных алгебрах операция насыщения дистрибутивна относительно операций объединения и пересечения таблиц. Приведены примеры, иллюстрирующие данные критерии. В роботi знайдено необхiднi та достатнi умови, за яких у табличних алгебрах операцiя насичення є дистрибутивною вiдносно операцiй об’єднання та перетину таблиць. Наведенi приклади, що iлюструють знайденi критерiї. In this paper there is found the necessary and sufficient conditions due to which a saturation operation is distributive to operations join and intersection. This conditions are illustrated in examples. ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения Про дистрибутивнiсть в табличних алгебрах операцiї насичення вiдносно операцiй об’єднання та перетину On a distributivity of a saturation to join and intersection in table algebra published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения |
| spellingShingle |
О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения Сенченко, А.С. |
| title_short |
О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения |
| title_full |
О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения |
| title_fullStr |
О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения |
| title_full_unstemmed |
О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения |
| title_sort |
о дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения |
| author |
Сенченко, А.С. |
| author_facet |
Сенченко, А.С. |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Труды Института прикладной математики и механики |
| publisher |
Інститут прикладної математики і механіки НАН України |
| title_alt |
Про дистрибутивнiсть в табличних алгебрах операцiї насичення вiдносно операцiй об’єднання та перетину On a distributivity of a saturation to join and intersection in table algebra |
| description |
В работе найдены необходимые и достаточные условия, при которых в табличных алгебрах операция насыщения дистрибутивна относительно операций объединения и пересечения таблиц. Приведены примеры, иллюстрирующие данные критерии.
В роботi знайдено необхiднi та достатнi умови, за яких у табличних алгебрах операцiя насичення є дистрибутивною вiдносно операцiй об’єднання та перетину таблиць. Наведенi приклади, що iлюструють знайденi критерiї.
In this paper there is found the necessary and sufficient conditions due to which a saturation operation is distributive to operations join and intersection. This conditions are illustrated in examples.
|
| issn |
1683-4720 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124169 |
| citation_txt |
О дистрибутивности в табличных алгебрах операции насыщения относительно операций объединения и пересечения / А.С. Сенченко // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2013. — Т. 26. — С. 197-204. — Бібліогр.: 2 назв. — рос. |
| work_keys_str_mv |
AT senčenkoas odistributivnostivtabličnyhalgebrahoperaciinasyŝeniâotnositelʹnooperaciiobʺedineniâiperesečeniâ AT senčenkoas prodistributivnistʹvtabličnihalgebrahoperaciínasičennâvidnosnooperaciiobêdnannâtaperetinu AT senčenkoas onadistributivityofasaturationtojoinandintersectionintablealgebra |
| first_indexed |
2025-11-25T22:43:39Z |
| last_indexed |
2025-11-25T22:43:39Z |
| _version_ |
1850570092483444736 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2013. Том 26
УДК 004.655
c©2013. А.С. Сенченко
О ДИСТРИБУТИВНОСТИ В ТАБЛИЧНЫХ АЛГЕБРАХ
ОПЕРАЦИИ НАСЫЩЕНИЯ ОТНОСИТЕЛЬНО ОПЕРАЦИЙ
ОБЪЕДИНЕНИЯ И ПЕРЕСЕЧЕНИЯ
В работе найдены необходимые и достаточные условия, при которых в табличных алгебрах опера-
ция насыщения дистрибутивна относительно операций объединения и пересечения таблиц. Приве-
дены примеры, иллюстрирующие данные критерии.
Ключевые слова: табличная алгебра, насыщение, база данных.
1. Введение. В настоящее время системы управления базами данных широко
используются практически во всех сферах деятельности человека. Наиболее распро-
странённой является реляционная модель данных, впервые предложенная Э. Код-
дом в 1970 году. С математической точки зрения реляционная база данных являет-
ся конечным набором конечных отношений различной размерности между заранее
определёнными множествами элементарных данных.
Табличные алгебры, введённые В.Н. Редько и Д.Б. Буем, построены на основе
реляционных алгебр Э. Кодда и существенно их уточняют. Они составляют теорети-
ческий фундамент языков запросов современных табличных баз данных. Элементы
носителя табличной алгебры уточняют реляционные структуры данных, а сигнатур-
ные операции построены на базе основных табличных манипуляций в реляционных
алгебрах и языке SQL.
В ставшей уже классической монографии по табличным алгебрам [1] найдено и
доказано много различных свойств операций табличных алгебр. В настоящей работе
найдены и доказаны необходимые и достаточные условия, при которых некоторые
включения, доказанные в [1], превращаются в равенства.
2. Основные определения. Зафиксируем некоторое непустое множество A =
{A1, . . . , An}, элементы которого называются атрибутами. Произвольное конечное
подмножество R = {A′1, . . . , A′k} ⊆ A назовем схемой, причем схема может яв-
ляться пустым множеством. Строкой s схемы R называется множество пар s =
{(A′1, d1), . . . , (A′k, dk)}, проекция которого по первой компоненте равна R. Таблицей
схемы R называется конечное множество строк схемы R. Далее в работе рассматри-
ваем таблицы схемы R с количеством атрибутов k. На множестве всех таких таблиц
введены такие операции:
1) объединение
⋃
двух таблиц – таблица, состоящая из тех и только тех строк,
которые принадлежат хоть одной из исходных таблиц;
2) пересечение
⋂
двух таблиц – таблица, состоящая из тех и только тех строк,
которые принадлежат одновременно обеим исходным таблицам;
Автор благодарит Дмитрия Борисовича Буя за постановку задачи и полезные замечания.
197
А.С. Сенченко
3) разность T1−T2 двух таблиц – таблица, состоящая из тех и только тех строк,
которые принадлежат таблице T1 и не принадлежат таблице T2.
Для введения операции насыщения нам необходимо дать определение понятия,
используемого в работе в дальнейшем. Активным доменом атрибута A относительно
таблицы T называется множество DA,T = {d|∃s ∈ T ∧ (A, d) ∈ s}, состоящее из все-
возможных значений атрибута A в таблице T . Насыщением C(T ) называется табли-
ца
∏
A∈R
DA,T , где
∏
– оператор прямого (декартового) произведения всех атрибутов
схемы T . Другими словами, мы можем понимать насыщение как аналог декартового
произведения активных доменов всех атрибутов таблицы в применении к именным
множествам. Активным дополнением таблицы T называется таблица T̃ = C(T )−T .
Кроме этих операций на множестве всех таблиц введены операции проекции,
селекции, соединения (в некоторых источниках, например в [2], эта операция на-
зывается эквисоединением), деления таблиц и операция переименования атрибутов;
эти операции не будут использованы в настоящей работе, поэтому их определения не
приводим. Табличной алгеброй называют частичную алгебру с носителем – множе-
ством всех таблиц произвольной схемы и приведенными выше девятью операциями
(насыщение рассматривается как вспомогательная операция). В табличной алгебре
выделяют две пустые таблицы: таблицу Tε, схема которой является пустым множе-
ством и таблицу T∅ – пустое множество строк произвольной (в том числе и непустой)
схемы.
3. Основные результаты. В монографии [1] в подразделе о свойствах насыще-
ния и активного дополнения сформулирован и доказан ряд свойств этих операций,
большая часть которых являются включениями. Автором были найдены необхо-
димые и достаточные условия (в виде двух теорем), при которых эти включения
превращаются в равенства для непустых таблиц, для пустых таблиц эти равенства
тоже выполняются, но в этом случае могут не выполняться критерии. Кроме фор-
мулировки и доказательства к каждой теореме будут приведены примеры, в кото-
рых будет показано, что выполнение/невыполнение критериев приводит к выполне-
нию/невыполнению равенства.
Теорема 1 (о дистрибутивности насыщения по объединению). Для непу-
стых таблиц T1 и T2 равенство C(T1
⋃
T2) = C(T1)
⋃
C(T2) выполняется тогда и
только тогда, когда выполняется хоть одно из двух условий:
а) хотя бы для k − 1 атрибута значения их активных доменов относительно
таблиц T1 и T2 попарно совпадают, то есть, существует не более одного ат-
рибута, для которого значения активного домена относительно таблиц T1 и T2
различается;
б) значение активного домена каждого атрибута относительно одной таблицы
является подмножеством значения активного домена соответствующего атри-
бута относительно другой таблицы, то есть выполняются включения ∀i DAi,T1 ⊆
DAi,T2 или ∀i DAi,T2 ⊆ DAi,T1.
Доказательство. Необходимость. Пусть выполняется равенство C(T1
⋃
T2) =
C(T1)
⋃
C(T2). Допустим, что условие (а) не выполняется, то есть значение актив-
198
О дистрибутивности насыщения относительно объединения и пересечения
ного домена минимум двух атрибутов попарно различны. Пусть DAq ,T1 6= DAq ,T2
и DAw,T1 6= DAw,T2 . Покажем, что в этом случае обязательно должно выполняться
условие (б), то есть должны одновременно выполняться включения DAq ,T1 ⊂ DAq ,T2
и DAw,T1 ⊂ DAw,T2 (или DAq ,T1 ⊃ DAq ,T2 и DAq ,T1 ⊃ DAq ,T2).
Из DAq ,T1 6= DAq ,T2 следует, что существует хоть один элемент x одного ак-
тивного домена, который не принадлежит другому, то есть x ∈ DAq ,T1 − DAq ,T2 ∨
x ∈ DAq ,T2 − DAq ,T1 . Пусть x ∈ DAq ,T1 − DAq ,T2 . Докажем, что в таком случае
выполняются включения DAq ,T2 ⊂ DAq ,T1 и DAw,T2 ⊂ DAw,T1 . Допустим, что не
выполняется второе включение, то есть DAw,T2 6⊂ DAw,T1 . Следовательно, суще-
ствует такой y ∈ DAw,T2 , что y 6∈ DAw,T1 . Включения x ∈ DAq ,T1 и y ∈ DAw,T2
по определениям объединения таблиц и активного домена влекут включения x ∈
DAq ,T1∪T2 и y ∈ DAw,T1∪T2 , поэтому по определению активного домена существуют
такие строки s′, s′′ ∈ T1
⋃
T2, что (Aq, x) ∈ s′ и (Aw, y) ∈ s′′. Тогда по определе-
нию насыщения в C(T1
⋃
T2) входит строка s = {(A1, d1), . . . , (Aq−1, dq−1), (Aq, x),
(Aq+1, dq+1), . . . , (Aw−1, dw−1), (Aw, y), (Aw+1, dq+1), . . . , (Ak, dk)}, где d1, . . . , dq−1,
dq+1, . . . , dw−1, dw+1, . . . , dk – некоторые элементы активных доменов соответству-
ющих атрибутов A1, . . . , Aq−1, Aq+1, . . . , Aw−1, Aw+1, . . . , Ak относительно таблицы
T1
⋃
T2. Поскольку x 6∈ DAq ,T2 , то s 6∈ C(T2), а поскольку y 6∈ DAw,T1 , то s 6∈ C(T1),
следовательно s 6∈ C(T1)
⋃
C(T2), и значит C(T1
⋃
T2) 6= C(T1)
⋃
C(T2), что неверно
по допущению. Поэтому включение DAw,T2 ⊂ DAw,T1 выполняется. Далее, исходя из
доказанности включения DAw,T2 ⊂ DAw,T1 , полностью аналогично доказывается и
выполнимость включения DAq ,T2 ⊂ DAq ,T1 . Затем точно таким же способом можно
доказать выполнимость включений DAi,T2 ⊆ DAi,T1 и по всем остальным атрибутам
Ai (заметим, что по условию (б) строгость этих включений не требуется).
Случай, когда x ∈ DAq ,T2−DAq ,T1 , влечет выполнение включений DAq ,T1 ⊂ DAq ,T2
и DAw,T1 ⊂ DAw,T2 , а следовательно, и включений DAi,T1 ⊆ DAi,T2 для всех i 6=
q ∧ i 6= w доказывается аналогично путем замены индексов таблицы T1 на T2 и
наоборот. Таким образом мы показали, что при выполнении равенства C(T1
⋃
T2) =
C(T1)
⋃
C(T2) и не выполнении условия (а) обязательно выполняется условие (б),
что доказывает необходимость теоремы.
Достаточность. Сначала докажем вспомогательное утверждение.
Лемма 1. Пусть выполняется принадлежность z ∈ DA,T1∪T2. Тогда:
а) равенство DA,T1 = DA,T2 влечет z ∈ DA,T1 ∧ z ∈ DA,T2;
б) включение DA,T1 ⊆ DA,T2 влечет z ∈ DA,T2.
Доказательство леммы 1. Пусть z ∈ DA,T1∪T2 и DA,T1 = DA,T2 . Принадлеж-
ность z ∈ DA,T1∪T2 возможна только в том случае, когда существует такая строка
s ∈ T1
⋃
T2, что (A, z) ∈ s. По определению объединения таблиц при этом выполня-
ется хоть одна из принадлежностей s ∈ T1 или s ∈ T2. Тогда s ∈ T1 влечет z ∈ DA,T1
и из равенства DA,T1 = DA,T2 следует принадлежность z ∈ DA,T2 . Тот факт, что
s ∈ T2 влечет z ∈ DA,T1 доказывается аналогично; случай (а) доказан.
Пусть теперь z ∈ DA,T1∪T2 и DA,T1 ⊆ DA,T2 . Так же как и в пункте (а) леммы
в этом случае существует такая строка s ∈ T1
⋃
T2, что (A, z) ∈ s, следовательно
выполняется s ∈ T1 или s ∈ T2. Тогда s ∈ T1 влечет z ∈ DA,T1 , и из включения
199
А.С. Сенченко
DA,T1 ⊆ DA,T2 следует принадлежность z ∈ DA,T2 , а s ∈ T2 влечет принадлежность
z ∈ DA,T2 по определению активного домена. ¤
Докажем теперь достаточность условия (а). Пусть у таблиц T1 и T2 значения
активных доменов по k−1 атрибуту попарно совпадают: для всех i 6= q выполняют-
ся равенства DAi,T1 = DAi,T2 . Докажем, что в этом случае выполняется равенство
C(T1
⋃
T2) = C(T1)
⋃
C(T2).
В монографии [1] (лемма 2.2.1, пункт 7) доказано включение
C(T1)
⋃
C(T2) ⊆ C(T1
⋃
T2). Для доказательства искомого равенства нужно дока-
зать включение C(T1
⋃
T2) ⊆ C(T1)
⋃
C(T2) . От противного, допустим, что включе-
ние не выполняется, то есть существует строка s = {(A1, d1), . . . , (Aq−1, dq−1), (Aq, x),
(Aq+1, dq+1), . . . , (Ak, dk)}, которая принадлежит C(T1
⋃
T2) и не принадлежит C(T1)⋃
C(T2). По определениям активного домена и насыщения выполняются принадлеж-
ности d1 ∈ DA1,T1∪T2 , . . . , dq−1 ∈ DAq−1,T1∪T2 , x ∈ DAq ,T1∪T2 , dq+1 ∈ DAq+1,T1∪T2 , . . . ,
dk ∈ DAk,T1∪T2 . С учётом условий DAi,T1 = DAi,T2 для всех i 6= q и пункта (а)
леммы 1 получаем, что d1 ∈ DA1,T1 и d1 ∈ DA1,T2 , . . . , dq−1 ∈ DAq−1,T1 и dq−1 ∈
DAq−1,T2 , dq+1 ∈ DAq+1,T1 и dq+1 ∈ DAq+1,T2 , . . . , dk ∈ DAk,T1 и dk ∈ DAk,T2 . Факт при-
надлежности x ∈ DAq ,T1∪T2 влечет существование в таблице T1
⋃
T2 такой строки
s′ , что (Aq, x) ∈ s′. По определению объединения таблиц в этом случае выполня-
ется хоть одна из принадлежностей s′ ∈ T1 или s′ ∈ T2, то есть выполняется хотя
бы одно из условий: x ∈ DAq ,T1 или x ∈ DAq ,T2 . Если выполняется x ∈ DAq ,T1 , то
s′ ∈ C(T1) , а если выполняется x ∈ DAq ,T2 , то s′ ∈ C(T1). В любом случае выполня-
ется s′ ∈ C(T1)
⋃
C(T2), что противоречит допущению. Достаточность условия (а)
доказана.
Докажем теперь достаточность условия (б). Пусть выполняются включения
∀i DAi,T1 ⊆ DAi,T2 . От противного, допустим, что C(T1
⋃
T2) 6= C(T1)
⋃
C(T2). Как
уже было показано в доказательстве достаточности условия (а), это неравенство
возможно только в том случае, когда существует такая строка s = {(A1, d1), . . . ,
(Ak, dk)}, что s ∈ C(T1
⋃
T2) и s 6∈ C(T1)
⋃
C(T2). Тот факт, что s ∈ C(T1
⋃
T2) вле-
чет выполнение принадлежностей di ∈ DAi,T1∪T2 для всех i . Из условия ∀i DAi,T1 ⊆
DAi,T2 ввиду пункта (б) леммы 1 следует, что ∀i di ∈ DAi,T2 , поэтому по определе-
нию насыщения s ∈ C(T2) , и значит, s ∈ C(T1)
⋃
C(T2). Таким образом, допущение
s 6∈ C(T1)
⋃
C(T2) неверно; достаточность условия (б) доказана. ¤
Проиллюстрируем критерии теоремы 1 на следующих примерах
Пример 1.1.
Пусть T1 =
A B C
1 2 3
2 2 3
2 3 3
и T2 =
A B C
2 2 1
2 3 1
3 3 1
.
Значения активных доменов DA,T1 = {1, 2}, DB,T1 = {2, 3}, DC,T1 = {3} и DA,T2 =
{2, 3}, DB,T1 = {2, 3}, DC,T1 = {1} не удовлетворяют ни одному из условий, равенство
не должно выполняться. Действительно,
200
О дистрибутивности насыщения относительно объединения и пересечения
C(T1
⋃
T2) =
A B C
1 2 1
1 2 3
1 3 1
1 3 3
2 2 1
2 2 3
2 3 1
2 3 3
3 2 1
3 2 3
3 3 1
3 3 3
, C(T1) =
A B C
1 2 3
1 3 3
2 2 3
2 3 3
, C(T2) =
A B C
2 2 1
2 3 1
3 2 1
3 3 1
, то есть
C(T1
⋃
T2) 6= C(T1)
⋃
C(T2).
Пример 1.2.
Пусть T1 =
A B C
1 2 3
2 2 3
2 3 3
и T2 =
A B C
1 2 4
2 2 4
2 3 4
.
Значения активных доменов DA,T1 = {1, 2}, DB,T1 = {2, 3}, DC,T1 = {3} и DA,T2 =
{1, 2}, DB,T1 = {2, 3}, DC,T1 = {4} удовлетворяют условию (а), равенство должно
выполняться. Действительно,
C(T1
⋃
T2) =
A B C
1 2 3
1 2 4
1 3 3
1 3 4
2 2 3
2 2 4
2 3 3
2 3 4
, C(T1) =
A B C
1 2 3
1 3 3
2 2 3
2 3 3
, C(T2) =
A B C
1 2 4
1 3 4
2 2 4
2 3 4
, то есть
C(T1
⋃
T2) = C(T1)
⋃
C(T2).
Пример 1.3.
Пусть T1 =
A B C
1 2 3
2 2 1
2 3 3
и T2 =
A B C
2 2 1
2 3 1
.
Значения активных доменов DA,T1 = {1, 2}, DB,T1 = {2, 3}, DC,T1 = {1, 3} и
DA,T2 = {2}, DB,T1 = {2, 3}, DC,T1 = {1} удовлетворяют условию (б), равенство
должно выполняться. Действительно,
201
А.С. Сенченко
C(T1
⋃
T2) =
A B C
1 2 1
1 2 3
1 3 1
1 3 3
2 2 1
2 2 3
2 3 1
2 3 3
, C(T1) =
A B C
1 2 1
1 2 3
1 3 1
1 3 3
2 2 1
2 2 3
2 3 1
2 3 3
, C(T2) =
A B C
2 2 1
2 3 1
, то есть
C(T1
⋃
T2) = C(T1)
⋃
C(T2).
Теорема 2 (о дистрибутивности насыщения по пересечению). При
C(T1)
⋂
C(T2) 6= T∅ эквивалентны утверждения:
1) выполняется равенство C(T1
⋂
T2) = C(T1)
⋂
C(T2);
2) выполняются равенства ∀i DAi,T1
⋂
T2
= DAi,T1
⋂
DAi,T2;
3) для любого индекса i и каждого элемента x из множества DAi,T1
⋂
DAi,T2
существует такая строка s ∈ T1
⋂
T2, что (Ai, x) ∈ s.
Доказательство. Покажем сначала эквивалентность утверждений (1) и (2). Пусть
выполняется равенство (1). От противного, допустим, что не выполняется равенство
(2), то есть DAq ,T1
⋂
T2
6= DAq ,T1
⋂
DAq ,T2 для некоторого индекса q. При этом воз-
можны два случая:
а) ∃x ∈Aq ,T1
⋂
T2
и x 6∈ DAq ,T1
⋂
DAq ,T2 . Тогда по определению активного домена,
существует такая строка s ∈ T1
⋂
T2, что (Aq, x) ∈ s. Включение s ∈ T1
⋂
T2 влечёт
s ∈ T1 и s ∈ T2, следовательно x ∈ DAq ,T1 и x ∈ DAq ,T2 , то есть x ∈ DAq ,T1
⋂
DAq ,T2 .
Получившееся противоречие доказывает невозможность этого случая.
б) ∃y ∈ DAq ,T1
⋂
DAq ,T2 и y 6∈ DAq ,T1
⋂
T2
. Тогда y ∈ DAq ,T1 и y ∈ DAq ,T2 . По
условию таблица C(T1)
⋂
C(T2) непустая, следовательно, в ней существует хоть од-
на строка. Пусть s = {(A1, d1), . . . , (Ak, dk)} ∈ C(T1)
⋂
C(T2). Тогда по определе-
нию активного домена d1 ∈ DA1,T1 и d1 ∈ DA1,T2 , . . . , dk ∈ DAk,T1 и dk ∈ DAk,T2 .
По определению насыщения получаем, что s′ = {(A1, d1), . . . , (Aq−1, dq−1), (Aq, y),
(Aq+1, dq+1), . . . , (Ak, dk)} ∈ C(T1) и s′ ∈ C(T2) , то есть s′ ∈ C(T1)
⋂
C(T2) . Из
равенства (1) следует, что s′ ∈ C(T1
⋂
T2), поэтому y ∈ DAq ,T1
⋂
T2
, что доказывает
невозможность этого случая; импликация
(
1
) ⇒ (
2
)
доказана.
Пусть теперь выполняется равенство (2). От противного, допустим, что не выпол-
няется равенство (1). В монографии [1] доказано включение C(T1
⋂
T2) ⊆ C(T1)
⋂
C(T2), поэтому равенство (1) может не выполняться только в случае, когда суще-
ствует такая строка s = {(A1, d1), . . . , (Ak, dk)} ∈ C(T1)
⋂
C(T2), что s 6∈ C(T1
⋂
T2).
Рассмотрим этот случай. Из s ∈ C(T1)
⋂
C(T2) следует, что s ∈ C(T1) и s ∈ C(T2). Из
равенства (2) и определения активного домена получаем, что d1 ∈ DA1,T1
⋂
T2
, . . . , dk ∈
DAk,T1
⋂
T2
. Тогда по определению насыщения выполняется {(A1, d1), . . . , (Ak, dk)} ∈
C(T1
⋂
T2), что противоречит допущению, импликация
(
2
) ⇒ (
1
)
доказана, поэтому
утверждения (1) и (2) равносильны.
Докажем теперь, что эквивалентны утверждения (1) и (3). Пусть выполняется
равенство (1). От противного, допустим, что не выполняется утверждение (3), то
202
О дистрибутивности насыщения относительно объединения и пересечения
есть ∃x ∈ DAq ,T1
⋂
DAq ,T2 | ∀s ∈ T1
⋂
T2 (Aq, x) 6∈ s для некоторого индекса q. По
доказанному выше равенство (1) эквивалентно равенству (2). Из равенства (2) сле-
дует, что x ∈ DAq ,T1
⋂
T2
, значит по определению активного домена для некоторой
строки s′ ∈ T1
⋂
T2 выполняется принадлежность (Aq, x) ∈ s′, что противоречит
допущению. Импликация
(
1
) ⇒ (
3
)
доказана.
Пусть теперь выполняется утверждение (3). От противного, допустим, что не вы-
полняется равенство (1), что может быть только в том случае, когда ∃s = {(A1, d1),
. . . , (Ak, dk)} ∈ C(T1)
⋂
C(T2) и s 6∈ C(T1
⋂
T2). Рассмотрим этот случай. s 6∈ C(T1
⋂
T2) влечет dq 6∈ DAq ,T1
⋂
T2
для некоторого индекса q. Поскольку s ∈ C(T1)
⋂
C(T2),
и, значит s ∈ C(T1) и s ∈ C(T2), то по определениям активного домена и насыщения
выполняются включения dq ∈ DAq ,T1 и dq ∈ DAq ,T2 , поэтому dq ∈ DAq ,T1
⋂
DAq ,T2 .
По условию (3) в этом случае должна существовать такая строка s′ ∈ T1
⋂
T2, что
(Aq, dq) ∈ s′. По определению активного домена dq ∈ DAq ,T1
⋂
T2
, противоречие дока-
зывает неверность допущения, импликация
(
3
) ⇒ (
1
)
доказана. ¤
Проиллюстрируем критерий теоремы 2 на примерах.
Пример 2.1.
Пусть T1 =
A B C
1 2 1
1 3 3
2 3 1
4 2 1
4 2 3
и T2 =
A B C
1 1 1
1 2 1
3 1 3
3 2 4
4 2 3
.
Значения активных доменов DA,T1 = {1, 2, 4}, DB,T1 = {2, 3}, DC,T1 = {1, 3} и
DA,T2 = {1, 3, 4}, DB,T1 = {1, 2}, DC,T1 = {1, 3, 4}; общие значения активных доменов
(A, 1), (A, 4), (B, 2), (C, 1), (C, 3). Общие строки T1 и T2 {(A, 1), (B, 2), (C, 1)} и {(A, 4),
(B, 2), (C, 3)} покрывают все общие значения доменов, выполняется утверждение
(3), равенство (1) должно выполняться. Действительно,
C(T1
⋂
T2) =
A B C
1 2 1
1 2 3
4 2 1
4 2 3
, C(T1)
⋂
C(T2) =
A B C
1 2 1
1 2 3
4 2 1
4 2 3
, то есть C(T1
⋂
T2) =
C(T1)
⋂
C(T2).
Пример 2.2.
Пусть T1 =
A B C
1 1 3
1 2 2
1 4 2
4 1 3
4 4 2
и T2 =
A B C
1 1 3
1 2 1
2 1 3
2 2 1
4 1 3
.
Значения активных доменов DA,T1 = {1, 4}, DB,T1 = {1, 2, 4}, DC,T1 = {2, 3} и
DA,T2 = {1, 2, 4}, DB,T1 = {1, 2}, DC,T1 = {1, 3}; общие значения активных доме-
нов (A, 1), (A, 4), (B, 1), (B, 2), (C, 3). Общие строки {(A, 1), (B, 1), (C, 3)} и {(A, 4),
203
А.С. Сенченко
(B, 1), (C, 3)} не покрывают все общие значения доменов (не покрыто значение (B, 2)),
утверждение (3) не выполняется, равенство (1) не должно выполняться. Действи-
тельно,
C(T1
⋂
T2) =
A B C
1 1 3
4 1 3
, C(T1)
⋂
C(T2) =
A B C
1 1 3
1 2 3
4 1 3
4 2 3
, то есть C(T1
⋂
T2) 6=
C(T1)
⋂
C(T2).
4. Выводы. В работе исследованы свойства операций насыщения и активного
дополнения табличных алгебр. Найдены критерии, при которых некоторые включе-
ния из [1] превращаются в равенства. Результаты работы могут быть использованы
в теории обобщенных табличных алгебр и, на наш взгляд, для оптимизации запросов
в реляционных базах данных.
1. Реляцiйнi бази даних: табличнi алгебри та SQL-подiбнi мови / [В.Н. Редько, Ю.Й. Брона, Д.Б.
Буй, С.А. Поляков]. – Київ: Видавничий дiм «Академперiодика», 2001. – 198 с.
2. Мейер Д. Теория реляционных баз данных: [пер. с англ.] / Д. Мейер. – Москва: Мир, 1987. –
608 с.
A. S. Senchenko
On a distributivity of a saturation to join and intersection in table algebra.
In this paper there is found the necessary and sufficient conditions due to which a saturation operation
is distributive to operations join and intersection. This conditions are illustrated in examples.
Keywords: table algebra, saturation, database.
О.С. Сенченко
Про дистрибутивнiсть в табличних алгебрах операцiї насичення вiдносно операцiй
об’єднання та перетину.
В роботi знайдено необхiднi та достатнi умови, за яких у табличних алгебрах операцiя насичен-
ня є дистрибутивною вiдносно операцiй об’єднання та перетину таблиць. Наведенi приклади, що
iлюструють знайденi критерiї.
Ключовi слова: таблична алгебра, насичення, бази даних.
Донбасский государственный педагогический ун-т
senchenko@pisem.net
Получено 05.04.13
204
|