Федорус Олексій Мстиславович Застосування систем ПАРКС для моделювання операцій реляційної алгебри вибору

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

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

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

Зміст
АНОТАЦІЯ................................................................................................................................................2
ПЕРЕЛІК УМОВНИХ СКОРОЧЕНЬ...........................................................................................................11
ВСТУП ....................................................................................................................................................12
РОЗДІЛ 1. ВИКЛИКИ СУЧАСНИХ СУБД..................................................................................................18
1.1 СИСТЕМИ УПРАВЛІННЯ ПОТОКОМ ДАНИХ .................................................................................20
1.2 СЛАБКІ МІСЦЯ РЕЛЯЦІЙНИХ СУБД............................................................................................23
1.3 СУМІСНЕ ІСНУВАННЯ РЕЛЯЦІЙНИХ ТА НЕ РЕЛЯЦІЙНИХ БАЗ......................................................24
1.4 СУЧАСНИЙ РОЗВИТОК РЕЛЯЦІЙНИХ АЛГЕБР ..............................................................................30
1.5 ВИСНОВКИ .................................................................................................................................31
РОЗДІЛ 2. РОЗРОБКА ПАРКС-WCF ........................................................................................................33
2.1 ПАРКС ......................................................................................................................................34
2.2 ПЛАНУВАННЯ ТА ВИБІР КОМПОНЕНТІВ .....................................................................................35
2.3 КЛЮЧОВІ ОСОБЛИВОСТІ ТЕХНОЛОГІЇ WCF ДЛЯ РЕАЛІЗАЦІЇ ПАРКС........................................39
2.4 ДЕТАЛІ РЕАЛІЗАЦІЇ ПАРКС-WCF .............................................................................................43
2.5 ПОРІВНЯННЯ З ІНШИМИ РЕАЛІЗАЦІЯМИ ПАРКС.......................................................................61
2.6 ТЕСТУВАННЯ ПАРКС-WCF......................................................................................................61
2.7 НАЛАГОДЖЕННЯ РОЗПОДІЛЕНИХ ЗАСТОСУНКІВ........................................................................65
2.8 ВИСНОВКИ .................................................................................................................................67
РОЗДІЛ 3. МОДЕЛЮВАННЯ РЕЛЯЦІЙНОЇ АЛГЕБРИ..............................................................................69
3.1 РЕЛЯЦІЙНЕ ЧИСЛЕННЯ. РЕЛЯЦІЙНІ АЛГЕБРИ. АЛГЕБРА ДРІБАСА..............................................69
3.2 МОДЕЛЮВАННЯ ОПЕРАЦІЙ РЕЛЯЦІЙНОЇ АЛГЕБРИ ВИБОРУ ЗАСОБАМИ ПАРКС .......................79
3.3 ВИСНОВКИ .................................................................................................................................85
РОЗДІЛ 4. РЕАЛІЗАЦІЯ РОЗПОДІЛЕНИХ РЕЛЯЦІЙНИХ ОПЕРАЦІЙ ЗА ДОПОМОГОЮ ПАРКС-WCF ......86
4.1 ФОРМА КЕРУЮЧОГО ПРОСТОРУ ТА БАЗОВІ ПРОЦЕСИ ................................................................86
4.2 РЕАЛІЗАЦІЯ ОПЕРАЦІЇ FΒ ............................................................................................................88
4.3 РЕАЛІЗАЦІЯ ОПЕРАЦІЇ ОБ’ЄДНАННЯ...........................................................................................94
4.4 РЕАЛІЗАЦІЯ ОПЕРАЦІЇ ПЕРЕТИНУ ...............................................................................................96
4.5 РЕАЛІЗАЦІЯ ОПЕРАЦІЇ РІЗНИЦІ....................................................................................................99
4.6 РЕАЛІЗАЦІЯ ОПЕРАЦІЇ РОЗШИРЕНОГО ДЕКАРТОВОГО ДОБУТКУ...............................................100
4.7 РЕАЛІЗАЦІЯ ОПЕРАЦІЇ ПРОЕКЦІЇ ...............................................................................................101
4.8 РЕАЛІЗАЦІЯ ОПЕРАЦІЙ ФІЛЬТРАЦІЇ ПО ДЕКІЛЬКОМ ТАБЛИЦЯМ................................................101
4.9 ДОДАТКОВІ ПРОПОЗИЦІЇ ..........................................................................................................105
4.10 ВИСНОВКИ ...............................................................................................................................107
ВИСНОВКИ...........................................................................................................................................108
10
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ.....................................................................................................110
ДОДАТОК А. ........................................................................................................................................119
ДОДАТОК Б. ........................................................................................................................................121
11
ПЕРЕЛІК УМОВНИХ СКОРОЧЕНЬ
ACID - Atomicity, Consistency, Isolation, Durability
BSON - Binary JavaScript Object Notation
IDE - Integrated Development Environment
JSON - JavaScript Object Notation
RCE - Remote Code Execution
SOAP - Simple Object Access Protocol
SSL - Secure Sockets Layer
TCP - Transmission Control Protocol
TLS - Transport Layer Security
WCF - Windows Communication Foundation
WSDL - Web Services Description Language)
АМ – алгоритмічний модуль
КП – керуючий простір
ПАРКС – паралельні асинхронні рекурсивно керовані системи
ПС – паралельні системи
СУБД – система управління базою даних
СУПД - система управління потоком даних
СУРБД - система управління реляційною базою даних
12
ВСТУП
Щодня все більше аспектів людського буття та систем, що його
обслуговують чи підтримують, потребують побудови цифрових аналогів а ті
що вже існують ускладнюються через інтенсивне збільшення вимог до об'ємів
оперованої ними інформації. Кожна хвилина нашого існування оцифровується
та має бути оброблена та збережена для подальших запитів. Подібні системи
змушені оперувати неймовірно великими обсягами інформації при цьому
блискавично швидко відповідаючи на запити різної складності.
Відповідаючи на поставлені виклики бази даних почали прагнути
легкості у горизонтальному масштабуванні, і пришвидшенні операцій
читання/запису даних. Оскільки традиційні СУБД не встигали за вимогами
користувачів - це призвело до появи нових систем, які називають NoSQL.
Чіткого визначення термін «NoSQL» так і не отримав і його можна розуміти і
як «не тільки SQL» так і «не реляційні». Ці бази сильно відрізняються як одна
від одної так і від традиційних реляційних СУБД. Але можна виділити
декілька особливостей що характерні переважній більшості:
● здатність дублювати або розподіляти дані по різним серверам;
● здатність здійснювати ефективне горизонтальне масштабування;
● здатність ефективно використовувати оперативну пам’ять (кешування
даних, зберігання усієї бази в оперативній пам’яті, тощо);
● здатність зберігати та обробляти не структуровані(або частково
структуровані) дані.
Поступово традиційні, реляційні СУБД, також почали надавати подібну
функціональність, але будучи розробленими за інших вимог та не
вирізняючись гнучкістю - результатом завжди був певний компроміс між
надійністю, швидкістю і функціональність.
Так само вже деякі не реляційні бази намагаючись охопити все ширше
коло вимог користувачів розвиваючись почали реалізовувати
функціональність, що характерна традиційним реляційним базам: транзакції
13
та зв’язки між таблицями. Такий перебіг свідчить про неможливість відмови
від реляційних операцій, зокрема для пошуку в розподілених системах.
Дослідження різноманітних СУБД та реляційних алгебр присвячено ряд
робіт закордонних вчених К. Дейт, Х. Дарвен, Г. Сандра, Р. Каттель, А.
Салехнія, а також вітчизняних вчених: Брона Ю.Й., Буй Д.Б, Дрібас
Глушко(Лисенко) І.М. Поляков С.А, Редько В.Н..
За час існування баз даних було створено тисячі різноманітних СУБД,
базованих на різноманітних принципах, алгебрах, програмних засобах. Як
результат існують тисячі несумісних між собою баз даних. Навіть сучасний
SQL, що здавалося б вже став стандартом і має офіційну міжнародну
підтримку і супровід, відрізняється у кожній популярній СУБД, що створює
різноманітні перепони як при роботі системи так і при написанні коду.
Відповідно SQL широко критикують і NoSQL бази дуже часто мають взагалі
унікальні мови запитів, намагаючись віднайти кращі засоби формування
запитів.
За подібних пошуків більш ефективних альтернатив необхідний
програмний застосунок за допомогою якого було б можливо легко перевірити
ту чи іншу теорію. Такий застосунок має забезпечувати мережеву взаємодію
та можливість паралельних обчислень. І саме тут виникає ніша для
застосування технології Паралельних Асинхронних Рекурсивно Керованих
Систем (ПАРКС). Як засіб паралельних обчислень він може дати можливість
легко тестувати паралельні алгоритми реляційних операцій, тестувати
різноманітні розподілені сценарії взаємодії СУБД, а також можливість
застосування різних СУБД як одну розподілену базу даних.
Концепція ПАРКС є розробкою науковців факультету комп’ютерних
наук та кібернетики (А.В. Анісімовим та В.М. Глушковим), Київського
національного університету імені Тараса Шевченка дослідженнями у різні
роки займалися: Анісімов А.В., Глушков В.М., Годованюк М.І., Кулябко П.П.,
Дерев’янченко О.В., Хавро А.Ю.
14
Зв’язок роботи з науковими програмами, планами, темами. Основні
дослідження за темою дисертації проводились на факультеті комп’ютерних
наук та кібернетики Київського національного університету імені Тараса
Шевченка в рамках кафедральної теми 16КФ015-02 «Теорія і методи розробки
інтелектуальних інформаційних технологій та систем» (номер держреєстрації
0116U006378, 2016-2020)
Мета та завдання дослідження. Метою дисертаційного дослідження є
моделювання операцій реляційної алгебри вибору в паралельних, та
розподілених системах, створених на базі концепції ПАРКС.
Реалізація цієї мети передбачає виконання таких завдань:
• створити новий засіб реалізації паралельних/розподілених обчислень, на
базі концепції ПАРКС;
• провести тестування та переконатися у ефективності розробленої
системи;
• розробити нові модифікації концепції ПАРКС, які дозволять
ефективніше вирішувати поставлене завдання;
• розробити шляхи розпаралелювання та схеми керуючого простору для
реляційних операцій алгебри вибору в термінах класичної концепції
ПАРКС
• реалізувати розроблені операції
Об’єктом дослідження є операції алгебри основних операцій вибору
(запропонованої Дрібасом), зокрема розподілений пошук і обробка даних, а
також системи ПАРКС як засіб їх розподілених реалізації.
Предметом дослідження є шляхи реалізації розподілених операцій
пошуку даних та можливості використання систем ПАРКС для моделювання
та дослідження розподілених операцій пошуку.
Методи дослідження. В дослідженні застосовується концепція ПАРКС
та її методи опису паралельних операцій.
Наукова новизна отриманих результатів. Основними результатами,
що виносяться на захист є наступні:
15
вперше:
• реалізована система ПАРКС-WCF. Перша реалізація що
підтримує: захист інформації що передається, підтримка різних протоколів
передачі даних, автоматичну оптимізацію протоколу передачі даних, відміна
завдань, можливість автоматичного знищення керуючого простора при
критичній помилці в одному з алгоритмічних модулів, можливість зміни
методу серіалізації даних, можливість реалізувати свій планувальник завдань,
можливість отримати інформацію про машини, що є в керуючому просторі для
подальшої оптимізації створення точок, додана можливість асинхронної
взаємодії з ПАРКС;
• створені поняття локальної і віддаленої точки в рамках концепції
ПАРКС. Запропоновано метод пошуку помилок для довільного АМ;
• теоретично описані шляхи паралелізації реляційних операцій за
допомогою загальної концепції ПАРКС та наведено базові схеми керуючого
простору;
• реалізовані паралельні операції реляційної алгебри основних
операцій вибору за допомогою розробленої системи ПАРКС-WCF з
урахуванням особливостей системи.
Практичне значення отриманих результатів. Розроблена в
дисертаційній роботі система ПАРКС-WCF може застосовуватися для
реалізації паралельних або розподілених обчислень і є повністю готовою для
використання. Крім того, вона впроваджена в навчальний процес факультету
комп’ютерних наук та кібернетики Київського національного університету
імені Тараса Шевченка при підготовці фахівців за напрямом «інформатика»
освітньо-кваліфікаційного рівня «Бакалавр» (в теоретичній та практичній
підготовці за дисципліною «Розподілене та паралельне програмування», 3 рік
бакалаврату).
Розроблені методи моделювання реляційної алгебри вибори можуть
використовуватися при тестуванні інших реляційних алгебр, або при
моделюванні інших операцій роботи з розподіленими даними.
16
Результати цього дисертаційного дослідження також використовуються
при підготовці фахівців за напрямками «інформатика» та «інженерія
програмного забезпечення» освітньо-кваліфікаційного рівня «Бакалавр» в
рамках курсів «Організація баз даних та знань» (3 рік бакалаврату), «Бази
даних та інформаційні системи» (2 рік бакалаврату).
Особистий внесок здобувача. Дисертація є самостійно виконаною
науковою роботою. Всі основні результати дисертаційної роботи отримано
автором особисто та опубліковані у наукових фахових виданнях. У роботі [2],
опублікованій у співавторстві здобувачу належать перші два блоки статті
(вступ та представлення концепції ПАРКС). Робота [6] опублікована у
співавторстві з Анісімовим А.В., якому належить постановка проблеми, вибір
методів дослідження та обговорення результатів.
Апробація матеріалів дисертації.
Основні положення та результати дисертаційної роботи доповідалися
автором та отримали позитивну оцінку на чотирьох міжнародних науковотехнічних та науково-практичних конференціях:
• 2-га міжнародна науково-практична конференція «Інформаційні
технології та взаємодії» IT&I (м. Київ 2015р.);
• 16-та міжнародна науково-технічна конференція «ШТУЧНИЙ
ІНТЕЛЕКТ ТА ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ» AIIS’2016 (м. Київ,
2016р.)
• 17-та міжнародна науково-технічна конференція «ШТУЧНИЙ
ІНТЕЛЕКТ ТА ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ» AIIS’2017 (м. Київ,
2017р.)
• 5-та міжнародна науково-технічна конференція «Високопродуктивні
обчислення» («High Performance Computing», HPC-UA 2018) (м. Київ
2018р.)
Публікації. Основні наукові результати дисертаційної роботи в повній
мірі викладено у 10 наукових працях, з яких 6 наукових статей [1-6] і 4 тез
доповідей міжнародних наукових конференцій [7-10]. 5 робіт [1, 3-6]
17
опубліковано у наукових видання з переліку фахових видань України, з яких
одна наукова робота [6] – у виданні, що перекладається англійською мовою за
кордоном видавництвом Springer у США під назвою «Cybernetics and System
Analysis» та включено до міжнародної науково метричної бази SCOPUS.
Робота [2] опублікована в міжнародному виданні.
Структура дисертації. Дисертаційна робота складається зі вступу,
чотирьох розділів, висновків, списку використаних джерел з 80 найменувань
та 2 додатків. Загальний обсяг роботи становить 123 сторінок, з яких 109
сторінок основної частини

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

ВИСНОВКИ
У даної дисертаційної роботи є два головних результати. Перший -
розроблена і представлена система ПАРКС-WCF, що має велику практичну
цінність. І другий – промодельовані операції реляційної алгебри вибору, що
мають як теоретичну цінність (зроблено вперше для систем ПАРКС), так і
практичну: сирцевий код може бути використаний для подальших моделювань
інших алгебр і перевірки роботи різноманітних розподілених операцій.
Загалом робота включає наступні результати:
1. Реалізована система ПАРКС-WCF. Це перша реалізація що підтримує:
захист інформації що передається, різні протоколів передачі даних,
автоматичну оптимізацію протоколу передачі даних, відміна завдань,
можливість автоматичного знищення керуючого простора при критичній
помилці в одному з алгоритмічних модулів, можливість зміни методу
серіалізації даних, можливість реалізувати свій планувальник завдань,
можливість отримати інформацію про машини, що є в керуючому просторі для
подальшої оптимізації створення точок, додана можливість асинхронної
взаємодії з ПАРКС;
2. Проведено тестування розробленої системи на базі простого
алгоритму розпаралелювання матриць для можливості порівняння швидкодії
з іншими подібними системами.
3. Запропоновано поняття локальної і віддаленої точки у ПАРКС, що
дозволяє ефективніше планувати задачі які використовують ресурси
конкретної машини (у випадку даної роботи – дані, що зберігаються на диску);
4. Запропоновано метод пошуку помилок та налагодження АМ для
розподілених систем з деякими обмеженнями на алгоритми АМ.
5. Теоретично розписані шляхи паралелізації реляційних операцій
алгебри вибору за допомогою ПАРКС та наведено базові схеми керуючого
простору;
109
6. Промодельовані окремі операції реляційної алгебри вибору за
допомогою систем ПАРКС. Детально описано процес тестування та умови
середовища тестування.
Розроблена система ПАРКС-WCF в купі з прикладом реалізації
реляційних операцій на ній може полегшити науковцям подальші дослідження
та тестування теорій відносно реляційних алгебр та створення
паралельних/розподілених баз даних. Втім розроблена система може також
використовуватись і при тестуванні не реляційних операцій над даними.
Природнім та логічним продовженням цієї роботи можуть бути аналізи
швидкості обчислення різноманітних реляційних алгебр, в тому числі тих, для
порівняння яких використовували реляційну алгебру вибору. Крім того
розроблена система ПАРКС-WCF може використовуватись як для написання
нових алгоритмів так і для тестування раніше описаних.