zinet home
home home
home ИНТЕЛЛЕКТ-ПОРТАЛ
home Стартовал прием материалов в сборник XХХIX-й научной конференции. Требования к публикациям - в разделе "Объявления".

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

РЕСУРСЫ ПОРТАЛА:

Тридцать восьмая научно-практическая конференция
(23 - 28 мая 2016 г.)


Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)


Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)


Тридцать пятая научно-практическая конференция
(24-27 ноября 2015 г.)


Тридцать четвертая научно-практическая конференция
(13-17 октября 2015 г.)


Тридцать третья научно-практическая конференция
(20-27 мая 2015 г.)


Тридцать вторая научно-практическая конференция
(2-7 апреля 2015 г.)


Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)


Тридцатая научно-практическая конференция
(19-25 января 2015 г.)


Двадцать девятая международная научно-практическая конференция
(19-25 ноября 2014 г.)


Двадцать восьмая международная научно-практическая конференция
(08-13 октября 2014 г.)


Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)


Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)


Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)


Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)


Двадцать третья научно-практическая конференция
(10-15 декабя 2013 г.)


Двадцать вторая научно-практическая конференция
(4-9 ноябя 2013 г.)


Первая международная научно-практическая конференция
(14-18 мая 2013 г.)


Двадцать первая научно-практическая конференция
(14-18 мая 2013 г.)


Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)


Девятнадцатая научно-практическая конференция
(26 февряля - 3 марта 2013 г.)


Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)


Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)


Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)


Пятнадцатая научно-практическая конференция
(01 - 07 марта 2012 г.)


Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)


Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)


Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)


Одинадцатая научно-практическая конференция
(26 апреля - 04 мая 2011 г.)


Десятая научно-практическая конференция
(15-23 марта 2011 г.)


Девятая научно-практическая конференция
(27-31 декабря 2010 г.)


Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)


Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)


Шестая научно-практическая конференция
(1-15 апреля 2010 г.)


Пятая научно-практическая конференция
(20-27 мая 2009 г.)


Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)


Третья научно-практическая конференция
(20-27 декабря 2008 г.)


Вторая научно-практическая конференция
(1-7 ноября 2008 г.)


Первая научно-практическая конференция
(10-15 мая 2008 г.)



НАШИ ПАРТНЕРЫ:

Студия веб-дизайна www.zinet.info



Студия ландшафтного дизайна Флора-МК


Уникальное предложение!



Сайт-визитка - теперь
всего за 200 грн!

подробнее>>>



ОСОБЛИВОСТІ ЗАСТОСУВАННЯ ГЕНЕТИЧНИХ АЛГОРИТМІВ ПРИ ПРОЕКТУВАННІ ГІБРИДНИХ СХОВИЩ ДАНИХ З ВРАХУВАННЯМ ДЖЕРЕЛ ДАНИХ

 

Яцишин А.Ю.

Україна, м. Київ,

Національний технічний університет України

«Київський політехнічний інститут»

 

Application of genetic algorithms to building of hybrid data warehouses considering data sources is discussed in this article. The author analyses existing solutions which use genetic algorithms to data warehouse building and emphasizes several important issues that can be used to increase efficiency of building.

 

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

У світовій практиці у якості сховищ даних найчастіше використовуються реляційні та багатовимірні бази даних. Перші найчастіше використовуються у транзакційних системи (ІС банків, які обробляють фінансові операції великої кількості клієнтів), другі - у аналітичних (ІС великих корпорацій, які мають велику кількість різноманітних подань даних). Однак в силу необхідності мати сховище даних, яке відповідало би одночасно обидвом вимогам (наприклад, для Міністерства Фінансів), мною було запропоновано узагальнене гібридне сховище даних [13], яке поєднує у собі переваги як реляційних, так і багатовимірних баз даних.

Крім того, існує багато рішень з автоматизованого проектування сховищ даних, зокрема таких, що використовують генетичні алгоритми [1]-[12]. Розглянемо ці рішення.

У [1] представлено алгоритм, який дозволяє покращувати швидкодію бази даних при певних обмеженні витрат на її обслуговування. Пропонується генетичний алгоритм, задаються його параметри (цільова функція, структура хромосоми). У якості допоміжного використовується жадібний алгоритмдля формування популяції особин. Цей алгоритм описаний лище для реляційних баз даних, у ньому враховані особливості реляційних БД. Також він може бути використаний для баз даних типу OLAP в тому випадку, коли багатовимірна база даних будується на базі реляційної бази даних.

У [2] наведений алгоритм для вибору розбиття схеми у сховищі даних. У роботі розглянуто вертикальну та горизонтальну фрагментації. Робиться аналіз які таблиці доцільно фрагментувати, перевага надається узгодженій фрагментації таблиць вимірів і таблиці фактів. Пропонується представлення хромосоми генетичного алгоритму на основі предикатів фрагментації. Також використовується порогова функція придатності, що враховує вартість виконання запитів до сховища. Ця функція базується на релевантності (відповідності) запиту поточній «зірці».

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

У [3] розглядається проблема вибору кубів даних OLAP. Для визначення вартостізапиту використовується концепція решітки кубів.Метою роботи алгоритму є вибрати такі куби з заданих вимірів, щоб сумарна функція вартості була мінімальна. Використовується генетичний алгоритм з функцією придатності, що дорівноє функції вартості роботи системи кубів. Використовується одноточкове схрещування та турнірний метод відбору особин з принципом елітності. Також застосовується жадібний алгоритм відновлення, який усуває непридатні хромосоми (недопустимі рішення). Цей алгоритм за рахунок специфіки придатний виключно для багатовимірних баз даних. Він є застосовним у тих випадках, коли є наперед визначений набір кубів. В роботі не зазначено ніякої евристики як ці куби формуються, крім вибору за вимірами.

У [4] розглядаються багатоцільові алгоритми для вибору матеріалізованих представлениь в сховищах даних OLAP. У цій статті зосереджено увагу на застосуванні матеріалізованих представлень при декількох цільових функціях. Розглядаються існуючі алгоритми MOEAі MOGA, описуються способи управління обмеженнями. Пропонується алгоритм NPGA і вивчається вплив змінних на популяціїї алгоритмів. Цікавим є твердження про те, що автор дозволяє існування деяких недопустимих рішень в популяції, базуючись на можливості породження з них допустимих індивідів. Однак такий підхід до, на мою думку, може призвести до появи значної кількості недопустимих хромосом і виродження популяції, а тому і до подовження часу роботи алгоритму.

У [5], як і в [6], висвітлена проблема вибору схеми фрагментації в сховищі даних. Алгоритм у [5] також базується на предикатах і грунтується на понятті релевантності запиту схемі БД. Використовується метод селекції за допомогою колеса рулетки та двоточкове схрещування, яке дає одинакові шанси атрибутам з великою та малою кількостями піддоменів. Однак цей алгоритм є простішим і більш універсальним, однак результати, отримані за його допомогою, можуть бути гіршими, ніж у [6]. Він застосовний до реляційних і багатовимірних баз даних.

У роботах [7] та [8] авторами вивчили декілька гібридних евристичних та еволюційних алгоритмиів Чисто еволюційні алгоритми виявилися непрактичними через їх надмірного часу обчислень. Чисто евристичні алгоритми були незадовільними з точки зору якості рішення. Рішення, представлене в даній роботі може бути використано як для вибору матеріалізованих представлень, але тим самим вирішується лише питання оптимізації сховища даних..

У роботі [9] авторами розроблені алгоритми для проблеми проектування матеріалізованих подань, тобто, як вибрати безліч думок, які будуть матеріалізувався з різних MVPP так що загальна вартість обробки безлічі запитів і підтримки матеріалізованих представлень зводиться до мінімуму. Ми розробили підхід з використанням генетичного алгоритму локального пошуку, щоб вирішити цю проблему.Дане рішення також може бути використано як для вибору матеріалізованих представлень, але тим самим вирішується лише питання оптимізації сховища даних.

У статті [10] авторами представлено основу для оптимізації структур баз даних. Ця оптимізація була ініційована концептуальною схемою, що зазначена в моделі Predicator. Емпіричні дослідження будуть використані для подальшого вдосконалення цього підходу. результати, викладені в статті можна врахувати у алгоритмі побудови сховища даних.

У статті [11] автори представляють сімейство однокрокових алгоритмів, щоб вибрати, які куби та індекси повинні бути попередньо обчислені для підвищення продуктивності запитів, враховуючи обмеження простору. Результати, представлені в роботі показують, що алгоритм середньої складності виконується майже так само добре, як і високої складності. Ми також представляємо експериментальні результати, які перевіряють наш аналіз. Ці результати доцільно використати як елемент рішення для вибору індексів базі даних OLAP.

У роботі [12] розроблена теоретична основа для загальної проблеми вибору подання у сховищі даних. Автори представили конкурентоспроможні евристики поліноміальний час для деяких важливі нюансів проблеми, які виникають на практиці. Автори надали докази, що показують, що алгоритми гарантовано забезпечити рішення, яке знаходиться на постійний чинник оптимальним. Викладені у цій роботі результати доцільно використати у алгоритмі для проектування сховищ даних.

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

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

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

Сформулюємо задачу проектування гібридних сховищ даних, як це зроблено у [13]. Задані множини атрибутів розділених файлів, файлів XML , відношення у реляційній базі даних , виміри багатовимірної бази даних  та міри . Крім того, відоме порогове значення частот доступу до даних. Спроектувати гібридне сховище даних, визначивши області сховища даних , таблиці  та атрибути .

Знайти такі значення ознак розміщення , індексування , матеріалізації , на яких значення цільової функції

 

                                                     (1)

 

буде мінімальним серед всіх можливих наборів значень цих змінних.

При такій постановці до змінних задачі варто додати . Ці змінні позначають ті області сховища даних, які містять дані з джерела . Тоді до ЦФ потрібно додати суму штрафних величин , де і  - нормовані значення часів відносно середнього значення проектування та виконання запитів відповідно. Ці значення часів отримуються безпосередньо за результатами перепроектування та запитів.

Таким чином, отримуємо наступну функцію оптимізації:

 

                      (2)

 

Для вирішення цієї задачі використаємо алгоритм, що описаний в [14], враховуючи змінні. При цьому введемо механізм адаптації : для кожного наступного покоління знаходимо пари "батько-нащадок", які мають найбільшу кількість спільних і найменшу кількість змінених генів, співставляємо ті гени, які змінилися від їх батьків і якщо маємо значення ЦФ гірше, то ці гени фіксуються у значенні, протилежному тому, на яке вони змінилися.

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

 

Перелік посилань:

1.      C. Zhang. An evolutionary approach to materialized views selection in a data warehouse environment [Текст]. IEEE Transactions on Systems, Man and Cybernetics / C. Zhang, X. Yao, and J. Yang – 2001.

2.      C. Zhang. Genetic algorithm for materialized view selection in data warehouse environments. Proceeding of the International conference on Data Warehousing and knowledge discovery (DAWAK’99), / C. Zhang et J. Yang - 1999, pages 24-36.

3.      Himanshu Gupta. Index Selection for OLAP [Текст]. 13th International Conference on Data Engineering (ICDE'97) / Himanshu Gupta, Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ulman – 1997

4.      Himanshu Gupta. Selection of Views to Materialize in a Data Warehouse [Текст]. Database Theory — ICDT '97. Lecture Notes in Computer Science, 1997, Volume 1186/1997 / Himanshu Gupta - 1997

5.      J.-T. Horng, Y.-J. Chang, B.-J. Liu. Applying evolutionary algorithms to materialized view selection in a data warehouse [Текст]. Soft Computing - A Fusion of Foundations, Methodologies and Applications Volume 7, Number 8 / J.-T. Horng - 2003

6.      J.-T. Horng. Materialized view selection using genetic algorithms in a data warehouse system [Текст]. In Proc. CEC 1999, volume 3 / J.-T. Horng, Y.-J. Chang, B.-J. Liu, and C.-Y. Kao – 1999.

7.      Ladjel Bellatreche. An Evolutionary Approach to Schema Partitioning Selection in a Data Warehouse, Lecture notes in computer science [Текст], Congrès DaWaK 2005 : data warehousing and knowledge discovery: International conference on data warehousing and knowledge discovery No7 / Ladjel Bellatreche,Kamel Boukhalfa - Copenhagen - 2005

8.      Michael Lawrence. Multiobjective genetic algorithms for materialized view selection in OLAP data [Текст], Proceedings of the 8th annual conference on Genetic and evolutionary computation / Michael Lawrence – 2006

9.      Nectaria Tryfona. starER: A Conceptual Model for Data Warehouse Design [Текст], DOLAP '99 Proceedings of the 2nd ACM international workshop on Data warehousing and OLAP / Nectaria Tryfona, Frank Busborg, and Jens G. Borch Christiansen – 1999

10.  Venky Harinarayan. Implementing Data Cubes Efficiently [Текст]. SIGMOD '96 Proceedings of the 1996 ACM SIGMOD international conference on Management of data / Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ulman – 1996.

11.  Wen-Yang Lin. A Genetic Selection Algorithm for OLAP Data Cubes [Текст], Knowledge and information systems, vol. 6 / Wen-Yang Lin,I-Chung Kuo – 2004

12.  Ziyati Elhoussaine. Complete Algorithm for fragmentation in Data warehouse [Текст], 7th WSEAS Int. Conf. on ARTIFICIAL INTELLIGENCE, KNOWLEDGE ENGINEERING and DATA BASES (AIKED'08) / Ziyati Elhoussaine, Driss Aboutajdine, El Qadi Abderrahim - 2008

13.  Томашевський В.М.Математична модель задачі проектування гібридних сховищ даних з врахуванням структур джерел даних [Текст]. Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. пр. /Томашевський В.М.,Яцишин А.Ю. – К.:Век+, – 2011. – № 53. – 211

14.  Томашевський В.М. Особливості проектування гібридних сховищ даних з врахуванням джерел даних [Текст]. Подано до друку у Вісник Національного університету „Львівська політехніка”, секція "Інформаційні системи та мережі" / Томашевський В.М., Яцишин А.Ю. - 2012



Первая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(10-15 мая 2008 г.)


(отчет)
Вторая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(1-7 ноября 2008 г.)
(отчет)
Третья научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(20-27 декабря 2008 г.)
(отчет)
Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)
(отчет)
Пятая научно-практическая конференция
(20-27 мая 2009 г.)
(отчет)
Шестая научно-практическая конференция
(1-15 апреля 2010 г.)
(отчет)
Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)
(отчет)
Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)
(отчет)
Девятая научно-практическая конференция
(27-31 декабря 2010 г.)
(отчет)
Десятая научно-практическая конференция
(15-23 марта 2011 г.)
(отчет)
Одинадцатая научно-практическая конференция
(26 апреля 04 мая 2011 г.)
(отчет)
Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)
(отчет)
Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)
(отчет)
Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)
(отчет)
Пятнадцатая научно-практическая конференция
(01-07 марта 2012 г.)
(отчет)
Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)
(отчет)
Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)
(отчет)
Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)
(отчет)
Девятнадцатая научно-практическая конференция
(26 февраля - 3 марта 2013 г.)
(отчет)
Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)
(отчет)
Двадцать первая научно-практическая конференция
(13-18 мая 2013 г.)
(отчет)
Первая международная научно-практическая конференция
"Перспективные направления отечественной науки - ХХI век"
(13-18 мая 2013 г.)
(отчет)
Двадцать вторая научно-практическая конференция
(4-9 ноября 2013 г.)
(отчет)
Двадцать третья научно-практическая конференция
(10-15 декабря 2013 г.)
(отчет)
Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)
(отчет)
Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)
(отчет)
Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)
(отчет)
Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)
(отчет)
Двадцать восьмая научно-практическая конференция
(08-13 октября 2014 г.)
(отчет)
Двадцать девятая научно-практическая конференция"
(19-25 ноября 2014 г.)
(отчет)
Тридцатая научно-практическая конференция
(19-25 января 2015 г.)
(отчет)
Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)
(отчет)
Тридцать вторая научно-практическая конференция
(2 - 7 апреля 2015 г.)
(отчет)
Тридцать третья научно-практическая конференция
(20 - 27 мая 2015 г.)
(отчет)
Тридцать четвертая научно-практическая конференция
(13 - 17 октября 2015 г.)
(отчет)
Тридцать пятая научно-практическая конференция
(24 - 27 ноября 2015 г.)
(отчет)
Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)
(отчет)
Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)
(отчет)
Тридцать восьмая научно-практическая конференция
(23 - 25 мая 2016 г.)
(отчет)

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

Copyright © Zinet.info. Разработка и поддержка сайта - Студия веб-дизайна Zinet.info