Моделі, методи та інструментальні засоби оптимізації розподілених сховищ даних

Размещено на http://www.allbest.ru/

ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

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

Спеціальність 05.13.06 - Інформаційні технології

Автореферат дисертації

на здобуття наукового ступеня кандидата технічних наук

ПЕТРОВ ОЛЕКСАНДР ВАЛЕРІЙОВИЧ

Донецьк - 2009

Дисертацією є рукопис

Робота виконана в Донецькому національному технічному університеті Міністерства освіти і науки України.

Науковий керівник: кандидат технічних наук, доцент, Лаздинь Сергій Володимирович, Донецький національний технічний університет (м. Донецьк), професор кафедри автоматизованих систем управління.

Офіційні опоненти: доктор технічних наук, професор, Левикін Віктор Макарович, Харківський національний університет радіоелектроніки (м. Харків), завідувач кафедри інформаційних і управляючих систем.

доктор технічних наук, професор, Ульшин Віталій Олександрович, Східноукраїнський національний університет ім. Володимира Даля (м. Луганськ), завідувач кафедри системної інженерії.

Захист відбудеться «16» жовтня 2009р. о 13.00 годині на засіданні спеціалізованої вченої ради К 11.051.08 Донецького національного університету за адресою: 83000, м. Донецьк, пр. Театральний, 13, корп. 4, ауд. 416.

З дисертацією можна ознайомитись у бібліотеці Донецького національного університету за адресою: 83000, м. Донецьк, вул. Університетська, 24, головний корпус.

Автореферат розісланий «16» вересня 2009 р.

Вчений секретар спеціалізованої вченої ради К 11.051.08 кандидат технічних наук, доцент Д.В. Шевцов.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

розподіленний сховище дані запит

Актуальність проблеми. На сучасному етапі розвитку інформаційних технологій спостерігається тенденція до побудови великих розподілених комп'ютерних інформаційних систем (КІС). Це зумовлено розповсюдженням технічних засобів високошвидкісної передачі даних та вдосконаленням засобів побудови розподілених систем. Ця тенденція спостерігається не тільки за кордоном, але й в Україні. З появою надійних засобів швидкісної передачі даних все більше підприємств впроваджують розподілені комп'ютерні інформаційні системи.

Важливим компонентом багатьох розподілених КІС є розподілене сховище даних (РСД), яке становить сукупність фрагментів таблиці фактів, таблиць вимірів, матеріалізованих уявлень, розподілених між вузлами РСД, що з'єднані між собою глобальною комп'ютерною мережею. Користувачі через запуск та використання застосувань формують запити до РСД.

Розподіленим сховищам даних присвячено багато досліджень та публікацій, серед яких можна виділити роботи таких вчених, як Е. Коста, М. Мадейра, К. Ейзефе, К.Д. Шеве, Дж. Жао, І. Станоі та ін. Але через те, що у проведених дослідженнях не було враховано розподіленість даних, реплікація фрагментів таблиці фактів та матеріалізованих уявлень, технічні характеристики РСД, задача побудови оптимального РСД не отримала остаточного рішення та є актуальною.

Зараз під час побудови РСД, як правило, при обранні тієї чи іншої структури розподіленого сховища даних, головною є думка експертів, що ґрунтується на особистому досвіді та не підтверджена розрахунками. Вплив складу матеріалізованих уявлень, а також розподілення даних між вузлами РСД на загальну продуктивність оцінюється виходячи з особистого досвіду та інтуїції спеціалістів. Тому створення моделі розподіленого сховища даних та засобів аналізу його функціонування має важливе значення, адже це дозволить оцінити вплив складу матеріалізованих уявлень та розміщення даних у РСД на продуктивність його роботи.

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

Зв'язок роботи з науковими програмами, планами, темами. Роботу виконано в рамках держбюджетних НДР ДонНТУ: Д-5-04 «Розробка методів моделювання і оптимізації корпоративних систем з розподіленими базами даних» (№ державної реєстрації 0104U004059), Н-33-05 «Розробка наукових засад системного аналізу об'єктів комп'ютеризації та проектування інформаційних управляючих систем», у яких автор брав участь як виконавець.

Мета та задачі дослідження: підвищення продуктивності роботи РСД шляхом оптимізації складу матеріалізованих уявлень та розподілення даних між вузлами комп'ютерної інформаційної системи.

Для досягнення поставленої мети у дисертаційній роботі необхідно вирішити наступні задачі:

1. Провести аналіз структури РСД, виділити його типові компоненти. Обрати метод моделювання РСД.

2. Розробити моделі типових компонентів РСД. Побудувати загальну модель РСД як систему моделей типових компонентів РСД, що взаємодіють.

3. Визначити критерій ефективності функціонування РСД. Розробити підхід до оптимізації складу матеріалізованих уявлень та розподілення даних по вузлах РСД.

4. Розробити інструментальний засіб для моделювання, аналізу характеристик та оптимізації РСД.

5. Провести експериментальні дослідження за допомогою моделі РСД та на основі результатів їх аналізу розробити рекомендації щодо підвищення продуктивності роботи РСД.

6. З використанням розробленого підходу до оптимізації РСД провести машинні експерименти та виконати оптимізацію розподілення даних по вузлах РСД.

Об'єктом дослідження є розподілені сховища даних, їх структура та процеси функціонування.

Предметом дослідження є моделі роботи РСД, методи оптимізації складу матеріалізованих уявлень та розподілення даних по вузлах комп'ютерної інформаційної системи.

Методи дослідження. Для розробки моделі РСД було використано методи об'єктно-орієнтованого аналізу та моделювання, для оптимізації РСД було застосовано один з методів еволюційних обчислень - модифіковані генетичні алгоритми.

Наукова новизна отриманих результатів полягає у тому, що:

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

2. Вперше розроблено підхід до оптимізації РСД, який ґрунтується на спільному використанні генетичного алгоритму та об'єктної моделі РСД. На відміну від існуючих підходів, розроблений підхід дозволяє оптимізувати як склад матеріалізованих уявлень, так і розміщення даних по вузлах комп'ютерної інформаційної системи, що дозволяє підвищити продуктивність роботи РСД за рахунок скорочення середнього часу виконання користувацьких запитів.

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

Практичне значення результатів, отриманих у ході дослідження, полягає у тому, що:

1. Об'єктна модель РСД дозволяє отримувати характеристики РСД, а саме: час виконання запитів, завантаженість каналів передачі даних та серверів, дозволяє виявляти «вузькі місця» системи, що негативно впливають на продуктивність РСД у цілому. Проведення на моделі аналізу різних конфігурацій РСД дозволяє розробити практичні рекомендації щодо підвищення ефективності його роботи шляхом перерозподілу фрагментів таблиці фактів, зміни складу та перерозподілу матеріалізованих уявлень, а також зміни технічних характеристик серверів і каналів передачі даних.

2. Використання модифікованого генетичного алгоритму сумісно з об'єктною моделлю РСД дозволяє отримати субоптимальне рішення у вигляді розподілу фрагментів таблиць, а також складу та розподілу матеріалізованих уявлень у РСД. При цьому відхилення від глобального оптимуму складає не більше 5%, що забезпечує достатньо високу ефективність РСД.

3. Результати експериментів, а також інструментальний засіб, що побудовано на базі об'єктної моделі РСД та нового підходу до оптимізації РСД, було передано до філії «Куйбишевське відділення Промінвестбанку у м. Донецьк». Їх використання призвело до підвищення продуктивності вузла РСД у філії, що підтверджується актом впровадження.

4. Результати дисертаційної роботи були використані під час виконання наступних держбюджетних НДР ДонНТУ: Д-5-04 «Розробка методів моделювання і оптимізації корпоративних систем з розподіленими базами даних» (№ державної реєстрації 0104U004059), Н-33-05 «Розробка наукових засад системного аналізу об'єктів комп'ютеризації та проектування інформаційних управляючих систем», у яких автор брав участь як виконавець. Крім того, матеріали роботи були використані в навчальному процесі кафедри АСУ ДонНТУ в курсах «Розподілені та об'єктно-орієнтовані бази даних» та «Сховища даних та засоби аналітичної обробки інформації».

Особистий внесок здобувача. Усі нові результати, що наведено у дисертації автором отримані самостійно.

У роботах [1,2] автором виконано об'єктно-орієнтований аналіз РСД, виділено його основні компоненти, розроблено їх об'єктні моделі, а також побудована загальна модель РСД як система об'єктних моделей типових компонентів РСД, що взаємодіють. У роботі [3] автором запропоновано новий підхід до оптимізації РСД, що ґрунтується на спільному використанні об'єктної моделі РСД та генетичних алгоритмів. У роботі [4] автором представлено нову модифікацію генетичного алгоритму для задачі оптимізації РСД. Розроблено нову схему представлення розміщення даних в РСД за допомогою подвоєних мультихромосом. Розроблено нові версії генетичних операторів схрещування, мутації та рекомбінації, що працюють з подвоєними мультихромосомами.

Апробація результатів дисертації. Основні положення та результати дисертаційної роботи було викладено на ІІ Міжнародній науковій конференції студентів, аспірантів та молодих вчених «Комп'ютерний моніторинг та інформаційні технології» (ДонНТУ, Донецьк, 2006), на ІІ Міжнародній конференції «Сучасні тенденції розвитку інформаційних технологій в науці, освіті та економіці» (ЛНПУ, Луганськ, 2008), на наукових семінарах кафедри «Автоматизовані системи управління» ДонНТУ (2005-2008) та кафедри «Комп'ютерні технології» ДонНУ (2009).

Публікації. З теми дисертації опубліковано 6 наукових робіт, у тому числі 4 у провідних науково-технічних збірках, затверджених ВАК України, та 2 у тезах доповідей на конференціях.

Структура та обсяг дисертації. Дисертаційна робота складається зі змісту, вступу, п'яти розділів, висновку. Основний текст викладено на 166 сторінках друкованого тексту, містить 57 рисунків, 32 таблиці, перелік літератури з 99 найменувань та 5 додатків.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано наукову актуальність обраної теми, сформульовано мету та розв'язувані у роботі задачі. Представлено нові наукові результати, що були отримані під час виконання роботи, показано практичну цінність роботи, оцінку особистого внеску здобувача, наведено відомості про апробацію та публікацію результатів дослідження.

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

Розподілене сховище даних становить предметно-орієнтований, інтегрований, прив'язаний до часу набір даних, що використовується для підтримки прийняття рішень, різні частини якого розподілено між вузлами комп'ютерної мережі.

У загальному випадку РСД складається з набору вузлів, з'єднаних глобальною мережею, у якій на кожному вузлі зберігаються свої фрагменти таблиць та матеріалізованих уявлень, виконуються свої застосування та запити, а також забезпечена погоджена робота вузлів, така, що кожен користувач може отримати доступ до даних з будь-якого вузла мережі так, ніби він працює з локальним сховищем даних.

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

Аналіз робіт з моделювання РСД показав, що моделі РСД, що використовуються на початку, було розроблено для моделювання нерозподілених сховищ даних, і вони не враховують такі аспекти функціонування розподіленого сховища даних, як реплікація, фрагментація даних, розподілене виконання запитів. У ході аналізу відзначено, що для побудови моделі РСД доцільно використовувати на метод об'єктно-орієнтованого моделювання.

Аналіз методів оптимізації РСД показав, що, незважаючи на те, що вказані методи дозволяють знайти деяке субоптимальне рішення задачі, однак вони не враховують багато важливих особливостей РСД, а саме: розподіленість даних між вузлами, можливу наявність низькошвидкісних каналів зв'язку між вузлами РСД. У ході аналізу відзначено, що для оптимізації РСД доцільно використовувати на використання методу генетичних алгоритмів.

У другому розділі розроблено об'єктні моделі типових компонентів РСД, а також побудовано об'єктну модель РСД як систему об'єктних моделей її типових компонентів, що взаємодіють.

У результаті проведеного об'єктно-орієнтованого аналізу у складі РСД було виділено дві групи типових компонентів: логічної та фізичної архітектури. Було розроблено класи, що описують кожен з типових компонентів РСД. Для створення моделей було використано уніфіковану мову моделювання UML.

До компонентів логічної архітектури було віднесено усі компоненти сховища даних, що пов'язані із даними, та не пов'язані із технічним боком функціонування сховища, а саме:

- вимір (клас TDimension);

- фрагмент таблиці фактів (клас TDWFactTable) - частини таблиці фактів, що зберігаються незалежно від інших частин та основної таблиці;

- таблиця виміру (клас TDWDimTable) - таблиця СД, яка зберігає рідко змінювані дані, що характеризують та класифікують дані з таблиці фактів;

- матеріалізоване уявлення (клас TMatView) - заздалегідь обчислені результати запитів;

- запити на вставку, вибірку та оновлення (клас TDWQuery).

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

- сервер (клас TDWServer);

- канал зв'язку (клас TDWChannel);

- застосування (клас TDWApplication);

- користувач (клас TDWUser);

- вузол сховища даних (клас TNode) - структурний компонент сховища даних, що об'єднує у собі сервери, фрагменти таблиці фактів та вимірів, матеріалізовані уявлення, канали зв'язку, застосування, та користувачів, що територіально знаходяться у одному місці.

Розглянемо докладніше розроблену об'єктну модель типового компонента «Запит». Структуру класу TDWQuery наведено на рис. 1.

Размещено на http://www.allbest.ru/

Рис. 1. Структура класу TDWQuery

Властивостями класу TDWQuery є: ID - ідентифікатор, Name - найменування, Type - тип запиту, Tables - список таблиць, MatViews - список матеріалізованих уявлень, SubQueries - список підзапитів, Cost - складність запиту, ResultSize - розмір відповіді, Dimensions - список вимірів.

Крім того, цей клас містить такі методи: Execute - виконання запиту та RunSubQuery - запуск підзапиту.

Час виконання запиту на вибірку визначається виразом:

, (1)

де ts - час вибірки даних з основного фрагмента, ttr - час передавання даних по каналах зв'язку, - час виконання i-го підзапиту, QCS - кількість підзапитів.

Час виконання запиту на вставку визначається виразом:

, (2)

де ti - час вставки даних до основного фрагмента, ttr - час передавання даних по каналах зв'язку, - час виконання i-го підзапиту на оновлення, QCU - кількість підзапитів на оновлення.

Час виконання запиту на оновлення визначається виразом:

, (3)

де - час оновлення даних у ході виконання i-го підзапиту на оновлення, - час передавання даних по каналах зв'язку.

Загальна об'єктна модель РСД побудована як система об'єктних моделей типових компонентів РСД, що взаємодіють. Об'єктну модель наведено на рис.2.

Для об'єднання об'єктних моделей у єдине ціле та керування процесом моделювання було створено клас «Сховище даних» (TDataWarehouse), що містить методи, які працюють з усім сховищем даних у цілому.

Як метод просування модельного часу обрано метод найближчої події. У ході використання принципу найближчої події лічильник модельного часу просувається від кожної події до найближчої наступної, не зупиняючись на інтервалах між ними.

Результати моделювання зберігаються у базі даних моделі у вигляді протоколу подій, що виникли у ході моделювання. У подальшому ці результати можуть бути використані для аналізу показників роботи РСД.

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

Як критерій ефективності роботи РСД запропоновано використовувати середній час виконання користувацьких запитів на вибірку даних , який розраховується таким чином:

, (4)

де QCM - загальна кількість користувацьких запитів за час моделювання; - час виконання і-го запиту на вибірку, який визначається наступним виразом:

, (5)

де - час вибірки при виконанні i-го запиту; - час передачі даних при виконанні i-го запиту; - час виконання j-го підзапиту при виконанні i-го запиту; QCSi - кількість підзапитів, що виникають при виконанні i-го запиту.

Задачу оптимізації РСД сформульовано таким чином.

Структура та параметри розподіленого сховища даних задаються такими множинами:



Рис. 2. Об'єктна модель РСД

- вузлів сховища даних

N =

де NC - кількість вузлів РСД;

- серверів

S =

де SC - кількість серверів у РСД;

- каналів зв'язку

C =

де СС - кількість каналів зв'язку у РСД;

- фрагментів таблиці фактів

F =

де FC - кількість фрагментів таблиці фактів у РСД;

матеріалізованих уявлень

M =

де МС - кількість матеріалізованих уявлень у РСД;

- застосувань

A =

де АС - кількість застосувань у РСД;

- типів користувачів

U =

де UC - кількість типів користувачів у РСД;

- запитів

Q =

де QC - кількість запитів у РСД.

Взаємозв'язки між вказаними вище компонентами РСД визначаються перетинами перелічених вище множин.

Так, розподіл даних (фрагментів таблиці фактів, матеріалізованих уявлень) у РСД задається таким чином:

а) розподіл фрагментів таблиці фактів F по вузлах РСД N задається бінарним відношенням FA, на множині вигляду:

. (7)

Відношення FA можна подати у вигляді бінарної матриці Х розмірністю NCFC, де одиниця у i-й стрічці j-му стовбці означає, що j-й фрагмент таблиці фактів присутній на i-му вузлі РСД. При цьому:

(8)

б) склад та розподіл матеріалізованих уявлень М по вузлах РСД N задається бінарним відношенням MA, на множині вигляду:

. (9)

Відношення MA можна подати у вигляді бінарної матриці Y розміністю NCMC, де одиниця в i-й стрічці j-му стовбці означає, що j-е матеріалізоване уявлення присутнє на i-му вузлі РСД. При цьому:

(10)

При оптимізації РСД такі параметри, як множини вузлів сховища даних, серверів, каналів зв'язку, фрагментів таблиці фактів, матеріалізованих уявлень, застосувань, користувачів, запитів залишаються незмінними. Змінними параметрами є розподіл фрагментів таблиці фактів між вузлами РСД (матриця Х), а також склад та розподіл матеріалізованих уявлень (матриця Y).

Необхідно визначити такий склад матеріалізованих уявлень та їх розподіл Y, а також такий розподіл фрагментів таблиці фактів Х, за яких критерій ефективності роботи РСД - середній час виконання користувацьких запитів був би мінімальним.

, (11)

де QCM - загальна кількість користувацьких запитів на вибірку за час моделювання; - час виконання i-го запиту.

Для отримання оцінок у роботі використана розроблена у другому розділі об'єктна модель РСД.

При визначенні оптимального значення критерію (11) повинні бути враховані такі обмеження:

1. Обмеження на середній час оновлення даних. X та Y повинні бути такими, що середній час оновлення даних не повинен бути більше заданого при проектуванні РСД граничного значення часу оновлення:

, (12)

де - середній час оновлення даних, - час виконання k-го оновлення, QCU - загальна кількість запитів на оновлення за час виконання РСД, TUL - граничне значення середнього часу оновлення.

2. Обмеження на обсяги даних, що розміщуються:

, (13)

де - обсяг с1-го фрагмента таблиці фактів на i1-му вузлі РСД, Мб, - обсяг с2-го матеріалізованого уявлення на i1-му вузлі РСД, Мб, Dc3i1 - розмір с3-го пристрою зберігання даних на i1-му вузлі РСД; DC - кількість фрагментів таблиці фактів на i1-му вузлі РСД, MC - кількість матеріалізованих уявлень на i1-му вузлі РСД, HC - кількість пристроїв зберігання даних на i1-му вузлі РСД, i1 - номер вузла РСД.

3. Обмеження на розміщення хоча б одного екземпляра таблиці фактів.

(14)

де - ознака наявності i4-го фрагмента таблиці фактів, на i1-му вузлі, NC - кількість вузлів у сховищі даних; FC - кількість фрагментів таблиці фактів.

Часи виконання запитів у (11) динамічно залежать від завантаженості серверів, каналів зв'язку, розмірів черг передачі каналів зв'язку та черг обробки запитів серверів, тобто, виконання того самого запиту у різні моменти часу може зайняти різний час. Тому використання класичних методів оптимізації для розв'язання цієї задачі має певні ускладнення.

Кількість К можливих варіантів розв'язання задачі визначається виразом:

, (15)

де FC - кількість фрагментів таблиці фактів в РСД, MC - кількість матеріалізованих уявлень, NC - кількість вузлів РСД.

Наприклад, при кількості вузлів NC = 15, кількості фрагментів таблиці фактів FC = 20, кількості матеріалізованих уявлень MC = 16 кількість можливих розв'язань задачі складає. Така висока складність задачі не дозволяє розв'язати її методом повного перебору у прийнятний строк.

Запропоновано новий підхід до оптимізації РСД. Сутність підходу полягає у наступному: структура та параметри РСД кодуються у вигляді набору хромосом. У цих хромосомах міститься інформація про розміщення матеріалізованих уявлень і фрагментів таблиці фактів на вузлах РСД. За допомогою об'єктної моделі РСД проводиться обчислення значення критерію ефективності (4) для кожної з хромосом, яке є значенням фітнес-функції генетичного алгоритму (ГА). ГА на основі отриманого значення фітнес-функції формує нові хромосоми. Схематично запропонований підхід до оптимізації розподіленого сховища даних подано на рис. 3.

Размещено на http://www.allbest.ru/

Рис. 3. Підхід до оптимізації РСД

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

Перша мультихромосома описує розміщення фрагментів таблиці фактів по вузлах РСД. Друга - описує розміщення матеріалізованих уявлень по вузлах РСД.

У РСД що має NC вузлів, FC фрагментів таблиці фактів і МС матеріалізованих уявлень мультихромосома фрагментів таблиці фактів є сукупністю з NC хромосом, кожна з яких має розмірність FC.. Мультихромосома матеріалізованих уявлень у цьому випадку є сукупністю з NC хромосом, кожна з яких має розмірність МС.

Одиниця у j-й позиції i-ї хромосоми означає, що j-е матеріалізоване уявлення присутнє на i-му вузлі РСД.

Таким чином, кожна особина генетичного алгоритму є подвоєними муль-тихромосомами - комбінацією мультихромосом фрагментів та уявлень.

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

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

Програмний комплекс складається з трьох блоків: моделювання РСД, аналізу результатів моделювання і оптимізації РСД (рис. 4).

Рис. 4. Структура програмного комплексу моделювання і оптимізації РСД

Блок моделювання є програмною реалізацією розробленої об'єктної моделі РСД. Модель реалізована з використанням мови програмування С++, для зберігання вихідних даних і результатів моделювання використовується база даних, розроблена за допомогою СУБД Firebird.

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

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

У п'ятому розділі наводиться характеристика об'єкту експериментальних досліджень - розподіленого сховища даних Донецького регіонального управління АКБ «Промінвестбанк», а також опис і результати проведених машинних експериментів з моделювання і оптимізації РСД.

До складу ДРУ АКБ «Промінвестбанк» входять 29 філій, 165 безбалансових відділень, 13 відокремлених пунктів обміну валюти. РСД ДРУ АКБ «Промінвестбанк» містить 29 вузлів (рис. 5).

Рис. 5. Вузли РСД ДРУ АКБ «Промінвестбанк»

Також РСД містить таблицю фактів під назвою «Оплата» і таблиці вимірів: «Класи рахунків», «Категорії рахунків», «Клієнти», «Категорії клієнтів», «Час», «Відділення».

У таблиці фактів «Оплата» зберігається інформація про оплачені документи. Показниками таблиці фактів вказаного РСД є сума оплаченого документа, валюта документа, а також дебетовий і кредитовий рахунки документа. Таблиця розбита на 29 фрагментів.

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

Схема даних РСД наведена на рис. 6.

Проведені за допомогою об'єктної моделі РСД обчислювальні експерименти дозволили отримати і проаналізувати характеристики функціонування РСД. Середній час виконання запитів склав 54,76 сек.

Рис. 6. Схема даних РСД ДРУ АКБ «Промінвестбанк»

У результаті моделювання були виявлені "вузькі місця" системи. Ними є канали зв'язку, що мають найбільше завантаження, а саме: «ГВ Донецьк» - «Горлівка» (41,24%), «ГВ Донецьк» - «Макіївка» (39,15%), «ГВ Донецьк» - «Жовтневе» (31,18%).

З використанням об'єктної моделі РСД досліджено вплив параметрів технічних засобів і розміщення даних на ефективність роботи РСД. Заміна найбільш завантажених каналів зв'язку на більш високошвидкісні канали дозволила підвищити продуктивність РСД на 4,71%, а введення ряду нових матеріалізованих уявлень - на 13,75%.

Було проведено пошук глобального оптимуму за допомогою процедури повного перебору схем розміщення даних у РСД. У результаті було отримано середній час виконання запитів що дорівнює 32,29 сек.

Проведено обчислювальні експерименти з модифікованим генетичним алгоритмом, у результаті яких визначено раціональні значення параметрів алгоритму: вірогідність мутації Рмут = 0,05, вірогідність схрещування Рскр = 0,5, вірогідність рекомбінації Ррек = 0,35, розмір популяції Кпоп = 40 і кількість поколінь Кпок = 70. Субоптимальне значення критерію ефективності склало 33,79 сек.

Проведено порівняння отриманого за допомогою ГА субоптимального рішення з оптимальним , отриманим у результаті повного перебору схем розміщення даних. Абсолютне відхилення значення критерію ефективності роботи РСД, отриманого за допомогою генетичного алгоритму від глобального оптимуму, склало 1,41 секунди. Відносне відхилення склало 4,37%. Таке відхилення забезпечує достатньо високу ефективність РСД. При цьому субоптимальне рішення було отримано за 8 хвилин, у той час як пошук глобального оптимуму за допомогою повного перебору зайняв 12 діб.

ВИСНОВОК

У дисертаційній роботі представлено нове рішення актуальної науково-практичної задачі підвищення ефективності роботи РСД шляхом оптимізації складу матеріалізованих уявлень і їх розподілу спільно з фрагментами таблиці фактів на основі використання об'єктної моделі РСД і модифікованого генетичного алгоритму.

При виконанні роботи були отримані такі основні результати:

1. Шляхом об'єктно-орієнтованого аналізу побудовано загальну модель РСД як систему об'єктних моделей типових компонентів РСД, що взаємодіють. Побудована модель дозволяє проводити динамічне моделювання процесу функціонування РСД вільної структури.

2. Розроблено новий підхід до оптимізації РСД, побудований на спільному використанні об'єктної моделі РСД і генетичних алгоритмів. Модель використовується для обчислення цільової функції і обмежень задачі оптимізації РСД, генетичний алгоритм проводить модифікацію наборів рішень, представлених подвоєними мультихромосомами. Розроблено схему взаємодії між об'єктною моделлю РСД і ГА.

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

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

4. Проведені за допомогою об'єктної моделі РСД обчислювальні експерименти дозволили отримати і проаналізувати характеристики функціонування розподіленого сховища даних Донецького регіонального управління АКБ «Промінвестбанк». Досліджено вплив параметрів технічних засобів і розміщення даних на ефективність роботи РСД. Заміна найбільш завантажених каналів зв'язку на більш високошвидкісні канали дозволила підвищити ефективність РСД на 4,71%. Введення нових матеріалізованих уявлень дозволило підвищити ефективність роботи РСД на 13,75% за рахунок зменшення звернень до таблиці фактів.

5. Проведено обчислювальні експерименти з модифікованим генетичним алгоритмом, у результаті яких визначені раціональні значення параметрів алгоритму: Рмут = 0,05, Рскр = 0,5, Ррек = 0,35, Кпоп = 40 і Кпок = 70. Отримане при цьому субоптимальне значення критерію ефективності роботи РСД складає 33,70 сек, що на 38,46% менше вихідного його значення.

6. Проведено порівняння субоптимального рішення, отриманого за допомогою ГА з оптимальним рішенням, отриманим у результаті повного перебору варіантів розподілу матеріалізованих уявлень і фрагментів таблиці фактів. Абсолютне відхилення значення критерію ефективності, отриманого за допомогою генетичного алгоритму від глобального оптимуму, склало 1,41 секунд, відносне відхилення склало 4,37%.

7. Оптимізація складу матеріалізованих уявлень і їх розподілу спільно з фрагментами таблиці фактів забезпечує підвищення ефективності роботи РСД за рахунок зменшення середнього часу виконання призначених для користувача запитів без додаткових витрат на модернізацію устаткування.

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

1. Лаздынь С.В. Разработка объектной модели распределенного хранилища данных / С.В. Лаздынь, А.В. Петров // Наукові праці Донецького національного технічного унівеситету.- Серія: “Обчислювальна техніка та автоматизація”. Випуск 107.: Башков Є.О. (голова) та ін.- Донецьк: ДонНТУ.- 2006.- С.122-127.

2. Лаздынь С.В. Построение модели распределенного хранилища данных с использованием объектно-ориентированного похода / С.В. Лаздынь, А.В. Петров // Наукові праці Донецкького національного технічного університету.- Серія: “Обчислювальна техніка та автоматизація”. Випуск 130.- Донецьк: ДонНТУ.- 2008.- С.100-109.

3. Лаздынь С.В. Оптимизация распределенных хранилищ данных с использованием генетических алгоритмов и объектного моделирования / С.В. Лаздынь, А.В. Петров // Наукові праці Донецкького національного технічного університету. Серія: “Обчислювальна техніка та автоматизація”. Випуск 121.- Донецьк: ДонНТУ.- 2007.- С.72-82.

4. Петров А.В. Модифицированный генетический алгоритм для оптимизации распределенных хранилищ данных / А.В. Петров // Вісник Східноукраїнського Національного Університету ім. Володимира Даля.- №12(130).- 2008.- ч.2.- С.119-129.

5. Петров А.В. Моделирование и анализ работы распределенного хранилища данных / А.В. Петров // Сборник трудов конференции «Компьютерный мониторинг и информационные технологии».- Донецк: ДонНТУ.- 2006.- С.183;

6. Петров О.В. Використання генетичних алгоритмів для оптимізації розподілених сховищ даних / О.В. Петров // Збірка тез ІІ міжнародної конференції «Сучасні тенденції розвитку інформаційних технологій у науці, освіті та економіці» (ЛНПУ, Луганськ, 2008).- Луганськ.- 2008.- С.82-83.

АНОТАЦІЯ

Петров О.В. Моделі, методи та інструментальні засоби оптимізації розподілених сховищ даних. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - Інформаційні технології, Донецький національний технічний університет, 2009.

У дисертації розглядається важлива науково-практична задача оптимізації складу матеріалізованих уявлень, а також розміщення даних у розподіленому сховищі даних (РСД).

Дисертаційна робота присвячена розробці нових моделей та методів для оптимізації розподілених сховищ даних. Проведено аналіз розподіленого сховища даних, визначені основні його компоненти. Використовуючи об'єктно-орієнтований підхід, було розроблено об'єктні моделі типових компонентів РСД. Загальну модель розподіленого сховища даних побудовано як систему об'єктних моделей типових компонентів РСД, що взаємодіють.

Запропоновано новий підхід до розв'язання задачі оптимізації розподілених сховищ даних, який базується на сумісному використанні розробленої об'єктної моделі РСД та модифікованого генетичного алгоритму, що дозволяє підвищити ефективність роботи розподіленого сховища даних за рахунок зменшення середнього часу виконання користувацьких запитів.

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

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

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

Ключові слова: розподілене сховище даних, таблиця фактів, таблиця виміру, матеріалізоване уявлення, об'єктно-орієнтоване моделювання, генетичний алгоритм, схрещування, мутація, рекомбінація.

АННОТАЦИЯ

Петров А.В. Модели, методы и инструментальные средства оптимизации распределенных хранилищ данных. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - Информационные технологии, Донецкий национальный технический университет, 2009.

Диссертационная работа посвящена разработке новых моделей и методов для оптимизации распределенных хранилищ данных (РХД). Проведен анализ распределенного хранилища данных, определены основные его компоненты. Используя объектно-ориентированный подход, были разработаны объектные модели типовых компонентов РХД. Общая модель распределенного хранилища данных была построена как система взаимодействующих объектных моделей типовых компонентов распределенного хранилища данных.

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

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

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

Проведена серия машинных экспериментов по моделированию и оптимизации РХД. На основе проведенных экспериментов определены рациональные параметры модифицированного генетического алгоритма, а также разработаны рекомендации по повышению эффективности распределенных хранилищ данных.

Ключевые слова: распределенное хранилище данных, таблица фактов, таблица измерения, материализованное представление, объектно-ориентированное моделирование, генетический алгоритм, скрещивание, мутация, рекомбинация.

ABSTRACT

Petrov O.V. Models, methods and tools for distributed data warehouses optimization. - Manuscript.

Candidate of technical sciences' thesis on specialty 05.13.06 - Information technologies. Donetsk national technical university, 2009.

In this dissertation a new scientific and practical problem of optimization of a set of materialized view, and also of optimization of data allocation in a distributed data warehouse is being observed.

The thesis is devoted to development of new models and methods of distributed data warehouses (DDW) optimization. Structural analysis of distributed data warehouse has been conducted and on the basis of this analysis the main components of its physical and logical architecture have been revealed. Then using object-oriented approach object models of the distributed data warehouse's typical components were developed. For these models' development UML language was used.

A new approach to the problem of optimization of distributed data warehouses has been proposed. This approach is based on a simultaneous use the object-oriented model of distributed data warehouse that had been developed before and a modified genetic algorithm.

The modified genetic algorithm is used to obtain new schemas of data allocation in a distributed data warehouse (by manipulations with schemas of data allocation that are represented by doubled multichromosomes with genetic operators of recombination, crossover and mutation). In the same time object model of distributed data warehouse receives schemas of data allocation in DDW and then it is being used to calculate values of criterion of efficiency of distributed data warehouse. These values then are sent to the genetic algorithm which uses them as values of fitness-function.

The approach proposed allows increasing distributed data warehouse's efficiency by decreasing of the average time of user select queries processing.

A new modification of genetic algorithm for the problem of distributed data warehose optimization was developed. For encoding schemas of data distribution in distributed data warehouse for the first time doubled multichromosomes were used. New versions of genetic operators of recombination, crossover and mutation were developed. This modification of genetic algorithm allows obtaining suboptimal solutions of the problem of distributed data warehouse optimization. Also in this modification not only data allocation between the nodes of distributed data warehouse is being optimized but the set of materialized views is being optimized.

Basing on the developed object model and the modified genetic algorithm a new tool for distributed data warehouse modeling and optimization was developed. This tool consists of three subsystems: subsystem of modeling, analysis and optimization of distributed data warehouse.

The tool that has been developed can be used at the stage of distributed data warehouse development as well as it can be used when a distributed data warehouse is already implemented and functioning.

As an object of experiments the distributed data warehouse of Donetsk regional office of Prominvestbank was selected. Real data of functioning of this DDW were obtained and used to test model adequacy.

Then a series of computational experiments of modeling and optimization of distributed data warehouse was made. At the beginning an influence of data allocation and technical characteristics of DDW to its efficiency was researches. These experiments showed that doubling of channels' capacity leads to a slight increasing of DDW efficiency. Also it has been researched that creation of some new materialized views and allocation them on the nodes of most use leads to increasing of DDW efficiency as well. But this increase isn't enough to solve the distributed data warehouse optimization problem since the solutions obtained are far from optimal anyhow.

Basing on the experiments' results rational parameters of the modified genetic algorithm were determined (such as probabilities genetic operators, number of generation and number of individuals in the population). Then these parameters were used for genetic algorithm that was used for data warehouse optimization.

The suboptimal solution obtained with use of genetic algorithm was compared with optimal solution that was obtained used brute force method and the difference between these solutions was just 4,37%. This means that the genetic algorithm developed allows to receive suboptimal solutions that are very close to the global optimum. Also some recommendations for distributed data warehouse efficiency increasing were developed.

Keywords: distributed data warehouse, fact table, dimension table, materialized view, fragmentation, replication, object-oriented modeling, genetic algorithm, crossover, mutation, and recombination.

Размещено на Allbest.ur

...