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

ВВЕДЕНИЕ.

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

1.1 Общая характеристика документно -ориентированных СУБД.

1.2 Основные архитектуры СУБД.

1.3 Анализ известных моделей построения баз данных.

1.4 Постановка проблемы оптимизации 29 механизма поиска ДО СУБД.

ГЛАВА 2. ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ

ОПТИМИЗАЦИИ ПРОЦЕССА ПОИСКА ДО

СУБД.

2.1 Описание структуры БД.

2.1.1 Схема БД.

2.1.2 Механизм отыскания дерева соединений.

2.1.3 Алгоритм накопления данных.

2.1.4 Структура хранимых документов.

2.2 Оптимизация механизма поиска информации.

2.2.1 Генерация разбиений множеств.

2.2.2 Нерекуррентная схема алгоритма генерации всех разбиений.

2.2.3 Построение алгоритма оптимизации по списку рабочих индексов.

ГЛАВА 3.РАЗРАБОТКА МЕХАНИЗМА

ВЗАИМОДЕЙСТВИЯ ОТДЕЛЬНЫХ

ЭЛЕМЕНТОВ СИСТЕМЫ.

3.1 Общие требования к системе.

3.2 Логическая структура системы.

3. 3 Структура представления данных.

3.4 Индексные структуры.

3.4.1 Основные типы структур, используе-мых для индексирования. Древовидные структуры.

3.4.2 В+ деревья.

3.4.3 Ранжирование индексов.

ГЛАВА 4. ПОСТРОЕНИЕ ЯДРА ДО СУБД. ОЦЕНКА

ПРОИЗВОДИТЕЛЬНОСТИ СИСТЕМЫ.

4.1 Практическая реализация.

4.1.1 Определение языка программирования для реализации системы.

4.1.2 Блок-схема ядра системы.

4.1.3 Модуль поддержки файлов страничной организации.

4.1.4 Модуль кэширования файла страничной организации.

4.1.5 Модуль поддержки индексов.

4.1.6 Модуль поддержки документов.

4.1.7 Интерфейсный модуль.

4.1.8 Компоненты работы с БД для Delphi., юб 4.2 Сравнительные характеристики.

Одной из важнейших задач, практически любой, компьютерной системы является хранение и обработка данных. Для ее решения были предприняты усилия, которые привели к появлению' в конце б0-х - начале 7 0-х годов специализированного программного обеспечения - систем управления базами данных (СУБД database management systems). Опыт применения ЭВМ для построения прикладных систем обработки данных показывает, что наиболее эффективным инструментом здесь являются не универсальные алгоритмические языки высокого уровня, а специализированные языки для создания систем управления данными. Такие средства обычно включаются в состав СУБД, но они могут существовать и отдельно. СУБД дают возможность пользователям осуществлять непосредственное управление данными, а программистам быстро разрабатывать более совершенные программные средства их обработки .

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

В этой связи проблема построения алгоритмических средств недорогой ДО СУБД, обладающей малым временем поиска и эффективно работающей на обычных ПК, представляется весьма актуальной.

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

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

• анализ современного состояния проблемы;

• разработка и математическое обоснование метода оптимизации механизма поиска ДО СУБД на основе генерирования разбиений множеств;

• разработка алгоритма построения индексных структур с использованием общих принципов реализации ДО СУБД;

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

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

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

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

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

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

1.Предложено решение для работы с любым набором данных через интеллектуальный интерфейс ДО СУБД, включая конвертер для преобразования вводимых данных.

2.Разработано универсальное ядро СУБД, обладающее переносимостью на различные операционные системы (Windows- и UNIX- совместимые).

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

4.Разработано программное обеспечение, выполненное в виде скрипта для динамического доступа к базе данных в глобальной сети Интернет.

5. Результаты диссертации использованы в учебном процессе в Вологодском государственном техническом университете в курсе «Основы проектирования баз данных и разработка приложений» Результаты диссертационной работы докладывались и получили положительную оценку на:

• международном форуме по проблемам науки, техники и образования (Москва, Академия наук о земле, 25-8 ноября 1997);

• первой международной конференции «Повышение эффективности теплообменных процессов и систем» в секции «Информационные системы и технологии» (Вологда .ЭоГТУ, 24-27 июня 1998) ;

• второй международной научно-технической конференции «Информационные технологии в производственных, социальных и экономических процессах» (Череповец ЧГУ, 24-27 мая 1999);

• межвузовской конференции «Управляющие вычислительные системы. Новые технологии» (Вологда ВоГТУ, март 2 000);

• второй международной конференции «Повышение эффективности теплообменных процессов и систем» в сек- ции «Информационные системы и технологии» (Вологда ВоГТУ, 19-22 апреля 2000);

• science readings WHITE NIGHT-2000: Abstract of International Ecological Symposium Perspective Information tecnology and risk namagment problem on the Millenium threshold (Saint-Petersburg July, 22-27, 2000) .

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

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

Выводы ло четвертой главе.

1.Рассмотрены вопросы практической реализации ДО СУБД. Показана целесообразность использования в качестве языка программирования ядра системы компилятора С++, в качестве средства построения новых приложений - системы визуального проектирования Delphi.

2.Дано описание блок-схемы системы, выполненной по модульному принципу. Определен состав объектов и механизм их взаимодействия. Приведено описание реализации каждого модуля ДО СУБД.

3. Приведены результаты тестовых испытаний реализованной системы по сравнению ■ с СУБД подобного класса. Показано, что разработанная ДО СУБД обладает высокими скоростными характеристиками, в сравнении с выбранными системами. Наибольшая разница з скорости достигается при достаточно сложных запросах.

ЗАКЛЮЧЕНИЕ

В результате выполненной работы были получены следующие результаты:

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

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

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

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

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

6.Разработано универсальное ядро СУБД, обладающее переносимостью на различные операционные системы

Windows- и UNIX- совместимые).

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

8. Созданы программные компоненты для разработки новых приложений под систему программирования Delphi.

9.Реализована программа - скрипт для динамического выхода в глобальную сеть Интернет.

10. С помощью разработанной системы созданы и внедрены двадцать девять готовых приложений.

11. Разработанная система зарегистрирована в Российском агентстве по патентам и товарным знакам. Свидетельство № 2000610851 от б сентября 2000 г.

С помощью разработанной ДО СУБД НИМБ, версии 3.0 внедрены и успешно эксплуатируются следующие программные комплексы:

• Проект «Международная информационная ярмарка товаропроизводителей» в глобальной сети Интернет для Федерального компьютерного центра фондовых, товарных и информационных технологий Министерства имущественных отношений РФ;

• «Оперативный учет недвижимости» - система, используемая в МУП «Гортехинвентаризация» г. Вологды;

• «Аренда» - программное обеспечение для учета арендуемых зданий и помещений администрации г. Вологды;

Телефонный справочник «Наши абоненты 2000» -электронный справочник телефонов предприятий и организаций г. Вологды. Разработан для ОАО «Электросвязь» Вологодской области;

Статьи» - программный комплекс, созданный для хранения и обработки газетных и журнальных статей как в локальном варианте, так и в глобальной сети Интернет. Разработан для газеты «МК в Вологде»;

БухПроф» - программа автоматизации бухгалтерского учета, эксплуатирующаяся более двух лет на 4 8 предприятиях и организациях; «ИПС Закон» - библиотека законодательных актов Российской Федерации;

Вологодская информационная ярмарка» - программное обеспечение для поддержки баз данных телефонной справочной службы «0 65» г. Вологды.

1.Авен О.Н., Гурин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. - М.¡Наука, 1982. - 464 с.

2. Авен О.И., Коган Я. А. Управление вычислительным процессом в ЭВМ: (Алгоритмы и модели) . М: Энергия, 1978. - 240 с.

3. Альянах И.Н. Моделирование вычислительных систем. JI.: Машиностроение, 1988. - 233 с.

4. Архингельский Б.В., Никитин А. И. Системы оптимизации программ. Киев: Техника, 1983. - 167 с.

5. Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980.19 2 с., ил.

6. Барфилд Э., Уолтере Б. Программирование «клиент-сервер» в локальных вычислительных сетях / Пер. с англ. М. : Информационно-издательский дом «Фи-линъ», 1997. - 424 с.

7. Батищев Д. И. Методы оптимального проектирования: Учебн. Пособие для вузов. М.: Радио и связь, 1984. - 248 е., ил.

8. Башарин Г.П., Бочаров П.П., Коган Я. А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М. ; Наука, 1989. - 336 с,

9. Бернстайн Ф. Middleware: модель сервисов распределенной системы // Системы Управления Базами Данных, № 2, 1997. С. 41-46

10. Ю.Богуславский Л.Б., Дрожжинов В.И. Основы построения вычислительных сетей для автоматизированных систем. М.: Энергиоатомиздат, 1990. - 256 с.

11. Богуславский Л.Б., Ляхов А. И. Оценка производительности распределенных информационно-вычислительных систем архитектуры «клиент-сервер» // Автоматика и телемеханика. М.: 1995. - № 9,с. 160-175

12. Брой М. Информатика. Структуры систем и системное программирование: В 4-х ч. Ч.2.' / Пер. с нем. -М.: Диалог-МИФИ, 1996. 244 с.

13. Брюхов Д.О., Задорожный В.И., Калиниченко Л. А., Курошев М.Ю., Шумилов С.С. Интероперабельные информационные системы: архитектуры и технологии // Системы Управления Базами Данных, № 4, 1995. -С. 96-113

14. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С+ + , 2-е изд. / Пер с англ. М. : Издательство Бином, СПб: Невскийдиалект, 1998. 560 е., ил.

15. Васкевич Д. Стратегии клиент-сервер. Киев:

16. Диалектика, 1996. 384 е., ил.

17. Воеводин В. В. Математические модели и методы в параллельных процессах. М.: Наука, 1986.296 с.

18. Вон К. Технология объектно-ориентированных баз данных // Системы Управления Базами Данных, № 4, 1994, С.30-42

19. Дейт К. Введение в системы баз данных. М. : Наука, 1980. - 463 с.

20. Дейтел Г. Введение в операционные системы: В 2-х т. Т.1. Пер. с англ. ~ М.: Мир, 1987. 359 с.

21. Дейтел F. Введение в операционные системы: В 2-х т. Т.2. Пер. с англ. М.: Мир, 1987. - 398 с.

22. Жоголев Е.А. Объектная организация систем гиперпрограммирования // Программирование, № 5, 1997. С. 24-32

23. Зильберштац А., Здоник. Э. Стратегические направления в системах баз данных // Системы Управления Базами Данных, № 4, 1997. С.4-23

24. Ирэ П. Объектно-ориентированное программирование с использованием С++: Пер. с англ. Киев:НИПФ ДиаСофт Лтд., 1995. - 480 с.

25. Искусственный интеллект: Применение в интегрированных производственных системах / Под ред. Э. Кьюсиака; Пер. с англ. А.П. Фомина; Под. ред. А.И. Дащенко, Е.В. Левнера. М.: Машиностроение, 1991. - 54 4 с., ил.

26. Исследование операций: В 2-ч т. Пер. с англ. / Под ред. Дж. Моудера, С. Элмаграби. Т.1. М. : Мир, 1981. - 712 е., ил.

27. Калиниченко Л.А. Методы и средства интеграции неоднородных баз данных. М.: Наука, 1983.424 с.

28. Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука, 1988, - 334 е., ил.

29. Керниган Б. Ритчи Д. Язык программирования Си: Пер. с англ. / Под ред. И с предисл. B.C. Штаркмана. 2-е иэд. перераб. И доп. - М Финансы и статистика, 1992. - 272 е., ил.

30. Кинг A. Windows 95 изнутри / Пер. с англ. = СПб: Питер, 1995. 512 е., ил.

31. Коллинз Г, Блэй Дж. Структурные методы разработки систем: от стратегического планирования до тестирования. Пер. с англ. / Под ред. И с предисл.

32. В. М. Савинкова. м.: Финансы и статистика, 1986.- 2 64 с. ил.

33. Компьютер и задачи выбора. Автор предисл. Ю.И.

34. Лентин И.Н Документно-ориентированные СУБД. Новое направление развития // Сборник научных трудов Т.1. Вологда: ВоГТУ, 1998. - С.75

35. Лентин И.Н. Проблемы «больших» и «малых» СУБД // Повышение эффективности теплообменных процессов и систем: Тезисы международной научно-технической конференции. Вологда: ВоГТУ, 1998. - С.248

36. Лентин И.Н., Пасынков К. В. СУБД НИМБ система, ориентированная на документы // Труды международного форума по проблемам -науки, техники и образования Т1 4.1. - М. : Академия наук о земле, 1997. - С.70

37. Липаев В.В. Распределение ресурсов в вычислительных системах. М.: Статистика, 1979. - 87 с.

38. Липский В. Комбинаторика для программистов: Пер. с польск. М.: Мир, 1988. - 213 е., ил.

39. Мамиконов А. Г. Оптимизация структур данных в АСУ М.: Наука, 1988. - 254 е., ил.

40. Мейер Д. Теория реляционных баз данных. М. :1. Мир,1987.- 608 с.

41. Мутушев Д.М. Реализация расширения объектной модели ОБМО в среде реляционных СУБД // Программирование, № 3, 1998. С.46-58

42. Назаров С.В. Операционные системы специализированных вычислительных комплексов: Теория построения системного проектирования. М. : Машиностроение, 1989. - 400 е., ил.

43. Орлик С. Многоуровневые модели в архитектуре клиент-сервер // Системы Управления Базами Данных, № 1, 1997. С.74-77

44. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ. М.: Мир, 1985. - 512 е., ил.

45. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: теория и практика. М. : Мир, 1 980. -47 8 с., ил.

46. Рубинштейн М.И. Оптимальная группировка взаимосвязанных объектов. М.: Наука, 1989. - 168 с.

47. Системное программирование и вопросы оптимизации: Сб. тр. фак. ВМИК МГУ. М.: МГУ, 1987. - 211 с.

48. Солдатенко Г.В. Последовательный метод решения экстремальных комбинаторных задач. Новосибирск: Наука, 1991. - 143 с.

49. Спесивцев A.B. Жадные алгоритмы распределения ресурсов. Списки и ограниченный перебор. М. : МП «Малин», 1993. - 288 с.

50. Страуструп Б. Язык программирования Си++: Пер. с англ. М.: Радио и связь, 1991. - 352 е., ил.

51. Суржко C.B., Горбунов В. А. Реляционные базы данных и СУБД ORACLE. Вологда: ВОГТУ, 1999.80 с.

52. Тараканов В.Е. Комбинаторные задачи и (0,1) матрицы. М.: Наука, 1985. - 288 е., ил.

53. Ульман Д. Основы систем баз данных. М. : Финансыи статистика, 1983. 335 с.

54. Феррари Д. Оценка производительности вычислительных систем. М.: Мир, 1981. - 576 с.

55. Хантер Р. Проектирование и конструирование компиляторов / Пер. с англ.; Предисл. В.М. Савинкова. 232 е., ил.

56. Шаффер Д., Эшельман Л. Комбинаторная оптимизация с использованием генетических алгоритмов: важность отличия понятий генотипа от фенотипа / Пер. с англ. // Обозрение прикладной и промышленной математики, Т.З. Вып. 5, 1996 352 е., ил.

57. Шень А. Программирование: теоремы и задачи. М. : МЦНМО, 1995. - 263 с.

58. Шилдт Г. Теория и практика С++: пер. с англ. -СПб: BHV Санкт-Петербург, 1996. - 416 е., ил.

59. Эллис М., Страуструп Б. Справочное руководство по языку программирования Си++ с комментариями: Пер. с англ. М.: Мир, 1992. - 445 е., ил.

60. Application Server, White paper, Imprise corp. Aug/ 1998

61. Common Facilities Architecture // Object Management Group, Revision 4.0., 1995.- 582 c.

62. Date C.J. An Introduction to Database Systems. V.l. 4th ed.- Reading, Mass.: Addison-Wesley.1984.- 639 c.

63. Delphi 5 developers guide, Imprise corp. 1999.456 c.

64. Holland J. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. Michigan Press, 1975.- 143 c.

65. IEEE Database Eng.- 1982.- 5, N 3: Special Issue on Query Optimization.- C. 32-34

66. Jarke M. , Koch J. Query Optimization in Database Systems // ACM Comput. Surv.- 1984.- 16, N 2.1. C. 111-152

67. Kooi R. ,' Frankforth D. Query Optimization in INGRES // IEEE Database Eng. Bull.- 1982.- 5, N 3 . C. 2-5

68. Whang K.-Y. Constructing Cost Formulas for Relational Database Query Optimizers: A Tutorial // TENCON' 87: IEEE Reg. 10th. Proc. Vol. 1. New York, 1987.- C. 132-141