49743 (588672), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

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

В качестве основных ограничений используется ограничения на временных и стоимостные характеристики процесса реализации запросов и корректировок, на объём доступной внешней памяти и узлах вычислительной сети (ВС), пропускную способность каналов связи, надежность доступа к заданному узлу ВС и др.

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

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

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

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

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

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

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

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

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

Поставлены и решены задачи синтеза оптимальных по заданным критериям эффективности логических и физических структур локальных баз данных. При проектировании оптимальных логических структур локальных баз данных возможны два подхода, каждый из которых детально исследован [69, 76, 79, 80].

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

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

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

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

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

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

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

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

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

Разработанные методы, модели, алгоритмы и комплексы программ нашли широкое практическое использование при проектировании модульных СОД различного класса и назначения.

С использованием полученных результатов сформулированы принципы построения и рассмотрены основные элементы, структура и алгоритмическое обеспечение автоматизированной системы проектирования оптимальных модульных СОД, а также имитационные модели для анализа технологии обработки информации на системном уровне. На этой основе разработаны системы автоматизированного проектирования СОД семейства “Модуль”.

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

1.2 Модели и методы решения задач дискретного программирования при проектировании систем обработки данных

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

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

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

Как показал анализ проектирования модульных системы обработки данных в подавляющем большинстве задач анализа и синтеза СОД сводится к задачам дискретного программирования.

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

Определим задачу дискретного программирования следующим образом. [83]

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

, (1.2.1)

где - -мерный вектор; - скалярный функция; -некоторое множество в , .

Если - конечное (или счетное) множество или декартово произведение конечного (счетного) множества на множество мощности континиума, то будет иметь место задача ДП. В этом случае условие принадлежности некоторому множеству может быть записано в виде:

Характеристики

Список файлов ВКР