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

На правах рукописи

о 1 }

Бабанова Наталья Ивановна

РАЗРАБОТКА И ОПТИМИЗАЦИЯ МОДЕЛЕЙ И АЛГОРИТМОВ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ЛОКАЛЬНЫХ И РАСПРЕДЕЛЕННЫХ

БАЗ ДАННЫХ

Специальность 05.13.12 - " Системы автоматизации проектирования (промышленность)"

Автореферат диссертации на соискание ученой степени кандидата технических наук

од

Г)

Владикавказ - 2000 г.

Работа выполнена на кафедре "Промышленная электроника" Северо-Кавказского государственного технологического университета

докт. техн. наук, профессор

докт. техн. наук, профессор

докт. техн. наук, профессор

канд.техн.наук

Научные руководители:

Дедегкаев Альберт Гагеевич

Хадонов Зураб Мусаевич

Официальные оппоненты:

Гроппен Виталий Оскарович Теняев Вячеслав Геннадьевич

Ведущее предприятие:

Национальный банк РСО-Алания

Защита диссертации состоится 23 июня 2000 г. в 14.00 час. на заседании диссертационного Совета К 063.12.03 в Северо-Кавказском ордена Дружбы Народов государственном технологическом университете.

Отзывы (в двух экземплярах, заверенные печатью) просим направлять по адресу: 362021, РСО-Алания, г. Владикавказ, ул. Николаева 44, Ученый Совет СКГТУ.

С диссертацией можно ознакомиться в библиотеке СКГТУ.

Автореферат разослан 22 мая 2000 г.

Ученый секретарь диссертационного Совета К 063.12.03

докт. техн. наук,

профессор Б.Д. Хасцаев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Поставленная цель достигается решением следующих задач:

- создание модели концептуального уровня и модели логического уровня локальных баз данных (ЛБД), а также формализация процедур преобразования концептуальной модели в модель логического уровня, выделения запрещенных фигур (ЗФ) такого преобразования и их расщепления;

- создание методики оценки влияния расщепления той или иной ЗФ на значение функционала оптимизации;

- разработка алгоритма выбора оптимальных логических моделей ЛБД;

- разработка критерия и метода многокритериальной оптимизации структур ЛБД;

- создание методики проектирования распределенных баз данных (РБД) с оптимальными характеристиками;

- разработка пакета прикладных программ реализации предложенных методов и процедур и создание системы автоматизированного проектирования (САПР) ЛБД и РБД.

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

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

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

- выявлены ЗФ преобразования модели концептуального уровня в оптимальную логическую модель и предложены алгоритмы их расщепления;

- предложен метод многокритериальной оптимизации структур ЛБД, позволяющий проводить оптимизацию уже на первом этапе проектирования, что значительно сужает дерево поиска оптимального варианта структуры;

- предложено два подхода к проектированию РБД, позволяющих получить РБД с оптимальными характеристиками;

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

- на основе предложенных моделей и методов разработана и внедрена САПР ЛБД и РБД, в которой автоматизированы этапы получения и оптимизации проектных решений при проектировании ЛБД и РБД.

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

- соответствием результатов теоретических и экспериментальных исследований;

- работоспособностью и соответствием предъявляемым требованиям спроектированных с применением разработанной САПР БД.

Практическая ценность работы состоит:

- в создании единой методики проектирования БД для локальных и распределенных информационных систем;

- разработанные модели, алгоритмы и программные средства позволяют автоматизировать все этапы выработки и оптимизации проектных решений при создании ЛБД и РБД;

- внедрение предложенной САПР позволяет сэкономить время разработки БД в среднем на 15-20%.

Реализация результатов работы. Разработанная САПР использована при проектировании РБД для автоматизированной информационно - управляющей системы Управления Жилшцно -Коммунального Хозяйства (УЖКХ) г. Владикавказа и для автоматизированной системы управления экологическим мониторингом Министерства Экологии РСО-Алания. Экономический эффект от внедрения системы в УЖКХ составил 52 тыс.руб. в год, а от внедрения системы управления экологическим мониторингом - 68 тыс.руб. в год. Основные результаты выполненной работы внедрены в учебный процесс в рамках курсов "САПР" и "Информатика", в курсовом и дипломном проектировании.

Апробация работы. Основные положения диссертационной работы доложены и обсуждены на Международной конференции «Устойчивое развитие горных территорий» (г.Москва-г.Владикавказ, 1998г.), научно-технических конференциях СКГТУ (г.Владикавказ, 1998 - 1999 г.г.) и Межрегиональной научной конференции «Студенческая наука - экономике научно - технического прогресса» (г.Ставрополь, 2000г.).

Публикации. Основное содержание диссертационной работы опубликовано в 7 печатных работах.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 82 наименований и 2 приложений. Общий объем диссертации 126 страниц, включая 24 рисунка и 11 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Проводится анализ существующих моделей реляционных БД. Основные теоретические результаты в этой области были получены еще в семидесятых годах: ЕЯ-модель, предложенная Ченем в 1976 год}'; модель Смитов, предложенная в статьях Смит и Смита в 1977 году; модель ЯМ/Т, предложенная Б.Коддом в 1979 году и другие. Постепенное накопление методов и алгоритмов организации реляционных БД привело к тому, что уже в середине 80-х годов реляционные системы практически вытеснили с мирового рынка иерархические и сетевые БД.

Различным аспектам разработки моделей БД посвящены труды таких ученых, как Джексона Г., Дейта К., Сибли Э., Хардгрейва Т., Горбатова В.А., Мамиконова А.Г. и др. Наиболее распространенная трактовка реляционной модели данных принадлежит К.Дейту. Согласно Дейту, реляционная модель состоит из трех частей, описывающих разные аспекты реляционного подхода: структурной части (структура данных, используемая в реляционных БД - нормализованное п-арное отношение), манипуляционной части (механизмы манипулирования реляционными БД - реляционная алгебра - базируется на классической теории множеств и реляционное исчисление - основывается на классическом логическом аппарате исчисления предикатов первого порядка) и целостной части (требования целостности: требование целостности сущностей и требование целостности по ссылкам).

В настоящее время общепринята трехуровневая архитектура БД, предложенная исследовательской группой института стандартов по системам управления базами данных ЛЫЗГ/ХЗ/БРАЯС и рабочей группой по БД КОДАСИЛ, согласно которой выделяются три уровня моделирования БД: концептуальный, логический и физический. В соответствии с тем, какой формализм положен в основу модели, все

модели разделены на два класса: теоретико-множественные, в которых основным средством представления отношений являются кортежи и теоретико - графовые, в которых внешний мир моделируется графом.

Отмечено, что общепринятых формальных критериев выбора моделей данных не существует. Имеющиеся попытки формализовать критерии носят упрощенный характер и не охватывают всех сторон понятия. Хорошей теоретической обоснованностью обладают реляционная модель и модель "объект - роль", а более насыщенной семантикой - модель ЯМ/Т и объектная модель.

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

Логический уровень проектирования включает в себя преобразование концептуальной модели в логическую и оптимизацию последней. Процесс преобразования выполняется под управлением методик, в которых достаточно четко оговорены все ее этапы. Наиболее известными методами оптимизации логической модели являются: декомпозиционный (по некоторой схеме реляционной БД, состоящей из схем нескольких отношений и набора ограничений на связи некоторых атрибутов найти другую, эквивалентную данной схему, в которой бы отсутствовали аномалии и число отношений было бы минимальным); синтаксический (исходными данными является множество атрибутов и ограничения на связи атрибутов, необходимо найти схему реляционной БД с теми же свойствами, что и в первой постановке) и подход, предложенный Горбатовым В.А. (строится специальный граф, в котором гамильтонов путь минимального веса задает желаемый порядок ролей взаимосвязей; при этом уменьшается объем памяти, необходимый для хранения БД). Большинство методов оптимизации логических моделей

являются одно- или двукритериальными, в то время, как критериев оптимизации неколько:

- уменьшение объема памяти, необходимой для хранения всей информации;

- уменьшение времени поиска требуемой информации;

- уменьшение времени первоначальной загрузки информации;

- уменьшение вероятности перестраивания набора отношений при введении новых типов данных;

- освобождение набора отношений от аномалий добавления, изменения и уд аления.

Проведен обзор существующих САПР реляционных БД. Отмечено, что несмотря на очевидную привлекательность концептуального проектирования, оно существует лишь в статьях и не реализовано напрямую ни в одной компьютерной системе. - Автоматизированная компипяция концептуальной схемы в реляционную реализована в СА8Е-:;истемах фирмы ORACLE (CASE - Dictionary, CASE-Designer, CASE - Generator). Выполнение задач физического проектирования полностью автоматизировано в современных системах управления базами данных (СУБД).

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

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

Введена формализация предметной области проектируемой БД заданием графа:

GK= <(V,YJ), Ri, RZ RS>,

где: V - множество сущностей; У - множество атрибутов; I - множество информационных запросов пользователей; отношение

Ri cV2 - отражает наличие или отсутствие взаимосвязей между

двумя сущностями; отношение R2 с; V х Y- отражает наличие

или отсутствие взаимосвязи /-го атрибута и у'-ой сущности; два элемента у, и у, множества У состоят в отношении Я^сг У х У, если /-ый атрибут расширяет смысловое содержание у-го атрибута; отношение Л4сУ х I - отражает принадлежность /-го арти-бута ¡-му информационному запросу (ИЗ). Граф Ск является концептуальной моделью проектируемой БД. Предлагаемая в работе логическая модель также является графом:

<(Г,Т0, Би

Носителем этого графа являются элементы многосортного множества М(Т,У), где: Т- множество логических массивов и индексных файлов; У- множество атрибутов и указателей, а сигнатуру образуют отношения 51;, причем: отношение с Т2 - отражает наличие или отсутствие взаимосвязей между двумя логическими массивами; отношение сг Т2 - определяет: входят ли два логических массива в один и тот же ИЗ; отношение сг Т х У -отражает принадлежность ¡-го атрибута^му логическому массиву.

Построенные теоретико - графовые модели являются основой для разработки САПР реляционных БД.

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

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

Таблица 1

Продолжение табл. 1

1 2 3 4 5

3 1:1 обязателен для 1-ой сущности У1 VI1 у4 у6 оУ4 У5 ^ ^ Уб

4 1:1 необязателен ДЛЯ М)Й и]-ой сущности У1 VI1 У1} у4 //2М:2у2ШУ5

1:п

обязателен для j-oй сущности

1:п

Необязателен для j -ой сущности

ш:п

любой

У1

(ХО» >0:

Определение 1. Логическая модель локальной базы данных с минимальным объемом необходимой памяти и минимальным временем первоначальной загрузки (У-структура) - это граф Оц-полученный в результате преобразования Ск Сд по правилам 2-7 (табл. 1):

такой, что Si = 0.

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

Определение 2. Логическая модель локальной базы данных с минимальным временем ответа на запросы пользователей (Т -структура) - это граф GLT:

такой, что 5/ =5?.

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

Описаны конструктивные условия преобразования Ск —> (7£г и С к С1Т.

Определение 3. Подграф Оа с вк с носителем {у/,у/, ...уДу/, У:,—, Ут} и сигнатурой {(V/, у ¡), ... ,( у„',ут)} является запрещенной фигурой преобразования Ок Оц- если веса к-ой и ^ой вершин связаны отношениями:

где: 2к Ук - веса к-ой вершины; Ук - длина к-то атрибута (в байтах); 2ь - количество значений к-го атрибута.

Gli =<(T,V), sh S2, Sj>,

Glt=<(T,Y), Si, S2, s3>,

Zk<Zj ZjYk > ZjYky + ZkYk,

(1) (2)

Например, если в концептуальной модели имеется ЗФ вида Са, где ¡-ой сущностью является сущность "Поставщик", а атрибутами: у/- номер поставщика, уз - фамилия поставщика, уз - статус поставщика, у4 - город, в котором поставщик расположен, причем имеется 10000 поставщиков (х}) и размещены они в 10 различных городах (г/), то есть выполняется условие (1) и если указатель занимает меньше памяти, чем название города, то есть выполняется условие (2), то расщепление ЗФ приведет к значительной экономии памяти.

Определение 4. Запрещенной фигурой преобразования Ск Сц- является подграф Сь сг С/л: с носителем { у/,...у,Д у/,...у/, у/,...уг',у,...ут} и сигнатурой {(у,1,у,), ...,( у„',ут)}, в котором каждой го вершин (Уь-Ут) инцидентно две или более вершины, относящиеся к различным сущностям.

Например, если в концептуальной модели имеется ЗФ вида вь, это означает, что к сущности относятся атрибуты, каждый из которых в то же время относится и к какой-либо другой сущности. Сущность V; в этом случае является избыточной, а расщепление ЗФ ведет к уменьшению объема памяти, необходимого для хранения проектируемой БД и времени ее первоначальной загрузки.

Наличие запрещенных фигур С/а и Сь в графе Ск приводит к тому, что он не может быть преобразован в Сц-.

Определение 5. Подграф Сс с Ок с носителем { у/,...у,/,

v/,...víí, уД...у/, У1,...,Ур.,, Ур,...,Уа-1, Уа.....Ут, е,ь, еш} и сигнатурой

{(VI,У/), ... , (у£,уп), (ур,е1Ь),(уа+1,еш), (у/+1,е1Ь), (у/*1,еш)} является запрещенной фигурой преобразования (-Гц-, если у/+1 является супертипом для подтипов ур и д»а+л

Например, если в концептуальной модели имеется ЗФ вида Сс, где сущность V] - служащий является супертипом для подтипов К, -мастер и Ук - сборщик, а в запросе е, необходима информация о том, кем конкретно является служащий: мастером или сборщиком, то для увеличения скорости поиска информации необходимо произвести расщепление ЗФ. Наличие ЗФ фигуры <7С в графе Ск приводит к тому, что он не может быть преобразован в

Отмечено, что структуры БД оптимальные по одному критерию крайне редко применяются на практике. Логическая модель реальной БД - это определенная комбинация У-структуры и Т-структуры. Поиск оптимальной комбинации предлагается проводить

в следующей последовательности: первый этап - определение носителя графа (?/,, то есть элементов множеств Е и У; второй - нахождение сигнатуры графа Ои (состоит в последовательном выборе ее элементов), то есть определение элементов множества 5/ и Б}.

Первый этап включает построение определенного числа вариантов логической модели Ст./, —> ..., Ск —> С?дг-/: )]= г+/, где г-число элементов множества /?/. Причем первый вариант Сд/ - это результат преобразования —> (?£, произведешюго строго в соответствии с правилами 2-7 (табл. 1), последний - С/.г./ -это результат преобразования Сд,- Од, произведенного по правилу 1 (табл.1), а остальные г-/ вариантов модели являются промежуточными и строятся следующим образом: ¡-ый вариант <7/., -это результат преобразования Ск С/., произведенного с применением к (¡-1)-м взаимосвязям правила преобразования 1, а к остальным взаимосвязям правила 2-7 из табл.1.

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

На втором этапе производится преобразование Си Сщ, С7 ц Си2> в при этом число вариантов логической

модели возрастает на Ат]=е+], где £ - число элементов множества (тН)-ый вариант логической модели Ощ, такой, что = 0; (гр-2)-ой - у которого число элементов множества 5/ =/, и так далее. Результатом выполнения второго этапа является (е+1) вариант логических моделей, которые также заносятся в формируемый банк логических моделей.

Логические модели, полученные на первом этапе - это модели БД с небольшим объемом требуемой для их хранения памяти и временем первоначальной загрузки, с максимальным временем обслуживания ИЗ. С каждым шагом второго этапа объем необходимой памяти и время первоначальной загрузки увеличиваются, а время ответа на запросы пользователей уменьшается.

Третья глава посвящена задаче оптимизации структур БД. В основу решения этой задачи для ЛБД положен метод многокритериальной оптимизации. Предложен критерий оптимизации логического проектирования, которым является многокомпонентный вектор:

^ = ~--, (3)

и V, У2

где: = 1,2,...,«; г = 1,2,...,ш,; /г - общее количество логических массивов и индексных файлов; тч - количество атрибутов в <у-м логическом массиве; 5/ - стоимость хранения одного байта информации; ¿2 - стоимость единицы времени работы персонального компьютера; Яз - стоимость единицы времени работы оператора ЭВМ; V/ - скорость обмена информацией между ОЗУ и внешней памятью; X,- - вес вершины графа Ос - количество экземпляров записей |-го логического массива или индексного файла; щ = 1, если вершины Х] и У, графа б/, инцидентны друг другу; ау = О - в противном случае; у1к = 1, если вершины и (к графа С?£ состоят в отношении £/; у5к~ О-в противном случае; х5р 1, + х/ хкр 1к, если вершины и 4 графа не состоят в отношении Б¡\ со,к — х/1, +хкр 1к, если вершины и 1к графа Сд состоят в отношении 51/; х/ - количество записей б-го информационного массива (ИМ), требуемых в р-м информационном запросе; /., - длина записи б-го ИМ; Я/, А? и Аз - шкалирующие коэффициенты. В выражении (3) первый член характеризует объем необходимой памяти, второй - общее время обслуживания ИЗ пользователей, третий - время первоначальной загрузки данных.

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

тайные алгоритмы выделения и расщепления ЗФ базируются на приемах характеризационного анализа.

После устранения ЗФ производится преобразование Ск —> С?/.. Разработана методика оценки влияния каждого шага преобразования на функционал Р, основанная на вычислении параметров логических моделей.

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

1. Построение концептуальной модели.

2. Выделение ЗФ с помощью разработанных алгоритмов.

3. Количественная оценка влияния каждой ЗФ на значение функционала оптимизации Р.

4. Расщепление ЗФ Оа, С/,, С/с с /2.

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

6. Выбор логической модели с минимальным значением функционала Ртт.

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

хода: первый - для проектирования РБД с применением стратегии расчленения, второй - с применением смешанной стратегии.

При этом вводится понятие стоимости ¡-го ИМ с', которая складывается из стоимости его хранения с/, стоимости передачи требуемых из ¡-го ИМ данных с/ и стоимости синхронизации его обновлений с/

Стоимость хранения ¡-го ИМ можно определить как:

т

с/=2н',йе/Кф (4)

1 I

где: т - количество узлов сети; w¡ - объем ¡-го ИМ; се] - стоимость хранения единицы информации в ]-м узле; Ху = 1 - если ¡-ый массив хранится в .¡-м узле; хц = 0 - в противном случае. Для определейия стоимости передачи требуемой информации из ¡-го ИМ строятся две матрицы: Н- матрица информационных потребностей, на пересечении ¡-ой строки и ]-го столбца которой находится элемент А(/ - объем информации, требуемый из ¡-го массива в ]-м узле в единицу времени и матрица В - матрица стоимости передач, на пересечении ¡-ой строки и ]-го столбца которой находится элемент Ъу — стоимость передачи байта информации из ¡-го узла в .¡-ый. Все элементы главной диагонали матрицы В равны нулю. С помощью матриц Н и В производится расчет с2 по строго определенному алгоритму. Так например, если ¡-ый ИМ хранится одновременно в к-м и Б-м узлах и участвует в ответах на запросы из к-го, б-го, г-го и 1-го узлов, стоимость передачи требуемых из него данных определяется выражением:

с2' = И,,(тт(Ьк,,Ь.+ И,г(тт(Ькг,Ь5Г)) (5)

Расчет синхронизации обновлений ¡-го ИМ производится по формуле:

ш

-, (6)

где: д, - объем обновлений ¡-го ИМ в единицу времени.

Основными этапами алгоритма оптимального распределения ИМ по узлам РБД с применением стратегии расчленения являются:

1. Вертикальное и горизонтальное разбиение отношений. Исходное отношение равно теоретико - множественному объединению получаемых отношений при горизонтальном разбиении и нормальному соединению новых отношений при вертикальном разбиении.

2. Определение по формулам (4,5,6) стоимости хранения ¡-го ИМ при хранении его в ^м узле для каждого ИМ и для всех узлов.

3. Минимизация функции:

Е = (7)

где: /=1 ..л; у'=1 ...т\ п - общее количество ИМ; ¿¡¡,- стоимость ¡-го ИМ при хранении его в ^м узле, при ограничениях на однократность размещения ИМ по узлам сети стандартными методами математического программирования. Распределение ИМ по узлам РБД предлагается производить по следующему алгоритму:

1. Вертикальное и горизонтальное разбиение отношений.

2. Построение модели информационных потребностей пользователя, которой является граф в]:

в,= <(Т,Ц),Е>,

где: Т - множество ИМ; и - множество узлов РБД; отношение Е сТ х и - отражает необходимость информации из ¡-го ИМ в ответе на запросы из ^го узла.

3. Вычисление порядка производной ^^от модели у/ :

др

к = п / т. Если п не является целым числом, то оно округляется до целого числа.

4. Дифференцирование модели информационных запросов пользователя ^по событию: "о/! повременное участие р ИМ в отведи/

тах на запросы из 1-го узла". Производные по предикату Р на р

др

элементах вычисляются по формуле:

Яп

где: /'/,/2,...,1а,-..,1р=т,,т2,...,тр, ...,/„./*/„.

5. Упорядочивание каждой группы производных по возрастанию, определение минимальной (минимальных - если минимальных производных равных между собой несколько) производной для каждой группы; соответственное распределение ИМ по узлам РБД; проверка для каждого узла ограничений по емкости; определение множества узлов У/, для которых ограничения не выполняются.

6. Расчет стоимости ¿/(/для каждого ИМ, помещенного в узлы из множества J¡, причем у'=1,2,...,2 - множество узлов ./? £ У/. Нахождение <1ут-т для ИМ, помещенных в узлы из множества У/ и помещение ¡-го ИМ в]-ый узел.

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

Предложенные модели и алгоритмы реализованы в САПР ЛБД

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

Решена задача оптимального распределения данных по узлам РБД: для АИУСГИ применена смешанная стратегия, для АСУЭМ - стратегия расчленения. Решение этой задачи с помощью предло-

и РБД.

женных в диссертации методик позволяет продемонстрировать преимущества такого подхода. Так, в проекте РБД АСУЭМ при минимальных затратах на хранение информации максимально снижены стоимость передачи данных между узлами сети при ответах на запросы пользователей - на 16 % и стоимость синхронизации обновлений - на 19,5 % по сравнению с проектом, разработанном с применением традиционных методов. В РБД АИУСГИ запрашиваемые данные расположены преимущественно по тем узлам, где производятся запросы, за счет чего значительно снижена стоимость передачи данных при ответах на запросы, и, соответственно, общее время ответа на запросы пользователей. При этом применение предложенной в диссертации методики позволило снизить и стоимость синхронизации обновлений данных. После распределения данных по узлам РБД была произведена дальнейшая оптимизация характеристик обоих проектов. Каждый узел РБД рассматривался, как ЛБД.

За счет применения предложенного в работе метода многокритериальной оптимизации ЛБД затраты на хранение информации снижены на 13-21 % для каждого узла РБД (так, при общем объеме памяти ЛБД 1,34 Кбайт экономия составила 280 байт), время первоначальной загрузки при этом уменьшено на 16-19 %, а уменьшение общего времени ответа на запросы пользователей для каждой ЛБД составило 3-5 %.

Эффективность разработанных моделей, методов и алгоритмов можно оценить по следующим характеристикам: сокращение общего времени проектирования реляционных баз данных в среднем на 15-20 %; универсальность разработанной САПР, позволяющей проектировать как локальные, так и распределенные БД с архитектурой файл - сервер и клиент - сервер; возможность разработки оптимальных структур ЛБД за счет многокритериальное™ метода оптимизации и оптимальных структур РБД за счет предложенного подхода к оптимизации распределения отношений по узлам сети.

В приложении приведены словари - справочники спроектированных РБД АИУСГИ и АСУЭМ, а также документы, подтверждающие внедрение результатов диссертации.

ЗАКЛЮЧЕНИЕ

1. Предложены графовые модели ЛБД концептуального и логического уровня, положенные в основу создания САПР БД.

2. Найдены ЗФ преобразования модели концептуального уровня в модель логического уровня и предложен способ их оптимального расщепления.

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

4. Предложены методы оптимального распределения данных при проектировании РБД любого типа.

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

Основные положения диссертации опубликованы в следующих работах:

1. Дедегкаев А.Г., Яровая - Бабанова Н.И. Математическое моделирование взаимосвязей компонентов системы. Тезись докладов III Международной конференции «Устойчивое развитие горных территорий», 21-26 сентября, 1998.

2. Дедегкаев А.Г., Яровая - Бабанова Н.И. Оптимизация матема тической модели базы данных городских инфраструктур. Тезись докладов НТК, посвящ. 60-летию научно - исследовательского сек тора. - Владикавказ: Терек. - 1998.

3. Дедегкаев А.Г., Яровая - Бабанова Н.И. Анализ информаци онных потоков и построение канонической структуры базы данны? для подсистемы «База данных городских инфраструктур»./ Трудь СКГТУ, выпуск 6, Владикавказ: Терек, 1999.

4. Бабанова Н.И. Применение двухуровневой графовой модел1 для проектирования реляционных баз данных./ Труды СКГТУ, вы пуск 7, Владикавказ: Терек, 2000.

5. Дедегкаев А.Г., Бабанова Н.И. Запрещенные фигуры оптими зации структур локальных баз данных на этапе логического проек тирования./ Сб.трудов аспирантов, Владикавказ, 2000.

6. Дедегкаев А.Г., Бабанова Н.И. Проектирование распределенных баз данных с оптимальным размещением информационных массивов по узлам сети. Тезисы докладов Межрегиональной научной конференции «Студенческая наука - экономике наушо - технического прогресса». - Ставрополь. - 2000.

7. Дедегкаев А.Г., Бабанова Н.И. Проектирование распределенных баз данных с оптимальными характеристиками./ Сб.трудов аспирантов, Владикавказ, 2000.

Зак.№124 Тир. 100. Объем 1 п.л. Подразделение оперативной полиграфии СКГТУ. г.Владикавказ, ул.Николаева 44.