Содержание к диссертации
Введение
Глава I. Методы анализа информационных потоков области пользователей АБД 19
1.1. Обзор методов проектирования БД 20
1.2. Методы анализа информационных требований пользователей и формирования графов информационных структур 35
1.3. Процедуры выделения ключей и атрибутов в группах данных 42
1.4. Формализованные процедуры построения канонической структуры ВД 46:
Глава II. Задачи синтеза оптимальных логических структур ВД 66
2.1. Основные определения и формализованное описание исходных данных 67
2.2. Методы расчета основных характеристик канонической структуры ВД 77
2.3. Задачи синтеза логической структуры ВД 86
Глава III. Задачи синтеза оптимальных физических структур ВД .101
3.1. Задачи оптимального распределения логических массивов по типам памяти и оптимального размещения экземпляров логических записей по страницам памяти 103
3.2. Выбор оптимальных методов организации записей и связей 107
3.3. Задача синтеза модулей прикладного программного обеспечения при заданной логической и физической структурах ВД 114
Глава ІV. Методи и алгоритмы решения задач синтеза структур БД иерархического и сетевого типов 122
4.1. Точные алгоритмы решения задач синтеза логической структуры БД для основных режимов функционирования АЩ 123
4.2. Приближенные алгоритмы решения задач синтеза логической структуры БД 141
4.3. Алгоритм решения задачи синтеза состава логических массивов Щ 157
4.4. Методы и алгоритмы решения задач синтеза физической структуры Щ и прикладного модуль ного программного обеспечения 161
Краткие выводы 168
Заключение 170
Литература . 173
Приложения 182
- Методы анализа информационных требований пользователей и формирования графов информационных структур
- Основные определения и формализованное описание исходных данных
- Задачи оптимального распределения логических массивов по типам памяти и оптимального размещения экземпляров логических записей по страницам памяти
- Точные алгоритмы решения задач синтеза логической структуры БД для основных режимов функционирования АЩ
Методы анализа информационных требований пользователей и формирования графов информационных структур
В данной главе рассматриваются цели и задачи проектирования баз данных, приведен обзор основных работ в данной области, указаны особенности предложенного в диссертации подхода, приведены формализованные процедуры анализа и структуризации предметной области пользователей»
Разработка эффективных структур БД иерархического и сетевого типов включает следующие этапы: предпроектный анализ информационных потоков пользователей, синтез логической структуры БД, синтез физической структуры Щ, синтез прикладного модульного программного обеспечения.
В главе изложена методология формализации и автоматизации основных этапов анализа и синтеза оптимальных структур Щ иерархического и сетевого типов, в основу которой положено последовательное преобразование исходных данных и результатов, получаемых при решении задач проектирования на каждом из этапов с учетом ограничений и критериев эффективности, специфичных для каждого этапа. На основании обобщения опыта использования различных моделей и методов анализа и структуризации предметной области пользователей в работе предложен комплекс графовых и матричных моделей, обеспечивающих формальный анализ и структуризацию предметной области, выявление и анализ дублируемых элементов и избыточных взаимосвязей, выделение ключей и атрибутов, а также интеграцию информационных структур пользователей в единый граф - каноническую структуру Щ, Исходной информацией для разработанных процедур анализа является информация о парных отношениях между элементами предметной области, задаваемая в информационных требованиях пользователей и формализуемая в виде матриц семантической смежности. Разработанные модели ориенти- рованы на автоматизацию этапа предпроектного анализа и обеспечивают подготовку исходных данных для последующих этапов синтеза оптимальных логических и физических структур БД.
Процесс анализа информационных потоков и структуризации предметной области пользователей разбивается в работе на три взаимо -связанных этапа: 1. Анализ информационных требований пользователей и формирование графов информационных структур ( 1,2). 2. Выделение ключей и атрибутов в группах данных ( 1,3). 3. Построение канонической структуры БД ( 1,4). Каноническая структура БД является основой при построении рациональной логической структуры БД с учетом ограничений СУВД, а также при разработке оптимальной по заданным критериям эффектив -ности логической структуры БД. Обзор методов проектирования БД Практика создания АДД выдвигает новые задачи проектирования, которые невозможно решить традиционными методами и средствами. Особую важность при этом приобретает необходимость соверщенствования методологии их проектирования, охватывающей основные этапы процесса создания систем /I-I8, 68/. Среди круга проблем, связанных с разработкой АЕЩ, особое внимание уделяется вопросам проектирования баз данных, являющихся неотъемлемой частью информационных систем. Проектирование БД является длительным и трудоемким процессом. Результаты принимаемых при этом проектных решений по выбору состава и структуры Щ оказывают существенное влияние на эффективность функционирования МУС в целом. Поэтому в отдельных случаях предлагается выделять процесс проектирования баз данных в самостоятель -ныи этап при разработке МУС в виду специфики методов их разработки и большого объема работ /19-22, 69/.
Проектирование оптимальных структур БД является многоэтапным процессом принятия обоснованных решений в ходе анализа ин -формационных потоков и структуризации предметной области пользователей АВД, синтеза, логических и физических структур Щ, синтеза модулей прикладного программного обеспечения, взаимодействующего с Щ /19-28, 48, 49/, Сложившаяся в настоящее время этапность проектирования Щ в основном определяется принципами многоуровневой организации данных, поддерживаемых современными СУЩ. В отчете Исследовательской группы Американского национального института стандартов да системам управления базами данных ДШДЗ/5РЖ определены три уровня организации данных: концептуальный, внешний и внутренний /70/. На концептуальном уровне задается описание общей логической организации данных, формируемой в результате согласования и объединения пользовательских представлений о данных предметной области в единую обобщенную (интегрированную) структуру предметной области. Описание данных на концептуальном уровне осуществляется с учетом ограничений конкретной СУЩ, что обеспечивает инвариантность структуры предметной области используемым программным средствам СУЩ /19, 25/, Концептуальному уровню организации данных соответствует понятие логической структуры Щ /19, 49/, В отдельных случаях выделяется информационно-логическая (инфологи-ческая) /21, 22, 25, 71/, либо каноническая /19, 26-28, 72, 73/ структуры данных, отражающих наиболее характерные свойства данных и взаимосвязей предметной области без учета ограничений СУЩ. На внешнем уровне описание структуры Щ соответствует представлению о данных с позиций требований пользователей и прикладных программ. Внешнему уровню организации данных соответствуют подсхемы логической структуры Щ при её задании /19, 20, 49/, или информационные требования пользователей, задаваемые в виде парных отношений /26, 28/.
На внутреннем уровне задается описание физической структуры Щ, характеризующее размещение данных в памяти ЭВМ. В настоящее время используется ряд различных методик проектирования БД иерархического, сетевого и реляционного типов, среди которых следует выделить неформализованные /23, 25, 29, 38, 75, 76/ и формализованные (автоматизированные) /26т28, 30, 35, 72, 73, 78, 79/.
Наиболее развитыми являются методы проектирования реляционных Щ, основывающиеся на формальном аппарате реляционной алгебры и функциональных зависимостях /31-34, 74/.
Проектирование Щ иерархического и сетевого типов сопряжено с большими трудностями, связанными с отсутствием единых формаль -ных методов их проектирования, большими размерностями решаемых задач проектирования, необходимостью учета различного рода ограничений, накладываемых на разрабатываемую структуру, а также трудно -стью формализации и оценки качества критериев эффективности их разработки.
Начальным этапом проектирования БД является этап предпроект-ного анализа информационных потоков и структуризации предметной области пользователей. На данном этапе осуществляется изучение и анализ конкретной предметной области, информацию о которой разра -ботчик Щ получает путем выявления информационных потребностей пользователей к разрабатываемой информационной системе. В процессе изучения и анализа должны быть выявлены требования к разрабатываемой структуре Щ, определен состав информационных элементов, образующих заданную предметную область, выделены информационные группы (объекты), описывающие некоторые сущности предметной области, о которых пользователь хотел бы получить сведения или которые являются предметом его деятельности, установлены взаимосвязи между группами. Результатом данного этапа
Основные определения и формализованное описание исходных данных
Алгоритм анализа и преобразования циклических составляющих приведен ниже. Он основан на построении локальных ориентирован -ных деревьев для каждой вершины входящей в цикл и выделении, а также последующем преобразовании элементарных циклов. Алгоритм состоит из следующих шагов:
1Из множества Dt=4 ds ,dp,. .. ...Дрлементов уровня c Ct входящих в цикл, выбирается произвольный элемент а-ь , для которого осуществляется построение древовидной структуры возможных путей доступа рассматриваемого элемента к остальным элементам множества j Os7dpr..?djk образующих циклы одного уровня. Элемент QL является корневой вершиной данной древовидной структуры» 2. Определяется совокупность элементов второго уровня древо видной структуры, которые непосредственно связаны с корневой вер шиной. Наличие такой связи определяется выполнением условия 3. Висячая вершина 0 (Ок40і), полученная на (п-І)-м эта пе (элементы второго, третьего и т.д. уровней) связываются с таки ми вершинами следующего уровня, для которых &к == » V Uj. Dt. Процесс построения локального дерева заканчивается при выполнении следующих условий: I) вершина ак получает метку dt , т.е. совпа дает с корневой вершиной дерева ветвления; 2) вершина ак получа ет метку, совпадающей с меткой некоторой промежуточной вершины, ле жащей на одном пути из корневой вершины (d ) дерева ветвления. Второй случай указывает на запрещение ветвления по вершинам, не образующим элементарных циклов с данной корневой вершиной (d .). Полученные пути от корня дерева ( GL) до висячих вершин с метками UL определяют элементарные циклы, проходящие через анализируемый ключ (QL). Древовидная структура для элемента ds множества Dt [u-L, QSjdp,...,dt [ строится аналогично описанному выше алгоритму - 56 по вершинам, не проходящим через элемент Qi, для элемента Ch -по вершинам, не проходящим через элементы jdg,dp,...,di.,."H т.д. Общее число построенных для заданного уровня Xt локальных древовидных структур совпадает с мощностью множества Dt 4. В состав элементарных циклов включаются ключи, лежащие на одном пути из корневой древовидной структуры в висячие вершины, помеченные меткой исходной корневой вершины. 5. Выявленные элементарные циклы преобразуются в линейные структуры путем удаления любой из связей в цикле и введения специальной вершины-указателя на вершину, в которую заходила удаленная дуга. С целью ускорения процесса построения локальных древовидных структур целесообразно предварительно упорядочивать элементы множества D± по степени убывания числа циклов различной длины, проходящих через элементы множества. Подсчет максимального числа циклов, проходящих через анализируемый ключ QL осуществляется с использованием матриц путей различных длин JJOI , путем суммирования записей и -ul У/{ , лежащих вдоль главной диагонали матриц D оі яо всем матрицам ІЗ 01 , I = 2,1. В результате выполнения рассмотренных выше процедур третьего этапа осуществляется построение результирующей матрицы смежности Е и упорядоченного графа канонической структуры (3(D,U), который не содержит избыточных взаимосвязей и пересекающихся атрибутов, на котором выявлены и проанализированы циклы. На основе предложенных методов анализа и структуризации предметной области разработаны методические материалы и автоматизированная система анализа информационных потоков пользователей и построения канонической структуры Щ, функционирующая в режиме диалога с проектировщиком. - 57 Обобщенная блок-схема данной системы представлена на рис.1.4.2. Программное обеспечение написано на языке Фортран ІУ, объем программного обеспечения - свыше 1000 операторов, требуемый объем оперативной памяти - 190 Кбт. Предусмотренный режим диалога с проектировщиком позволяет уточнять и корректировать входные данные, а также промежуточные результаты анализа, что позволяет более точно описать и структурировать предметную область пользователей. Результаты формализации процедур анализа направлены на построение канонической структуры БД и могут быть использованы в двух направлениях: - при построении рациональных логических и физических структур БД путем реструктуризации канонического проекта Щ с учетом структурных и системных ограничений, накладываемых операционными средствами и СУЩ; - при разработке оптимальных по заданным критериям эффективности логических и физических структур Щ путем использования элементов канонической структуры Щ в качестве исходных данных при син -тезе оптимальных структур Щ. Разработанные формализованные процедуры анализа, матричные и графовые модели позволяют повысить эффективность и качество проектируемых интегрированных информационных систем, снизить стоимост -ные и временные затраты на их разработку и, кроме того, создать предпосылки автоматизации основных операций предпроектного анализа предметной области пользователей.
Задачи оптимального распределения логических массивов по типам памяти и оптимального размещения экземпляров логических записей по страницам памяти
В работе получены следующие результаты: 1. На основе обзора в области методов и средств создания баз данных показано, что проектирование оптимальных структур БД есть многоэтапный процесс принятия решений в ходе анализа информационных потоков пользователей, синтеза логических и физических структур БД и модулей прикладного программного обеспечения. Выделены основные цели и задачи проектирования на каждом из этапов. 2. Разработана единая методология проектирования оптимальных структур БД иерархического и сетевого типов, заключающаяся в последовательном преобразовании исходных данных и результатов, получаемых при решении задач проектирования на каждом из этапов с учетом ограничений и критериев эффективности, специфичных для каждого этапа. 3. Предложена совокупность графовых и матричных моделей, обеспечивающих формальный анализ и структуризацию предметной области пользователей и направленных на построение рациональных канонических структур БД на этапе, предшествующем техническому проектированию БД. 4. Разработаны модели и постановки задач синтеза оптимальных логических структур БД иерархического и сетевого типов с учетом требований обработки данных и режимов функционирования АБД. Критерий оптимальности, обеспечивающий минимум суммарного времени первоначальной загрузки информации в БД и обслуживания заданного множества запросов пользователей, сформулирован для двух случаев: при наличии одной точки входа в структуру по каждому запросу и при наличии нескольких возможных вариантов точек входа в структуру по каждому запросу. Предложены постановки частных задач синтеза оптимальной логической структуры БД, учитывающие особенности функционирования АДЦ в отдельных режимах. 5. На основе анализа различных вариантов поиска данных, задаваемых условиями сформулированных к Щ запросов, а также с учетом объемно-временных параметров элементов предметной области и их взаимосвязей, получены аналитические выражения для расчета основных характеристик канонической структуры БД, используемых при постановках и решении задач синтеза оптимальных логических структур БД. 6. Поставлена и решена задача синтеза оптимальной логической структуры БД для задач обработки данных реального масштаба времени. В качестве критерия оптимизации используется минимум времени ответа на запросы, обслуживаемые в реальном масштабе времени. 7. Разработана формализованная модель синтеза состава логических массивов БД, заключающаяся в оптимальной декомпозиции логической структуры БД на ряд взаимосвязанных подструктур (массивов). 8. Разработаны модели и постановки задач синтеза физической структуры БД. Синтез оптимальной физической структуры БД включает последовательное решение следующего комплекса задач: оптимальное распределение логических массивов по типам памяти; оптимальное размещение экземпляров логических записей по страницам памяти в пределах каждого типа памяти; выбор оптимальных методов организации записей и связей в пределах каждого массива или страницы па -мяти. 9. С учетом особенностей решения прикладных задач обработки данных в условиях заданных логической и физической структур БД разработана постановка задачи синтеза оптимального состава модулей прикладного программного обеспечения пользователей АБД. 10. Разработаны точные и приближенные алгоритмы решения по ставленных задач синтеза оптимальных структур баз данных иерархического и сетевого типов, основанные на методах дискретного программирования, локальной оптимизации, теории графов и методах оптимизации на сетях и графах. 11. На примере практического использования моделей и методов анализа и синтеза структур БД при разработке базы данных подсистемы "Контингент студентов", входящей в состав АСУ "ВУЗ" Казахского политехнического института, проведен сравнительный анализ синтезированных рациональной логической структуры БД и оптимальной логической структуры Щ с логической структурой, разработанной традиционными методами. Результаты анализа показывают эффективность предложенных в диссертации моделей и методов анализа и синтеза оптимальных структур баз данных иерархического и сетевого типов. 12. Разработанные в диссертации методы, алгоритмы и программы использовались при разработке информационного обеспечения ряда подсистем АСУ, ориентированных на использование различных систем управления базами данных иерархического и сетевого типов: при разработке БД подсистем учебного комплекса АСУ "ВУЗ" Казахского политехнического института им.В.И.Ленина (СУБД ИНЭС), при разработке БД справочно-информационной системы АСУ ВПО "Союзрезинотехника" (СУБД БАНК-УС), при разработке информационного обеспечения информационно-поисковой фактографической системы АСУ ЩПО "Каскад" (СУБД ОКА) и др. Практическое использование предложенных методов анализа и синтеза оптимальных структур баз данных показывает, что по сравнению с традиционными методами их проектирования сроки предпроектного анализа и разработки структур баз данных иерархического и сетевого типов сокращаются на 15-20% при одновременном повышении качества вырабатываемых проектных решений.
Точные алгоритмы решения задач синтеза логической структуры БД для основных режимов функционирования АЩ
Обзор методов проектирования БД Практика создания АДД выдвигает новые задачи проектирования, которые невозможно решить традиционными методами и средствами. Особую важность при этом приобретает необходимость соверщенствования методологии их проектирования, охватывающей основные этапы процесса создания систем /I-I8, 68/. Среди круга проблем, связанных с разработкой АЕЩ, особое внимание уделяется вопросам проектирования баз данных, являющихся неотъемлемой частью информационных систем. Проектирование БД является длительным и трудоемким процессом. Результаты принимаемых при этом проектных решений по выбору состава и структуры Щ оказывают существенное влияние на эффективность функционирования МУС в целом. Поэтому в отдельных случаях предлагается выделять процесс проектирования баз данных в самостоятель -ныи этап при разработке МУС в виду специфики методов их разработки и большого объема работ /19-22, 69/.
Проектирование оптимальных структур БД является многоэтапным процессом принятия обоснованных решений в ходе анализа ин -формационных потоков и структуризации предметной области пользователей АВД, синтеза, логических и физических структур Щ, синтеза модулей прикладного программного обеспечения, взаимодействующего с Щ /19-28, 48, 49/, Сложившаяся в настоящее время этапность проектирования Щ в основном определяется принципами многоуровневой организации данных, поддерживаемых современными СУЩ. В отчете Исследовательской группы Американского национального института стандартов да системам управления базами данных ДШДЗ/5РЖ определены три уровня организации данных: концептуальный, внешний и внутренний /70/. На концептуальном уровне задается описание общей логической организации данных, формируемой в результате согласования и объединения пользовательских представлений о данных предметной области в единую обобщенную (интегрированную) структуру предметной области. Описание данных на концептуальном уровне осуществляется с учетом ограничений конкретной СУЩ, что обеспечивает инвариантность структуры предметной области используемым программным средствам СУЩ /19, 25/, Концептуальному уровню организации данных соответствует понятие логической структуры Щ /19, 49/, В отдельных случаях выделяется информационно-логическая (инфологи-ческая) /21, 22, 25, 71/, либо каноническая /19, 26-28, 72, 73/ структуры данных, отражающих наиболее характерные свойства данных и взаимосвязей предметной области без учета ограничений СУЩ. На внешнем уровне описание структуры Щ соответствует представлению о данных с позиций требований пользователей и прикладных программ. Внешнему уровню организации данных соответствуют подсхемы логической структуры Щ при её задании /19, 20, 49/, или информационные требования пользователей, задаваемые в виде парных отношений /26, 28/.
На внутреннем уровне задается описание физической структуры Щ, характеризующее размещение данных в памяти ЭВМ. В настоящее время используется ряд различных методик проектирования БД иерархического, сетевого и реляционного типов, среди которых следует выделить неформализованные /23, 25, 29, 38, 75, 76/ и формализованные (автоматизированные) /26т28, 30, 35, 72, 73, 78, 79/.
Наиболее развитыми являются методы проектирования реляционных Щ, основывающиеся на формальном аппарате реляционной алгебры и функциональных зависимостях /31-34, 74/.
Проектирование Щ иерархического и сетевого типов сопряжено с большими трудностями, связанными с отсутствием единых формаль -ных методов их проектирования, большими размерностями решаемых задач проектирования, необходимостью учета различного рода ограничений, накладываемых на разрабатываемую структуру, а также трудно -стью формализации и оценки качества критериев эффективности их разработки.
Начальным этапом проектирования БД является этап предпроект-ного анализа информационных потоков и структуризации предметной области пользователей. На данном этапе осуществляется изучение и анализ конкретной предметной области, информацию о которой разра -ботчик Щ получает путем выявления информационных потребностей пользователей к разрабатываемой информационной системе. В процессе изучения и анализа должны быть выявлены требования к разрабатываемой структуре Щ, определен состав информационных элементов, образующих заданную предметную область, выделены информационные группы (объекты), описывающие некоторые сущности предметной области, о которых пользователь хотел бы получить сведения или которые являются предметом его деятельности, установлены взаимосвязи между группами. Результатом данного этапа
