Шишацька Олена Володимирівна Формальні моделі баз даних та багатозначні логі­ки

Короткий опис

Шишацька Олена Володимирівна, асистент кафе­дри теорії та технології програмування Київського національного університету імені Тараса Шевченка: «Формальні моделі баз даних та багатозначні логі­ки» (01.05.03 - математичне та програмне забезпе­чення обчислювальних машин і систем). Спецрада Д 26.001.09 у Київському національному університеті імені Тараса Шевченка

Київський національний університет імені Тараса Шевченка
Міністерство освіти і науки України
Київський національний університет імені Тараса Шевченка
Міністерство освіти і науки України
Кваліфікаційна наукова
праця на правах рукопису
ШИШАЦЬКА ОЛЕНА ВОЛОДИМИРІВНА

УДК 004.652
ДИСЕРТАЦІЯ
ФОРМАЛЬНІ МОДЕЛІ БАЗ ДАНИХ ТА БАГАТОЗНАЧНІ ЛОГІКИ
01.05.03 – Математичне та програмне забезпечення обчислювальних машин і
систем
Подається на здобуття наукового ступеня кандидата фізико-математичних наук
Дисертація містить результати власних досліджень. Використання ідей,
результатів і текстів інших авторів мають посилання на відповідне джерело
___________________________ підпис, ініціали та прізвище здобувача
Науковий керівник Буй Дмитро Борисович, доктор фіз.-мат. наук, професор
Київ – 2019

ЗМІСТ
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ ТА СКОРОЧЕНЬ....................................... 15
ВСТУП........................................................................................................................ 16
РОЗДІЛ 1. ФОРМАЛЬНІ МОДЕЛІ БАЗ ДАНИХ. ПРЕДСТАВЛЕННЯ
НЕВИЗНАЧЕНОЇ ІНФОРМАЦІЇ В БАЗАХ ДАНИХ ........................................... 22
1.1. Моделі баз даних та їх основні характеристики ...................................... 23
1.2. Представлення невизначеної інформації в базах даних ............................. 25
1.2.1. Типи невизначеностей в моделях баз даних...................................... 25
1.2.2. Системи багатозначних логік та їх використання............................. 31
1.2.3. Багатозначна логіка в мовах керування/управління базами даних . 33
1.3. Модель даних UML/OCL............................................................................ 38
1.3.1. Уніфікована мова моделювання UML................................................ 39
1.3.2. Формальний синтаксис та семантика об’єктних моделей ............... 48
1.3.3. Синтаксис та семантика ядра мови об’єктних обмежень OCL ........... 51
1.3.4. Багатозначні логіки мови ОCL............................................................ 69
1.4. Висновки....................................................................................................... 72
РОЗДІЛ 2. БАГАТОЗНАЧНІ ЛОГІКИ.................................................................... 73
2.1. Тризначні логіки Кліні................................................................................ 73
2.1.1. Сильна тризначна логіка Кліні ............................................................... 74
2.1.2. Слабка тризначна логіка Кліні................................................................ 80
2.1.3. Алгебри часткових предикатів, індуковані тризначними логіками
Кліні ..................................................................................................................... 86
2.2. Багатозначні логіки, отримані розширенням сигнатурних операцій
сильної тризначної логіки Кліні ....................................................................... 91
2.3. Висновки....................................................................................................... 96
РОЗДІЛ 3. СЕМАНТИЧНІ ВЛАСТИВОСТІ П’ЯТИЗНАЧНИХ ЛОГІК............. 97
3.1. Онтологічне обґрунтування п’ятизначної логіки ................................ 100
3.2. Пропозиційна п'ятизначна EU-логіка...................................................... 104
14
3.2.1. Визначення пропогшзиційних зв'язок логіки L
P, EU
..................... 105
3.2.2. Алгебра істиннісних значень та її властивості................................ 107
3.2.3. Мова пропозиційної EU-логіки......................................................... 109
3.2.4. Відношення еквівалентності формул та логічного наслідку.
Принцип дуальності......................................................................................... 110
3.3. EU-логіка п'ятизначних квазіарних предикатів......................................... 113
3.3.1. Алгебра п'ятизначних квазіарних предикатів та її властивості......... 114
3.3.2. Мова п'ятизначних квазіарних предикатів та її властивості ............. 118
3.3.3. Принцип дуальності та нормальні форми ........................................... 119
3.4. Висновки..................................................................................................... 121
РОЗДІЛ 4. РОЗШИРЕННЯ МОДЕЛІ UML/OCL ДО П’ЯТИЗНАЧНОЇ EUЛОГІКИ .................................................................................................................... 122
4.3. Висновки..................................................................................................... 128
ВИСНОВКИ............................................................................................................. 130
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ............................................................... 132
Додадок 1. Форми некласичних даних та їхні характеристики ......................... 151
Додаток 2. Означення компонентів об’єктної моделі ......................................... 152
Додаток 3.Синтаксис базових типів та їх операцій ............................................. 158
Додаток 4. Вхідний файл (OCLjflex) генератора JFlex для OCL/ ...................... 178
Додаток 5. Вхідний файл (OCL.cup) генератора CUP для розширеної граматики
OCL. .......................................................................................................................... 183
Додаток 6. Список публікацій здобувача за темою дисертації .......................... 198
Додаток 7. Відомості про апробацію результатів дисертації ............................. 202

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

ВИСНОВКИ
Головним результатом дисертаційної роботи є побудова нового класу
програмно-орієнтованих логічних формалізмів – пропозиційних п’ятизначних
логік та логік п’ятизначних квазіарних предикатів, які дозволяють адекватно
формалізувати специфікації моделей баз даних.
У роботі отримано наступні результати:
1. Проаналізовано та систематизовано наявні підходи до представлення
невизначеної інформації в базах даних. Одним з підходів до подання та
опрацювання такої інформації є застосування багатозначних логік. На сьогодні
найбільш використовуваними логіками є двозначні та тризначні, зустрічаються
чотиризначні, однак майже не представлена робота з логіками, основою яких є
більше чотирьох істиннісних значень. В роботі показано, що використання
останніх призводить до підвищення рівня адекватності побудови формальних
моделей деяких класів інформаційних систем предметній області.
2. Досліджено та формально описано модель UML/OCL (об’єктну модель
у нотації UML з обмеженнями цілісності засобами OCL-виразів). Уточнено
синтаксичні та семантичні структури мови об’єктних обмежень OCL.
3. Для типових задач, що виникають при специфікації моделей баз даних і
природним чином індукують багатозначні логіки, досліджено еволюцію
використання багатозначної логіки на прикладі версій мови OCL. Досліджено
основні відмінності синтаксичних та семантичних структур версій мови для
оптимального вибору представлення невизначеної інформації в моделях баз даних.
4. Для побудови нових багатозначних логік використано конструкцію
повного образу, що дозволяє природним чином поширити операції на певній
множині елементів на її булеан. Продемонстровано виникнення сильної та слабкої
тризначних логік Кліні. Досліджено відповідні структури алгебри цих логік.
Конструкцію повного образу застосовано до сильної тризначної логіки Кліні.
131
5. Визначено передумови побудови п’ятизначних логік (EU-логік), які
дозволяють адекватно моделювати предметну область при формальній розробці
інформаційних систем. Наведено приклади п’ятизначних функцій та предикатів,
які індукують відповідні п’ятизначні логіки.
6. Побудовано і досліджено п’ятизначні логіки: логіку пропозиційного
рівня та логіку квазіарних предикатів. Визначено та доведено їх основні
властивості. Конструктивно побудовано нормальні форми (пренексну,
реномінативно-атомарну та квазікласичну) для довільної формули п’ятизначної
логіки квазіарних предикатів, застосування яких дозволяє ефективно проводити
перевірку виконуваності та спростовності цих формул, звівши спочатку
проблему виконуваності та спростовності формул до логіки n-арних
п’ятизначних предикатів, а далі – до класичної (бівалентної) логіки предикатів.
7. На основі побудованих логічних формалізмів розширено логіку моделі
UML/OCL до п’ятизначної логіки. Отримані результати застосовані та
апробовані при програмній реалізації прототипу синтаксичного аналізатора
розширеної мови OCL.