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

• Новосельский, Вениамин Борисович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Новосельский, Вениамин Борисович

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР И АНАЛИЗ МЕТОДОВ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ РАСПРЕДЕЛЕННЫХ СИСТЕМ И БАЗ ДАННЫХ.

1.1 Характеристики распределенных систем.

1.1.1 Прозрачность.

1.1.2 Открытость.

1.1.3 Гибкость.

1.1.4 Масштабируемость.

1.2 Концепции программных решений.

1.3 Распределенные базы данных.

1.3.1 Разновидности распределенных СУБД.

1.4 Проектирование базы данных.

1.4.1 Моделирование локальных представлений.

1.4.2 Объединение локальных моделей.

1.4.3 Средства автоматизированного проектирования.

1.5 Построение модели данных.

1.5.1 Иерархическая модель.

1.5.2 Сетевая модель.

1.5.3 Реляционная модель.

1.5.4 Модель «Сущность-связь».

1.5.5 Многомерная модель данных.

1.5.6 Объектно-ориентированная модель.

1.6 Объектные базы данных.

1.7 Проектирование распределенных БД.

1.7.1 Проектирование распределенных ООБД.

1.7.2 Терминология.

1.8 Фрагментация данных.

1.9 Размещение данных.

1.10 Репроекгирование и материализация.

1.11 Обзор и анализ существующих работ.

1.11.1 Фрагментаг(ия.

1.11.2 Размещение.

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

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

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

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

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

Целью работы является разработка методов проектирования распределенной базы данных, которые описывают способ разбиения централизованной БД на фрагменты и размещения полученных фрагментов в узлах заданной вычислительной сети (ВС). На основании полученных методов необходимо создать алгоритмы автоматизированной системы, результатами работы которой, помимо схем фрагментации и размещения БД, будут рекомендации по повышению эффективности обработки запросов к РБД.

Для достижения указанной цели определены следующие задачи исследования:

- рассмотрение и анализ характеристик распределенных систем обработки данных;

- описание и изучение основных задач, входящих в процесс проектирования РБД;

- анализ постановки и исследование зависимостей задач фрагментации БД, размещения фрагментов и формирования стратегий исполнения запросов;

- выбор и обоснование критерия эффективности РБД;

- разработка алгоритмов проектирования эффективной РБД, описывающих способы фрагментации БД, размещения фрагментов по узлам ВС и формирующих рекомендации по архитектуре РБД;

- разработка прикладных программ на основании предложенных алгоритмов.

Объект исследования - распределенные базы данных. Предметом исследования являются модели и алгоритмы автоматизированной системы, предназначенной для описания методики распределения БД.

Методологическая н теоретическая основа исследования. При выполнении работы использованы элементы теории множеств, теория графов, методы проектирования локальных и распределенных БД, генетические алгоритмы, теория массового обслуживания, теория вычислительных систем.

Научная новизна исследования заключается в следующем:

- Сформулирована задача проектирования РБД, учитывающая взаимозависимости схем фрагментации БД, размещения фрагментов и формирования стратегий исполнения запросов;

- Выбран и обоснован критерий эффективности РБД, учитывающий влияние степени загрузки ресурсов на время ответа на запрос и коэффициент готовности транзакций. Критерий позволяет проектировщику устанавливать желаемые приоритеты времени ответа на запрос и готовности транзакций;

- Проведено исследование и выявлены зависимости влияния репликации фрагментов БД и физических характеристик ВС на время ответа на запрос с учетом применения внутриоператорного параллелизма;

Предложен подход на основании вложенных генетических алгоритмов, позволяющий учесть взаимозависимость NP-полных задач, входящих в процесс проектирования;

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

Апробация результатов исследования. Основные положения диссертационной работы доложены и обсуждены на IV Межвузовской конференции молодых учёных (г. Санкт-Петербург, 2007 г.), XXXVII научной и учебно-методической конференция СПбГУ ИТМО (г. Санкт-Петербург, 2008 г.), V Межвузовской конференции молодых учёных (г. Санкт-Петербург, 2008 г.), XV Всероссийской научно-методической конференции «Телематика'2008» (г. Санкт-Петербург, 2008 г.).

Публикации. По теме диссертации опубликовано 6 статьей.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, библиографического списка использованной литературы из 65 наименований.

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

Заключение

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

1. Проанализированы этапы, входящие в процесс проектирования РБД;

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

3. Выбран и обоснован критерий эффективности РБД, позволяющий проектировщику устанавливать приоритеты времени ответа на запросы и коэффициента готовности транзакций;

4. Описана архитектура РБД, учитывающая возможности параллельного исполнения операторов;

5. Исследовано влияние репликации фрагментов БД п физических характеристик ВС на время ответа на запрос с учетом параллельного исполнения;

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

7. Разработанная экспсртно-исследовательская система, реализующая предложенный алгоритм, является прототипом САПР РБД. Использование разработанного прототипа САПР распределенной базы данных позволяет повысить эффективность построения распределенных интегрированных систем автоматизированного проектирования, используемых в приборостроении.

Список литературы диссертационного исследования кандидат технических наук Новосельский, Вениамин Борисович, 2008 год

1. Стеен М., Тенебаум Э. Распределенные системы. Принципы и парадигмы // СПб: Питер, 2003. 880 с.

2. Швецов В.И., Визгунов А.Н., Мееров И.Б. Базы данных // Нижний Новгород: Издательство Нижегородского госуниверситета, 2004. — 271 с.

3. Цегелик Г.Г. Системы распределенных баз данных // Львов: Свит, 1990. 166,1. с.

4. Дейт К.Д. Введение в системы баз данных: Пер. с англ. 6-е изд. // Диалектика, 1998.- 846 с.

5. Garcia-Molina Н., Lindsay В. Research directions for distributed databases // SIGMOD Rec. 1990. - Vol. 19, N4. - 98-103. - ISSN 0163-5808.

6. Роб П., Коронел К. Системы баз данных: проектирование, реализация и управление. 5-е издание. // СПб: БХВ-Петербург, 2004. 1040 с.

7. Багуи С. Объектно-ориентированные базы данных: достижения и проблемы // Открытые системы. 2004. - №3.

8. Харрингтон Д. Проектирование объектно-ориентированных баз данных // Москва: ДМК Пресс, 2001. 272 с.

9. Новосельский В.Б. Проблемы и задачи автоматизированного проектирования распределенных баз данных // Научно-технический вестник СПбГУ ИТМО. 2007. - №39. - с. 157-163. - ISSN 1819-222Х.

10. Cattell R. The Object Data Standart: ODMG 3.0 // San Francisco, USA: Morgan Kaufmann Publishers Inc., 2000. 280 p.

11. Eisenberg A., Melton J. SQL 1999, formely known as SQL 3 // ACM SIGMOD international conference on Management of data. 1999. - pp. 131-138.

12. Meghini C., Thanos C. The complexity of operations on a fragmented relation // ACM Transactions on Database Systems. 1991. - Vol. 16,1. N1.-pp. 56-87.

13. Baiao F., Mattoso M., Zaverucha G. A Distribution Design Methodology for Object DBMS // Distributed and Parallel Databases. 2004. - N16. -pp. 45-90.

14. Ceri S., Pelagatti G. Distributed databases principles and systems // McGraw-Hill, Inc., 1984. 393 p.

15. Navathe S., Ra M. Vertical partitioning for database design: a graphical algorithm // SIGMOD Rcc. 1989. - Vol. 18, N2. - pp. 440-450. - ISSN 0163-5808.

16. Бурков B.H., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными системами // М.: Спнтег, 2001. 124 с.

17. Materialization of Redesigned Distributed Relational Databases: Technical Report / Hong Kong University of Science & Technology; Karlapalem K., Navathe S.B. Hong Kong, 1994. - 44 p. - HKUST-CS94-14.

18. Stepwise Redesign of Distributed Relational Databases: Technical Report / Hong Kong University of Science & Technology; Kazerouni L., Karlapalem K. Hong Kong, 1997. - 28 p. - HKUST-CS97-12.

19. Karlapalem K., Navathe S.B., Ammar M. Optimal redesign policies to support dynamic processing of applications on a distributed relational database system // Information Systems. 1996. - Vol. 21, N4. - pp. 353-367. - ISSN 0306-4379.

20. Apers P.M.G. Data allocation in distributed database systems // ACM Transactions on Database Systems. 1988. - Vol. 13, N3. - pp. 263-304.

21. Бабанова Н.И. Разработка и оптимизация моделей и алгоритмов автоматизированного проектирования локальных и распределенных баз данных : Автореф. дис. . канд. техн. наук : 05.13.12 // Владикавказ: 2000. 23 с.

22. Baiao F., Mattoso М. A Mixed Fragmentation Algorithm for Distributed Object Oriented Databases // The Ninth International Conference on Computing Information. Winnipeg, Canada. 1998. - pp. 141-148.

23. Navathe S., Karlapalem K., Ra M. A Mixed Fragmentation Methodology for Initial Distributed Database Design // Journal of Computer and Software Engineering. 1995. - Vol. 3, N4.

24. Navathe S., Ceri S., Weiderhold G., et al. Vertical Partitioning Algorithms for Database Design // ACM Transactions on Database Systems. 1984. - Vol. 9, N4. - pp. 680-710.

25. Ma H., Schewe K.-D., Wang Q. A heuristic approach to cost-efficient derived horizontal fragmentation of complex value databases // Eighteenth conference on Australasian database. Ballarat, Australia. — 2007. pp. 103-111.

26. Horizontal Class Partitioning for Queries in Object-Oriented Databases: / Hong Kong University of Science & Technology: Bellatreche L., Karlapalem K., Basak G.K. Hong Kong, 1998. - 27 p. - HKUST-CS98-6.

27. Ahmad I., Karlapalem K., Kwok Y.K., et al. Evolutionary Algorithms for Allocating Data in Distributed Database Systems // Distributed and Parallel Databases.-2002.-Vol. ll,Nl.-pp. 5-32.

28. Hababeh Ismail O., Ramachandran M., Bo wring N. A high-performance computing method for data allocation in distributed database systems //

29. Journal of Supercomputing. 2007. - Vol. 39, N1. - pp. 3-18. - ISSN 0920-8542.

30. Graham J.M. Theoretical properties of two problems of distribution of interrelated data // 44th annual Southeast regional conference. Melbourne, Florida. 2006. - pp. 395-398.

31. Ozsu Т., Valduriez P. Principles of Distributed Database Systems: 2nd Edition // Englewood Cliff, NJ: Prentice-Hall, 1999. 666 p.

32. Ziane M., Zait M., Hong H.Q. Parallelism and query optimization // International Journal of Computer Science and Engineering. 1995. -Vol. 10, Nl.-pp. 50-56.

33. Михайлов М.Ю. Моделирование размещения данных при проектировании распределенных баз данных : автореферат дис. . кандидата экономических наук : 08.00.13 // Москва: 1991. 18 с.

34. Новосельский В.Б. Решение задачи распределения реляционной базы данных // Журнал научных публикаций аспирантов и докторантов. -2008. -N5.-с. 158-160.-ISSN 1991-3087.

35. March S.T., Rho S. Allocating Data and Operations to Nodes in Distributed Database Design // IEEE Transactions on Knowledge and Data Engineering. 1995. - Vol. 7, N2. - pp. 305-317. - ISSN 10414347.

36. Johansson J.M., March S.T., Naumann J.D. Modeling Network Latency and Parallel Processing in Distributed Database Design // Decision Sciences Journal. 2003. - Vol. 34, N4. - pp. 677-706.

37. Tamhankar A.M., Ram S. Database fragmentation and allocation: an integrated methodology and case study // IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans. 1998. - Vol. 28, N3,-pp. 288-305.

38. Shah A., Ghosal D. Trade-offs between response times and availability in a distributed database // 4th workshop on ACM SIGOPS European workshop. Bologna, Italy. 1990. - pp. 1-4.

39. Cook J.H., Groner L.H. Analytic response time model for distributed systems // APL 90: for the future. Copenhagen, Denmark. 1990. - pp. 81-101.

40. Kossmann D. The state of the art in distributed query processing // ACM Computing Surveys. 2000. - Vol. 32, N4. - pp. 422-469. - ISSN 03600300.

41. Новосельский В.Б., Павловская Т.А. Выбор и обоснование критерия эффективности при проектировании распределенных баз данных // Научно-технический вестник СПбГУ ИТМО. 2008. - принято в печать.

42. Evrendilek С., Dogac A., Nural S., et al. Multidatabase .Query Optimization // Distributed and Parallel Databases. 1997. - Vol. 5, N1. -pp. 77-114.

43. Brunie L., Kosch H. Control strategies for complex relational query processing in shared nothing systems // SIGMOD Rec. 1996. - Vol. 25, N3. - pp. 34-39. - ISSN 0163-5808.

44. Hong W. Exploiting Inter-Operation Parallelism in XPRS // ACM SIGMOD International Conference on Management of Data. USA. -1992.-pp. 19-28.

45. Lanzelotte R.S.G., Valduriez P., Zait M. Industrial-Strength Parallel Query Optimization: Issues and Lessons // Information Systems. 1994. -Vol. 19, N4. - pp. 311-330. - ISSN 0306-4379.

46. Johansson J.M., March S.T., Naumann J.D. The effects of parallel processing on update response time in distributed database design // Twenty first international conference on Information systems. Brisbane, Queensland, Australia. -2000. pp. 187-196.

47. Bernstein P.A., Chiu D.-M.W. Using Semi-Joins to Solve Relational Queries // Journal of the ACM. 1981. - Vol. 28, N1. - pp. 25-40. -ISSN 0004-5411.

48. Ives Z.G., Florescu D., Friedman M., et al. An adaptive query execution system for data integration // ACM SIGMOD international conference on Management of data. Philadelphia, Pennsylvania. United States. 1999. -pp. 299-310.

49. Hammer M., Niamir B. A heuristic approach to attribute partitioning // ACM SIGMOD international conference on Management of data. Boston, Massachusetts. 1979. - pp. 93-101.

50. Bernstein P.A., Goodman N., Wong E., et al. Query processing in a system for distributed databases (SDD-1) // ACM Transactions on Database Systems. 1981. - Vol. 6, N4. - pp. 602-625. - ISSN 03625915.

51. Джонс Д.К. Методы проектирования: пер. с англ. 2-е изд., доп. // М.: 1986.-326 с.

52. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. 1999. -№1. - с. 2-7. - ISSN 1994-0408.

53. Bennett К., Ferris М.С., Ioannidis Y.E. A Genetic Algorithm for Database Query Optimization // Fourth International Conference on Genetic Algorithms. San Mateo, CA. 1991. - pp. 400-407.

54. Corcoran A.L., Hale J. A genetic algorithm for fragment allocation in a distributed database system // ACM symposium on Applied computing. Phoenix, Arizona, United States. 1994 - pp. 247-250.

55. Rho S., March S.T. A nested genetic algorithm for distributed database design // Twenty-Seventh Hawaii International Conference on System Sciences, Information Systems: Decision Support and Knowledge-Based Systems. Wailea, HI, USA. 1994. - pp. 33-42.

56. Wang J.-C., Horng J.-Т., Hsu Y.-M., et al. A genetic algorithm for set query optimization in distributed database systems // IEEE International Conference on Systems, Man, and Cybernetics. 1996. - pp. 1977-1982.

57. Rho S., March S.T. Optimizing distributed join queries: A genetic algorithm approach // Annals of Operations Research. 1997. - Vol. 71, NO. - pp. 199-228.

58. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence // MIT Press, 1992. 228 p.

59. Whitley D. An Overview of Evolutionary Algorithms: Practical Issues and Common Pitfalls // Journal of Information and Software Technology. -2001.-Vol. 43, N4.-pp. 817-831.

60. Новосельский В.Б. Применение генетических алгоритмов при проектировании распределенных баз данных // Научно-технический вестник СПбГУ ИТМО. 2008. - Принято в печать.

61. Новосельский В.Б. Метод проектирования процесса распределения реляционной базы данных // Изв. вузов. Приборостроение. 2008. -Т. 51, №7.-с. 39-42.

62. Ceri S., Negri М., Pelagatti G. Horizontal data partitioning in database design // ACM SIGMOD international conference on Management of data. Orlando, Florida. 1982. - pp. 128-136.

63. Ma H., Schewe K.-D., Wang Q. A heuristic approach to cost-efficient fragmentation and allocation of complex value databases // 17th Australasian Database Conference. Hobart, Australia. 2006. - pp. 183192.

64. Transaction Processing Performance Council (TPC). TPC Benchmark™ -Standard Specification, Revision 5.9.// 2007. 130 p.

65. Новосельский В.Б. Метод автоматизации проектирования распределенной реляционной базы данных // Программные продукты и системы. 2008. - №3. - с. 45-48.