ПУЗІКОВА АННА ВАЛЕНТИНІВНА. ТЕОРІЯ НОРМАЛІЗАЦІЇ В ТАБЛИЧНИХ БАЗАХ ДАНИХ

Краткое описание

ПУЗІКОВА АННА ВАЛЕНТИНІВНА. Назва дисертаційної роботи: "ТЕОРІЯ НОРМАЛІЗАЦІЇ В ТАБЛИЧНИХ БАЗАХ ДАНИХ"

Міністерство освіти та науки України
Київський національний університет імені Тараса Шевченка
На правах рукопису
ПУЗІКОВА АННА ВАЛЕНТИНІВНА
УДК 004.655
ТЕОРІЯ НОРМАЛІЗАЦІЇ В ТАБЛИЧНИХ БАЗАХ ДАНИХ
01.05.03 – математичне та програмне забезпечення обчислювальних
машин і систем
Дисертація на здобуття наукового ступеня
кандидата фізико-математичних наук
Науковий керівник
доктор фіз.-мат. наук,
проф. Буй Дмитро Борисович
Київ – 2016
2
ЗМІСТ
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ ТА СКОРОЧЕНЬ ............................ 4
ВСТУП ............................................................................................................. 5
РОЗДІЛ 1 ТЕОРІЯ НОРМАЛІЗАЦІЇ В РЕЛЯЦІЙНИХ БАЗАХ ДАНИХ:
СУЧАСНИЙ СТАН............................................................................................... 10
1.1 Логіко-історичний огляд розвитку теорії нормалізації (класичні
нормальні форми 1-4 порядків) ....................................................................... 10
1.2 Аналіз еквівалентності означень класичної п‟ятої нормальної
форми.................................................................................................................. 16
1.3 Некласичні нормальні форми ............................................................ 18
1.4 Основні результати розділу ............................................................... 30
РОЗДІЛ 2 АКСІОМАТИКА ФУНКЦІОНАЛЬНИХ ЗАЛЕЖНОСТЕЙ
АРМСТРОНГА...................................................................................................... 32
2.1 Повнота аксіоматики Армстронга..................................................... 32
2.2 Критерій повноти аксіоматики Армстронга в термінах
потужностей множини атрибутів та універсального домена ....................... 44
2.3 Незалежність складових аксіоматики Армстронга ......................... 48
2.4 Алгебра функціональних залежностей в табличних базах даних . 50
2.5 Основні результати розділу ............................................................... 53
РОЗДІЛ 3 АКСІОМАТИКА БАГАТОЗНАЧНИХ І ФУНКЦІОНАЛЬНИХ
ЗАЛЕЖНОСТЕЙ................................................................................................... 56
3.1 Аксіоматика багатозначних залежностей......................................... 56
3.2 Аксіоматика багатозначних і функціональних залежностей ......... 65
3.3 Коректність та повнота аксіоматики багатозначних і
функціональних залежностей .......................................................................... 74
3.4 Критерій повноти аксіоматики багатозначних залежностей ......... 82
3.5 Критерій повноти аксіоматики багатозначних і функціональних
залежностей ....................................................................................................... 87
3.6 Основні результати розділу ............................................................... 90
3
РОЗДІЛ 4 ФРАГМЕНТ МАТЕМАТИЧНОЇ ТЕОРІЇ НОРМАЛІЗАЦІЇ:
НОРМАЛЬНІ ФОРМИ 2-4 ПОРЯДКІВ.............................................................. 92
4.1 Суперключі, потенційні ключі, первинні та непервинні атрибути,
повні та транзитивні ФЗ ................................................................................... 92
4.2 Друга нормальна форма ..................................................................... 98
4.3 Третя нормальна форма.................................................................... 100
4.4 Нормальна форма Бойса-Кодда....................................................... 104
4.5 Четверта нормальна форма .............................................................. 107
4.6 Основні результати розділу ............................................................. 109
ВИСНОВКИ................................................................................................. 111
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ................................................... 113
ДОДАТКИ.................................................................................................... 123
4
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ ТА СКОРОЧЕНЬ
БД база даних
СУБД система управління базами даних
НФ нормальна форма
ФЗ функціональна залежність
БЗЗ багатозначна залежність
□ кінець формулювання твердження, леми або теореми,
доведення
■ початок логічної частини доведення
▪ кінець логічної частини доведення
*( , ,..., ) R1 R2 Rn
залежність з‟єднання за підсхемами
1 2 , ,..., R R Rn

множина потенційних ключів

множина обмежень
відношення синтаксичного слідування
відношення семантичного слідування
 X ,R
операція проекції за множиною атрибутів
X
таблиць схеми
R

операція з‟єднання (природнього з‟єднання)
X
2
булеан множини
X
U | X
обмеження (звуження) відношення
U
за множиною
X
X F
[ ]
замикання множини атрибутів
X
відносно множини ФЗ
F
[ ] F
синтаксичне замикання множини ФЗ
F
 X
відношення еквівалентності для рядків, які збігаються на
множині атрибутів
X
bas
F G R
X
,
[ ] 
базис множини атрибутів
X
відносно множини залежностей
F G
і схеми
R
range s( )
множина значень рядка (функції)
s
5
ВСТУП
Актуальність теми дослідження. В багатьох сучасних напрямках
розвитку технологій баз даних (БД) в тій чи іншій мірі використовується
реляційна модель даних, яка була запропонована Е. Коддом у 70-х роках
ХХ ст.
Однією з ключових вимог, яка висувається до розробників БД, є
забезпечення їх надійності, яка, в свою чергу, значною мірою залежить від
правильності логічного проектування схеми БД. Проблема звільнення від
відомих аномалій (оновлення, вставки, знищення) в реляційних БД, яка
виникає на етапі логічного проектування внаслідок наявності різних видів
обмежень (наприклад, функціональних і багатозначних залежностей),
вимагає здійснення нормалізації – зведення до відповідних нормальних
форм. Про потреби в автоматизації процесу нормалізації свідчать розробки
CASE-засобів (Computer-Aided Software Engineering tools), наприклад, таких
як ERwin1
, Vantage Team Builder (Cadre), Silverrun2
), які здійснюють
нормалізацію до третоьї нормальної форми, що, в свою чергу, вимагає
залучення формальних, насамперед, математичних методів.
Теорія нормалізації спирається на теорію функціональних і
багатозначних залежностей, в основі якої лежать відповідні аксіоматики та
твердження про їх коректність і повноту. Аналіз наукової і методичної
літератури показав, що в ній відсутні доведення згадуваних результатів, які б
задовольняли стандартним вимогам до строгості математичного доведення, а
також, відсутні критерії, за яких аксіоматики функціональних і
багатозначних залежностей є повними.
Зв’язок роботи з науковими програмами, планами, темами.
Дисертаційна робота є складовою частиною наукових робіт, які велись на
кафедрі теорії та технології програмування факультету кібернетики

1
http://erwin.com/products/detail/ca_erwin_process_modeler/
2
http://www.silverrun.com/
6
Київського національного університету імені Тараса Шевченка при
виконанні фундаментальної теми: "Формальні специфікації та методи
розробки надійних програмних систем" (№ 0111U007052, 2011-2015 рр.).
Мета і завдання дисертаційного дослідження. Метою дисертаційної
роботи є математичні результати щодо коректності та повноти аксіоматик
функціональних і багатозначних залежностей в табличних (реляційних) БД, а
також цілісний несуперечливий фрагмент математичної теорії нормалізації
стосовно другої-четвертої нормальних форм.
Із огляду на мету в роботі ставляться такі задачі:
 побудувати математичне доведення відомого класичного
результату в теорії реляційних БД про повноту аксіоматики
Армстронга для функціональних залежностей, яке б задовольняло
стандартним вимогам строгості та повноти математичного
доведення;
 встановити критерій повноти аксіоматики ФЗ Армстронга;
 довести незалежність складових аксіоматики Армстронга в тому
розумінні, що без втрати повноти з аксіоматики не можна
видалити будь-яку складову;
 побудувати та дослідити алгебру функціональних залежностей;
 побудувати математичне доведення відомого класичного
результату в теорії реляційних БД про повноту аксіоматики
багатозначних і функціональних залежностей, яке б задовольняло
традиціям встановлення повноти в аксіоматичних системах;
 встановити критерії повноти аксіоматики багатозначних
залежностей та аксіоматики багатозначних і функціональних
залежностей;
 побудувати фрагмент математичної теорії нормалізації щодо
нормальних форм 2-4 порядків.
7
Об’єктом дисертаційного дослідження є табличні БД. Предметом
дослідження є аксіоматики функціональних і багатозначних залежностей та
нормалізація в табличних БД.
У роботі використовуються теоретико-множинні та логіко-алгебраїчні
методи.
Наукова новизна одержаних результатів. Доведення повноти
аксіоматик функціональних і багатозначних залежностей доповнено строгим
математичним доведенням їх коректності; для цього були введені
відношення синтаксичного і семантичного слідування для кожної з цих
аксіоматик.
Вперше встановлено критерії повноти аксіоматик функціональних і
багатозначних залежностей в термінах потужностей множин атрибутів та
універсального домена.
Певні важливі для доведення основних результатів властивості, поперше, замикання множини атрибутів в зазначених аксіоматиках та, подруге, базису в аксіоматиці багатозначних і функціональних залежностей
також розглянуті вперше.
Доведена незалежність складових аксіоматики Армстронга в вище
зазначеному розумінні.
Побудовано алгебру функціональних залежностей − алгебраїчний аналог
аксіоматики Армстронга, що дозволяє при дослідженні аксіоматики
використовувати алгебраїчну мову.
Теоретичне і практичне значення одержаних результатів. Дисертація
має теоретико-прикладну спрямованість. Отримані результати можуть бути
застосовані в учбовому процесі та при розробці CASE-засобів, які
підтримують нормалізацію.
Отримані результати були впроваджені у навчальний процес за
спеціальністю "Інформатика" на факультеті кібернетики Київського
національного університету імені Тараса Шевченка (нормативний курс
"Композиційна семантика SQL-подібних мов").
8
У Кіровоградському державному педагогічному університеті імені
Володимира Винниченка на кафедрі інформатики був прочитаний
нормативний курс "Бази даних та СУБД", що включає результати, отримані в
дисертації.
Особистий внесок здобувача. Основні результати роботи отримані
здобувачем самостійно. Статті [10-13, 48-51, 54-55, 58-59, 61-62] написані у
співавторстві з науковим керівником, якому належить постановка задачі
дослідження, вибір методів дослідження та обговорення результатів. Із
праць, виконаних зі співавторами, на захист виносяться лише результати,
отримані особисто здобувачем.
Апробація результатів дослідження. Основні положення та висновки
дисертаційного дослідження обговорювалися на наукових семінарах кафедри
теорії та технології програмування Київського національного університету
імені Тараса Шевченка.
Результати дисертаційного дослідження оприлюднені у доповідях і
повідомленнях на Міжнародних та Всеукраїнських наукових конференціях,
семінарах: І Міжнародному семінарі “Critical Infrastructure Safety and
Security” – CrISS-Dessert'11 (Кіровоград, Україна, 2011 р.), VIII Міжнародній
конференції "Теоретичні та прикладні аспекти побудови програмних систем"
– TAAPSD‟2011 (Ялта, Україна, 2011 р.), XVI Міжнародній конференції
"Проблемы теоретической кибернетики" (Нижній Новгород, РФ, 2011 р.),
X Міжнародній конференції “Теоретичні та прикладні аспекти побудови
програмних систем” – TAAPSD‟2013 (Ялта, Україна, 2013 р.),
VII Міжнародній науково-технічній конференції “Dependable Systems,
Services and Technologies” – DESSERT‟2014 (Київ, Україна, 2014 р.),
XVII Міжнародній конференції “Проблемы теоретической кибернетики”
(Казань, РФ, 16–20 червня 2014 р.), Міжнародній науково-технічній
конференції “Компьютерное моделирование в наукоемких технологиях”
(Харків, Україна, 28-31 травня 2014 р.), ІX Міжнародній конференції
“Інтернет-Освіта-Наука-2014” – ІОН-2014 (Вінниця, Україна, 14-17 жовтня
9
2014 р.), XI Міжнародній науковій конференції “Теоретичні та прикладні
аспекти побудови програмних систем” – TAAPSD‟2014 (Київ, Україна, 15-17
грудня 2014 р.), Міжнародній науковій конференції “Сучасні проблеми
математичного моделювання та обчислювальних методів” (Рівне, Україна,
19-22 лютого 2015 р.), XVII Міжнародній конференції “Дискретные модели в
теории управляющих систем” (Москва и Подмосковье, РФ, 20–22 мая
2015 г.), Tenth International Conference on Dependability and Complex Systems –
DepCoS-RELCOMEX (June 29 – July 3 2015, Brunów, Poland), Workshop on
Foundations of Informatics – FOI-2015 (August 24-29, 2015, Chisinau, Republic
of Moldova) [1210, 52, 60, 62, 13, 57, 58, 56, 50, 49, 53, 11, 10].
Публікації. Результати дисертаційного дослідження опубліковано у 19
працях. Серед них – 7 статей у наукових журналах і збірниках наукових
праць [11, 48, 51, 54-55, 59, 61], з них 6 статей опубліковано у фахових
виданнях, затверджених ВАК України, 1 стаття опублікована у науковому
фаховому іноземному виданні [11]; 12 праць конференцій [10, 12-13, 49-50,
52-53, 56-58, 60, 62].
Структура та обсяг дисертації. Дисертаційна робота складається зі
вступу, чотирьох розділів, висновків, списку використаних джерел
(81 найменування) і двох додатків. Загальний обсяг дисертації становить
132 с., основний зміст викладено на 107 с. Праця містить 9 табл. та 5 рис.

Список литературы

ВИСНОВКИ
Основні результати дисертаційної роботи.
1. Математично доведені повнота та коректність трьох основних
аксіоматик залежностей в реляційних БД: по-перше, аксіоматики ФЗ
Армстронга, по-друге, аксіоматики БЗЗ, та по-третє, аксіоматики ФЗ і
БЗЗ через збіжність відношень синтаксичного та семантичного
слідувань.
2. Встановлено критерії повноти аксіоматики ФЗ та аксіоматик ФЗ і БЗЗ
в термінах потужностей множини атрибутів та універсального домена.
3. Доведена незалежність складових аксіоматики ФЗ Армстронга
(видалення кожної складової зменшує породжуючу силу аксіоматики).
4. Побудована алгебра ФЗ, сигнатура якої складена відповідно до
складових аксіоматики ФЗ Армстронга. Розглянута підалгебра
тривіальних ФЗ та множина, яка її породжує. Це дозволяє
формулювати результати щодо властивостей аксіоматики Армстронга
на алгебраїчній мові.
5. Побудовано цілісний та несцперечливий фрагмент математичної
теорії нормалізації щодо нормальних форм 2-4 порядків. Для
спеціальних випадків встановлені значення потенційних ключів, а
також, достатні умови для знаходження таблиці у НФ 2-4 порядків.
Сформульовані означення 2-4 НФ задовольняють принципу
«включення» НФ вищих порядків в НФ нижчих порядків.
Зазначені результати дозволяють будувати математично обгрунтовані
алгоритми нормалізації.
Аналіз отриманих результатів дозволяє зробити наступні висновки.
1. Аксіоматика ФЗ Армстронга є повною, коли в інтерпретації
| D|  2
або
| R| 0.
112
2. Аксіоматика Армстронга є незалежною в тому розумінні, що без
втрати повноти не можна опустити ні єдину аксіому, ні жодне з
правил виведення.
3. Аксіоматика БЗЗ є повною, коли в інтерпретації
| | 1 R 
або
| R | 2
і при цьому
| D |  2.
4. Аксіоматика ФЗ і БЗЗ є повною, коли в інтерпретації
| D|  2
або
| R| 0.
5. НФ знаходяться у логічному зв‟язку вигляду 4НФ

НФБК


3НФ

2НФ.