Некоторые равенства в табличных алгебрах

Найдены необходимые и достаточные условия, при которых одиннадцать включений, выполняемых в табличных алгебрах, превращаются в равенства. Эти условия выражаются в терминах активных доменов таблиц и являются естественными....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2014
Hauptverfasser:	Редько, В.Н., Буй, Д.Б., Сенченко, А.С.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Видавничий дім "Академперіодика" НАН України 2014
Schriftenreihe:	Доповіді НАН України
Schlagworte:	Інформатика та кібернетика
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/87813
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Некоторые равенства в табличных алгебрах / В.Н. Редько, Д.Б. Буй, А.С. Сенченко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 48-52. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-87813
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-878132025-02-10T01:42:42Z Некоторые равенства в табличных алгебрах Деякi рiвностi в табличних алгебрах Some equalities in table algebras Редько, В.Н. Буй, Д.Б. Сенченко, А.С. Інформатика та кібернетика Найдены необходимые и достаточные условия, при которых одиннадцать включений, выполняемых в табличных алгебрах, превращаются в равенства. Эти условия выражаются в терминах активных доменов таблиц и являются естественными. Знайдено необхiднi та достатнi умови, при яких одинадцять включень, якi виконуються в табличних алгебрах, перетворюються у рiвностi. Цi умови виражаються в термiнах активних доменiв таблиць та є природними. The necessary and sufficient conditions, due to which eleven inclusions realized in table algebras become equalities, are found. These conditions are expressed in terms of active domains of the tables and are natural. 2014 Article Некоторые равенства в табличных алгебрах / В.Н. Редько, Д.Б. Буй, А.С. Сенченко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 48-52. — Бібліогр.: 7 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/87813 004.655 ru Доповіді НАН України application/pdf Видавничий дім "Академперіодика" НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Інформатика та кібернетика Інформатика та кібернетика
spellingShingle	Інформатика та кібернетика Інформатика та кібернетика Редько, В.Н. Буй, Д.Б. Сенченко, А.С. Некоторые равенства в табличных алгебрах Доповіді НАН України
description	Найдены необходимые и достаточные условия, при которых одиннадцать включений, выполняемых в табличных алгебрах, превращаются в равенства. Эти условия выражаются в терминах активных доменов таблиц и являются естественными.
format	Article
author	Редько, В.Н. Буй, Д.Б. Сенченко, А.С.
author_facet	Редько, В.Н. Буй, Д.Б. Сенченко, А.С.
author_sort	Редько, В.Н.
title	Некоторые равенства в табличных алгебрах
title_short	Некоторые равенства в табличных алгебрах
title_full	Некоторые равенства в табличных алгебрах
title_fullStr	Некоторые равенства в табличных алгебрах
title_full_unstemmed	Некоторые равенства в табличных алгебрах
title_sort	некоторые равенства в табличных алгебрах
publisher	Видавничий дім "Академперіодика" НАН України
publishDate	2014
topic_facet	Інформатика та кібернетика
url	https://nasplib.isofts.kiev.ua/handle/123456789/87813
citation_txt	Некоторые равенства в табличных алгебрах / В.Н. Редько, Д.Б. Буй, А.С. Сенченко // Доповiдi Нацiональної академiї наук України. — 2014. — № 6. — С. 48-52. — Бібліогр.: 7 назв. — рос.
series	Доповіді НАН України
work_keys_str_mv	AT redʹkovn nekotoryeravenstvavtabličnyhalgebrah AT buidb nekotoryeravenstvavtabličnyhalgebrah AT senčenkoas nekotoryeravenstvavtabličnyhalgebrah AT redʹkovn deâkirivnostivtabličnihalgebrah AT buidb deâkirivnostivtabličnihalgebrah AT senčenkoas deâkirivnostivtabličnihalgebrah AT redʹkovn someequalitiesintablealgebras AT buidb someequalitiesintablealgebras AT senčenkoas someequalitiesintablealgebras
first_indexed	2025-12-02T13:37:27Z
last_indexed	2025-12-02T13:37:27Z
_version_	1850403871477727232
fulltext	УДК 004.655 Академик НАН Украины В.Н. Редько, Д. Б. Буй, А. С. Сенченко Некоторые равенства в табличных алгебрах Найдены необходимые и достаточные условия, при которых одиннадцать включений, выполняемых в табличных алгебрах, превращаются в равенства. Эти условия выра- жаются в терминах активных доменов таблиц и являются естественными. Процесс информатизации общества имеет объективный характер. Ядром для подавляюще- го большинства современных информационных систем являются базы данных. В настоящее время наиболее распространенными остаются реляционные базы данных, математическая модель которых была впервые предложена Э. Коддом в 1970 г. [1]. С математической точ- ки зрения реляционная база данных является конечным множеством конечных отношений различной размерности (арности) между заранее определенными множествами элементар- ных данных. Табличные алгебры, введенные В.Н. Редько и Д.Б. Буем, построены на основе реляци- онных алгебр Э. Кодда и существенно их развивают. Они составляют теоретический фунда- мент языков запросов современных табличных баз данных. Элементы носителя табличной алгебры уточняют реляционные структуры данных, а сигнатурные операции построены на базе основных табличных манипуляций в реляционных алгебрах и SQL-подобных языках. В работе [2] установлено значительное количество различных свойств операций таблич- ных алгебр, большинство из которых для общего случая выполняются в виде включений. В настоящей работе приведены критерии перехода одиннадцати таких включений в равен- ства. Эти равенства представляют интерес для теории табличных алгебр по той причине, что только на основе равенств можно осуществлять эквивалентные преобразования выра- жений. Эти преобразования необходимы для решения актуальной задачи оптимизации за- просов [3, 4]. Основные определения. Зафиксируем некоторое непустое множество атрибутов A = = {A1, . . . , An}. Произвольное конечное подмножество множества A назовем схемой, при- чем схема может быть пустым множеством. Строкой s схемы R называется множество пар s = {(A′ 1, d1), . . . , (A ′ k, dk)}, проекция которого по первой компоненте равна R, причем атрибуты A′ 1, . . . , A ′ k попарно различны, т. е. строка является функциональным бинарным отношением. Таблицей схемы R называется конечное множество строк схемы R. Далее в ра- боте рассматриваем таблицы схемы R с количеством атрибутов k. На множестве всех таких таблиц введены такие операции: 1) объединение ⋃ R двух таблиц схемы R — таблица, состоящая из тех и только тех строк, которые принадлежат хотя бы одной из исходных таблиц; 2) пересечение ⋂ R двух таблиц схемы R — таблица, состоящая из тех и только тех строк, которые принадлежат одновременно обеим исходным таблицам; 3) разность T1 − R T2 двух таблиц схемы R — таблица, состоящая из тех и только тех строк, которые принадлежат таблице T1 и не принадлежат таблице T2. © В. Н. Редько, Д.Б. Буй, А.С. Сенченко, 2014 48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №6 Для введения операции насыщения необходимо одно вспомогательное понятие. Актив- ным доменом атрибута A относительно таблицы T называется множество DA,T = {d \| ∃ s ∈ ∈ T ∧ (A, d) ∈ s}, состоящее, говоря содержательно, из всевозможных значений атрибу- та A в таблице T . Насыщением C(T ) называется таблица ∏ A∈R DA,T , где R — схема та- блицы T , а ∏ — оператор прямого (декартового) произведения, отвечающий индексиро- ванию A 7→ DA,T , A ∈ R [5]. Активным дополнением таблицы T называется таблица T̃ = C(T ) − R T . Введем определение операции проекции. Проекцией по множеству атрибутов X ⊆ R называется унарная параметрическая операция πX , значением которой является таблица, состоящая из ограничений по X всех строк исходной таблицы: πX(T ) = {s \| x \| s ∈ T}. Здесь ограничение понимается стандартно: s \| x = s ⋂ X × pr2s, где pr2s — проекция строки s по второй компоненте. Пусть X = {X1, . . . ,Xp}. Далее в работе через O = {O1, . . . , Ok−p} обозначим множество атрибутов R − X, не участвующих в проекции. Для введения операции соединения (в некоторых источниках, например в [6], эта опе- рация называется эквисоединением) необходимо одно вспомогательное понятие. Бинарные отношения ρ и τ называются совместными (обозначается ρ ≈ τ), если ρ \| x = τ \| x, где X = pr1ρ ⋂ pr1τ [2]. Соединением называется бинарная операция ⊗, значением которой является таблица, состоящая из всевозможных объединений совместных строк исходных таблиц, т. е. T1 ⊗ T2 = { s1 ⋃ s2 \| s1 ∈ T1 ∧ s2 ∈ T2 ∧ s1 ≈ s2 } . Пусть T1 — таблица схемы R1, T2 — таблица схемы R2. Полусоединением [7] таблицы T1 по таблице T2 называется таблица T1 ⊲ T2 = {s1 ∈ T1 \| ∃ s2 ∈ T2 ∧ s1 ≈ s2}, состоящая, говоря содержательно, из всех строк T1, участвующих в соединении T1 ⊗ T2. Кроме этих операций на множестве всех таблиц введены операции селекции, деления таблиц и переименования атрибутов; эти операции не будут использованы в настоящей работе, поэтому их определения не приводим. Табличной алгеброй называют частичную алгебру с носителем — множеством всех таблиц произвольной схемы и приведенными выше девятью операциями (насыщение и полусоединение рассматриваются как вспомогательные операции). В табличной алгебре выделяют две особые таблицы: таблицу Tε = {ε}, где ε — пустая строка, при этом схема таблицы Tε является пустым множеством, и таблицу T∅ = ∅ — пустое множество строк произвольной (в том числе и непустой) схемы. Основные результаты. В работе [2] в подразделах о насыщении, активном дополне- нии, проекции и соединении сформулирован и доказан ряд свойств этих операции. В настоя- щей работе найдены необходимые и достаточные условия (в виде одиннадцати теорем), при которых включения превращаются в равенства для таблиц, не являющихся особыми; для особых таблиц эти равенства тоже выполняются, но в этом случае могут не выполняться критерии. Теорема 1 (дистрибутивность насыщения относительно объединения). Пусть T1, T2 — таблицы схемы R. Равенство C ( T1 ⋃ R T2 ) = C(T1) ⋃ R C(T2) выполняется тогда и только тогда, когда выполняется хотя бы одно из двух условий: а) существует не более одного атрибута, для которого активные домены относитель- но таблиц T1 и T2 различаются; б) активный домен каждого атрибута A ∈ R относительно одной таблицы является подмножеством активного домена этого же атрибута относительно другой таблицы, т. е. выполняется утверждение ∀A(A ∈ R ⇒ (DA,T1 ⊆ DA,T2 ∨DA,T2 ⊆ DA,T1 )). ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №6 49 Теорема 2 (дистрибутивность насыщения относительно пересечения). Пусть T1, T2 — таблицы схемы R. При C(T1) ⋂ R C(T2) 6= T∅ равенство C ( T1 ⋂ R T2 ) = C(T1) ⋂ R C(T2) выпол- няется тогда и только тогда, когда для каждого атрибута A ∈ R выполняется равенство DA,T1 ⋂ R T2 = DA,T1 ⋂ DA,T2 . Теорема 3 (закон двойного отрицания). Равносильны утверждения: а) C(T̃ ) = C(T ); б) ˜̃ T = T ; в) для каждого значения x активного домена каждого атрибута Aq существуют та- кие значения d1, . . . , dq−1, dq+1, . . . , dk активных доменов атрибутов A1, . . . , Aq−1, Aq+1, . . ., Ak соответственно, что для строки s = {(A1, d1), . . . , (Aq−1, dq−1), (Aq , x), (Aq+1, dq+1), . . ., (Ak, dk)} выполняется s 6∈ T . Теорема 4 (связь разности и активного дополнения). Равенство T1 ⋂ R T̃2 = T1 − R T2 при T1 − R T2 6= T∅ выполняется тогда и только тогда, когда для каждого атрибута A ∈ R выполняется включение DA,T1 ⊆ DA,T2 . Теорема 5 (первый закон де Моргана). Равенство T̃1 ⋂ R T̃2 = ˜( T1 ⋃ R T2 ) при ˜( T1 ⋃ R T2 ) 6= 6= T∅ выполняется тогда и только тогда, когда выполняется одно из четырех взаимоис- ключающих условий: 1) ∀A(A ∈ R ⇒ DA,T1 = DA,T2 ); 2) ∀A(A ∈ R ⇒ DA,T2 ⊆ DA,T1 ) и для всех индексов q, значений x ∈ DAq,T1 − DAq ,T2 и всех значений d1, . . . , dq−1, dq+1, . . . , dk, принадлежащих соответственно активным до- менам DA1,T1 , . . . ,DAq−1,T1 , DAq+1,T1 . . . ,DAk,T1 , строка {(A1, d1), . . . , (Aq−1, dq−1), (Aq , x), (Aq+1, dq+1), . . . , (Ak, dk)} ∈ T1; 3) ∀A(A ∈ R ⇒ DA,T1 ⊆ DA,T2 ) и для всех индексов q, значений x ∈ DAq,T2 − DAq ,T1 и всех значений d1, . . . , dq−1, dq+1, . . . , dk, принадлежащих соответственно активным до- менам DA1,T2 , . . . ,DAq−1,T2 , DAq+1,T2 . . . ,DAk,T2 , строка {(A1, d1), . . . , (Aq−1, dq−1), (Aq , x), (Aq+1, dq+1), . . . , (Ak, dk)} ∈ T2; 4) существует такой атрибут Aq, для которого существуют значения x ∈ DAq,T1 − −DAq,T2 , y ∈ DAq ,T2 −DAq,T1 , причем DAq,T1 ⋂ DAq,T2 6= ∅; кроме того, для всех i 6= q выпол- няются равенства DAi,T1 = DAi,T2 ; наконец, для всех z1 ∈ DAq,T1 −DAq ,T2 , всех z2 ∈ DAq,T2 − −DAq,T1 и всех d1, . . . , dq−1, dq+1, . . . , dk, принадлежащих соответственно активным до- менам DA1,T1 , . . . ,DAq−1,T1 , DAq+1,T1 . . . ,DAk ,T1 , строка {(A1, d1), . . . , (Aq−1, dq−1), (Aq, z1), (Aq+1, dq+1), . . ., (Ak, dk)} ∈ T1, а строка {(A1, d1), . . . , (Aq−1, dq−1), (Aq, z2), (Aq+1, dq+1), . . ., (Ak, dk)} ∈ T2. Теорема 6 (второй закон де Моргана). Равенство ˜( T1 ⋂ R T2 ) = T̃1 ⋃ R T̃2 при ˜( T1 ⋂ R T2 ) 6= 6= T∅ выполняется тогда и только тогда, когда выполняется одно из двух взаимоисклю- чающих условий: 1) для каждого атрибута A ∈ R выполняются равенства DA,T1 = DA,T1 ⋂ R T2 и DA,T2 = = DA,T1 ⋂ R T2 ; 2) для каждого атрибута Aq ∈ R и каждого такого значения x, что x ∈ DAq,T1 − −DAq ,T1 ⋂ R T2 и всех значений d1, . . . , dq−1, dq+1, . . . , dk, которые принадлежат соответст- 50 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №6 венно активным доменам DA1,T1 , . . . ,DAq−1,T1 , DAq+1,T1 , . . . ,DAk ,T1 , строка {(A1, d1), . . ., (Aq−1, dq−1), (Aq , x), (Aq+1, dq+1), . . . , (Ak, dk)} ∈ T1. Для каждого атрибута Aw ∈ R и каж- дого такого значения y, что y ∈ DAw,T2 − DAw,T1 ⋂ R T2 и всех значений d1, . . . , dw−1, dw+1, . . . , dk, которые принадлежат соответственно активным доменам DA1,T2 , . . . ,DAw−1,T2 , DAw+1,T2 , . . . ,DAk,T2 , строка {(A1, d1), . . . , (Aw−1, dw−1), (Aw, y), (Aw+1, dw+1), . . . , (Ak, dk)} ∈ ∈ T2. Теорема 7 (о перестановочности проекции и активного дополнения). При T 6= T∅ ра- венство ˜(πX(T )) = πX(T̃ ) выполняется тогда и только тогда, когда для каждой строки s = {(X1, x1), . . . , (Xp, xp)} ∈ πX(T ) и любых значений o1 ∈ DO1,T , . . . , ok−p ∈ DOk−p,T , строка s′ = {(X1, x1), . . . , (Xp, xp), (O1, o1), . . . , (Ok−p, ok−p)} ∈ T . Теорема 8 (дистрибутивность проекции относительно пересечения). При⋂ i Ti 6= T∅ равенство πX (⋂ i Ti ) = ⋂ i πX(Ti) выполняется тогда и только то- гда, когда для каждой строки s = {(X1, x1), . . . , (Xp, xp)} ∈ ⋂ i πX(T ) сущест- вуют такие значения o1 ∈ DO1, ⋂ i Ti , . . . , ok−p ∈ DOk−p, ⋂ i Ti , что строка s′ = = {(X1, x1), . . . , (Xp, xp), (O1, o1), . . . , (Ok−p, ok−p)} ∈ ⋂ i Ti. Теорема 9 (дистрибутивность проекции относительно разности). При πX(T1 − R T2) 6= 6= T∅ равенство πX(T1) − X πX(T2) = πX(T1 − R T2) выполняется тогда и только тогда, когда для каждой строки s = {(X1, x1), . . . , (Xp, xp)} ∈ πX(T1) ⋂ X πX(T2) и всех значений o1 ∈ DO1,T1 ⋃ R T2 , . . . , ok−p ∈ DOk−p,T1 ⋃ R T2 , из принадлежности s′ = {(X1, x1), . . . , (Xp, xp), (O1, o1),b. . . , (Ok−p, ok−p)} ∈ T1 следует принадлежность s′ ∈ T2. Теорема 10 (дистрибутивность насыщения относительно соединения). Пусть R1 = = {A1, . . . , Am, Gm+1, . . . , Gp} — схема таблицы T1, R2 = {A1, . . . , Am,Hm+1, . . . ,Hq} — схема таблицы T2, R′ = R1 ⋂ R2, T ′ 1 = T1 − R1 T1 ⊲ T2 и T ′ 2 = T2 − R2 T2 ⊲ T1. При T1 ⊗ T2 6= 6= T∅ равенство C(T1 ⊗ T2) = C(T1) ⊗ C(T2) выполняется тогда и только тогда, когда одновременно выполняются два условия: а) для всех i ∈ {m + 1, . . . , p} выполняется включение DGi,T ′ 1 ⊆ DGi,T1⊲T2 ; для всех i ∈ {m + 1, . . . , q} выполняется включение DHi,T ′ 2 ⊆ DHi,T2⊲T1 ; б) для всех i ∈ {1, . . . ,m} выполняются следующие две импликации: (x ∈ (DAi,T ′ 1 − −DAi,T1⊲T2 )) ⇒ x 6∈ DAi,T2 и (x ∈ (DAi,T ′ 2 −DAi,T2⊲T1 )) ⇒ x 6∈ DAi,T1 . Теорема 11 (дистрибутивность активного дополнения относительно соединения). Ра- венство T̃1 ⊗ T̃2 = ˜(T1 ⊗ T2) выполняется тогда и только тогда, когда выполняется хотя бы одно из двух условий: а) T1 = T2; б) T̃1 ⊗ T̃2 = T∅ и ˜(T1 ⊗ T2) = T∅. Таким образом, в работе исследована взаимосвязь между операциями пересечения, объе- динения, разности, насыщения, активного дополнения, проекции и соединения в табличных алгебрах. Найдены необходимые и достаточные условия, при которых включения, уста- новленные в [2], превращаются в равенства: критерии дистрибутивности насыщения отно- сительно объединения (теорема 1), пересечения (теорема 2) и соединения (теорема 10), выполнимости аналога закона двойного отрицания (теорема 3) и законов де Моргана (тео- ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2014, №6 51 ремы 5 и 6), взаимосвязи разности и активного дополнения (теорема 4), перестановочности проекции и активного дополнения (теорема 7), дистрибутивности проекции относительно пересечения (теорема 8) и разности (теорема 9) и дистрибутивности активного дополнения относительно соединения (теорема 11). Результаты работы представляют теоретический и практический интерес. На основании равенств можно вводить аналоги определяющих со- отношений, являющихся эффективным средством задания и анализа различных дискрет- ных структур, а также осуществлять эквивалентные преобразования выражений, необхо- димые для их оптимизации, в том числе и для оптимизации запросов в реляционных базах данных. 1. Codd E.F. A Relational model of data for large shared data banks // Communications of the ACM. – 1970. – 13, No 6. – P. 377–387. 2. Редько В.Н., Брона Ю.И., Буй Д.Б., Поляков С.А. Реляцiйнi бази даних: табличнi алгебри та SQL-подiбнi мови. – Київ: ВД “Академперiодика”, 2001. – 198 с. 3. Knuth D. E. The art of computer programming. Vol. 4, Fascicle 0. Introduction to combinatorial algorithms and Boolean functions. – Upper Saddle River: Addison-Wesley Professional, 2008. – 240 p. 4. Мендкович Н.А., Кузнецов С.Д. Обзор развития методов лексической оптимизации запросов // Тр. ИСП РАН. – 2012. – 23. – С. 195–214. 5. Куратовский К. Топология. Т. 1. – Москва: Мир, 1966. – 594 с. 6. Мейер Д. Теория реляционных баз данных. – Москва: Мир, 1987. – 608 с. 7. Конноли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практи- ка. – Москва: ИД “Вильямс”, 2003. – 1440 с. Поступило в редакцию 05.12.2013Киевский национальный университет им. Тараса Шевченко Академiк НАН України В.Н. Редько, Д.Б. Буй, О.С. Сенченко Деякi рiвностi в табличних алгебрах Знайдено необхiднi та достатнi умови, при яких одинадцять включень, якi виконуються в табличних алгебрах, перетворюються у рiвностi. Цi умови виражаються в термiнах активних доменiв таблиць та є природними. Academician of the NAS of Ukraine V.N. Red’ko, D.B. Buy, A. S. Senchenko Some equalities in table algebras The necessary and sufficient conditions, due to which eleven inclusions realized in table algebras become equalities, are found. These conditions are expressed in terms of active domains of the tables and are natural. 52 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2014, №6

Некоторые равенства в табличных алгебрах

Institution

Ähnliche Einträge