Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Бакулева, Марина Алексеевна

• Бакулева, Марина Алексеевна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Бакулева, Марина Алексеевна

Список применяемых сокращений.

Введение.

1 Анализ проблемы проектирования хранилищ данных.

1.1 Роль хранилища данных в системах поддержки принятия решений.

1.2 Модели хранилищ данных.

1.3 Методология проектирования хранилищ данных.

1.4 Структура данных хранилища данных.

1.5 Обоснование выбора инструментария для решения поставленных задач.

2 Математическая модель структуры. хранилища данных.

2.1 Тензорная модель реляционного хранилища данных.

2.1.1 Тензорная модель структуры реляционной базы данных.

2.1.2 Тензорная модель запросов к реляционной базе данных.

2.1.3 Тензорная модель реляционного хранилища данных.

2.1.4 Тензорная модель ROL АР.

2.2 Тензорная модель многомерного хранилища данных.

2.2.1 Модель операций над многомерным хранилищем данных

2.3 Алгоритм автоматизации проектирования хранилищ данных на основе разработанных моделей.

3 Алгоритмы повышения производительности систем оперативного анализа на основе кратномасштабного представления данных.

3.1 Анализ структуры реляционного хранилища данных.

3.2 Основная идея кратномасштабного анализа.

3.3 Обоснование выбора базиса Хаара.

3.4 Кратномасштабное представление данных хранилища на основе вейвлет разложения в базисе Хаара.

3.5 Агрегация данных масштабированного хранилища данных.

3.6 Расчет аналитических показателей.

3.6.1 Выделение тренда.

3.6.2 Периодичность.

3.6.3 Кратномасштабный анализ.

3.6.4 Ретроспективный анализ.

4 Экспериментальная часть.

4.1 Реализация алгоритма автоматизации.

4.2 Реализация алгоритмов агрегации и ЯОЬАР.

4.3 Результаты проводимых экспериментов.

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей»

Одним из основных компонентов современных информационных систем являются средства содержания и манипулирования массивами разнородных данных, технологии хранения и обработки которых постоянно совершенствуются. Это приводит к скоплению больших объемов (пластов) данных. Без средств продуктивной переработки эффективность их использования резко уменьшается. Кроме того, по мере увеличения объемов и сложности хранимых данных и по мере их интеграции растет потребность и в средствах автоматизированного проектирования способных сократить сроки разработки и внедрения новых методов обработки столь многообразной и неструктурированной информации.

Создание средств автоматизации процесса сбора и предварительной обработки данных для анализа является важной научно-технической задачей, поскольку от скорости и корректности этого процесса напрямую зависит способность информационной системы поддерживать (сопровождать) процессы принятия решений.

Основу информационно-поисковых систем производственных предприятий, образовательных учреждений, муниципальных структур и коммерческих образований составляют многочисленные базы данных (БД), построенные на основе реляционной модели [17, 18, 23, 25, 26, 51]. Основной идеей реляционной модели является нормализация с целью экономии ресурсов памяти [17, 18, 21, 39]. Сложные по структуре и многообразию связей реляционные БД не отвечают требованиям производительности аналитических приложений и соответственно не могут выполнять функции информационной поддержки процедуры принятия решений.

Поэтому в современных информационных системах наиболее востребованы денормализованные БД - хранилища данных (ХД). ХД являются основным источником данных оперативно-аналитических подсистем (ОЬАР-систем) современных систем поддержки принятия решений (СППР).

Однако отсутствие единого математического описания исходной БД и ХД, проектируемого на ее основе, приводит к торможению процесса разработки и внедрения ХД.

В работах Р. Кимбала [68], Б. Инмона [65], М.С. Куприянова [12], Б. Маркова [30] рассматриваются методы построения ХД на основе реляционной модели. В работах А. Кэмбла [60], Д. Селко [39] метод построения модели основан на теории множеств. Многомерная модель данных приводится в работе Э. Франкони [60] и У. Сатлера [61]. Некоторые из перечисленных методов применяются для автоматизации формирования многомерных представлений данных.

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

Потребность оперативной обработки данных ХД (содержащих порядка 107 записей) приводит к необходимости создания специализированных аналитических решений. Для достижения приемлемого быстродействия (время ответа не более 5 секунд) необходимо разработать способ представления данных, адаптированный к условиям оперативного анализа.

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

Цель работы. Исходя из вышеизложенного, можно заключить, что задача проектирования хранилищ данных включает в себя требование обеспечения оперативности аналитических подсистем, работающих с хранилищами.

Поэтому целями диссертационной работы являются:

1) ускорение процесса проектирования ХД;

2) повышение скорости аналитической обработки данных ХД.

Для достижения поставленных целей необходимо решить ряд задач:

1) разработать единую математическую модель реляционной БД и ХД;

2) разработать математическую модель многомерного ХД;

3) разработать математическую модель операций над многомерным

ХД;

4) разработать математическую модель структуры данных в ХД, отвечающую требованиям OLAP - систем по быстродействию;

5) разработать алгоритмы, автоматизирующие процесс построения ХД на основе предложенных моделей;

6) разработать алгоритмы OLAP на основе предложенной структуры;

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

Методы исследований. Для решения поставленных задач привлечены методы тензорной алгебры [1, 13, 15, 24, 27], кратномасштабного анализа [14, 19, 36, 37, 72], вейвлет-преобразований [34, 50, 53, 70, 71, 74, 81] и сигнатурного поиска [19,41, 48, 53].

В качестве инструментальных средств использовались: Borland Delphi 7, MySQL, PostgreSQL.

Научная новизна. В работе новыми являются следующие результаты:

1. Предложены новые модели реляционного и многомерного ХД на основе тензорного аппарата.

2. Разработан метод аналитической обработки данных ХД, основанный на вейвлет - преобразовании.

3. Разработан алгоритм автоматизации процесса проектирования ХД на основе разработанных моделей. Основным преимуществом данных алгоритмов является снижение временных затрат на разработку ХД и автоматизация рутинных операций по описанию разнообразных связей исходной БД и проецированию соответствующих отношений в ХД.

4. Разработаны алгоритмы агрегации и анализа данных ХД. Отличие от известных заключается в использовании кратномасштабного анализа.

5. Разработаны алгоритмы ретроспективного анализа. Отличие от известных алгоритмов, прежде всего - в большей производительности, полученной за счет применения сигнатурного поиска.

Практическая ценность. Практическая ценность полученных результатов состоит в следующем:

1. Создан комплекс программных средств на основе разработанного алгоритма автоматизации проектирования структур ХД, позволяющий сократить сроки проектирования ХД. На основе данного комплекса в научно -производственном предприятии «Эльф 4М» (г. Рязань) произведена реконструкция системы информационного обеспечения производственной деятельности предприятия.

2. Созданный комплекс программных средств по обработке данных ХД является инструментом, обеспечивающим высокую скорость аналитической обработки большого числа хранимых данных. Внедрение разработанного комплекса значительно повысило эффективность работы научно - производственного предприятия «Эльф 4М», масштабы производства которого охватывают 12 стран (БД содержит «500000 записей). Созданный программный комплекс предоставляет руководителю актуальную информацию о темпах производства, географии сбыта, а также векторе развития предприятия.

3. Созданный программный комплекс используется в ООО «Торгтек» (г. Рязань) для оперативной обработки отчетной и аналитической информации.

Апробация результатов диссертации. Результаты, полученные в рамках работы над диссертацией, докладывались на 10-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании»,

Рязань, 2005 г. [6]; 2-й Международной научно-практической конференции «Информационная деятельность: проблемы науки и практики», Киев, 2005 г. [10]; 14-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2005 г. [5]; 11-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 2006 г. [3]; 12-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 2007 г. [9].

Публикации. Основные результаты диссертации опубликованы в 11 работах, из них 2 работы опубликованы в изданиях, рекомендованных ВАК.

Внедрение результатов работы. Результаты, полученные в диссертационной работе, внедрены и использованы в научно - производственном предприятии «Эльф 4M» (г. Рязань), ООО «Торгтек» (г. Рязань) (приложение 3), а также представляют часть НИР (НИР № 10-06Г (РНТП 3.2.3.7637) «Разработка нормативной базы, информационного обеспечения и регламентов открытой информационно-образовательной среды для дистанционной подготовки, переподготовки и повышения квалификации специалистов в области ИЛИ (CALS) и CASE-технологий», НИР 11-06Г (РНТП 3.2.3.7652) «Интегрированная автоматизированная информационная система управления качеством образования ВУЗа»), проводимых РГРТУ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка (82 источника), изложенных на 131 странице (содержит 10 таблиц, 53 рисунка), и 3 приложения. Общий объем диссертации 147 страниц.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Бакулева, Марина Алексеевна

ЗАКЛЮЧЕНИЕ

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

В ходе выполнения работы:

1. Выполнен анализ современных работ в области новых информационных технологий хранения и обработки данных, рассмотрены существующие модели и методы проектирования ХД, проанализированы возможности применения в ходе автоматизированного проектирования ранее разработанных моделей и методов.

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

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

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

5. Разработана модель данных, внедрение которой значительно повышает производительность работы с ХД.

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

7. Разработан программный комплекс, подтверждающий экспериментально преимущества разработанных алгоритмов.

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

Список литературы диссертационного исследования кандидат технических наук Бакулева, Марина Алексеевна, 2007 год

1. Арменский А.Е. Тензорные методы построения информационных систем. -М.: Наука, 1989. 152 с.

2. Бакулева М.А, Бакулев А.В Применение вейвлет-преобразования для анализа данных хранилищаУ/Вестник РГРТУ. — 2007. — № 21. — С.57 — 60

3. Бакулева М.А. Математическая модель построения многомерной БД. Информационные технологии и телекоммуникации в образовании и науке. Межвуз. сб. научн. трудов. Рязань: РГРТА, 2005. — С.23—26

4. Бакулева М.А. Применение вейвлет-преобразований в задачах поиска информации. Информационные технологии и телекоммуникации в образовании и науке. Межвуз. сб. научн. трудов. Рязань: РГРТА, 2006. — С.26—31

5. Бакулева M.А. Применение вейвлет-преобразований для представления данных хранилища/УВестник РГРТА. — 2006. — № 18. — С.80— 86

6. Бакулева М.А. Тензорная модель работы реляционной СУБД// Информационные технологии в проектировании. Межвуз. сб. научн. трудов. Рязань: РГРТА, 2004. С.39-43

7. Баргесян A.A., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и модели анализа данных: OLAP и Data Mining. — СПб.: БХВ-Петербург, 2004. — 336 с.

8. Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры. — М.: «Физико математическая литература», 2006. — 304 с.

9. Бердышев В.И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложения. — Екатеринбург: УрО РАН, 1999.

10. Борисенко А.И., Таранов И.Е. Векторный анализ и начала тензорного исчисления. — Харьков: Изд-во Харьковского государственного университета, 1959. — 238 с.

11. Грехем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998. — 703 с.

12. Дарвин X., Дэйт К. Системы баз данных третьего поколения: Манифест/СУБД. — 1995. — № 2.

13. Дарвин X., Дэйт К. Третий манифест//СУБД. — 1996. — № 1.

14. Добеши И. Десять лекций по вейвлетам. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. — 464 с.

15. Долотов Д. Хранилище данных для «Мострансгаза»//Открытые системы. — 2003. — № 4. — С.43—48

16. Дэйт К. Введение в системы баз данных. — М.: «Вильяме», 1999. —848 с.

17. Дюк В., Самойленко A. Data Mining: учебный курс. — СПб.: Питер, 2001.—257 с.

18. Зильбершатц А., Стоунбрейкер М., Ульман Д. Базы данных: достижения и перспективы на пороге 21-го столетия//СУБД. 1996. № 3.

19. Кадомцев С.Б. Аналитическая геометрия и линейная алгебра. — М.: «Физико математическая литература», 2003. — 160 с.

20. Кодд Э. Расширение реляционной модели для лучшего отражения семантики//СУБД. — 1996. — № 5.

21. Кодд Э. Расширение реляционной модели для лучшего отражения семантики//СУБД. — 1996. — № 6.

22. Корячко В.П., Скворцов C.B., Телков И.А. Архитектуры многопроцессорных систем и параллельные вычисления. — М.: Высш.шк., — 1999. — 235 с.

23. Макаров A.A., Тюрин Ю.Н. Анализ данных на компьютере. — М.: ИНФРА-М, — 2003. — 544 с.

24. Маклаков С. Проектирование хранилищ данных//Компьютер пресс. —2001. —№ 1.

25. Марков Б. Проектирование систем регистрации и анализа данных. — http://www.citforum.ru/database/articles/regdata.shtml

26. Некрасов В. Архитектуры OLAP клиентов/ЛСомпьютерная неделя. — 2001. —№ 30.

27. Некрасов В. Введение в OLAP на практическом приме-ре//Компьютерная неделя. — 2001. — № 16.

28. Некрасов В., Кононова О. Распространенные заблуждения о хранилищах данных/ЯШ Magazine. — 2003. — № 5.

29. Новиков И.Я., Стечкин С.Б. Основные конструкции всплесков // Фундаментальная и прикладная математика. — 1997. — Т. 3, № 4. — С.999— 1028

30. Переберин A.B. О систематизации вейвлет-преобразований// Вычислительные методы и программирование. — 2001. — Т. 2, № 2. — С. 133158

31. Петухов А. П. Введение в теорию базисов всплесков. — СПб.: СПбГТУ, 1999.— 132с.

32. Пржияковский В.В. Абстракции в проектировании БД//СУБД. — 1998. —№ 1.

33. Пушников А.Ю. Введение в системы управления базами данных. Часть 1. Реляционная модель данных: Учебное пособие. — Уфа: Башкирский университет, 1999. — 108 с.

34. Селко Д. Стиль программирования Джо Селко на SQL. — СПб.: «Питер», 2006. — 206 с.

35. Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002. — 272 с.

36. Федоров А., Елманова Н. Хранилище данных//Компьютер пресс. — 2001. —№5. —С.137—145

37. Фищенко В.К., Кулешов Е. Л. Использование вейвлет-преобразования для оптимального оценивания тренда случайного процес-са//«Автометрия». — 2003. — Т. 39, № 1. — С. 103 — 113

38. Черняк JI. Хранилища и карты данных// Открытые системы. — 2005. — №47.

39. Agrawal R., Gupta A., Sarawagi S. Modeling multidimensional databases. — In Proc. of ICDE-97. — 1997. — P.56—72

40. Battle G. A block spin construction of ondelettes. Lemarie functions// Math. Phys. — 2002. — No. 10. — P.601—615

41. Bourgain J. A remark on the uncertainty principle for Hilbertian basis// Funct. Anal. —2001. — No. 79. — P. 136—143

42. Burt P.J., Adelson E.H. The Laplasian Pyramid as a Compact Image Code//IEEE Trans, on Communications. — 1983. — Vol. COM-31, No. 4. — P.532—540

43. Cabibbo L., Torlone R. A logical approach to multidimensional databases. — In Proc. of EDBT-98. — 1998. — P.23—29

44. Chui K. An Introduction to Wavelets. — Boston: Academic Press,1992

45. Codd E.F. Extending the Relational Database Model to Capture More Meaning//ACM Transactions on Database Systems. — 1979. — No. 4. — P.67— 78

46. Codd E.F. Providing OLAP to user-analysts: An IT mandate. Technical report, 1993.

47. Cohen A., Daudechies I., Feauveau J.C. Biorthogonal bases of compactly supported wavelets//Communications on Pure and Applied Mathematics. — 1992. — No. 45 — P.485—500

48. Date C.J. The Extended Relational Model RM/T. In C.J. Date, Relational Database Writings 1991-1994. — Mass.: Addison-Wesley, 1995

49. Daubechies I. Ten Lectures on Wavelets. — Philadelphia: SIAM,

50. Eidenderger H. Visual Data Mining. — Seattle: ACM, 2004. —307p.

51. Fayyad U.M., Piatetsky-Shapiro G., Smyth P., Uthurusamy R. Advances in Data Mining and Knowledge Discovery//MIT Press, Cambridge, — 1995.

52. Finkelstein A., Salesin D. Multiresolution Curves. —New York: In Proceedings of SIGGRAPH, 1994. — P.261—268

53. FIPS Integration Definition for Information Modeling: IDEF1X. — Computer Systems Laboratory, National Institute of Standards and Technology, 1993. — (Federal Information Processing Standards Publication 184)

54. Franconi E., Kamble A. The GMD Data Model and Algebra for Multidimensional Information. — In Proc. 5th International Conference on Data Warehousing and Knowledge Discovery. — 2003. — P.55-65

55. Franconi E., Sattler U. A data warehouse conceptual data model for multidimensional aggregation: a preliminary report//Journal of the Italian Association for Artificial Intelligence. — 1999. — P.9—21

56. Golfarelli M., Maio D., Rizzi S. The dimensional fact model: a conceptual model for data warehouses//IJCIS. — No. 7 — 1998. — P. 215—247

57. Gray J., Bosworth A., Layman A., Pirahesh H. Data cube: a relational aggregation operator generalizing group-by, cross-tabs and subtotals. — In Proc. ofICDE-96. — 1996. — P. 121—143

58. Gupta H. Selection of Views to Materialize in a Data Warehouse. — In Proc. of the 6th Intl. Conf. on Database Theory. — 1997. — P.98—112

59. Inmon B. Building the Data Warehouse. — New York: John Wiley & Sons, 1996.

60. Jagadish H.V., Lakshmanan V.S., Srivastava D. What can hierarchies do for data warehouses? — In Proc. 25th International Conference on Very Large Databases (VLDB). — 1999. — P.530—541

61. Jawerth B., Sweldens W. An Overwiew of Wavelet Based Multiresolution Analyses//SIAM Rev. — 1994. — Vol. 36, No. 3. — P. 377—412

62. Kimball R. The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouse. — New York: John Wiley & Sons, 2000.

63. Klein H.K., Hirschheim R.A. A Comparative Framework of Data Modelling Paradigms and Approaches//The Computer Journal. — 1987. — No. 1—P.8—15

64. Lemarie P.G. One nouvelle base d'ondelettes de //Math. Pures et Appl. —1997. — No. 67 — P. 227—236

65. Mallat S. A Wavelet Tour of Signal Processing. — New York — London: Academic Press, 1998

66. Mallat S. Multiresolution Approximation and Wavelet Othonormal Bases L2(R)//Trans. AMS. — 1989. — Vol. 1, No. 315. — P. 69-87

67. Manna Z., Pnueli A. The Temporal Logic of Reactive and Concurrent Systems//Springer Verlag. —1992. — P. 12—25

68. Meyer Y. Principe d'incertitude, bases hilbertiennes et algebras d'operateurs//Seminaire Bourbaki. — 1985. — No. 662. — P. 142—167

69. Ross K.A., Srivastava D., Sudarshan S. Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. — In Proc, of the ACM SIGMOD Intl. Conf. on Management of Data. — 1996. — P.447—458

70. Roussopoulos N. View Indexing in Relational Databases//ACM Transactions on Database Systems. — 1982. — No. 17. — P. 258—290

71. Theodoratos D., Sellis T. Data Warehouse Schema and Instance Design. — In Proc. of the 17th Intl. Conf. on Conceptual Modeling. — 1998. — P.363—376

72. Theodoratos D., Sellis T. Dynamic Data Warehouse Design. — Technical Report, Knowledge and data Base Systems Laboratory, Electrical and Computer Engineering Dept., National Technical University of Athens. — 1998. — P. 1—25

73. Vassiliadis P., Skiadopoulos S. Modeling and optimisationissues for multidimensional databases. — In Proc. of CAiSE-2000. — 2000. — P. 482— 497

74. Wilson K.G. Generalized Wannier Functoins. — Cornell University,1987.

75. Wojtaszczyk P. A Mathematical Introduction to Wavelets. — Cambridge: Cambridge University Press, 1997

76. Yang J., Karlapalem K., Li Q. Algorithms for Materialized View Design in Data Warehousing Environment. — In Proc. of the 23rd Intl. Conf. on Very Large Data Bases. — 1997. — P.136—145