Разработка моделей, методов и инструментальных средств анализа и синтеза оптимальных структур баз данных в автоматизированных информационно-управляющих системах тема диссертации и автореферата по ВАК РФ 05.13.06, доктор технических наук Сиротюк, Владимир Олегович

  • Сиротюк, Владимир Олегович
  • доктор технических наукдоктор технических наук
  • 1999, Москва
  • Специальность ВАК РФ05.13.06
  • Количество страниц 745
Сиротюк, Владимир Олегович. Разработка моделей, методов и инструментальных средств анализа и синтеза оптимальных структур баз данных в автоматизированных информационно-управляющих системах: дис. доктор технических наук: 05.13.06 - Автоматизация и управление технологическими процессами и производствами (по отраслям). Москва. 1999. 745 с.

Оглавление диссертации доктор технических наук Сиротюк, Владимир Олегович

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. Проблемы и задачи автоматизированного проектирования баз данных АИУС

1.1. Развитие методов автоматизированного проектирования информационно-управляющих систем

1.2. Основные положения по созданию промышленной технологии автоматизированного проектирования БД АИУС

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

ГЛАВА 2. Разработка моделей и методов формализации информационных требований пользователей, анализа и структуризации предметных областей

2.1. Формализованные модели предметных областей и спецификаций информационных требований пользователей

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

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

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

2.3.2. Методы нормализации информационных структур пользователей

2.3.3. Методы построения канонической структуры локальных баз данных

2.4. Модели и методы анализа и структуризации предмет ных областей при разработке распределенных баз дан ных

2.4.1. Методы анализа предметных областей пользова телей и построения внешних моделей

2.4.2. Процедуры формирования обобщенной внешней мо дели предметных областей пользователей

2.4.3. Методы структуризации обобщенной внешней мо дели и построения канонической структуры распреде ленных баз данных

2.5.Модели и методы объектно-ориентированного анализа и структуризации предметных областей пользователей баз данных

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

ГЛАВА 3. Модели и методы синтеза оптимальных логических структур локальных, сетевых и распределенных баз

данных

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

3.1.1. Основные определения и формализованное описа ние исходных данных

3.1.2. Методы расчета основных характеристик канони ческой структуры базы данных

3.1.3. Модели синтеза оптимальных логических структур локальных баз данных

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

3.2. Модели и методы синтеза оптимальных логических структур распределенных баз данных и базы метаданных репозитария

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

3.2.2. Модели синтеза оптимальных логических структур распределенных баз данных и структуры размещения базы метаданных репозитария

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

ГЛАВА 4. Модели и задачи синтеза оптимальных физических структур баз данных

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

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

4.3. Задача оптимального распределения кластеров сетевых баз данных между сервером и клиентами ЛВС

4.4. Задачи проектирования физических структур сетевого каталога СБД и базы метаданных репозитария РЕД

4.5. Задача синтеза модулей прикладного программного обеспечения в архитектуре "Клиент-Сервер"

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

262

ГЛАВА 5. Методы управления процессами сопровождения и развития баз данных

5.1. Методы анализа стратегий и выбора оптимальных периодов реорганизации РБД

5.2. Методы реорганизации канонической структуры БД с учетом ограничений на логические структуры баз данных

5.3. Модели и методы реструктуризации канонических структур БД с учетом развития предметных областей пользователей

5.3.1. Методы анализа и модификации информационных структур пользователей при изменении требований на

обработку

5.3.2 Методы анализа новых требований пользователей

и построения обобщенной внешней модели БД

5.3.3. Методы анализа и реструктуризации канонической структуры БД при удалении информационных требований пользователей

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

5.4.1. Моделирование процессов выполнения запросов пользователей и транзакций на языке сетей Петри

5.4.2. Методы анализа процессов обслуживания множества запросов и транзакций

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

351

ГЛАВА б. Разработка методов и алгоритмов решения задач синтеза оптимальных структур баз данных

6.1. Точные алгоритмы решения задач синтеза оптимальных логических структур локальных и сетевых баз данных

6.2. Эвристические алгоритмы решения задач синтеза логических структур локальных и сетевых баз данных

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

6.4. Методы и алгоритмы решения задач синтеза физических структур локальных и сетевых баз данных

6.5. Методы и алгоритмы решения задач синтеза оптимальных логических структур распределенных баз данных и базы метаданных репозитария

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

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

Приложение П1. Современные методы и средства автоматизированного проектирования баз данных АИУС

Приложение П2. Модели и методы анализа и синтеза оптимальных структур баз данных с учетом требований к достоверности и защите данных

П2.1. Основные задачи повышения достоверности информации при проектировании и эксплуатации баз данных

П2.2. Определение достоверности информации при отображении предметной области в каноническую структуру баз

данных

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

жении логической структуры БД в физическую

П2.5. Определение достоверности хранимой в БД информа

ции

П2.6. Задачи синтеза оптимальных логических структур БД с учетом требований к достоверности данных

оптимальных методов контроля данных

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

П2.9. Методы анализа и построения механизмов защиты

канонических структур БД

П2.10. Модели синтеза оптимальных механизмов защиты

логической структуры БД

П2.11. Модели синтеза оптимальных систем защиты физической структуры БД

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

учетом требований к достоверности данных

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

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

Приложение ПЗ. Инструментальные средства автоматизированного проектирования баз данных "АПРОБАЗ"

ПЗ . 1. Модель системы

ПЗ . 2 . Информационное обеспечение системы

ПЗ . 3 . Программное обеспечение системы

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

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

локальных баз данных

Приложение Пб. Методика анализа предметных областей и построения канонических структур распределенных баз

данных

Приложение П7. Методика проектирования реляционных логических структур БД

Приложение П8. Методика проектирования сетевых логических структур БД

Рекомендованный список диссертаций по специальности «Автоматизация и управление технологическими процессами и производствами (по отраслям)», 05.13.06 шифр ВАК

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

ВВЕДЕНИЕ

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

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

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

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

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

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

Диссертационная работа выполнена в соответствии с координационными планами научных исследований АН СССР по комплексной проблеме "Кибернетика" на 1981-1985 гг. и на 1986-1990 гг., раздел 1.12.4 "Разработка методологии проектирования проблемно-ориентированных АСУ"; в рамках общесоюзной научно-технической программы ГКВТИ 0.80.21 на 1985-1990 гг. "Разработка и внедрение комплексов типовых прикладных программных средств общесистемного и функционального назначения, программной технологии и автоматизированных систем проектирования АСУ"; по плану научных работ ИПУ РАН по темам 19-84 "Автоматизация проектирования типовых модульных информационно-управляющих систем" и 198 6 "Методы синтеза типовых модульных систем обработки данных в АСУ"; по заданию 2.11 "Разработка теоретических основ и промышленной технологии автоматизированного проектирования информационного и программного обеспечения на базе типовых модульных СОД" в рамках комплексной программы НТП СЭВ; в соответствии с программой фундаментальных исследований Института проблем информатики и управления Министерства науки - Академии наук Республики Казахстан "Теоретические проблемы информатики, управления и создания информационных систем" (шифр Ф.0083)по плану научно-исследовательских работ по теме "Разработка методов и средств обеспечения информационной безопасности в сетях передачи данных"(номер госрегистрации 0197РК00318).

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

- моделирование предметных областей АИУС, автоматизированную спецификацию информационных требований пользователей, декомпозицию предметных областей и классификацию пользователей;

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

- синтез оптимальных по заданным критериям эффективности логических и физических структур локальных, сетевых и распределенных БД;

- оптимизацию структур БД с учетом требований к достоверности и защите БД;

- оптимизацию управления сопровождением и развитием БД;

- автоматизацию решения задач анализа и синтеза структур БД.

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

Научная новизна. В результате проведенных научных исследований, анализа современных требований к системам баз данных и обобщения опыта разработки и внедрения БД АИУС различного класса и назначения впервые:

- разработаны научно-методические принципы и основные положения промышленной технологии автоматизированного проектирования структур баз данных АИУС;

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

- предложена структура и определены основные характеристики САПР БД, удовлетворяющей современным требованиям к системам БД;

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

- поставлены и решены задачи синтеза оптимальных по различным технологическим и эксплуатационным критериям эффективности логических и физических структур локальных, сетевых в архитектуре «Клиент-Сервер» и распределенных для корпоративных АИУС баз данных при ряде структурных и системных ограничений, а также ограничений целостности данных;

- поставлены и решены задачи синтеза оптимального модульного прикладного программного обеспечения АИУС, оптимальных схем реализации запросов пользователей и транзакций;

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

- поставлены и решены задачи синтеза оптимальных механизмов и систем защиты структур БД от несанкционированного доступа;

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

- разработаны практические методики анализа предметных областей АИУС, синтеза канонических и логических структур реляционных, сетевых и распределенных БД;

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

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

тивность и качество разрабатываемых систем баз данных, сокращает сроки и стоимость создания АИУС.

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

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

Внедрение. Эффективность разработанных в диссертационной работе моделей, методов и инструментальных средств автоматизированного проектирования и управления БД подтверждена положительным опытом их широкого использования на различных объектах информатизации Республики Казахстан, России и Белоруссии. При непосредственном участии автора они внедрены при проектировании, разработке, внедрении и эксплуатации локальных, сетевых и распределенных баз данных АСОИДО для Аппарата Президента и Правительства Республики Казахстан; автоматизированной библиотечной системы для Национальной библиотеки РК; АИУС ЧС для Госкомиссии РК по чрезвычайным ситуациям; сети БД информационно-вычислительной системы (ИБС)"Казпатент"; при создании ряда тематических БД по программе информатизации Республики Казахстан; при создании республиканской ИБС

"Приватизация"; при создании ИБС департамента аттестации научных кадров Министерства науки-Академии наук Республики Казахстан; при создании ряда БД деловой и коммерческой информации и других систем, а также в учебный процесс при подготовке студентов по специальностям "АСУ", "Автоматизация проектирования систем управления", "Базы и банки данных".

Использование разработанных методов и средств позволило существенно сократить временные и стоимостные затраты на разработку и эксплуатацию БД АИУС, повысить качество вырабатываемых проектных решений, а также достоверность данных и защищенность БД от несанкционированного доступа. Официально подтвержденный экономический эффект от внедрения разработанных моделей, методов и инструментальных средств составил свыше 7 9 тыс. рублей (в ценах 198 9 г.), 20 млн. тенге, 300 тыс. рублей РФ, 100 млн. рублей республики Беларусь.

Содержание работы. Содержание работы распределено по главам следующим образом.

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

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

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

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

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

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

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

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

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

цификации запросов и заданий на корректировки в архитектуре "Клиент - Сервер".

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

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

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

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

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

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

рактеристики технологии обработки SQL - запросов в архитектуре "Клиент - Сервер". Результатами решения задачи являются состав и структура модулей ППО (приложений), а также оптимальные схемы реализации SQL - запросов к СБД.

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

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

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

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

/ Ч^ \ Ум/

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

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

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

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

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

В приложении П1 приводится детальный обзор современных методов и средств автоматизированного проектирования баз данных в АИУС.

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

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

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

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

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

цедур проектирования и многовариантности расчетов, наличие встроенной информационной базы проектных данных и метаданных предметных областей (БмД репозитария). Описание системы «АПРОБАЗ» иллюстрируется компьютерными экранными формами (интерфейсом пользователей) , используемыми для решения функциональных задач проектирования БД и принятия решений разработчиками.

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на: пятой и шестой Международных конференциях «Проблемы управления безопасностью сложных систем» (Москва,1998,1999); научно-практической конференции «Управление в XX веке: итоги и перспективы» (Москва,1998); Республиканской конференции «Компьютеризация образования: проблемы и перспективы» (Алма-Ата,19 98); Республиканской конференции «Современные проблемы алгоритмизации»(Ташкент, 1996) ; Международной конференции «Проблемы управления в чрезвычайных конференциях» (Москва, 1992 ) ; Всесоюзной конференции «Системы баз данных и знаний»(Калинин, 1989) ; Международной конференции «Computer-aided control systems design. IFAC/IMACS Workshop» (Alma-Ata,1989); третьей Всесоюзной конференции

«Методы синтеза типовых модульных систем обработки данных» (Москва,1988); 12-ой Всесоюзной школе-семинаре по вычислительным сетям (Алма-Ата, 1987) ; Всесоюзной конференции по автоматизации проектирования систем планирования и управления (Москва, 1987); пятой Всесоюзной школе-семинаре «Распараллеливание обработки информации» (Львов,1985); Всесоюзной конференции по автоматизации систем управления (Ереван, 1984), других совещаниях и конференциях.

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

Структура и объем работы. Диссертационная работа состоит из введения, шести глав, заключения и приложений и содержит 3 98 страниц машинописного текста, 4 5 рисунков, 11 таблиц, а также список литературы (10 стр. наименований) .

Похожие диссертационные работы по специальности «Автоматизация и управление технологическими процессами и производствами (по отраслям)», 05.13.06 шифр ВАК

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Сиротюк, Владимир Олегович

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

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

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

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

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

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

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

448

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

Поставлены и решены задачи синтеза физической структуры БмД репозитария.

Разработана постановка задачи оптимизации синтеза модулей прикладного программного обеспечения приложений и структуры БОЬ-запросов в архитектуре "Клиент-Сервер".

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

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

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

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

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

8. В рамках предложенной промышленной технологии автоматизированного проектирования АИУС разработана система автоматизированного проектирования баз данных (САПР «АП-РОБАЗ») , предназначенная для автоматизации процессов моделирования и анализа предметных областей АИУС, спецификации информационных требований пользователей, концептуального и логического проектирования БД в диалоговом режиме. Разработанная система обеспечивает высокое качество вырабатываемых проектных решений за счет использования формализованных процедур проектирования и многовариантности расчетов, наличия встроенной информационной базы проектных данных и метаданных предметных областей (БмД репозитария) .

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

9. Разработанные в диссертации модели, методы, алгоритмы и инструментальные средства нашли широкое практическое применение при разработке баз данных АИУС широкого класса и назначения (АСОИДО для Кабинета Министров Республики Казахстан, АИУС ЧС для Госкомиссии РК по чрезвычайным ситуациям, ИБС «Казпатент», ИБС «Приватизация», ИБС Департамента аттестации научных кадров Министерства науки-Академии наук РК, АСУ Гродненского ПО «Азот», ЕИИС социального страхования РФ, АСУ страхованием в Венгерской республике и др.), что позволило получить значительный экономический эффект (свыше 20 млн.тенге, 7 9 тыс.рублей (в ценах 1989 г.), 300 тыс. рублей РФ, 100 млн. рублей республики Беларусь).

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

Список литературы диссертационного исследования доктор технических наук Сиротюк, Владимир Олегович, 1999 год

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.

1. Трапезников В.А. Управление и научно-технический прогресс. М.: Наука, 1983. 222 с.

2. Глушков В.М. Введение в АСУ.Киев: Техника,197 4. 318 с.

3. Мамиконов А.Г., Цвиркун А.Д., Кульба В.В. Автоматизация проектирования АСУ. М.: Энергоиздат, 1981. 328 с.

4. Коллинз Г., Блей Дж. Структурные методы разработки систем: От стратегического планирования до тестирования/Пер. с англ. под ред. В.М.Савинкова. М.: Финансы и статистика. 1986. 264 с.

5. Эпштейн В.JI., Сеничкин В.И. Языковые средства архитектора АСУ. М. : Энергоиздат, 1982. 200 с.

6. Мамиконов А.Г., Авен О.И., Кульба В.В., Косяченко С.А. Формализованное представление результатов анализа и проектирования автоматизированных систем управления. М.: Институт проблем управления, 1970.

7. Модин A.A., Зингер И.С., Коротяев М.Ф. Исследование и анализ потоков информации на промышленных предприятиях. М.: Наука, 1970.

8. Мамиконов А.Г., Пискунов А.К., Цвиркун А.Д. Модели и методы проектирования информационного обеспечения АСУ. ■М.: Статистика, 1978.

9. Зингер И.С. Моделирование информационных процессов в системах управления предприятиями. М. : Статистика, 1974 .

10. Столяров Г.К., Калинин B.C., Иванов В. И. Система моделирования банков данных СИМБ7\Д. - Управляющие системы и машины, 1975, № 1, с. 1-5.

11. Липаев В.В., Фидловский Л.А., Филлипович В.В., Шней-дер Б.Н. Отладка систем управляющих алгоритмов ЦВМ реального времени. М.: Советское радио, 1974.-252 с.

12. Косяченко С.А., Кульба В.В., Цвиркун А.Д. Вопросы оптимального планирования системной отладки задач, реализуемых в АСУ. Вопросы создания и проектирования АСУ. Сборник трудов. М. : Институт проблем управления, 1975, вып. 6, с. 122-142.

13. Косяченко С.А., Кульба В.В., Цвиркун А.Д. Оптимизация системной отладки с использованием таблиц решений. Автоматика и телемеханика. 197 4. № 8, с. 171-177.

14. Мамиконов А.Г., Кульба В.В. Синтез оптимальных модульных систем обработки данных. М.:Наука. 1986. 275 с.

15. Мамиконов А.Г., Косяченко С.А., Кульба В.В., Цвиркун А.Д. Отладка и опытная эксплуатация комплексов программ АСУ. Препринт ИПУ. М., 197 9. 78 с.

16. Мамиконов А.Г., Кульба В.В., Косяченко С.А. Типизация разработки модульных систем обработки данных. М. : Наука, 1989, 165 с.

17. Мамиконов А.Г., Кульба В.В., Шелков A.B. Достоверность, защита и резервирование информации в АСУ. М. : Энергоатомиздат, 1986. 304 с.

18. Липаев В.В. Надежность программного обеспечения АСУ. М. : Энергоиздат, 1981. 240 с.

19. А.Г. Мамиконов, В.В. Кульба, С.А. Косяченко, В.О. Си-ротюк и др. Оптимизация структур данных в АСУ. М. : Наука, 1998. 256 с.

20. Косяченко С.А., Кульба В.В и др. Модели и методы проектирования распределенных баз данных (Обзор). АиТ, 1989, N 3, с. 3-58.

21. А.Г. Мамиконов, В.В. Кульба, С.А. Косяченко, И.А. Ужастов. Оптимизация структур распределенных баз данных в АСУ. М.: Наука. 1990.

22. Штрик A.A. CASE: машинное проектирование программного обеспечения. М.: МЦИЭ ИнтерЭВМ. 1990.

23. Липаев В.В., Позин Б.А., Штрик А.А. Технология сборочного программирования. М.: Радио и связь. 1992.

24. Г.Н. Калянов. Структурный системный анализ (автоматизация применения). М.:"Лори". 1996.

25. A.M. Вендров. Практические рекомендации по освоению и внедрению CASE-средств (по материалам стандартов IEEE). СУБД. 1997, N 1, с.62-73.

26. Gibson M.L. The CASE Philosophy. - BYTE. 1989, April, p.209-218.

27. Г. Калянов. Номенклатура CASE-средств и виды проектной деятельности. СУБД, 1997, N2, с.61-64.

28. H.В. Крохин. Современные системы моделирования бизнеса и их применение в реинжениринге. Сети, 1996, N 3-4, с. 140-146.

29. Fisher A.S. CASE: Using Software Development Tools. N.Y.: J.Wiley and Sons Inc., 1988.

30. Harmon P. Object - Oriented CASE. Object - Oriented Strategis V.l, N8, August 1996.

31. Ю.В. Новоженов, М.З. Звонкин, H.H. Тимонин. Объектно-ориентированные CASE - средства. СУБД, 1996, N 5-6, с.119-125.

32. А. Саймон. Репозитарии и управление метаданными. СУБД, 1996, N5-6, с. 154-162.

33. J.Noll, W. Scacchi. Integrating Diverse Information Repositories: Bistributed Hypertext Approach. IEEE Computer (December 1991).

34. Дэвид А. Марка, Клемент МакГоуэн. Методология структурного анализа и проектирования: Пер. с англ. М. "Ме-татехнология", 1993.

35. ORACLE - интегрированная среда проектирования и разработки приложений. - Технология "Клиент - Сервер", 34 квартал 1996 г., с.20-26.

36. C.B. Горин, А.Ю. Тандоев. Применение CASE-средства ERWin 2.1 для информационного моделирования в системах обработки данных. СУБД, 1995, N3.

37. Booch G. Object - Oriented Analysis and Design with Applications. - Bengamin/Cummings, Redword City, CA, USA, 1994.

38. Rumbaugh J., Blaha M. Object - Oriented Modeling and Design. - Prentis Hall Englewood Cliffs, NJ, 1991.

39. Jacobson I. et al. Object - Oriented Software Engineering. Addison-Wesley Reading, MA, 1992.

40. Штрик A.A. Зарубежные CASE-средства создания программного обеспечения в отечественных разработках. Монитор, 1993, N 3.

41. Морозова А. Отечественные CASE - средства разработки проектов информационных систем. Монитор, 1993, N 7-8, с.8-13.

42. Д. Мейер. Теория реляционных баз данных: Пер. с англ. М.: Мир, 1987.

43. С.Д. Кузнецов. Введение в СУБД. СУБД, 1996, N5-6, с. 136-153.

44. Базы данных: достижения и перспективы на пороге 21-го столетия/ Под ред. А. Зильбершатца, М. Стоунбрейкера, Д. Ульмана. СУБД, 1996, N 3, с. 103-117.

45. X. Дарвин, К. Дейт. Третий манифест. СУБД, 1996, N 1, с.110-123.

46. Е.З. Зиндер. Новое системное проектирование: информационные технологии и бизнес-реинжениринг. СУБД, 19 96, N 1, с. 55-67.(часть вторая), СУБД, 1996, N 2, с.61-76 (часть третья).

47. Е.З. Зиндер. Проектирование баз данных: новые требования, новые подходы. СУБД, 1996, N 3, с.10-22.

48. Hammer M., Champy J. Reengineering the Corporation. A Manifesto for Business Revolutions. HarperBusiness, 1993.

49. М.Ш. Цаленко. Моделирование семантики в базах данных. М: Наука, 1989.

50. А. В. Замулин. Системы программирования баз данных и знаний. Новосибирск: Наука, Сиб. отд-ние, 1990.

51. А. Цикритзис, Ф. Лоховски. Модели данных.: Пер. с англ. М.: Финансы и статистика, 1985.

52. П. Грей. Логика, алгебра и базы данных.: Пер. с англ. М.: Машиностроение, 1989.

53. Хаббард Дж. Автоматизированное проектирование баз данных.: Пер. с англ. М.: Мир, 1984.

54. Сиротюк В. О. Задачи оптимального проектирования баз данных. В сб.: Проблемы проектирования банка данных АСПР республики. Алма-Ата, 1990. С. 17-3 9.

55. Л.А. Калиниченко, В.М. Рыбкин. Машины баз данных и знаний. М.: Наука, 19 90.

56. А. Саймон. Обработка транзакций. СУБД, 19 97, N2, с. 70-82.

57. J-C. Freytag et al. Query Processing for Advanced Database Systems. San Mateo, CA: Morgan Kaufman, 1993.

58. P.A. Bernstein et al. Concurrency Control and Recovery in Database Systems. Reading, MA: Addison Wesley, 1987.

59. Ш. Атре. Структурный подход к организации баз данных.: Пер. с англ. М.: Финансы и статистика, 1983.

60. Тиори Т., Фрай Дж. Проектирование структур баз данных. В 2 кн.: Пер. с англ. М.: Мир, 1985.

61. Mitoma M.F., Irani К.В. Automatic data base schema design and optimization. - Proc. Intern. Conf. Very Large Data Bases. Massachusetts, 1975, p.286-321.

62. Б. Нанс. Компьютерные сети: Пер. с англ. М. : "Бином", 19 95.

63. С.В. Орлик. Многоуровневые модели в архитектуре клиент-сервер. СУБД, 1997, N 1, с.74-77.

64. Г. Ладыженский. Технология "клиент-сервер" и мониторы транзакций. Открытые системы, 1994, лето, с.4-12.

65. В.И. Артемьев. Обзор способов и средств построения информационных приложений. СУБД, 1996, N5-6, с.52-67.

66. Davenport R.A. Distributed data base technology - a survey. Computer Networks, 1978, v.2, v.3, p.155-167.

67. M. Тамер Оззу, П. Валдуриз. Распределенные и параллельные базы данных. СУБД, 1996, N4, с.4-2 6.

68. Дж. Мартин. Вычислительные сети и распределенная обработка данных: Пер. с англ. Вып.1,2. М. : Финансы и статистика, 1985, 1986 гг.

69. Prabndha D., Haseman W.B., Kriebel С.Н. Toward on optimal design of network data base from relational descriptions. Operations Research, 1978, v.26, N5, p. 805-823.

70. Шаймарданов P.Б. Моделирование и автоматизация проектирования структур баз данных. М. : Радио и связь, 1984 .

71. Калиниченко Л.А. Методы и средства интеграции неоднородных баз данных. М.: Наука, 1983.

72. В. Ивлев, Т. Попова Построение бизнес-систем. Типовые технические решения. Компьютер-Пресс, 1996, июль, с. 84-90.

73. Akoka J. Design of optimal distributed Data Bases. -International Symposium on distributed Data Bases. Paris: North-Holland Publ. Co., INRIA, 1980, p.229-246.

74. В. Елисеев, Г. Ладыженский. Введение в Интранет. СУБД, 1996, N5-6, с.19-43.

75. С.Д. Кузнецов. Доступ к базам данных с использованием технологии WWW. СУБД, 1996, N5-6, с.4-9.

76. A.Tannenbaum. Implementing A Corporate Repository: The Models Meet Reality. New York: John Wiley and Sons, 1993.

77. Информационная технология. Структура системы словаря информационных ресурсов (IRDS). ГОСТ Р ИСО/МЭК 1002193.

78. Б. Леонг-Хонг, Б. Плагман. Системы словарей-справочников данных: Пер. с англ. М. : Финансы и статистика, 1986.

79. C.B. Горин, А.Ю. Тандоев. CASE-средство S-Designor 4.2 для разработки структуры базы данных. СУБД, 1996, N 1, с.79-86.

80. А. Фомичев. S-Designor 5.0 - модулвный CASE инструмент для анализа, проектирования и разработки информационных систем. - Технология "Клиент - Сервер", 3-4 квартал 1996 г., с.3-9.

81. Морозов В.П. Особенности проектирования систем обработки экономической информации на базе ЕС ЭВМ. М. : Финансы и статистика, 1982.

82. С. Бемер. MS Access 2.0: Пер. с нем.: Санкт-Петербург, Изд-во "BHV", 1995.

83. Microsoft Visual FoxPro. Руководство пользователя. Техническая документация.

84. Геловани В.А., Безруков Д.И., Бритков В. Б. и др. Интерактивная разработка информационных систем. Техническая кибернетика, 1986, N 2.

85. Бойко В.В., Цветков C.B., Глазов A.B. Дизайнер баз данных. IV Всесоюзная конференция "Системы баз данных и знаний". Тезисы докладов. Калинин, 1989.

86. Семейство САПР "Синтез": Каталог организаций и программных средств, экспонируемых на международной выставке-ярмарке SOFTOOL -91. М.: ВДНХ СССР, 1991.

87. Кабаков Ю.Б., Медведева А.И., Фурман Г.И. КОМОД-91 -система поддержки концептуальных схем и гипертекстов. УСиМ, 1991, N 7.

88. Алтухова А.Н., Чумаков Ю.С. СЛОВАРВ ПРОЕКТА - CASE -средство для аналитиков и проектировщиков баз данных. Семинар "CASE - технология". Сб. материалов. М.: 1992.

89. CASE. Аналитик для IBM PC. Руководство аналитика. -М. :"Эйтекс", 1993.

90. A.A. Сахаров. Концепция построения и реализации информационных систем, ориентированных на анализ данных. СУБД, 1996, N4, с.55-70.

91. А. Тимонин. Распределенные хранилища данных. СЮ (русское издание), 1997, N 2-3, с. 10-13.

92. А. Константинов. Интегрированная технология хранилищ данных. СЮ (русское издание), 1997, N 2-3, с. 17-19.

93. Ашимов A.A., Сиротюк В.О., Горковенко Е.В. Программно-технологический комплекс автоматизированного проектирования БД. В сб.: Программно-алгоритмическое обеспечение АСУ. Алма-Ата: НИИ АСПУ, 1991, с.17-34.

94. Сиротюк В.О., Китапбаев Ж.Б., Горковенко Е.В., Выш-кварко С.С. Models, Methods and Designing and Maintain-nance of the Databases. В сб.: Доклады Национальной академии наук республики Казахстан. Алма-Ата: HAH PK, 1993, N 6, с.19-23.

95. Сиротюк В.О., Курманов Б.К., Шангитбаев Ж.К. Имитационные средства оценки качества проектных решений при разработке баз данных интегрированных АСУ. Учебное пособие. Алма-Ата: КазПТИ, 1989. 95 с.

96. Сиротюк В.О. Модели и методы синтеза оптимальных логических структур и базы метаданных репозитария распределенных баз данных в АСУ. Автоматика и телемеханика. М. : 1999, № 1, с. 166-186.

97. Кульба В.В., Сиротюк В.О., Ковалевский С.С. Синтез оптимальных логических структур и базы метаданных репозитария распределенных баз данных. «Компьюлог», 19 98, № 2, с. 52-67.

98. Кульба В.В., Сиротюк В.О., Горковенко Е.В. и др. Промышленная технология и CASE-средства автоматизированного проектирования баз данных. Препринт. М. : ИПУ РАН, 1998, 120 с.

99. Мандель И.Д. Кластерный анализ. М. : Финансы и статистика, 1988, 176 с.

100. Кристофидес Н. Теория графов: алгоритмический подход: Пер. с англ. М.: Мир, 1978, 432 с.

101. Мелихов A.M. Ориентированные графы и конечные автоматы. М.: Наука, 1971, 416 с.

102. Уилсон Р. Введение в теорию графов: Пер. с англ. М. : Мир, 1977.

103. Берзтисс А.Т. Структуры данных: Пер. с англ. М. : Статистика, 1974, 408 с.

104. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1968, 368 с.

105. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наук. Думка, 1981, 287 с.

106. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М. : Наука, 1976, 283 с.

107. Агибалов Г.П., Беляев В.А. Технология решения комбинаторно-логических задач методом сокращенного обхода дерева поиска. Томск: Изд-во Том. Ун-та, 1981, 125 с.

108. Коробков Б.П., Растригин JI.A. Рандомизированные методы разрезания графов//Изв. АН СССР. ТК, 1982, 4.1. №3, с.163-172; 4.2. №4, с.120-126.

10 9. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. М.: Мир, 1981, 323 с.

110. Мамиконов А.Г., Деметрович Я., Кульба В.В. и др. Использование сетей Петри при проектировании систем обработки данных. М.: Наука, 1988, 103 с.

111. Котов В.Е. Сети Петри. М.: Наука, 1984, 160 с.

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ (АВТОМАТИКИ И ТЕЛЕг ^^ЩХАНИКИ) им. В.А. Трапезникова

Президиум ВАК~Россми

| (решение от" • О ? №

| присудил ученум степень ДОКТОРА I

РАЗРАБОТКА МОДЕЛЕЙ, МЕТОДОВ И ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ АНАЛИЗА И СИНТЕЗА ОПТИМАЛЬНЫХ СТРУКТУР БАЗ ДАННЫХ В АВТОМАТИЗИРОВАННЫХ ИНФОРМАЦИОННО -УПРАВЛЯЮЩИХ СИСТЕМАХ.

Специальность 05.13.06 "Автоматизированные системы управления".

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