Чистякова Інна Сергіївна Метод відображення між дескриптивною логікою та реляційною моделлю даних : Чистякова Инна Сергеевна Метод отображения между дескриптивной логике и реляционной моделью данных Chistyakova Inna Serhiivna Mapping method between descriptive logic and relational data model

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

Чистякова Інна Сергіївна, молодший науковий співробітник відділу автоматизованих інформаційних систем, Інститут програмних систем НАН України. Назва дисертації: «Метод відображення між дескриптивною логікою та реляційною моделлю даних». Шифр та назва спеціальності 01.05.03 математичне та програмне забезпечення обчислювальних машин і систем. Спецрада Д26.001.09 Київського національного університету імені Тараса Шевченка

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

ЗМІСТ
ВСТУП........................................................................................................................ 14
РОЗДІЛ 1 ОГЛЯД ЛІТЕРАТУРИ ТА ВИБІР НАПРЯМКУ ДОСЛІДЖЕНЬ .......... 21
1.1 Складові проблеми інтеграції даних .............................................................. 22
1.2 Онтолого-орієнтована інтеграція даних......................................................... 25
1.3 Відображення між онтологіями та реляційними базами даних.................... 28
1.3.1 Використання проміжної моделі ................................................................. 31
1.3.2 Безпосереднє відображення онтології в БД ................................................ 32
1.3.3 Безпосереднє відображення БД в онтологію .............................................. 33
1.4 Висновки до першого розділу ........................................................................ 39
РОЗДІЛ 2 ВИЗНАЧЕННЯ ПІДМНОЖИНИ РЕЛЯЦІЙНОЇ МОДЕЛІ ДАНИХ ТА
ДЕСКРИПТИВНОЇ ЛОГІКИ ДЛЯ СТВОРЕННЯ ВІДОБРАЖЕНЬ ....................... 40
2.1 Бінарна реляційна модель даних .................................................................... 41
2.1.1 Бінарна реляційна структура даних............................................................. 41
2.1.2 Бінарна реляційна алгебра ........................................................................... 42
2.1.3 Обмеження цілісності .................................................................................. 48
2.2 Перетворення n-арної реляційної структури в бінарну................................. 49
2.3 Визначення підмножини дескриптивної логіки та поняття реіфікації......... 52
2.4 Висновки до другого розділу.......................................................................... 57
РОЗДІЛ 3 ВІДОБРАЖЕННЯ МІЖ ДЕСКРИПТИВНОЮ ЛОГІКОЮ ТА
БІНАРНОЮ РЕЛЯЦІЙНОЮ МОДЕЛЛЮ ДАНИХ ................................................ 58
3.1 Побудова концептуальної інформаційної моделі DL.................................... 58
3.2 Відображення DL ALC у RM2
........................................................................ 63
3.2.1 Відображення концептів C і D..................................................................... 64
3.2.2 Відображення ролі R .................................................................................... 64
3.2.3 Відображення концептів Thing та Nothing.................................................. 65
3.2.4 Відображення доповнення концепту C ....................................................... 65
3.2.5. Відображення об’єднання концептів С і D ................................................ 66
3.2.6 Відображення перетину концептів С і D..................................................... 66
3.2.7 Відображення конструктора екзистенціального обмеження ..................... 66
12
3.2.8 Відображення конструктора обмеження значення..................................... 67
3.3 Відображення розширень ALC в RM2
............................................................ 69
3.3.1 Відображення чисельних обмежень на ролі ............................................... 69
3.3.2 Відображення номіналу ............................................................................... 73
3.3.3 Відображення конструкторів ролей ............................................................ 74
3.4 Відображення термінологічних аксіом DL в RM2
......................................... 78
3.5 Відображення бінарної реляційної моделі даних в дескриптивну логіку.... 79
3.6 Висновки до третього розділу ........................................................................ 86
РОЗДІЛ 4 СПОСІБ ПЕРЕВІКРИ ВІДОБРАЖЕНЬ МІЖ ДЕСКРИПТИВНОЮ
ЛОГІКОЮ ТА РЕЛЯЦІЙНОЮ МОДЕЛЛЮ ДАНИХ НА РІВНІ RDF .................. 88
4.1 Огляд літератури ............................................................................................. 89
4.2 Постановка задачі............................................................................................ 98
4.3 Огляд засобу трансляції OWL 2 у RDF........................................................ 103
4.4 Огляд мови R2R ML...................................................................................... 109
4.5 Апробація алгоритму відображення DL-RM2 у RDF .................................. 114
4.6 Апробація алгоритму відображення RM2
-DL у RDF .................................. 118
4.7 Оцінка складності алгоритму відображення................................................ 126
4.8 Висновки до четвертого розділу................................................................... 130
ВИСНОВКИ ............................................................................................................. 133
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ................................................................. 135
ДОДАТОК 1 ............................................................................................................. 148
ДОДАТОК 2 ............................................................................................................. 153
ДОДАТОК 3 ............................................................................................................. 163
ДОДАТОК 4 ............................................................................................................. 166
ДОДАТОК 5 ............................................................................................................. 171
ДОДАТОК 6 ............................................................................................................. 173
ДОДАТОК 7 ............................................................................................................. 174
13
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ
ІС – інфомаційна система
СІД – система інтеграції даних
БД – база даних
РБД – реляційна база даних
МД – модель даних
РМД – реляційна модель даних
СУБД – система управління базами даних
RDM – Relational Data Model
RDB – Relational Database
DL – Description Logic
ALC – Attributive Language with Complement
RM2 – бінарна реляційна модель даних
RS2 – бінарна реляційна структура даних
RA2 – бінарна реляційна алгебра
OWL 2 – Ontology Web Language 2
RDF – Resource Definition Framework
R2R ML – RDB to RDF Mapping Language
OBDB – Ontology-Based Databases
14
ВСТУП
Обґрунтування вибору теми дослідження. З початку 70-х років минулого
століття широко розвивається один з найбільш затребуваних напрямків сучасної
інформаційної індустрії – інтеграція даних. Його розвиток відслідковується у
наступній короткій ретроспективі: відбувається формування більш чіткого
уявлення про багаторівневу архітектуру баз даних (БД), про моделі даних (МД) як
інструмент інформаційного моделювання реальності та про відображення між
ними. Задача зводилася, головним чином, до підтримки глобальної схеми для
сукупності локальних схем, що підтримують одну й ту саму (або різні) МД, що
функціонують у різних вузлах під керуванням однієї системи управління базами
даних (СУБД). У подальшому задача була узагальнена та включала в себе
створення сховищ даних, різноманітних репозиторій інформаційних ресурсів та
веб-додатків.
В наш час для роботи з даними інтернет-простору широко застосовуються
різноманітні інформаційні системи (ІС), кожна з яких, незалежно одна від одної,
використовує різні засоби зберігання, оперування, маніпулювання, пошуку даних,
розмежування доступу до них як всередині так и ззовні системи. В основі кожної
з них лежить своя МД, яка ґрунтується на власному математичному апараті, що є
головним джерелом труднощів, виникаючих при взаємодії цих систем. Таким
чином, гетерогенність даних, породжена низкою причин, ускладнює процеси
використання та зберігання їх в інформаційному просторі. А отже, на
сьогоднішній день ключовим питанням інтеграції даних є інтеграція
неоднорідних (гетерогенних) даних різноманітних інформаційних систем.
Актуальність проблеми. Створення відображень між дескриптивною
логікою та реляційною моделлю даних (РМД) є однією з ключових задач
проблеми інтеграції даних. З кожним днем об’єм інформації зростає в
геометричній прогресії, а її релевантність – в арифметичній. Це породжує низку
актуальних питань, пов’язаних із використанням та зберіганням даних
інформаційного простору. Наприклад, за різними оцінками, від 75% до 90%
сучасних інформаційних систем використовують РМД у якості основоположної
15
для створення реляційної бази даних (РБД), що зберігає дані ІС. З іншого боку, на
решту 10-25% припадає чимала кількість даних, що зберігається в структурах, які
визначаються цілковито іншими МД зі своєю специфічною семантикою. У цей
час продовжує активно розвиватись найсучасніша концепція організації
інформаційного простору – семантичний веб. Зокрема, в рамках цієї концепції для
роботи з даними створюються онтології, які побудовані на основі різноманітних
діалектів дескриптивних логік, що в дисертаційній роботі розглядаються у якості
самостійних МД. Такий стан справ породжує наступні концептуальні питання.
По-перше, яким чином організувати зберігання онтологій ІС. Чи можливо це
зробити за допомогою РБД та у який саме спосіб. По-друге, яким чином існуючі
дані традиційних РБД впровадити в семантичне середовище, тобто зробити
придатними для онтологій семантичного вебу. Створення відображень між
дескриптивною логікою та РМД покликане дати відповідь на ці питання.
Робота по дослідженню онтологій, дескриптивних логік та їх використанню у
різних прикладних застосуваннях висвітлена у працях Н. Гуріно, П. Гіаретта,
Ф. Баадер, Д. Кальванез, Д. МакГінез, Д. Нарді, П. Патель-Шнайдер, І. Ф. Круз,
Х. Ксяо, Е.Е. Золіна, А.А. Бездушного, М.О. Сидорова, О.В. Франчука,
М.М. Глибовця, П.І. Андона, В.А, Резниченка, О.В. Новіцького та інших.
Методології створення відображень між дескриптивною логікою та РМД
присвячені роботи І. Астрової, А. Калья, Н. Корда, Л. Стоянович, Н. Стоянович,
Р. Вольц, С. Мартінез-Круз, І. Ж. Бланко, М. А. Віла, К. Церанса, Г. Буманса,
С. Дас, С. Сундара, Р. Циганяка, С. Р. Упадхая, П. С. Кумар, Е. Виснякас,
Л. Немурате та інших.
В наш час існує декілька специфікацій мов відображення РБД в онтологію,
створену за допомогою мов OWL та RDF. До їх складу входить R2R ML (RDB to
RDF Mapping Language), що має рекомендацію консорціуму W3C. Слід
відзначити мову RDB2OWL, автори якої пропонують власний програмний
інструмент для її реалізації.
Як показує огляд літератури, усі існуючі мови відображення мають ряд
особливостей, які суттєво звужують їх практичне використання. На сьогоднішній
16
день не існує такого алгоритму, який би реалізовував можливість двостороннього,
зі збереженням повноти та цілісності, механізму відображення між DL та РМД.
Одним із підходів є пряме перетворення основних конструкцій DL у РМД та
навпаки, з подальшою автоматизацією описаного процесу; також зустрічаються
спроби формалізації розглянутого підходу та побудови певної мови відображення,
ґрунтуючись на приведених викладках (мова RDB2OWL), тощо.
Основним завданням дисертаційної роботи є дослідження та розробка
алгоритмів відображення між дескриптивною логікою та реляційною моделлю
даних, а також їх апробація на тестових даних за допомогою RDF.
Зв’язок роботи з науковими програмами, планами, темами. Робота
виконувалася відповідно до планів наукових досліджень відділу автоматизованих
інформаційних систем Інституту програмних систем НАН України в рамках
науково-дослідних тем: «Розробка методів та засобів підтримки побудови
інтелектуальних інформаційних систем у семантичному Веб-середовищі», шифр
ІІІ-2-12, № держреєстрації 0112U002761, (2012-2016); «Інтелектуальні
інформаційні системи підтримки аналізу великих даних (Big Data)», шифр ІІІ-10-
18, № держреєстрації 0118U001906, (2018-2019); «Методи та засоби створення
інтелектуальних сервіс-орієнтованих інформаційно-забезпечуючих систем у
середовищі семантичного Вебу», шифр ІІІ-2-17, № держреєстрації 0117U000736,
(2017-2021).
Мета і завдання дослідження. Мета дисертаційної роботи – розробка,
обґрунтування та апробація відображень між дескриптивною логікою та
реляційною моделлю даних. Для досягнення поставленої мети необхідно
вирішити наступні задачі:
- визначити та створити схему інтеграції даних;
- розробити концептуальну інформаційну ER-модель дескриптивної логіки;
- створити бінарну реляційну модель даних (RM2
);
- розробити двосторонні механізми відображення між попередньо
визначеними діалектами DL та RM2
;
17
- здійснити апробацію розробленого двостороннього механізму
відображень за допомогою RDF.
Об’єкт дослідження – проблема інтеграції даних в семантичному вебі.
Предмет дослідження – засоби та технологія відображення між
дескриптивною логікою та реляційною моделлю даних
Методи дослідження. Вирішення завдань, поставлених в дисертаційній
роботі, виконано з використанням дескриптивних логік, математичної логіки,
методів опису відображень між моделями даних, методології концептуального
інформаційного моделювання предметних областей, теорії нормалізації
реляційної моделі даних, методів проектування реляційних баз даних.
Наукова новизна отриманих результатів. В результаті проведених
досліджень було отримано наступні результати:
- побудовано таксономію досліджень, які стосуються відображень між
онтологіями та реляційними базами даних; визначено вузькі місця
напрямків досліджень, з яких складається визначена таксономія;
обґрунтовано важливість опису відображень між дескриптивною логікою
та реляційною моделлю даних, а також вибір централізованої схеми
інтеграції даних ІС, керуючись результатами проведеного аналізу
проблеми інтеграції даних в семантичному веб;
- уперше побудовано концептуальну інформаційну ER-модель
дескриптивної логіки із залученням технології, яка забезпечує: підтримку
гіпотези відкритого світу та не унікальності імен, повне представлення
усіх інформаційних складових дескриптивної логіки, використання тільки
унарних та бінарних сутностей, безпосереднє її відображення у бінарну
реляційну структуру даних зі схемою бази даних у третій нормальній
формі;
- визначено спеціальний варіант класичної РМД – бінарну реляційну модель
даних (RM2
) яка складається з бінарної реляційної структури даних (RS2
),
бінарної реляційної алгебри (RA2
), та обмежень цілісності. Оскільки, будьяке n-арне відношення можна представити сукупністю бінарних, було
18
запропоновано спосіб перетворення n-арної (класичної) реляційної
структури в бінарну;
- уперше визначено бінарну реляційну алгебру (RA2
), у яку внесено
принципово нові операції по відношенню до класичної реляційної алгебри
(RA), для підтримки відображення конструкторів концептів та ролей DL.
Операції RA, які не збільшують арність результуючого відношення
внесено в RA2 без змін. Операції RA, що утворюють відношення арністю
більше 2, були внесені в RA2 у модифікованому вигляді, такому, що
результат їх виконання теж утворює унарне або бінарне відношення;
- уперше розроблено метод двостороннього відображення між
онтологічною та реляційною моделями даних, який: носить формальний
характер; визначається як на структурному, так і на операційному рівні
(включено конструктори концептів та ролей, а також операції реляційної
алгебри); передбачає відображення термінологічних аксіом дескриптивної
логіки;
- проведено програмну апробацію алгоритму відображення за допомогою
мови RDF на прикладі тестових даних; визначено алгоритмічну оцінку
складності.
Практичне значення одержаних результатів. Розроблений метод
відображення було використано в Інституті розробки інформаційних систем з
метою підвищення інтелектуальності автоматизованих інформаційних систем
шляхом перетворення реляційних інформаційних ресурсів в онтологічну базу
даних (акт упровадження від 7 червня 2021р).
Метод відображення було впроваджено у компанії Зініт Солюшенс Юкрейн
під час проектування автоматизованої системи комплектації обчислювальної
техніки (акт упровадження від 3 червня 2021р).
Алгоритм відображення між дескриптивною логікою та реляційною моделлю
даних може бути використано для створення бібліотеки функцій при розробці
програмного забезпечення що підтримує відображення між існуючими
онтологіями та базами даних.
19
Особистий внесок здобувача. Усі наукові результати та положення, які
складають основну частину дисертаційної роботи, отримано здобувачем
самостійно. Визначення напрямку досліджень та загальна постановка задачі
належить науковому керівнику. Роботи [1, 3, 4, 7, 8, 9, 11, 12, 13, 14] написано
здобувачем особисто і всі наукові результати, представлені в них, є
оригінальними. У працях, опублікованих у співавторстві [2, 5, 6, 10], дисертанту
належать наступні результати: [6] – побудовано бінарну реляційну структуру
даних, розроблено та описано алгоритм відображення для базових складових
дескриптивної логіки ALC, а також обраних розширень та термінологічних
аксіом; [2] – побудовано концептуальну інформаційну модель дескриптивної
логіки; [5] – створено та описано бінарну реляційну модель даних та її складові
частини; [10] – розроблено та описано алгоритм відображення для обраних
чисельних розширень ALC та номіналу.
Апробація результатів дисертації. Основні ідеї, принципи, положення та
результати доповідалися: на Міжнародній науково-практичній конференції з
програмування «УкрПрог 2014» (м. Київ, 20-22 травня 2014); на міжнародній
науковій конференції студентів та молодих науковців «Aviation in the XXI-st
century» (м.Київ, 21–23 листопада 2014); на Міжнародній науково-практичній
конференції з програмування «УкрПрог 2016», (м. Київ, 24–25 травня 2016); на
Міжнародній науково-практичній конференції з програмування «УкрПрог 2018»,
(м. Київ, 22–24 травня 2018); на IX Міжнародній науково-практичній Інтернет
конференції «Глобальні та регіональні проблеми інформатизації в суспільстві та
природокористуванні 2021» (м.Київ 13-14 травня 2021).
Публікації. Основні наукові результати дисертації опубліковано в 14
наукових працях, із них – 9 наукових статей [1-7, 13, 14] у фахових виданнях
України, з яких одна наукова робота [5] у міжнародному науково-технічному
журналі, що перекладається у США англійською мовою – у видавництві Springer
під назвою «Сybernetics and Systems Analysis», та індексується SCOPUS; 5 тез [8–
12] опубліковано у матеріалах міжнародних наукових конференцій, серед яких [9,
10, 11] індексуються SCOPUS.
20
Структура та обсяг дисертації. Дисертаційна робота складається із вступу,
чотирьох розділів, загальних висновків, списку використаних джерел із 99
найменувань. Загальний обсяг дисертації становить 171 сторінку, у тому числі
основний текст викладено на 115 сторінках. Робота містить 13 рисунків, 12
таблиць та 7 додатків.

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

ВИСНОВКИ
Основним результатом дисертаційної роботи є розробка методу
відображення між дескриптивною логікою та реляційною моделлю даних. В
рамках проведених досліджень було отримано наступні наукові результати.
1. Побудовано таксономію досліджень, які стосуються відображень між
онтологіями та реляційними базами даних; визначено вузькі місця напрямків
досліджень, з яких складається визначена таксономія; обґрунтовано важливість
опису відображень між дескриптивною логікою та реляційною моделлю даних, а
також вибір централізованої схеми інтеграції даних ІС, керуючись результатами
проведеного аналізу проблеми інтеграції даних в семантичному веб.
2. Визначено спеціальний варіант класичної РМД – бінарну реляційну
модель даних (RM2
), яка складається з бінарної реляційної структури даних (RS2
),
бінарної реляційної алгебри (RA2
), та обмежень цілісності. Оскільки, будь-яке nарне відношення можна представити сукупністю бінарних, було запропоновано
спосіб перетворення n-арної (класичної) реляційної структури в бінарну.
3. Уперше визначено бінарну реляційну алгебру (RA2
), до якої внесено
принципово нові операції по відношенню до класичної реляційної алгебри (RA),
для підтримки відображення конструкторів концептів та ролей DL. Операції RA,
які не збільшують арність результуючого відношення внесено в RA2 без змін.
Операції RA, що утворюють відношення арністю більше 2, були внесені в RA2 у
модифікованому вигляді, такому, що результат їх виконання теж утворює унарне
або бінарне відношення.
4. Уперше розроблено метод двостороннього відображення між
онтологічною та реляційною моделями даних, який: носить формальний характер;
визначається як на структурному, так і на операційному рівні (включено
конструктори концептів та ролей, а також операції реляційної алгебри);
передбачає відображення термінологічних аксіом дескриптивної логіки.
5. Проведено програмну апробацію алгоритму відображення на прикладі
тестових даних; сформульовано постановку задачі апробації відображень із
залученням добре дослідженої теорії, у якості якої виступає RDF; обґрунтовано
134
переваги використання стандартів «OWL 2 Web Ontology Language Mapping to
RDF Graphs» та R2R ML для виконано алгоритмічну оцінку складності методу
відображення та визначено, що проблема функціонування системи, яка підтримує
відображення DL у реляційну алгебру та навпаки є PSPACE-повною; стосовно
включення транзитивних ролей, питання складності функціонування такої
системи, залишається відкритим.
Алгоритм відображення між дескриптивною логікою та реляційною
моделлю даних може бути використано для створення бібліотеки функцій при
розробці програмного забезпечення що підтримує відображення між існуючими
онтологіями та базами даних. Метод відображення може бути використано у
навчальних спецкурсах з теорії проектування моделей даних.