Дисертаційна робота: “Розподілення навантаження в базах даних великого об’єму методом горизонтальної фрагментації”

Автореферат: "Розподілення навантаження в базах даних великого об’єму методом горизонтальної фрагментації"

Ось і підходять до завершення мої роки навчання в аспірантурі. Два роки пролетіли швидко, але залишили позаді чималий обсяг виконаної роботи і безліч вражень 🙂

Наукова діяльність дала поштовх до того, щоб піднятися на щабель вище при вирішенні складних задач. Перш ніж братися за їх рішення – необхідно їх вивчити. Для цього доводилось використовувати різну методологію теоретичних досліджень, включаючи ідеалізацію, яка правомірна лише у певних межах, та формалізацію – вивчення різноманітних обєктів шляхом відображення їхньої структури у знаковій формі за допомогою штучних мов.

Підсумком цього стало написання дисертації на тему: “Розподілення навантаження  в базах даних великого об’єму методом горизонтальної фрагментації” та автореферату, з яким можна ознайомитися нижче, завантаживши по відповідному посиланню. Основні результати дисертаційної роботи опубліковані в 12 наукових працях, серед яких: 8 – у наукових фахових виданнях України, 4 – матеріалах конференцій.

Апробація результатів дисертації. Результати досліджень за темою дисертації доповідались та обговорювались на міжнародних науково-технічних конференціях:

  • «Современные информационные и электронные технологии» (18-22 травня 2009р., м. Одеса, Україна);
  • «International scientific  technical conference» (22-25 квітня 2009р., ХАІ, м. Кіровоград , Україна);
  • Міжнародна науково-технічна конференція «Комп’ютерні системи та мережні технології» (10-12 червня 2009р., НАУ, м.Київ, Україна);
  • «Advanced computer systems and networks design and application: proceedings of the 4-th International conference» (9-11 листопада 2009р., ЛПІ, м. Львів, Україна);
  • Міжнародна науково-технічна конференції «Комп’ютерні системи та мережні технології» (15-17 червня 2010р., НАУ, м. Київ, Україна).

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась у рамках науково-дослідних робіт Національного авіаційного університету (НАУ):

  • НДР «Створити автоматизовану інформаційно-аналітичну систему Мінтрансзв’язку» (номер державної реєстрації №0108U000488) у період за 2007-2008р.р.
  • НДР № 668-ДБ-10 «Методи та засоби підвищення ефективності розподілених обчислювальних систем на базі тензорних нейронних мереж» (номер державної реєстрації №0110U000221) у період за 2010 р.

Наукова новизна одержаних результатів. В процесі розв’язання поставлених задач одержані такі нові результати:

  • вперше розроблено  метод динамічної горизонтальної фрагментації даних великого об’єму, який відрізняється від відомих використанням частоти звертань до кортежів даних, що дає змогу зменшити кількість збиткових фрагментів;
  • розроблено новий евристичний метод для пошуку найкоротшого маршруту у графі з навантаженими вершинами та дугами, який відрізняється від існуючих тим, що не потребує обчислення всіх можливих маршрутів. Даний метод дозволяє розраховувати маршрути у графах великої розмірності без суттєвої втрати швидкодії;
  • удосконалено спосіб оптимізації багатоекстремальних функцій за допомогою ГА, який на відміну від відомих, дозволяє зменшити час знаходження екстремуму;
  • вперше розроблено метод декомпозиції SQL-запиту для визначення найбільш ефективного маршруту вибору даних із різних РБД.

Практичне значення одержаних результатів полягає в тому, що розроблено об’єктно-орієнтований модуль «iSmartRoute», що ґрунтується на евристичній методології.  Його використання для оптимізації графів великої розмірності з навантаженими вершинами та дугами є швидшим у 520 раз за існуючі алгоритми з квадратичною чи кубічною складностями.

Поєднання методу декомпозиції SQL-запиту та методу для горизонтальної фрагментації даних дає змогу формувати базу знань, що представляє  собою частоту звертань до кортежів з різних РБД. На основі такої статистичної інформації можна виконати горизонтальну фрагментацію БД великого об’єму із ефективним використанням дискового простору по декількох РБД з мінімальним числом збиткових фрагментів.

Застосування способу для оптимізації багатоекстремальних функцій дозволяє знаходити екстремум за мінімальний час, включаючи складні функції. Це досягається завдяки розробленим операторам кросинговера та мутації, покращеним характеристикам, що використовуються для ГА на основі якого й відбувається оптимізація.

Розроблені методи були використані в інформаційно-аналітичній системі (ІАС) «Мінтрансзв’язку» України та автоматизованій системі управління навчальним процесом в Інституті комп’ютерних технологій НАУ. Це дало змогу підвищити ефективність діяльності Інституту за рахунок надання оперативної і вчасної інформаційної підтримки в основних областях діяльності Інституту, таких як: кадрова політика, наукова та навчально-методична діяльність.

Отримані результати дисертаційної роботи реалізовані і впроваджені в начальному процесі на кафедрі комп’ютерних систем та мереж НАУ в дисциплінах: «Інтелектуальні комп’ютерні системи», «Комп’ютерні мережі» та «Мережеорієнтовані комп’ютерні технології» та в автоматизованій системі управління навчальним процесом в Інституті комп’ютерних технологій НАУ, що підтверджено відповідними актами про впровадження.

Структура та обсяг дисертації. Дисертаційна робота, що викладена на 172 сторінках друкованого тексту, складається із вступу, чотирьох розділів і висновків, викладених на 130 сторінках основного тексту, списку використаної літератури із 127 найменувань. Дисертаційна робота містить 58 рисунків, 20 таблиць, 4 додатки та 2 акти про впровадження.

АНОТАЦІЯ

Кравець І.М. Розподілення навантаження  в базах даних великого об’єму методом горизонтальної фрагментації. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 – комп’ютерні системи та компоненти. – Національний авіаційний університет Міністерства освіти і науки України, Київ, 2010.

Дисертація присвячена розробці загальної методології, методики та алгоритмів для організації розподілення навантаження в БД великого об’єму. Розроблено новий евристичний метод «iSmartRoute» для оптимізації графів великої розмірності. Також, удосконалено спосіб оптимізації багатоекстремальних  функцій результати якого підтвердили практичну і наукову цінність еволюційних алгоритмів. Розроблено метод декомпозиції SQL-запиту у РБД, що формує сукупність відомостей про частоту звертань до кортежів. Проведено експериментальне дослідження використання постійних з’єднань з БД в традиційній кластерній системі та у сегментованій. Розроблено метод горизонтальної фрагментації БД великого об’єму. Проведено організацію розподілення навантаження в БД інформаційно-аналітичної системи методом горизонтальної фрагментації та описано її основні характеристики, включаючи її функціонування та захист інформації

Ключові слова: СУБД, розподілена база даних, евристична методологія, генетичний алгоритм, графи великої розмірності, оптимізація багатоекстремальних функцій.

АННОТАЦИЯ

Кравец И.М. Распределения нагрузки в базах данных большого объема методом горизонтальной фрагментации. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 – компьютерные системы и компоненты. – Национальный авиационный университет Министерства просвещения и науки Украины, Киев, 2010.

Диссертация посвящена разработке общей методологии, методики и алгоритмов для организации распределения нагрузки в базах данных большого объема.

Выполнен анализ существующих способов распределения нагрузки в базах данных большого объема. Рассмотрены известные методы балансировки нагрузки для Web-серверов. Приведены обзор существующих методов и средств для распределения информации в СУБД, в частности, обработка распределенных запросов, межоперабельность в контексте распределенной базы данных, тиражирование данных.

Разработан новый эвристический метод «iSmartRoute» для поиска кратчайшего маршрута в графе с нагруженными вершинами и дугами, который отличается от существующих тем, что для определения кратчайшего маршрута не требуется вычисления всех возможных маршрутов. Данный метод позволяет обрабатывать графы большой размерности без существенной потери производительности. Усовершенствован способ оптимизации многоэкстремальных функций результаты которого подтвердили практическую и научную ценность эволюционных алгоритмов. Разработан метод декомпозиции SQL-запроса в распределенной базе данных, который формирует совокупность сведений о частоте обращений к кортежам. Проведено экспериментальное исследование использования постоянных соединений с базой данных в традиционной кластерной системе и в сегментированной.

Разработан новый метод для горизонтальной фрагментации данных в базах данных большого объема, который в совокупности с методом декомпозиции SQL-запроса и его статистическим данным, позволяет: проводить динамическую фрагментацию на основе частоты обращений к кортежей в реальном времени; уменьшить время выполнения SQL-запросов; эффективно использовать дисковое пространство серверов баз данных и уменьшить нагрузку на них, путем эффективного распределения данных с минимальным числом избыточных фрагментов по нескольким распределенным базам данных. Проведено организацию распределения нагрузки в базе данных информационно-аналитической системы методом горизонтальной фрагментации и описаны ее основные характеристики, включая ее функционирования и защиту информации.

Ключевые слова: СУБД, распределенная база данных, эвристическая методология, генетический алгоритм, графы большой размерности, оптимизация многоэкстремальных функций.

ABSTRACT

Kravets  I.M. Distribution  of  load  balancing  in  large  volume databases using horizontal fragmentation. – Manuscript.

PhD (Engineering) thesis, speciality (according to Ukrainian nomenclature of specialities) 05.13.05 . Computer  systems  and  components. National Aviation University Ministry of education and science of Ukraine, Kyiv, 2010.

The thesis describes developing methodologies,  techniques and algorithms  for distribution of  load  in a  large volume database. A new heuristic method iSmartRoute optimization for large-scale graphs is proposed. Improved way of optimization for functions with multiple extremums, the results of which confirmed the  practical  and scientific  value  of  evolutionary  algorithms. Developed a method  of decomposing  SQL-query  in  a  distributed  database  to generate  aggregate  data about the frequency of traffic to tuples. An experimental study using permanent connections to the database in the traditional cluster system and segmented has been performed. Developed a method of horizontal  fragmentation of  large volume databases. Performed an organization of load balancing in database data-processing system using horizontal fragmentation  and  describes  its main characteristics,  including  its  performance  and  data protection.

Keywords: database, distributed database, heuristic methodology, genetic algorithm, large-scale graphs, optimization of multi-extreme functions.

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

  1. Жуков І. А. Адміністративно-начальна інформаційна система Інституту комп’ютерних технологій / І.А. Жуков, І.А. Клименко, І.М.  Кравець // Проблеми інформатизації та управління: зб. наук. пр. – 2007. – Вип. 1(19). – С. 56–57.
  2. Жуков І. А. Інформаційне забезпечення адміністративної та навчальної діяльності Інституту комп’ютерних технологій / [І.А. Жуков, І.А. Клименко, І.М. Кравець та ін.] // Вісник Національного технічного університету України «Київський політехнічний інститут», Інформатика, управління та обчислення: зб. наук. пр. – 2007. – Вип. 46. – С. 245–257.
  3. Жуков І. А. Методи балансування навантаження для Web-серверів / І.А. Жуков, І.М. Кравець // Проблеми інформатизації та управління: зб. наук. пр. – 2007. – Вип. 3(21). – С. 46–54.
  4. Жуков І. А. Розподілення навантаження баз даних в інформаційно-аналітичній системі / І.А. Жуков, І.М. Кравець // Проблеми інформатизації та управління: зб. наук. пр. – 2007. – Вип. 4(22). – С. 56–61.
  5. Жуков І. А. Організація розподілення навантаження баз даних в інформаційно-аналітичній системі / І.А. Жуков, І.М. Кравець // Науковий вісник Чернівецького університету. Фізика. Електроніка.: Тематичний випуск «Комп’ютерні системи та компоненти»: зб. наук. пр. – 2008. – Вип. 426. – Ч.ІІ. – С. 44–50.
  6. Жуков І. А. Постійні з’єднання з базами даних, як один із методів розподілення навантаження на WEB-серверах / І.А. Жуков, І.М. Кравець // Проблеми інформатизації та управління: зб. наук. пр. – 2008. – Вип. 2(24). – С. 5–13.
  7. Zhukov I. A. Organization of distribution  load database in the analysis and information system / I.A. Zhukov, I.M. Kravets // Radioelectronic and computer systems. – 2009. – Volume 5. – P. 25–30.
  8. Кравець І. М. Оптимізація багатоекстремальних функцій за допомогою генетичного алгоритму / І.М. Кравець // Проблеми інформатизації та управління: зб. наук. пр. – 2010. – Вип. 2(30). – С. 56–61.
  9. Жуков І. А. Програмно-апаратні засоби інформаційно-аналітичної системи / І.А Жуков, І.М. Кравець // Современные информационные и электронные технологии (СИЭТ-2009): междунар. науч.-практич. конф., 18-22 мая 2009 г.: тезисы докл. – Одесса: ОНПУ, 2009. – С. 115.
  10. Жуков І. А. Еволюційний алгоритм фрагментації та розподілу даних в інформаційно-аналітичній системі / І.А. Жуков, І.М. Кравець // Комп’ютерні системи та мережні технології (CSNT-2009): II міжнар. наук.-техн. конф., 10-12 червня 2009 р.: тези допов. – К.: Вид-во Нац. авіац. ун-ту «НАУ-друк», 2009. – С. 40.
  11. Zhukov I.A. An algorithm of fragmentation optimization in distributed database / I.A. Zhukov, I.M. Kravets // Advanced Computer Systems and Application: 4-th International Conference (ACSN-2009), November 9-11, 2009. – Lviv, 2009. – P. 72–75.
  12. Кравець І. М. Інтелектуальне розподілення навантаження для баз даних великого об’єму / І.М. Кравець // Комп’ютерні системи та мережні технології (CSNT-2010): III міжнар. наук.-техн. конф., 15-17 червня 2010 р.: тези допов. – К.: Вид-во Нац. авіац. ун-ту «НАУ-друк», 2009. – С. 54.

Завантажити автореферат: