Незалежність аксіоматики Армстронга та алгебра функціональних залежностей
Встановлюється незалежність складових аксіоматики Армстронга щодо функціональних залежностей в реляційних базах даних. Будується алгебра функціональних залежностей, операції якої визначаються відповідно до складових аксіоматики Армстронга. We establish the independence of the Armstrong’s axiomatic s...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2015 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/117157 |
| 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: | Незалежність аксіоматики Армстронга та алгебра функціональних залежностей / Д.Б. Буй, А.В. Пузікова // Штучний інтелект. — 2015. — № 1-2. — С. 121-126. — Бібліогр.: 3 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-117157 |
|---|---|
| record_format |
dspace |
| spelling |
Буй, Д.Б. Пузікова, А.В. 2017-05-20T10:47:01Z 2017-05-20T10:47:01Z 2015 Незалежність аксіоматики Армстронга та алгебра функціональних залежностей / Д.Б. Буй, А.В. Пузікова // Штучний інтелект. — 2015. — № 1-2. — С. 121-126. — Бібліогр.: 3 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/117157 004.65 Встановлюється незалежність складових аксіоматики Армстронга щодо функціональних залежностей в реляційних базах даних. Будується алгебра функціональних залежностей, операції якої визначаються відповідно до складових аксіоматики Армстронга. We establish the independence of the Armstrong’s axiomatic system (as for the functional dependences of relational databases) and built the algebra of functional dependencies with operations that are induced by components of this axiomatics. Показывается независимость составляющих аксиоматики Армстронга для функциональных зависимостей в реляционных базах данных. Строится алгебра функциональных зависимостей, операции которой определяются в соответствии с составляющими аксиоматики Армстронга. uk Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Теорія та засоби обчислювального інтелекту Незалежність аксіоматики Армстронга та алгебра функціональних залежностей Независимость аксиоматики армстронга и алгебра функциональных зависимостей The independence of the Armstrong’s axiomatic system and algebra of functional dependencies Article 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 |
Буй, Д.Б. Пузікова, А.В. |
| topic |
Теорія та засоби обчислювального інтелекту |
| topic_facet |
Теорія та засоби обчислювального інтелекту |
| publishDate |
2015 |
| language |
Ukrainian |
| container_title |
Штучний інтелект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Независимость аксиоматики армстронга и алгебра функциональных зависимостей The independence of the Armstrong’s axiomatic system and algebra of functional dependencies |
| description |
Встановлюється незалежність складових аксіоматики Армстронга щодо функціональних залежностей в реляційних базах даних. Будується алгебра функціональних залежностей, операції якої визначаються відповідно до складових аксіоматики Армстронга.
We establish the independence of the Armstrong’s axiomatic system (as for the functional dependences of relational databases) and built the algebra of functional dependencies with operations that are induced by components of this axiomatics.
Показывается независимость составляющих аксиоматики Армстронга для функциональных зависимостей в реляционных базах данных. Строится алгебра функциональных зависимостей, операции которой определяются в соответствии с составляющими аксиоматики Армстронга.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/117157 |
| citation_txt |
Незалежність аксіоматики Армстронга та алгебра функціональних залежностей / Д.Б. Буй, А.В. Пузікова // Штучний інтелект. — 2015. — № 1-2. — С. 121-126. — Бібліогр.: 3 назв. — укр. |
| work_keys_str_mv |
AT buidb nezaležnístʹaksíomatikiarmstrongataalgebrafunkcíonalʹnihzaležnostei AT puzíkovaav nezaležnístʹaksíomatikiarmstrongataalgebrafunkcíonalʹnihzaležnostei AT buidb nezavisimostʹaksiomatikiarmstrongaialgebrafunkcionalʹnyhzavisimostei AT puzíkovaav nezavisimostʹaksiomatikiarmstrongaialgebrafunkcionalʹnyhzavisimostei AT buidb theindependenceofthearmstrongsaxiomaticsystemandalgebraoffunctionaldependencies AT puzíkovaav theindependenceofthearmstrongsaxiomaticsystemandalgebraoffunctionaldependencies |
| first_indexed |
2025-11-24T02:22:29Z |
| last_indexed |
2025-11-24T02:22:29Z |
| _version_ |
1850839992480301056 |
| fulltext |
ISSN 1561 – 5359. Штучний інтелект, 2015, № 1-2
© Д.Б. Буй, А.В. Пузікова 121
УДК 004.65
Д.Б. Буй1, А.В. Пузікова1
1Київський національний університет імені Тараса Шевченка
Україна, 01033, м. Київ, вул. Володимирська, 60
НЕЗАЛЕЖНІСТЬ АКСІОМАТИКИ АРМСТРОНГА ТА
АЛГЕБРА ФУНКЦІОНАЛЬНИХ ЗАЛЕЖНОСТЕЙ
D.B.Bui1, А.V. Puzikova1
1Taras Shevchenko National University of Kyiv
Ukraine, 01033, Kyiv, Vladimirskaya st., 60
THE INDEPENDENCE OF THE ARMSTRONG’S
AXIOMATIC SYSTEM AND ALGEBRA OF FUNCTIONAL
DEPENDENCIES
Д.Б. Буй1, А.В. Пузикова1
1 Киевский национальный университет имени Тараса Шевченко
Украина, 01033, г. Киев, ул. Владимирская, 60
НЕЗАВИСИМОСТЬ АКСИОМАТИКИ АРМСТРОНГА И
АЛГЕБРА ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ
Встановлюється незалежність складових аксіоматики Армстронга щодо функціональних
залежностей в реляційних базах даних. Будується алгебра функціональних залежностей, операції якої
визначаються відповідно до складових аксіоматики Армстронга.
Ключові слова: реляційні бази даних, аксіоматика Армстронга, функціональні
залежності.
We establish the independence of the Armstrong’s axiomatic system (as for the functional dependences of
relational databases) and built the algebra of functional dependencies with operations that are induced by
components of this axiomatics.
Key words: relational databases, Armstrong’s axiomatic system, functional dependencies.
Показывается независимость составляющих аксиоматики Армстронга для функциональных
зависи-мостей в реляционных базах данных. Строится алгебра функциональных зависимостей,
операции которой определяются в соответствии с составляющими аксиоматики Армстронга.
Ключевые слова: реляционные базы данных, аксиоматика Армстронга, функциональные
зависимости.
Вступ
У попередніх роботах авторів було побудовано суворе та повне доведення
повноти аксіоматики Армстронга щодо функціональних залежностей (ФЗ) в
реляційних базах даних, яке наслідує традиції встановлення повноти
аксіоматичних систем у математичній логіці: введені відношення синтаксичного
та семантичного слідувань та показана їх збіжність [1], а також наведено критерій
повноти аксіоматики Армстронга в термінах потужностей множини атрибутів та
універсального домена [2].
Метою даної роботи є доведення незалежності складових аксіоматики
Армстронга та побудова алгебри ФЗ.
Незалежність аксіоматики функціональних залежностей Армстронга
Аксіоматика ФЗ Армстронга при зафіксованій множині атрибутів складається з:
аксіом рефлексивності X Y , Y X ;
ISSN 1561 – 5359. Штучний інтелект, 2015, № 1-2
122 © Д.Б. Буй, А.В. Пузікова
правил поповнення X Y
X Z Y Z
для Z R ;
правил транзитивності ,X Y Y Z
X Z
.
Лема 1. Аксіоми рефлексивності є незалежними від правил виведення
аксіоматики Армстронга.
Доведення є тривіальним, оскільки інших аксіом в аксіоматиці Армстронга
взагалі немає.
Лема 2. Правила транзитивності є незалежними від аксіом рефлексивності і
правил поповнення.
Доведення. Для доведення достатньо вказати множину ФЗ F , для якої
| |[ ] [ ]trF F , де |[ ] trF – замикання множини ФЗ F , побудоване за допомогою
аксіом рефлексивності і правил поповнення, а |[ ]F – замикання множини ФЗ F
відносно всіх аксіом і правил виведення [1]. Зафіксуємо множини атрибутів X і
Z , такі, що X Z , і розглянемо множину ФЗ F , яка задовольняє умовам
( )Y R X Y F Y Z F X Z F . Покажемо, що ФЗ X Z не
може бути виведена лише із застосуванням аксіом рефлексивності та правил
поповнення.
Оскільки Z X , то Z ⊈ X , отже, ФЗ X Z не є тривіальною.
Припустимо, що ФЗ X Z отримана з деякої ФЗ U V за правилом
поповнення, тобто існує така множина атрибутів W , що U W X і
V W Z . Тоді ( ) ( )Z X V W U W W , що суперечить умові
Z X . Отримали протиріччя з припущенням, отже, | |[ ] [ ]trF F і правило
транзитивності є незалежним.
Лема 3. Правила поповнення є незалежними від аксіом рефлексивності і
правил транзитивності.
Доведення. Розглянемо множину ФЗ { { }| }F X A A X X і
покажемо, що ФЗ вигляду { }X X A , де A X і X , не можна вивести
лише із застосуванням аксіом рефлексивності і правил транзитивності.
Припустимо, що ФЗ { }X X A F , тоді її права частина є
одноелементною множиною. Останнє виконується, якщо:
- A X і { }X A ;
- A X і X .
Оскільки кожен з зазначених випадків суперечить визначенню множини ФЗ
F , то { }X A не є одноелементною множиною і ФЗ { }X X A F .
Оскільки A X , то ФЗ { }X X A не є тривіальною.
Припустимо, ФЗ { }X X A отримана за правилами транзитивності.
Враховуючи, що
1) множина тривіальних ФЗ замкнена відносно правила транзитивності
([2, лема 3]);
2) результатом застосування правила транзитивності до ФЗ з
одноелементною правою частиною є ФЗ, права частина якої є знову
одноелементною множиною;
ISSN 1561 – 5359. Штучний інтелект, 2015, № 1-2
© Д.Б. Буй, А.В. Пузікова 123
3) результатом застосування правила транзитивності до тривіальної ФЗ і ФЗ з
одноелементною правою частиною є ФЗ з одноелементною правою частиною;
4) результатом застосування правила транзитивності до ФЗ виду { }X A і
тривіальної ФЗ { } { }A A є ФЗ виду { }X A ,
доходимо висновку, що ФЗ { }X X A повинна бути або тривіальною або її права
частина є одноелементною множиною, що суперечить визначенню цієї ФЗ.
Отримали протиріччя з припущенням, отже, правило транзитивності є незалежним.
Теорема 1. Аксіоматика Армстронга є незалежною.
Доведення випливає безпосередньо з лем 1-3.
Алгебра ФЗ. Задамо алгебру ,A , носієм якої є множина ФЗ
| , 2RX Y X Y , де 2R – булеан множини R ; а сигнатура складається з
операцій, які задаються наступним чином:
– нуль-арні операції (0)X Y , де ,X Y R , причому Y X , які відповідають
аксіомам рефлексивності в аксіоматиці Армстронга;
– унарні параметриричні операції (1)
ZR , які відповідають правилам поповнення
в аксіоматиці Армстронга:
(1) (1): , 2 , { | , 2 }R R
Z ZR Z dom R X Y X Y ,
(1) ( )ZR X Y X Z Y Z ;
– бінарна часткова операція (2)R , яка відповідає правилу транзитивності в
аксіоматиці Армстронга:
(2) (2): , , |R dom R X Y Y Z Y Y ,
(2) ( , )R X Y Y Z X Z .
Таким чином, алгебра ФЗ є частковою [3] і задається як:
(1) (2) (0)
, 2 , , 2 ,
,{ , , }R RZX Y Z X Y Y X
A X Y R R X Y
.
Позначимо множину аксіом рефлексивності, які задаються нуль-арними
операціями (0)X Y через { | , 2 }R
r X Y X Y Y X . Очевидно, що
(1) (2)
, , 2 ,
,{ , } Rr Z Z X Y Y X
A R R
є підалгеброю алгебри A , оскільки множина
тривіальних ФЗ r є замкненою відносно вказаних операцій.
Лема 4. Множина
0
|r A A R породжує множину тривіальних
залежностей r за допомогою операцій (1)
ZR і (2)R .
Доведення. Покажемо, що довільну тривіальну ФЗ rX Y де Y X
можна отримати з множини
0r
за допомогою операцій (1)
ZR і (2)R .
Нехай схема R задається множиною атрибутів 1 2, ,..., nA A A . Не втрачаючи
загальності, представимо множини атрибутів X і Y , де Y X , відповідно
1 2, ,..., mA A A і 1 2, ,..., kA A A , де k m n .
Якщо k m , то тривіальну ФЗ X Y можна отримати з ФЗ iA , де i –
фіксоване, причому i m , виконавши операцію:
1
(1)
1 1{ ,..., }({ } ) { } { ,..., } { ,..., }
m i i m mA AR A A A A A A ,
ISSN 1561 – 5359. Штучний інтелект, 2015, № 1-2
124 © Д.Б. Буй, А.В. Пузікова
результатом якої є ФЗ 1 1{ ,..., } { ,..., }m mA A A A .
У випадку k m ФЗ X Y можна отримати з множини ФЗ
1 2{ } ,{ } ,...,{ }k k mA A A , виконавши наступну послідовність
операцій:
крок 1:
1
(1)
1 1 1 1{ ,..., }({ } ) { } { ,..., } { ,..., }
k k k k kA AR A A A A A A ,
результатом якої є ФЗ 1 1 1{ ,..., } { ,..., }k kA A A A ; якщо 1k m , то ФЗ X Y
отримана, інакше ( 1k m ) виконуємо крок 2, який складається з двох операцій:
1)
1 1
(1)
2 2 1 1 1 1{ ,..., }({ } ) { } { ,..., } { ,..., }
k k k k kA AR A A A A A A
,
результатом якої є ФЗ 1 2 1 1{ ,..., } { ,..., }k kA A A A ;
2) (2)
1 2 1 1 1 1 1({ ,..., } { ,..., },{ ,..., } { ,..., })k k k kR A A A A A A A A
1 2 1{ ,..., } { ,..., }k kA A A A .
Перепишемо крок 2 для k i m ( 1,2,..., 1i m k ):
1)
1
(1)
1 1 1 1{ ,..., }({ } ) { } { ,..., } { ,..., }
k i k i k i k i k iA AR A A A A A A
,
результатом якої є ФЗ 1 1 1{ ,..., } { ,..., }k i k iA A A A ;
2) (2)
1 1 1 1 1({ ,..., } { ,..., },{ ,..., } { ,..., })k i k i k i kR A A A A A A A A
1 1 1{ ,..., } { ,..., }k i kA A A A .
Виконавши крок 2 1m k разів отримаємо ФЗ 1 1{ ,..., } { ,..., }m kA A A A ,
тобто, ФЗ X Y .
Таким чином, замикання множини
0r r операціями збіднення алгебри A
( (1)
ZR і (2)R операції збіднення, позначається: (1) (2)0 ,
[ ]
Z
r R R
) співпадає з
множиною тривіальних залежностей r , тобто:
(1) (2)0 ,
[ ]
Z
r rR R
.
У свою чергу, результат виконання операції (1)
ZR можна представити за
допомогою операції (1)
{ }AR , A R , отже, маємо:
(1) (2)0
{ },
[ ]
A
r rR R
.
Лема 5. Множина
0r – найменша множина, яка породжує множину r за
допомогою операцій (1)
{ }AR , A R , і (2)R .
Доведення. Якщо схема R , то очевидно, що
0
{ }r r .
Розглянемо випадок, коли схема R . Зафіксуємо деякий атрибут B R і
розглянемо множину
0 0r r таку, що 0
{ } | \r A A R B . Покажемо, що
множина
0r не породжує множину
0r r за допомогою операцій (1)
{ }AR , A R і
(2)R ; для цього розглянемо можливі випадки для ФЗ { }B :
ISSN 1561 – 5359. Штучний інтелект, 2015, № 1-2
© Д.Б. Буй, А.В. Пузікова 125
1. ФЗ { }B не може бути результатом виконання операції (1)
{ }AR , A R ,
застосованої до деякої тривіальної ФЗ
0r , оскільки містить порожню
множину у своїй правій частині;
2. припустимо, що тривіальна ФЗ { }B є результатом виконання операції
(2)R , застосованої до деяких тривіальних ФЗ
0
, r . Тоді повинна існувати
така множина атрибутів Y , де { }Y B , що виконуються ФЗ { }B Y і
Y . Випадки, коли Y або { }Y B вимагають використання самої ФЗ
{ }B :
a. { }B і ;
b. { } { }B B і { }B .
Оскільки множини атрибутів Y , яка б задовольняла умові { }Y B не
існує, приходимо до висновку, що множина
0r не породжує множину
0r r , а
отже, не породжує множину r .
Таким чином, алгебра ФЗ задається як своє збіднення наступного вигляду:
(1) (2) (0)
{ }, 2 ,{ , ,{ } }R A RAX YA X Y R R A
.
Зауважимо, що замикання [ ]F множини ФЗ F , де , 2RX YF X Y можна
розглядати як замикання множини
0rF операціями (1)
{ }AR , A R , і (2)R :
(1) (2)0
{ },
[ ]
A
r R R
F
.
Висновки
Показано, що аксіоматика Армстронга щодо функціональних залежностей, яка
складається з аксіом рефлексивності (можна казати про одну схему аксіом
рефлексивності), правила транзитивності та правил поповнення (і, знову ж, можна
казати про одну схему правил поповнення), є незалежною в тому розумінні, що без
втрати повноти не можна вилучити ні схему аксіом рефлексивності, ні правило
транзитивності, ні схему правил поповнення.
Побудована алгебра функціональних залежностей, операції якої визначені
відповідно до складових аксіоматики Армстронга. Розглянута підалгебра
тривіальних ФЗ та множина, яка її породжує. Побудова цієї алгебри дозволяє
формулювати результати щодо властивостей аксіоматики Армстронга алгебраїчною
мовою.
Література
1. Буй Д.Б. Повнота аксіоматики Армстронга / Д.Б. Буй, А.В. Пузікова // Вісник Київського національного
університету ім. Т. Шевченка. Серія: фіз.-мат. науки, 2011. – № 3. – С. 103-108.
2. Буй Д.Б. Критерій повноти аксіоматики Армстронга / Д.Б. Буй, А.В. Пузікова . // Матеріали 8-ої
міжнародної конференції «Теоретичні та прикладні аспекти побудови програмних систем» –
TAAPSD’2011 (Україна, Ялта, 19-23 вересня 2011 року). – C. 30-34.
3. Мальцев А.И. Алгоритмы и вычислимые функции. М.: Наука, 1965. 392 с.
ISSN 1561 – 5359. Штучний інтелект, 2015, № 1-2
126 © Д.Б. Буй, А.В. Пузікова
Literatura
1. Bui D.B. Completeness of Armstrong’s axiomatic / D.B. Bui, A.V. Puzikova // In Bulletin of Taras
Shevchenko National University of Kyiv. Series Physics & Mathematics. Volume 3, 2011. – P. 103-108.
2. Bui D.B. Completeness criteria of Armstrong’s axiomatic / D.B. Bui, A.V. Puzikova // The Eight
International Conference "Theoretical and Applied Aspects of Program Systems Development
(TAAPSD'2011). Abstracts (Ukraine, Yalta, 19-23 September 2011). Kirovograd: Avangard, 2011. –
P. 30-34.
3. Maltsev А.І. Algorithms and computational functions. Moscow: Nauka, 1965. 392 р.
RESUME
D.B. Bui, А.V. Puzikova
The independence of the Armstrong’s axiomatic system and algebra of functional
dependencies
It is shown that Armstrong’s axiomatic system for the functional dependences of
relational databases, which consists of the axioms of reflexivity (we can say about a single
schema of reflexivity axioms), rule of transitivity and rules of augmentation (again, for
rules of augmentation we can say about a single schema of these rules) is independent. It
means that completeness of Armstrong’s axiomatic system is violated if removed one of its
components: whether schema of the axioms of reflexivity or rule of transitivity or schema
of rules of augmentation.
Algebra of functional dependencies with operations that are induced by components
of the axioms Armstrong is built. Subalgebra of trivial functional dependencies and the set
that generates its, are considered. The construction of this algebra allows us to formulate
the results concerning properties of Armstrong’s axiomatic system in algebraic language.
Д.Б. Буй, А.В. Пузикова
Независимость аксиоматики Армстронга и алгебра функциональных
зависимостей
Показано, что аксиоматика Армстронга для функциональных зависимостей в
реляционных базах данных, которая состоит из аксиом рефлексивности (можно
говорить об одной схеме аксиом рефлексивности), правила транзитивности и правил
пополнения (и снова можно говорить об одной схеме правил пополнения), является
независимой в том смысле, что без потери полноты нельзя удалить ни схему аксиом
рефлексивности, ни правило транзитивности, ни схему правил пополнения.
Построена алгебра функциональных зависимостей, операции которой
определены в соответствии с составляющими аксиоматики Армстронга. Рассмотрена
подалгебра тривиальных функциональных зависимостей и множество, которое ее
порождает. Построение этой алгебры позволяет формулировать результаты,
касающиеся свойств аксиоматики Армстронга, на алгебраическом языке.
Надійшла до редакції 16.09.2015
|