Канарська Ірина Сергіївна Теоретико-множинні табличні операції та їх склад­ність

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

Канарська Ірина Сергіївна, лаборант ВП «Слов’янський коледж Луганського національного аграрного університе­ту»: «Теоретико-множинні табличні операції та їх склад­ність» (01.05.01 - теоретичні основи інформатики та кібер­нетики). Спецрада Д 26.001.09 у Київському національному університеті імені Тараса Шевченка

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

ЗМІСТ
ВСТУП …………………………………………………………………………… 14
РОЗДІЛ 1. Сигнатурні операції у реляційних та табличних алгебрах ….. 18
1.1 Необхідні теоретичні відомості ............................................................ 18
1.2 Огляд літератури щодо оптимізації реляційних (табличних)
операцій ........................................................................................................ 23
РОЗДІЛ 2. Складність реалізації алгоритмів теоретико-множинних
операцій у таблицях ……………………………..………………….………..... 29
2.1 Алгоритми перетину таблиць ………..……………………..…..……. 30
2.2 Алгоритми об'єднання таблиць ……..……………………….…..…... 33
2.3 Алгоритми різниці таблиць ………………..…………………….…... 36
2.4.Оцінки складності в найгіршому випадку запропонованих алгоритмів .. 41
2.5. Оцінки складності запропонованих алгоритмів у середньому ……. 58
2.6. Порівняння запропонованих алгоритмів за знайденими
теоретичними оцінками їх складності ....................................................... 71
2.7. Порівняння запропонованих алгоритмів за даними
обчислювального експерименту ................................................................. 75
Висновки розділу …………………..……………………………………..77
РОЗДІЛ 3. Cкладність реалізації алгоритмів теоретико-множинних
операцій у мультитаблицях ……..……………….…………………………… 78
3.1 Загальні поняття про мультитаблиці .................................................... 78
3.2 Алгоритми перетину мультитаблиць ................................................... 81
3.3 Алгоритми об'єднання мультитаблиць ................................................ 85
3.4 Алгоритми різниці мультитаблиць ....................................................... 88
3.5.Оцінки складності в найгіршому випадку запропонованих алгоритмів .. 92
3.6. Порівняння запропонованих алгоритмів за даними
обчислювального експерименту ............................................................... 106
Висновки розділу ………………..…………………………………….. 108
РОЗДІЛ 4. Збереження активного домену сигнатурними
операціями табличних алгебр .......................................................................... 109
4.1 Взаємозв’язки між активними доменами вихідних таблиць та таблицірезультату при виконанні сигнатурних операцій табличних алгебр …….109
4.2 Критерії збереження активного домену сигнатурними
операціями табличних алгебр ................................................................... 110
Висновки розділу ………………….………..………………………….. 117
ВИСНОВКИ ......................................................................................................... 118
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ........................................................ 120
ДОДАТОК 1. Опис інтерфейсу, функціональних можливостей та
лістинг розробленої програмної системи….................................................... 126
ДОДАТОК 2. Список публікацій здобувача та відомості про
апробацію результатів роботи ......................................................................... 164
ДОДАТОК 3. Акт про впровадження результатів роботи ......................... 167

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

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