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

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИТИЧЕСКИЙ ОБЗОР СОВРЕМЕННОГО СОСТОЯНИЯ СРЕДСТВ СУБД И МАШИН БАЗ ДАННЫХ (МБД).

1.1. Общие положения: Исторический очерк.

1.2. Классификация МБД по структурно-функциональным особенностям

1.3. Неоднородные многопроцессорные МБД.

1.4. Виды обработки и типы буферизации.

1.5. Работа с распределенными БД.

1.5.1. Варианты централизованных и децентрализованных СУБД.

1.5.2. Проблемы, возникающие при работе с распределенными БД.

1.5.3. Применение в БД одновременной обработки и обновления.

1.5.4. Особенности архитектуры однородных распределенных БД.

1.5.5. Особенности архитектуры неоднородных распределенных БД.

1.5.6. Оценка производительности некоторых МБД.

1.6. Выводы.

ГЛАВА 2. РАЗРАБОТКА ФОРМАЛЬНЫХ МОДЕЛЕЙ МАШИН БАЗ ДАННЫХ.

2.1. Интерпретация МБД как элемента современной информационной технологии.

2.3. Три уровня определения данных и манипулирования данными в МБД

2.4. Концептуальная модель данных МБД.

2.5. Формы представления данных.

2.6. Разработка модели БД с использованием полного графа состояний («все со всеми»).

2.7. Один из вариантов применения метода «все со всеми» при условии экономии дискового пространства.

2.8. Выводы.

ГЛАВА 3. РАЗРАБОТКА УСТРОЙСТВА КОЛЛЕКТИВНОГО ДОСТУПА К БАЗЕ ДАННЫХ С ПРИМЕНЕНИЕМ МЕТОДА «ВСЕ СО ВСЕМИ».

3.1. Обобщенная структурная модель устройства коллективного доступа к базе данных на основе метода «все со всеми».

3.2. Описание работы блока Буфер 1 (Б1).

3.3. Описание работы блока УРПИ.

3.4. Описание блока УПЕК.

3.5. Описание работы блока Буфер 2 (Б2).

3.6. Описание работы блока УБПИ.

3.7. Описание работы блока УПРК.

3.8. Описание работы динамического режима (ДР).

3.9. Анализ некоторых существующих систем коллективного доступа

3.10. Выводы.

ГЛАВА 4. СРАВНИТЕЛЬНЫЙ АНАЛИЗ РАБОТЫ УСТРОЙСТВА КОЛЛЕКТИВНОГО ДОСТУПА.

4.1. Сопоставление основных способов устранения тупиковых ситуаций

4.2. Сравнительные характеристики существующих проектов МБД и УКД при работе с уменьшением и ликвидацией тупиковых ситуаций

4.2.1. Зависимость отношения времен работы локальной сети традиционных систем и УКД от числа рабочих мест W.

4.2.2. Зависимость отношения времен работы локальной сети традиционных систем и УКД от длины кортежей S.

4.2.3. Зависимость отношения времен работы локальной сети традиционных систем и УКД от числа классов команд к.

4.3. ВЫВОДЫ.

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

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

Также существенно возрастают требования к механизмам организации баз данных (БД) и доступа к данным. Существующих традиционных семантических средств недостаточно для эффективной обработки разнородной информации, поэтому необходим переход к использованию средств представления, хранения и обработки данных в распределенных БД с коллективным доступом. При этом требуется рациональная организация совместной обработки данных группой компьютеров различных типов на основе интегрированных баз данных. Выполнение приведенных выше требований достигается путем создания систем организации манипулирования данными и управления БД в форме машин баз данных (МБД). Проблемам создания МБД и их аппаратной реализации посвящены работы М. Сенко, Я. Палмера, Г. Найсена, Э. Озкарахана, JI. Кали-ниченко, В. Рывкина и других исследователей как у нас в стране, так и за рубежом.

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

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

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

Основная часть диссертационной работы выполнялась в рамках госбюджетной НИР по распоряжению Госкомвуза № 10-36-41, ИН/10-20-03 от 16.03.92 г. с пролонгацией до 2001 г. при непосредственном участии автора.

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

Основные задачи диссертационного исследования:

1. Разработать способы формального представления МБД.

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

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

4. Разработать технические решения устройств на уровне функциональных схем.

5. Исследовать скоростные характеристики алгоритмов и устройств.

Методы исследования базируются на теории алгоритмов, математической логики, а также теории автоматов и проектирования ЭЦВМ.

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

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

2. Созданы способ и алгоритмы его реализации организации манипулирования данными в условиях коллективного доступа к БД, снижающие затраты времени до 7-8 раз.

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

4. На основании исследования скоростных характеристик алгоритмов и устройств установлено, что скоростные преимущества разработанной схемы организации манипулирования данными достигают 7,9 раза по отношению к существующим сетевым технологиям коллективного доступа к БД.

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

Реализация результатов работы внедрена в отделе АСУ администрации г.Курска и в учебном процессе Курского государственного технического университета.

Апробация работы. Результаты работы докладывались и обсуждались на Международной технической конференции «Медико-экологические информационные технологии» (Курск, 1998), I Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (Нижний Новгород, 1999), II Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (Нижний Новгород, 2000).

На защиту выносятся:

- модифицированные способы формального представления МБД;

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

- способ организации и алгоритм коллективного доступа к сетевой БД;

- способ функционально-структурной организации устройств,

- технические решения устройств, обеспечивающих коллективный доступ в распределенных базах данных;

- результаты исследования скоростных характеристик алгоритмов и устройств.

Публикации по работе. По материалам диссертации опубликовано 8 печатных работ, из них 4 - тезисы докладов.

Структура работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на /2 Я страницах (основного текста), содержит ZS рисунка, Sтаблиц, списка литературы из на

4.3. Выводы

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

2. Установлено, что по критерию зависимости от числа рабочих станций получены следующие результаты: когда число рабочих станций принимает значения 2, 3, 4, 5, то скоростные преимущества УКД составляют 2.63, 4.2, 5.2, 7.9 раз соответственно при равноценных потоках данных (см. раздел 4.2.1).

3. Определено, что по критерию зависимости времени реализации от числа команд в кортежах (длин кортежей) получены следующие результаты: при работе 4 рабочих станций, когда число команд в кортежах принимает значения 4, 6, 8, скоростные преимущества УКД составляют 5.2, 5.6, 5.08 раз соответственно при равноценных потоках данных (см. раздел 4.2.2).

4. По критерию зависимости времени реализации от числа классов команд получены следующие оценки: когда число рабочих станций равно 2, число классов команд принимает значения 2 и 3, скоростные преимущества УКД составляют 2.376 и 2.377 раз соответственно; когда число рабочих станций равно 3, число классов команд принимает значения 2 и 3, скоростные преимущества УКД составляют 3.85 и 3.68 раз соответственно; когда число рабочих станций равно 3, число классов команд принимает значения 2 и 3, скоростные преимущества УКД составляют 4.6 и 7.07 раз соответственно; при этом во всех случаях число команд в кортежах равно 4 и исследуются равноценные потоки данных (см. раздел 4.2.3).

120

ЗАКЛЮЧЕНИЕ

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

2. Созданы способ и алгоритмы его реализации организации манипулирования данными в условиях коллективного доступа к БД, снижающие затраты времени до 7-8 раз.

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

4. На основании исследования скоростных характеристик алгоритмов и устройств установлено, что скоростные преимущества разработанной схемы организации манипулирования данными достигают 7,9 раза по отношению к существующим сетевым технологиям коллективного доступа к БД.

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

121

1. Калиниченко Л.А., Рыбкин В.М. Машины баз данных и знаний. М.: Наука. Гл. ред. физ.-мат. лит., 1990.

2. Озкарахан Э. Машины баз данных и управление базами данных: Пер. с англ. М.: Мир, 1989.

3. Day К. Micro-based DBMS manages and relational database // Electronic Design. June 1982. - No. 3.

4. Boral H., De Witt D., Wilkinson K. Performance evolution of four associative disk designs // Inform. Systems. London, 1982. - Vol. 7, No.l.

5. Feng T.A. Very large data base computer // IEEE Computer Soc. Workshop on Computer Architecture for Analysis and Image Database Management. Virginia, USA, 1981.

6. Hawthorn P. В., De Witt D.J. Performance analysis of alternative database machine architectures // IEEE Trans, of Software Eng.— Jan. 1982.— Vol. SE-8, No.l.

7. Maryanski F. Backend database systems // Computing Surveys.— March 1980,—Vol. 12, No. 1.

8. Su S., Chang H., Eischer P., Lowenthal E. Database machine and some issues on database management systems standart // AFIPS, NCC, USA, 1980.

9. Boral H, Redfield S. Database machine Morphology // Proc. of the 11-th Int. Conf. on VLDB.— Stockholm, Aug. 1985.

10. Калиниченко Л. А., Курылев В. А., РЫБКИН В. М. Повышение производительности реляционных СБД в машинах баз данных // Измерения, контроль, автоматизация, 1987.— № 2.

11. Ozkarachan Е. Database machines and database management // USA, Prentice Hall, 1986.

12. Hsiao D. K., Madnick S. Database machine architecture on the Context of information technology Evolution //Proc. of the 3-rd Intern. Conf. on VLDB.— Japan, Tokyo, 1977.

13. Madnick S. E. INFOPLEX — hierarchical ecomposition of a large information management system using microprocessor complex //AFIPS, NCC.— 1975.

14. Kamibayashi N. A Database machine based on the data distribution approach //AFIPS, NCC.— USA, Virginia, 1984.

15. Kamibayashi N., Seo K. SPIRIT-3: an advanced relational data base machine introducing a novel data-staging architecture with tuple stream filters to process relational algebra// AFIPS, NCC.—1982.

16. Kamibayashi N., Kato H., KiokiP., Yozawa H. et. al. SPIRIT: A new relational data base computer employing functional-distributed multi-microprocessor configuration //Proc. of the 1-st Data Computer System Conference.— 1979.

17. Seo K., Mikamatsu A., Aiso H., Kamibayashi N. A. Look-ahead data staging architecture for relational data base machine // Proc. of 8-th Ann. Symp. Com-put,—Architecture.—May 1981.

18. Ullman, J. D. Principles of Database Systems, 2nd. ed. Rockville, Md: Computer Science Press, 1982. Имеется перевод: Ульман Дж. Основы систем баз данных.—М.: Финансы и статистика, 1983, 334 е.

19. Obermack, R. Global Deadlock Detection Algorithm.—IBM Research Report RJ2845 1980 (June).

20. Ellis, C. A. A Robust Algorithm for Updating Duplicate Databases.— Proc. of 2nd Berkeley Conf. on Distributed Data Management and Computer Networks, 1977.

21. Stonebraker, M., and Wong, E. Access Control in a Relational Database Management System by Query Modification.—Proc. of ACM National Conf., 1974.

22. Bernstein, P. A., and Goodman, N. Fundamental Algorithms for Concurrency Control in Distributed Database Systems. — ACM Computing Surveys, 1981, Vol. 13, No. 2.

23. Hsiao, D. K., and Ozsu, T. A Survey of Concurrency Control Mechanisms for Centralized and Distributed Databases.—Technical Report, OSU— CISRC— TR—81—1, Dept. of Computer Science, Ohio State University, Columbus, Oh. 1981.

24. Garcia-Molina, H. Centralized Control Update Algorithms for Fully, Redundant Distributed Databases.—Proc. of First Intl. Conf. on Distributed Computing Systems, 1979.

25. Rosenkrantz, D. J., Steams, R. E., Lewis, P. M., II. System Level Concurrency Control for Distributed Database Systems.—ACM Transactions on Database Systems, 1978, Vol. 3, No. 2.

26. Cardenas, A., and Pirahesh, M. H. Database Communication in a Heterogeneous Data Base Management System Network. — Information Systems, 1980, Vol. 5.

27. Smith, J. M., et al. Multibase — Integrating Heterogeneous Distributed Database Systems. —Proc. of AFIPS Conf., 1981, Vol.50.

28. Ozkarahan, E. A., Schuster, S. A., and Sevcik, К. C. Performance Evaluation of a Relational Associative Processor.—ACM Transactions on Database Systems, 1977, Vol. 2, No. 2.

29. Hawthorn, P. В., and Dewitt, D. J. Performance Analysis of Alternative Database Machine Architectures.—IEEE Transactions on Software Engineering, 1982, Vol. SE-8, No. 1.

30. Dewitt, D. J., and Hawthorn, P. B. A Performance Evaluation of Database Machine Architectures.—Proc. of Intl. Conf. on Very Large Data Bases, 1981.

31. ANSI/ХЗ/ SPARC DBMS Framework. Report of the study group on database management systems //Inform. Systems, 1978.

32. Hsiao D. K. Super database computers: hardware and software solution for efficient processing of very large database // Information Processing -86.— North Holland, 1986.

33. Калиниченко JI. А. Методы и средства интеграции неоднородных баз данных.—М.: Наука, 1983.—423 с.

34. Мальцев А. И. Алгебраические системы.—М.: Наука, 1970.—392 с.

35. Клини С. К. Математическая логика.—-М.: Мир, 1973.—482 с.

36. Мендельсон Э. Введение в математическую логику.—М.: Наука, 1971.

37. Черч А. Введение в математическую логику.— М.: ИИЛ, 1960.

38. Concepts and terminology for the conceptual scheme and the information base.—New York: ISO, 1982.— ISO (TC 97) WG3.

39. Плоткин Б. И. Универсальная алгебра, алгебраическая логика и базы данных.— М.: Наука. Гл. ред. физ.-мат. лит., 1991.— 448 с.— ISBN 5-02014635-8.

40. Г. Дейтел. Введение в операционные системы. М.: Мир, 1987.

41. Довгаль В.М., Тютюнов А.Д. Об одном подходе к исключению клинчей при групповом доступе к базам данных. М.: 2000. 9 с. Деп. в ВИНИТИ 24.03.00, № 763-в00.

42. Шкурба В.В. Задача трех станков.— М.: Наука. Гл. ред. физ.-мат. лит., 1976.

43. Ozkarahan E. A., and Sevcik, К. C. Analysis of Architectural Features for Enhancing the Performance of a Database Machine.—ACM Transactions on Database Systems, 1977, Vol. 2, No. 2.

44. Довгаль В.М., Тютюнов А.Д., Тютюнов Д.Н., Елагин В.В. Метод исключения клинчей при групповом доступе к базам данных. М.: 2000. 8 с. Деп. в ВИНИТИ 31.10.00, №2761 -вОО.

45. Игнатович Н. // СУБД. 1997. №2. С.5-17.

46. Compaq NonStop SQL/MP. http://www.tandem.com/prod des/nssqlpd/nssqlpd.htm

47. Лисянский К., Слободяников Д. // СУБД. 1997. №5-6. С.25-46.

48. Бернштейн Ф. и др. // Открытые системы. 1999. №1. С.61-68.

49. Кодд Е.Ф. // СУБД. 1995. №1. С.145-169.

50. Чамберлин Д.Д. и др. // СУБД. 1996. №1. С. 144-159.

51. Девитт Д., Грэй Д. // СУБД. 1995. №2. С.8-31.

52. Stonebraker М. // Database Engineering Bulletin. March 1986. V.9. №1. P.4-9.126

53. Bhide A. An Analysis of Three Transaction Processing Architectures // Proceedings of 14-th Internat. Conf. on Very Large Data Bases (VLDB'88), 29 August 1 September 1988. Los Angeles, California, USA, 1988. P.339-350.

54. Sokolinsky L.B., Axenov O., Gutova S. Omega: The Highly Parallel Database System Project // Proceedings of the First East-European Symposium on Advances in Database and Information Systems (ADBIS'97), St.-Petersburg. September 2-5,1997.V.2. P.88-90.

55. Левин B.K. Отечественные суперкомпьютеры семейства MBC. http://parallel.ru/mvs/levin.html

56. Д. Девитт (DAVID DEWITT) профессор факультета computer sciences Висконсинского университета, dewitt@cs.wisc.edu

57. Д. Грэй (JIM GRAY) сотрудник Digital Equipment Corporation, gray@sfbay.enet.dec.com

58. JI.Б. Соколинский, М.Л. Цымблер (Челябинск, Челябинский государственный университет) sokolinsky@acm.org, mzym@csu.ac.ru

59. КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ1. На правах рукописи

60. ТЮТЮНОВ АЛЕКСЕЙ ДМИТРИЕВИЧ

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

62. Специальность 05Л3.05 "Элементы и устройства вычислительной техники и систем управления"