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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

, (1.2.1)

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

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

, ;

, ; ; . (1.2.2)

При - задача частично дискретного программирования.

Если - множество всех целочисленных векторов, то при - имеем задачу целочисленного программирования (ЦП). А при - задачу частичного целочисленного программирования (ЧЦП).

В наибольшей степени изучены методы решения задач целочисленного линейного программирования (ЦЛП):

;(1.2.3)

Здесь - множество всех неотрицательных целых чисел, частный случай задач ЦЛП задачи с булевыми переменными, где в (1.2.3):

, ;

В ряде задач ЦП требование целочисленности накладывается и на целевую функцию.

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

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

Обычно эффективное решение задачи тесно связанно с математической моделью задачи, со структурой модели и ее особенностями.

Рассмотрим некоторые математические модели дискретного программирования и методы их решения.

Модели задач ДП. Классическим примером моделей этого класса являются модели целочисленного линейного программирования, в которых переменными являются неделимые величины. Модели этого класса в свою очередь генерировали различные варианты постановки прикладных задач и определены как модели с неделимостями.

В процессе развития теории дискретного программирования выделился класс комбинаторных моделей. [83]

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

Одним из типичных примеров комбинаторной модели является задача о коммивояжере. [84]

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

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16