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



российская академия наук институт проблем управления (автоматики и телемеханики) им. в.а. трапезникова

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

^ х^езидиум ВАК России

(решение от" " & ^

присудил ученую степень Д09ОТХГОА

--/^л л Д11М I I г

Начальник управления ВАК России

)вич

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

управляющих системах.

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

диссертация на соискание ученой степени доктора технических наук.

Научный консультант доктор технических наук, профессор в.в. Кульба

Москва, 1999 г.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ ......................................... 9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

данных............................................ 160

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

262

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

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

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

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

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

обработку....................................... 301

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

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

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

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

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

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

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

351

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ..........................................................................448

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

ПРИЛОЖЕНИЯ..........................................................................4 65

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

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

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

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

данных......................................... 524

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

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

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

ции............................................. 531

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

данных......................................... 699

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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