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

Актуальность темы

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

В настоящее время в СССР наибольшее распространение получили интегрированные информационные системы, в которых данные описываются иерархическими и сетевыми типами структур. Для таких систем разработано большое число систем управления базами данных (СУБД), обеспечивающих их поддержку, ведение и обслуживание (к ним относятся БАНК, ИНЭС, ОКА, СВДАН и др.). Развитые средства СУЩ и операционных систем вьщвигают в качестве главной проблемы проектирования АДЦ — проблему выбора состава и структуры баз данных, содержащих информацию предметной области пользователей. Широкий круг пользователей АВД, сложность решаемых прикладных задач, разнообразие и взаимосвязь используемых ими структур данных, изменчивость их характеристик, неравномерность и различная цриори-тетность поступающих запросов обуславливают высокую сложность выбора рациональных и оптимальных по заданным критериям эффективности структур и характеристик БД. Разработка эффективных структур баз данных представляет собой комплексную проблему, включающую в себя предцроектный анализ информационных потоков пользователей АЕЩ, синтез логических и физических структур баз данных с учетом режимов функционирования АБД и характеристик пользователей, синтез прикладного модульного црограммного обеспечения, взаимодействующего с БД* Большие масштабы работ по созданию и внедрению автоматизированных банков данных в различных областях народного хозяйства, широкое црактическое црименение и многообразие СУВД, ориентированных на поддержание и ведение иерархических и сетевых структур баз данных, целесообразность их использования при создании информационного обеспечения АИУС, и в то же время отсутствие формализованных моделей и методов анализа и синтеза оптимальных структур баз данных иерархического и сетевого типов обуславливают актуальность выполненных научных исследований.

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

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

Научная новизна. В результате проведенных научных исследований и обобщения опыта разработок и внедрения АЭД различного класса и назначения разработаны формализованные модели и методы ана ^ лиза и синтеза оптимальных структур баз данных иерархического и сетевого типов.

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

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

Практическая ценность. Разработанные формализованные модели, методы, алгоритмы и программы обеспечивают анализ и синтез оптимальных по заданным критериям эффективности структур ЦЦ иерархического и сетевого типов для интегрированных информационных систем широкого класса и назначения. Использование разработанного комплекса алгоритмов и программ формирования оптимальных структур баз данных на всех основных этапах их проектирования (цредпроект-ного анализа информационных потоков и структуризации предметной области пользователей, синтеза логических и физических структур Щ, синтеза црикладного модульного программного обеспечения) позволяет существенно уменьшить время и затраты на их разработку, повысить качество вырабатываемых проектных решений. Разработанные алгоритмы реализованы на языках Фортран и PUI и могут быть использованы при разработке информационного обеспечения АСУ, АИУС, систем обработки данных, создаваемых по принципу автоматизированных банков данных.

Внедрение. Разработанные формальные модели и методы анализа и синтеза оптимальных структур баз данных иерархического и сетевого типов использовались при про ектировании структур баз данных ряда подсистем учебного комплекса второй очереди системы управления учебным цроцессом Казахского политехнического института им. В. И. Ленина АСУ «ВУЗ», реализованных с использованием СУВД ИНЭС-2М. Предложенные методы и алгоритмы решения поставленных задач синтеза позволили сократить общее время разработки структур ВД примерно на-15 $, повысить оперативность загрузки Щ и получения выходных данных на 20−25%. Созданная на основе полученных теоретических результатов методика и методические материалы анализа информационных потоков и структуризации предметной области пользователей была включена в состав технического проекта на все подсистемы комплекса АСУ «ВУЗ», использовалась при разработке ДЦ справочно-информационной системы АСУ ВПО «Союзрезинотехника», работающей под управлением СУБД БАНК-УС, при разработке информационных баз данных подсистем «Управление кадрами», «Управление сбытом и реализацией», «Управление материально-техническим» и др., входящих в состав организационно-технологической АСУ Гродненского ПО «АЗОТ» и работающих под управлением СУБд ИНЭС-2Мпри разработке информационного обеспечения подсистем «Инженерная подготовка производства», «АСУ комплектации строек сборным железобетоном», «АСУ треста Монтажспецсельстрой», входящих в состав АСУ Минсель-строя БССР и предназначенных для работы под управлением СУЩ БАНК-УСцри разработке информационного обеспечения информационно-поисковой фактографической системы, входящей в состав отраслевых АСУ ВДПО «Каскад» и ориентированной на использование СУБД ОКА и др. Использование разработанных методов, алгоритмов и программ позволило сократить сроки пред проектного анализа и структуризации предметных областей пользователей на 15−20 $, что составляет от двух до четырех месяцев по каждой подсистеме в зависимости от их сложностисократить на 20% сроки проектирования логических структур баз данных, а также повысить оперативность учета при проектировании изменяющихся и вновь поступающих информационных требований пользователей.

В целом внедрение разработанных формализованных моделей и методов анализа и синтеза оптимальных структур баз данных иерархического и сетевого типов позволило получить экономический эффект свыше 50 тыс. рублей в год.

Апробация работы. Основные результаты диссертационной работы обсуждались и докладывались автором на: Всесоюзном семинаре по методам синтеза типовых модульных систем обработки данных (Звенигород, 1981), Всесоюзном совещании «Оптимизационные задачи в автоматизированных системах управления (Нальчик, 1981) — Школе-семинаре по проблемам управления качеством продукции (Звенигород, 1982) — П Всесоюзном совещании «Автоматизация проектирования и конструирования» (Ленинград, 1983) — Всесоюзном симпозиуме «Проблемы системотехники» (Ленинград, 1983) — Всесоюзном совещании по управлению большими системами (Алма-Ата, 1983) — П Всесоюзной конференции «Банки данных» (Ташкент, 1983) — Конференции молодых учёных и специалистов Института проблем управления (Москва, 1983), других совещаниях, конференциях.

Публикации. Проведенные автором научные исследования выполнены по плану научно-исследовательских работ Ордена Ленина Института проблем управления — тема Jfe 12−79 «Синтез оптимальных модульных и типовых модульных автоматизированных информационно-управляющих систем» (номер гос. регистрации 79 062 179), плану научных работ Казахского политехнического института им. В. И. Ленина — тема «Разработка теоретических аспектов цроцесса проектирования банков данных, построения на этой основе технологии автоматизированного проектирования банков данных» (номер гос. регистрации 0I8300422I5), а также в соответствии с Целевой комплексной программой ГКНТ 0.80.06 «Создать новые и усовершенствовать действующие автоматизированные системы управления (АСУ) промышленными министерствами, производственными объединениями и предцршггиями» и опубликованы в 7 научных трудах.

Объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и приложений. Работа включает 150 страниц машинописного текста, 57 рисунков, 39 таблиц.

КРАТКИЕ ВЫВОДЫ.

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

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

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

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

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

5. Разработан модифицированный рандомизированный алгоритм разрезания графов для решения задачи синтеза логических массивов БД.

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

7. Разработанные методы и алгоритмы решения задач синтеза оптимальных структур БД иерархического и сетевого типов реализованы в виде комплекса программ на языках Фортран 1У и PL Д.

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

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

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

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

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

11. На примере практического использования моделей и методов анализа и синтеза структур БД при разработке базы данных подсистемы «Контингент студентов», входящей в состав АСУ «ВУЗ» Казахского политехнического института, проведен сравнительный анализ синтезированных рациональной логической структуры БД и оптимальной логической структуры БД с логической структурой, разработанной традиционными методами. Результаты анализа показывают эффективность предложенных в диссертации моделей и методов анализа и синтеза оптимальных структур баз данных иерархического и сетевого типов.

12. Разработанные в диссертации методы, алгоритмы и программы использовались при разработке информационного обеспечения ряда подсистем АСУ, ориентированных на использование различных систем управления базами данных иерархического и сетевого типов: при разработке БД подсистем учебного комплекса АСУ «ВУЗ» Казахского политехнического института им. В. И. Ленина (СУБД ИНЭС), при разработке БД справочно-информационной системы АСУ ВПО «Союзрезинотехника» (СУБД БАНК-УС), при разработке информационного обеспечения информационно-поисковой фактографической системы АСУ ВДПО «Каскад» (СУБД ОКА) и др. Практическое использование предложенных методов анализа и синтеза оптимальных структур баз данных показывает, что по сравнению с традиционными методами их проектирования сроки предцроектного анализа и разработки структур баз данных иерархического и сетевого типов сокращаются на 15−20% при одновременном повышении качества вырабатываемых проектных решений.