Закон двойного отрицания и правило преобразования разности в табличных алгебрах

Закон двойного отрицания и правило преобразования разности в табличных алгебрах

В работе найдены необходимые и достаточные условия, при которых в табличных алгебрах выполняются закон двойного отрицания и правило преобразования разности. Приведены примеры, иллюстрирующие данные критерии....

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2013
Автор: Сенченко, А.С.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут проблем штучного інтелекту МОН України та НАН України 2013
Назва видання:Искусственный интеллект
Теми:
Обучающие и экспертные системы
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/85160
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Закон двойного отрицания и правило преобразования разности в табличных алгебрах / А.С. Санченко // Искусственный интеллект. — 2013. — № 2. — С. 139–144. — Бібліогр.: 3 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-85160
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-851602025-02-09T14:35:26Z Закон двойного отрицания и правило преобразования разности в табличных алгебрах Закон подвійного заперечення та правило перетворення різниці у табличних алгебрах A double Complement Law and a Difference Transformation Rule in Table Algebra Сенченко, А.С. Обучающие и экспертные системы В работе найдены необходимые и достаточные условия, при которых в табличных алгебрах выполняются закон двойного отрицания и правило преобразования разности. Приведены примеры, иллюстрирующие данные критерии. У роботі знайдено необхідні та достатні умови, за яких у табличних алгебрах виконуються закон подвійного заперечення та правило перетворення різниці. Наведені приклади, що ілюструють знайдені критерії. In this paper is found the necessary and sufficient conditions due to which in table algebra are fulfilled the double complement law and the difference transformation rule. This conditions are illustrated in exemples. 2013 Article Закон двойного отрицания и правило преобразования разности в табличных алгебрах / А.С. Санченко // Искусственный интеллект. — 2013. — № 2. — С. 139–144. — Бібліогр.: 3 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/85160 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 2013
topic_facet Обучающие и экспертные системы
url https://nasplib.isofts.kiev.ua/handle/123456789/85160
citation_txt Закон двойного отрицания и правило преобразования разности в табличных алгебрах / А.С. Санченко // Искусственный интеллект. — 2013. — № 2. — С. 139–144. — Бібліогр.: 3 назв. — рос.
series Искусственный интеллект
work_keys_str_mv AT senčenkoas zakondvojnogootricaniâipravilopreobrazovaniâraznostivtabličnyhalgebrah
AT senčenkoas zakonpodvíjnogozaperečennâtapraviloperetvorennâríznicíutabličnihalgebrah
AT senčenkoas adoublecomplementlawandadifferencetransformationruleintablealgebra
first_indexed 2025-11-26T22:41:06Z
last_indexed 2025-11-26T22:41:06Z
_version_ 1849894497740128256
fulltext ISSN 1561-5359 «Штучний інтелект» 2013 № 2 139 5С УДК 004.655 А.С. Сенченко Донбасский государственный педагогический университет, Украина 84116, Донецкая обл., г. Славянск, ул. Генерала Батюка, 19 Закон двойного отрицания и правило преобразования разности в табличных алгебрах A.S. Senchenko Donbas State Pedagogical University Donetsk area, Slavyansk, st. Generala Batyuka, 19 A double Complement Law and a Difference Transformation Rule in Table Algebra О.С. Сенченко Донбаський державний педагогічний університет, Україна 84116, Донецька обл., м. Слов’янськ, вул. Генерала Батюка, 19 Закон подвійного заперечення та правило перетворення різниці у табличних алгебрах В работе найдены необходимые и достаточные условия, при которых в табличных алгебрах выполняются закон двойного отрицания и правило преобразования разности. Приведены примеры, иллюстрирующие данные критерии. Ключевые слова: табличная алгебра, активное дополнение, разность, база данных. In this paper is found the necessary and sufficient conditions due to which in table algebra are fulfilled the double complement law and the difference transformation rule. This conditions are illustrated in exemples. Key words: table algebra, active complement, difference, database. У роботі знайдено необхідні та достатні умови, за яких у табличних алгебрах виконуються закон подвійного заперечення та правило перетворення різниці. Наведені приклади, що ілюструють знайдені критерії. Ключові слова: таблична алгебра, активне доповнення, різниця, база даних. Введение В настоящее время системы управления базами данных широко используются во многих сферах человеческой деятельности. Наиболее распространённой является реляционная модель данных, впервые предложенная Э. Коддом в 1970 году [1]. С точки зрения математики реляционная база данных – конечный набор конечных отношений разной размерности между заранее определёнными множествами эле- ментарных данных. Табличные алгебры, введённые В.Н. Редько и Д.Б. Буем, построены на основе реляционных алгебр Э. Кодда и существенно их уточняют. Они составляют теоре- тический фундамент языков запросов современных табличных баз данных. Элементы носителя табличной алгебры уточняют реляционные структуры данных, а сигнатурные операции построены на базе основных табличных манипуляций в реляционных алгебрах и языке SQL. В монографии [2] найдено и доказано большое количество различных свойств операций табличных алгебр. В настоящей работе найдены и доказаны необходимые и достаточные условия, при которых некоторые включения, доказанные в [2], пре- вращаются в равенства. Сенченко А.С. «Искусственный интеллект» 2013 № 2 140 5С Основные определения Зафиксируем некоторое непустое множество { } n AAA ,, 1 K= , элементы которого называются атрибутами. Произвольное конечное подмножество { } AAAR k ⊆′′= ,, 1 K назовем схемой, причем схема может являться пустым множеством. Строкой s схемы R называется множество пар ( ) ( ){ } kk dAdAs ,,,, 11 ′′= K , проекция которого по первой компоненте равна R . Таблицей схемы R называется конечное множество строк схемы R . Далее в работе рассматриваем таблицы схемы R с количеством атри- бутов k . На множестве всех таких таблиц введены операции объединения, пересе- чения и разности как аналогичные операции теории множеств; операции проекции, селекции, соединения (в некоторых источниках, например, в [3], эта операция назы- вается эквисоединением), деления таблиц и операция переименования атрибутов; эти операции не будут использованы в настоящей работе, поэтому их определения не приводим. Также на множестве таблиц введена операция активного дополнения, для определения которой необходимо дать определение понятиям, используемым в работе в дальнейшем. Активным доменом атрибута A относительно таблицы T называется множество ( ){ }sdATsdD TA ∈∧∈∃= , , , состоящее из всевозможных значе- ний атрибута A в таблице T . Насыщением ( )TC называется таблица ∏ ∈RA TA D , , где ∏ – оператор прямого (декартового) произведения всех атрибутов схемы T . Другими словами, мы можем понимать насыщение как аналог декартового про- изведения активных доменов всех атрибутов таблицы в применении к именным множествам. Активным дополнением таблицы T называется таблица ( ) TTCT −= ~ . Табличной алгеброй называют частичную алгебру с носителем – множеством всех таблиц произвольной схемы и приведёнными выше девятью операциями. В табличной алгебре выделяют две пустые таблицы: таблицу ε T , схема которой является пустым множеством, и таблицу ∅ T – пустое множество строк произвольной (в том числе и пустой) схемы. Основные результаты В монографии [2] в подразделе о свойствах насыщения и активного допол- нения сформулирован и доказан ряд свойств этих операций, большая часть которых являются включениями. Автором были найдены необходимые и достаточные усло- вия (в виде двух теорем), при которых этих включения превращаются в равенства для непустых таблиц, для пустых таблиц эти равенства тоже выполняются, но в этом случае могут не выполняться критерии. Теорема 1 (закон двойного отрицания). При ∅ ≠ TT равносильны утверждения: а) выполняется равенство ( ) ( )TCTC = ~ ; б) выполняются равенства TT = ~ ~ ; в) для каждого значения x активного домена каждого атрибута q A существуют такие значения kqq dddd ,,,,, 111 KK +− активных доменов соответствующих атрибутов kqq AAAA ,,,,, 111 KK +− относительно таблицы T , что строка ( ) ( ) ( ) ( ) ( ){ } TdAdAxAdAdA kkqqqqq ∉ ++−− ,,,,,,,,,,, 111111 KK . Закон двойного отрицания и правило преобразования разности… «Штучний інтелект» 2013 № 2 141 5С Доказательство. Покажем сначала эквивалентность утверждений (а) и (в). Пусть выполняется равенство ( ) ( )TCTC = ~ . По определению насыщения это равносильно выпо- лнению равенств TATA ii DDi ~ ,, =∀ . От противного, допустим, что для некоторого TA q Dx , ∈ для всех значений kqq dddd ,,,,, 111 KK +− активных доменов остальных атриибутов kqq AAAA ,,,,, 111 KK +− , все строки ( ) ( ) ( ) ( ) ( ){ } TdAdAxAdAdAs kkqqqqq ∈= ++−− ,,,,,,,,,,, 111111 KK . Тогда, по определению активного дополнения, все эти строки не принадлежат таблице T ~ , поэтому значение TA q Dx ~ , ∉ , то есть TATA qq DD ~ ,, ≠ . Получившееся противо- речие доказывает импликацию (а) ⇒ (в). Пусть теперь выполняется утверждение (в). От противного, допустим, что ( ) ( )TCTC ≠ ~ . В монографии [2] (утверждение 2.2.1 пункт 4) доказано включение ( ) ( )TCTC ⊆ ~ , поэтому неравенство возможно только в том случае, когда существует такая строка ( ) ( ){ } kk dAdAs ′′=′ ,,,, 11 K , что )(TCs ∈′ и ) ~ (TCs ∉′ . Последнее выраже- ние влечет существование некоторого индекса q , для которого TAq q Dd ~ , ∉′ . По пред- положению для некоторых значений kqq dddd ,,,,, 111 KK +− активных доменов атрибутов kqq AAAA ,,,,, 111 KK +− относительно таблицы T строка ( ) ( ) ( ) ( ) ( ){ } TdAdAdAdAdAs kkqqqqqq ∉′= ++−− ,,,,,,,,,,, 111111 KK , а поскольку TAq q Dd , ∈′ , то )(TCs∈ , и значит Ts ~ ∈ , следовательно, TAq q Dd ~ , ∈′ . Это противоречие доказывает импликацию (в) ⇒ (а), то есть утверждения (а) и (в) равносильны. Покажем теперь эквивалентность утверждений (а) и (б). Пусть выполняется равенство TT = ~ ~ . От противного, допустим, что ( ) ( )TCTC ≠ ~ . По определению насыщения в этом случае не выполняется равенства TATA ii DDi ~ ,, =∀ , следовательно, существует индекс q , для которого TATA qq DD ~ ,, ≠ . В монографии [2] (лемма 2.2.1 пункт 4) доказаны равенства ( ) TATСA ii DDi ,, =∀ , и поскольку по определению актив- ного дополнения TTCT −= )( ~ , то выполняется включение TATA qq DD ~ ,, ⊇ . Следова- тельно, из неравенства TATA qq DD ~ ,, ≠ и включения TATA qq DD ~ ,, ⊇ вытекает, что некото- рое значение x входит в TA q D , и не входит в TA q D ~ , . Тогда по определению активного домена существует такая строка Ts∈ , что ( ) sxA q ∈, . Так как TA q Dx ~ , ∉ , то по определению насыщения ) ~ (TCx∉ , и следовательно ( ) TTTCs ~~~ ) ~ ( =−∉ , то есть TT ≠ ~ ~ . Получили противоречие, что доказывает импликацию (б) ⇒ (а). Пусть теперь выполняется равенство ( ) ( )TCTC = ~ , что равносильно выполне- нию равенств TATA ii DDi ~ ,, =∀ . От противного, допустим, что TT ≠ ~ ~ . В [2] (утвержде- ние 2.2.1 пункт 6) доказано включение TT ⊆ ~ ~ , поэтому неравенство TT ≠ ~ ~ возможно только тогда, когда существует такая строка s , что Ts∈ и Ts ~ ~ ∉ . Пусть ( ) ( ){ } kk dAdAs ,,,, 11 K= . Из Ts∈ , по свойствам насыщения следует, что )(TCs∈ . Из Сенченко А.С. «Искусственный интеллект» 2013 № 2 142 5С равенств TATA ii DDi ~ ,, =∀ следует, что ) ~ (TCs∈ . По определению активного до- полнения Ts∈ влечет Ts ~ ∉ . Тогда получаем, что Ts ~ ~ ∈ , что противоречит до- пущению TT ≠ ~ ~ . Получившееся противоречие доказывает импликацию (а) ⇒ (б), то есть утверждения (а) и (б) равносильны. Проиллюстрируем критерий теоремы 1 на следующих примерах. Пример 1.1. Пусть 322 222 131 221 CBA T = . Значения активных доменов { } { } { }3,2,1,3,2,2,1 ,,, === TCTBTA DDD . Для каждого значения активного домена каждого атрибута условие из (в) выполняется, равенства (а) и (б) должны выполняться. Действительно, ( ) 332 232 132 322 222 122 331 231 131 321 221 121 CBA TС = , 332 232 132 122 331 231 321 121 ~ CBA T = , ( ) 332 232 132 322 222 122 331 231 131 321 221 121 ~ CBA TС = , 322 222 131 221 ~~ CBA T = . TT = ~ ~ и ( ) ( )TCTC = ~ . Пример 1.2. Пусть 232 222 231 131 221 CBA T = . Значения активных доменов { } { } { }2,1,3,2,2,1 ,,, === TCTBTA DDD . Для значения TC D , 2∈ все соответствующие строки в таблице T есть; условие из (в) не вы- полняется, равенства (а) и (б) не должны выполняться. Действительно, Закон двойного отрицания и правило преобразования разности… «Штучний інтелект» 2013 № 2 143 5С ( ) 232 132 222 122 231 131 221 121 CBA TС = , 132 122 121~ CBA T = , ( ) 132 122 131 121 ~ CBA TС = , 131 ~~ CBA T = ; TT ≠ ~ ~ и ( ) ( )TCTC ≠ ~ . Теорема 2 (правило преобразования разности). Равенство 2121 ~ TTTT −=I при ∅ ≠− TTT 21 выполняется тогда и только тогда, когда выполняются включения 21 ,, TATA ii DDi ⊆∀ . Доказательство. Необходимость. Пусть выполняется равенство 2121 ~ TTTT −=I . От противного, допустим, что для некоторого q включение 21 ,, TATA qq DD ⊆ не вы- полняется, то есть существует такой x , что 1 ,TA q Dx∈ и 2 ,TA q Dx∉ . Тогда по опре- делению активного домена ( ) sxATs q ∈∈∃ , 1 . Так как 2 ,TA q Dx∉ , то по определению активного домена 2 Ts∉ , следовательно, 21 TTs −∈ . С другой стороны, по определению насыщения 2 ,TA q Dx∉ влечёт ( ) 2 TCs∉ , а поскольку ( ) 222 ~ TTCT −= , то 2 ~ Ts∉ , и значит 21 ~ TTs I∉ , что противоречит допущению. Необходимость доказана. Докажем достаточность утверждения. Пусть выполняются включения 21 ,, TATA ii DDi ⊆∀ ; докажем, что выполняется равенство 2121 ~ TTTT −=I . В монографии [2] (утверждение 2.2.1 пункт 7) доказано включение 2121 ~ TTTT −⊆I , поэтому нам нужно доказать включение 2121 ~ TTTT I⊆− . Пусть ( ) ( ){ } 2111 ,,,, TTdAdAs kk −∈= K . Тогда 1 Ts∈ и 2 Ts∉ . Покажем, что 2 ~ Ts∈ . По определению активного домена выполняются принадлежности 11 ,1 TA Dd ∈ , …, 1 ,TAk k Dd ∈ . Из условий 21 ,, TATA ii DDi ⊆∀ следует, что 21 ,1 TA Dd ∈ , …, 2 ,TAk k Dd ∈ . По определению насыщения ( ) 2 TCs∈ , по определению операции активного дополнения в этом случае включение 2 Ts∉ влечет 2 ~ Ts∈ , поэтому 21 ~ TTs I∈ , то есть равенство выполняется. Выводы В работе найдены критерии, при которых в табличных алгебрах выполняются закон двойного отрицания и правило преобразования разности. Результаты работы могут быть использованы в теории обобщенных табличных алгебр и, на наш взгляд, для оптимизации запросов в реляционных базах данных. Автор благодарит Дмитрия Борисовича Буя за постановку задачи и полезные замечания. Сенченко А.С. «Искусственный интеллект» 2013 № 2 144 5С Литература 1. Codd E.F. A Relational Model of Data for Large Shared Data Banks / E.F. Codd // Communications of the ACM. – 1970. – V. 13, №. 6. – P. 377-387. 2. Реляційні бази даних: табличні алгебри та SQL-подібні мови / [В.Н. Редько, Ю.Й. Брона, Д.Б. Буй, С.А. Поляков]. – Київ : Видавничий дім «Академперіодика», 2001. – 198 с. 3. Мейер Д. Теория реляционных баз данных / Д. Мейер ; [пер. с англ.]. – Москва: Мир, 1987. – 608 с. Literaturа 1. Codd E.F. A Relational Model of Data for Large Shared Data Banks / E.F. Codd // Communications of the ACM. – 1970. – V. 13, №. 6. – P. 377-387. 2. Relational data base: table algebras and family of the SQL languages / [V.N. Redko, U.I. Brona, D.B. Buy, S.А. Polyakov]. – Kiev : Publisher «Academperiodica», 2001. – 198 р. (in Ukrainian). 3. D. Maier. The theory of Relational Databases / D. Maier ; [translation from English]. – Moscow : «Mir», 1987. – 608 p. (in Russian). RESUME A.S. Senchenko A Double Complement Law and a Difference Transformation Rule in Table Algebra In this paper some properties of operations of active complement and difference tables in table algebra is investigated. This algebra is built on the basis of Codd’s relational algebra and used for the theoretical ground of query languages of modern tabular databases. In book [2] is shown that in table algebra the double complement law and the difference transformation rule as inclusions are fulfilled. In this paper the necessary and sufficient conditions are found due to which in table algebra foregoing inclusions are becoming to identities. These conditions are defined in terms of relations between the active domains of attributes of tables. The results can be used in generalized table algebra theory and for query optimi- zation in relation databases. Статья поступила в редакцию 05.04.2013.

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