Содержание к диссертации
Введение
1. Анализ проблемы организации мобильных распределенных баз данных автоматизированных информационно-управляющих систем МЧС России 18
1.1. Информационная инфраструктура системы управления МЧС | (на примере Северо-Западного региона) 18 |
1.2. Архитектура распределенных баз данных 35
1.3. Система свойств информационного процесса 49
1.4. Современные технологии структурных модификаций распределенных баз данных 58
1.5. Формулировка и декомпозиция научной проблемы исследования 72
2. Основы теории мобильных распределенных баз данных 85
2.1. Структура теории мобильных распределенных баз данных 85
2.2. Понятийный аппарат теории мобильных распределенных баз данных 92
2.3. Принципы построения мобильных распределенных баз данных 95
2.4. Концептуальная модель мобильной распределенной базы данных 99
2.5. Показатели эффективности реструктуризации мобильной распределенной базы данных 109
3. Анализ и синтез мобильных распределенных баз данных 112
3.1. Модель реализации запросов к мобильным распределенным базам данных 113
3.2. Модель решения задач в автоматизированнойинформационно-управляющей системе 131
3.3. Метод выбора стратегии размещения мобильных распределенных баз данных 141
3.4. Метод и модель синтеза структуры мобильных распределенных баз данных 150
4. Динамическое управление мобильными распределенными базами данных 165
4.1. Концептуальная модель динамического управления структурой мобильных распределенных баз данных 165
4.2. Метод и алгоритм динамического планирования локального представления структуры мобильных распределенных
баз данных 174
4.3. Метод и алгоритм децентрализованного управления размещением фрагментов данных на серверах базы данных 183
4.4. Метод и алгоритм определения моментов проведения реструктуризации мобильных распределенных баз данных 190
4.5. Оценка качества алгоритмов динамического управления структурой мобильных распределенных баз данных 194
5. Обеспечение целостности мобильных распределенных баз данных 198
5.1. Содержание процессов обеспечения целостности данных 198
5.2. Метод обеспечения целостности 207
5.3. Алгоритмы оптимизации выполнения запросов и восстановления целостности данных 219
6. Применение мобильных распределенных баз данных 225
6.1. Методика оценки эффективности мобильных распределенных баз данных 225
6.2. Результаты модельных исследований мобильных распределенных баз данных 237
6.3. Рекомендации по архитектурному построению системы управления реструктуризацией 246
6.4. Рекомендации по технологии реструктуризации 248
Заключение 253
Список использованных источников 259
Приложение
- Современные технологии структурных модификаций распределенных баз данных
- Понятийный аппарат теории мобильных распределенных баз данных
- Модель решения задач в автоматизированнойинформационно-управляющей системе
- Алгоритмы оптимизации выполнения запросов и восстановления целостности данных
Введение к работе
Актуальность работы. За последние десятилетия произошли кардинальные изменения в управлении силами и средствами МЧС. Информатизация мероприятий повседневной деятельности и операций при ликвидации чрезвычайных ситуаций приобрела статус решающего фактора.
Информационное обслуживание пользователей - должностных лиц органов управления - осуществляется на основе концепции баз данных (БД). С переходом к сетевым технологиям начали развиваться распределенные базы данных (РБД). При их создании и применении стремятся к обеспечению эффективного обслуживания пользователей, работающих в различных точках пространства, а именно, к своевременному и полному удовлетворению потребности в информации.
Автоматизированные информационно-управляющие системы (АИУС) на основе РБД обладают повышенной устойчивостью и оперативностью. Однако большинство РБД строится в расчете на стабильную структуру сети и постоянное размещение пользователей. Такое допущение облегчает решение задач построения РБД и оптимизации выполнения запросов к ней. В то же время динамика повседневной работы органов управления и их действий в критических условиях предполагает как штатное, так и внезапное изменение структуры системы управления и ее информационной инфраструктуры.
В этом случае применение традиционной методологии построения и управления РБД не гарантирует успешного выполнения запросов к базе данных, что незамедлительно приведет к снижению эффективности управления силами и средствами МЧС в автоматизированном режиме.
Подобное состояние обусловлено тем, что существующие методы построения РБД ориентированы на устоявшиеся технологии. Сдерживание их перспективного развития объясняется следующими причинами.
Во-первых, значительным дисбалансом между нисходящим и восходящим методами проектирования РБД в сторону последнего. При этом построение РБД сводится к интеграции нескольких локальных БД. Реет-
руктуризация такой базы требует ее реновации. Реализация нисходящего метода, в свою очередь, опирается на положение о стабильности условий, что приводит к статичности структуры РБД.
Во-вторых, преимущественным использованием промышленно выпускаемых систем управления распределенными базами данных (СУРБД), для которых вопросы оперативности обработки информации не всегда являются доминирующими.
В-третьих, недостаточной проработкой методологических основ построения РБД и управления ими в условиях активного перемещения пользователей и деформации структуры сети.
Таким образом, возникает противоречие между потребностями должностных лиц в оперативном, полном, достоверном и безопасном обеспечении информацией в динамически изменяющихся условиях обстановки, с одной стороны, и ограниченными возможностями существующей технологии РБД, с другой стороны, что порождает проблему организации мобильных распределенных баз данных (МРБД). Эти базы данных будут наделены способностью к динамической реструктуризации в целях своевременного и полного удовлетворения запросов от всех категорий пользователей, включая и подвижных, в условиях нестабильности структуры системы управления и, следовательно, ее информационной инфраструктуры.
Разработка и внедрение в практику МРБД позволит повысить оперативность и устойчивость информационного процесса и усовершенствовать технологию решения задач управления силами и средствами МЧС. При этом предполагается, что гарантированно будут обеспечены, с одной стороны, сохранение целостной логической структуры РБД, а с другой стороны, - реструктуризация базы данных на физическом уровне в интересах оптимального выполнения запросов.
Таким образом, проблема организации МРБД является одной из основополагающих проблем, решаемых при комплексной информатизации МЧС России.
В настоящее время уместно вести речь о прочном становлении технологии БД, которая имеет под собой солидный теоретический фундамент. Значительный вклад в развитие общей теории баз данных, внесли зарубежные исследователи Дж. Мартин {Martin J.), К. Дейт {Date С), Э. Кодд (СoddЕ.), Дж. Ульман {UllmanJ.), Д. Цикритзис {Tsichritzis D.), С. Чери {CeriS.) и др. Среди отечественных специалистов в области БД следует отметить Мамиконова А.Г., Калиниченко Б.О., Цегелика Г.Г., Галатенко В.А., Ладыженского Г.М., Кузнецова С.Д., Сахарова С.С. Представителями Санкт-Петербургской научной школы информационных систем и БД по праву считают Артамонова B.C., Яшина А.И., Саен-ко И.Б., Котенко И.В., Лычагина Н.И., Ломако С.Г. и других.
Несмотря на внушительный научный задел в указанной области исследований, методологические основы решения проблемы реструктуризации РБД в настоящее время не разработаны и находятся в стадии становления. Тем не менее, для создания таких основ сложились объективные предпосылки, к числу которых следует отнести:
формирование общей концепции единого информационно-функционального пространства органов управления МЧС России;
наличие обширного арсенала средств и технологий, обеспечивающих работу мобильных пользователей в информационно-телекоммуникационных сетях;
разработку и доведение до практической реализации механизмов отображения и синхронизации данных, таких как репликация;
разработку и публикацию отечественными и зарубежными учеными методов организации РБД, которые могут найти отражение в общей методологии МРБД.
В совокупности это определяет актуальность темы настоящего диссертационного исследования.
Цель диссертационной работы состоит в решении научной проблемы, заключающейся в разработке концепции мобильных распределенных баз данных, а также моделей и методов их организации, как основы мето-
дологии структурных трансформаций МРБД при изменении условий функционирования, применение которой позволит разрешить противоречие между потребностями должностных лиц органов управления МЧС в своевременном получении информации в динамически изменяющейся обстановке, с одной стороны, и ограниченными возможностями существующей технологии РБД, с другой стороны, и обеспечит повышение эффективности использования информационного обеспечения АИУС МЧС.
Объектом исследования являются распределенные базы данных автоматизированных информационно-управляющих систем МЧС России.
Предмет исследования составляют эмпирические факты, закономерности, модели и методы построения МРБД и управления ими в АИУС МЧС России.
Декомпозиция научной проблемы привела к необходимости постановки и решения следующих научных задач:
-
исследование необходимости и возможности реализации структурных изменений РБД в интересах повышения эффективности функционирования АИУС МЧС;
-
разработка основ теории МРБД;
-
разработка моделей и методов анализа и синтеза МРБД;
-
разработка модели, методов и алгоритмов динамического управления МРБД;
-
разработка метода и алгоритмов обеспечения целостности МРБД;
-
разработка методики оценки эффективности МРБД;
-
формирование научно-обоснованных рекомендаций по применению МРБД.
При проведении исследований использовались методы теории множеств, теории вероятностей и математической статистики, теории массового обслуживания, теории систем, теории случайных процессов, теории распределений, теории принятия решений, теории эффективности.
Результатами диссертационного исследования, полученными автором лично и выносимыми на защиту в форме научных положений, определяющих методологические основы организации МРБД, являются следующие.
-
Концепция мобильных распределенных баз данных, включающая в себя систему понятий в области МРБД, концептуальную модель МРБД, систему показателей эффективности и позволяющая сформировать общую методологию решения научной проблемы.
-
Модели и методы анализа и синтеза МРБД, обеспечивающие расчет значений показателей оперативности АИУС, выбор стратегии размещения базы данных в сети и нахождение оптимального варианта структуры МРБД в случае централизованного управления реструктуризацией.
-
Модель и методы динамического управления структурой МРБД, позволяющие выработать общий подход к управлению размещением фрагментов данных (ФД) без перерывов в обслуживании запросов, осуществлять поиск структуры базы данных, близкой к оптимальной, путем последовательных улучшений, формировать решение на перераспределение ФД по критерию минимизации сетевого трафика, а также назначать моменты проведения реструктуризации на основе линейной модели роста эффекта и затрат.
-
Метод и алгоритмы обеспечения целостности МРБД, направленные на формирование плана прохождения запросов по двойному критерию - максимум вероятности своевременного выполнения и минимум среднего времени реализации в случае равенства вероятностей, а также на выбор варианта восстановления данных из двух возможных - путем полного копирования или расчетными методами.
-
Научно-практические предложения по оценке МРБД, позволяющие оценивать эффективность применения таких баз данных в аспекте выполнения предъявленных к ним требований и с позиций обеспечения результативности АИУС.
Научная новизна работы определяется следующим.
-
Впервые разработана концепция мобильных распределенных баз данных, на содержательном уровне определяющая цели, функции и показатели эффективности реструктуризации распределенных баз данных, позволяющая исследовать закономерности организации МРБД и в теоретическом отношении определяющая методологию их построения и обеспечения функционирования.
-
Разработаны новые математические модели и методы анализа и синтеза МРБД, модель системы управления реструктуризацией и методы, реализующие процесс динамического управления, а также методы и алгоритмы поддержания целостности базы данных, которые в совокупности составляют методологию решения проблемы организации мобильных распределенных баз данных и обеспечивают возможность повышения эффективности АИУС.
-
При разработке моделей и методов построения МРБД применены и получили развитие методы теории массового обслуживания, теории распределений, математического программирования, теории принятия решений. Задача синтеза структуры МРБД приведена в новой постановке и для ее решения предложен оригинальный метод, который ранее в области разработки структуры распределенных баз данных не применялся.
-
При разработке методологии управления реструктуризацией предложен новый подход - динамическое управление, основанный на решении задачи оптимизации методом последовательных улучшений и использующий принцип децентрализованного управления, а также реализующий поиск на множестве возможных вариантов с помощью модифицированного метода решения известной задачи линейного программирования.
-
Обоснована предпочтительность перехода к динамическому управлению реструктуризацией, позволяющему изменять структуру МРБД без перерывов в выполнении запросов и без существенного снижения значений показателей эффективности (ПЭ).
-
Предложен метод обеспечения целостности, основанный на поиске множества планов выполнения запросов с выбором предпочтительного по двойному критерию с возможностью восстановления данных без их полного копирования.
-
При разработке методики оценки эффективности МРБД использован подход к определению критерия эффективности на основе зависимых по полезности показателей эффективности,
Практическая ценность работы обусловлена следующим:
формированием экспериментально проверенных на моделях предложений по использованию полученных результатов в распределенных базах данных существующих и перспективных АИУС;
возможностью постановки и решения практических задач построения МРБД на основе разработанных методологических основ;
доведением полученных результатов до практических алгоритмов и возможностью их реализации в существующих и перспективных АИУС.
Достоверность результатов диссертационной работы обеспечена:
использованием системного подхода при изучении объекта исследования;
корректностью постановок задач и применением математических методов их решения;
полнотой учета совокупности и характера факторов, влияющих на информационный процесс и АИУС;
общностью и полнотой представленных моделей, методов и алгоритмов построения и управления МРБД, позволяющих на единой основе решать задачи реструктуризации базы данных в режиме, близком к реальному времени;
непротиворечивостью предлагаемых решений известным результатам, полученным другими способами.
Публикации. Результаты диссертационного исследования опубликованы в монографии, 19 статьях в журналах и научно-технических сборниках, 14 сборниках докладов международных, всероссийских и ве-
домственных научно-технических конференций. Список 40 основных работ приведен в конце автореферата.
Реализация. По результатам работы получены акты реализации от следующих организаций: Северо-Западный региональный центр МЧС России, ГУП НИИ «Рубин», ОАО «Институт сетевых технологий»,
Научные результаты и разработанные в рамках диссертационного исследования модели, методы и алгоритмы реструктуризации МРБД внедрены в учебный процесс Санкт-Петербургского университета Государственной противопожарной службы МЧС России и Военной академии связи.
Апробация. Результаты диссертационной работы докладывались и обсуждались на II Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2006 г.), Международной конференции по мягким вычислениям и измерениям SCM-2005 (Санкт-Петербург, 2005 г.), I Научно-практической конференции Военной академии связи (Санкт-Петербург, 2005 г.), Международной конференции по мягким вычислениям и измерениям SCM-2003 (Санкт-Петербург, 2003 г.), Международной научно-практической конференции «Проблемы обеспечения безопасности при чрезвычайных ситуациях» (Санкт-Петербург, 2003 г.), II Международной научно-практической конференции «Экономика и инфокоммуникации в XXI веке» (Санкт-Петербург, 2003 г.), 2-ой Всероссийской научной конференции «Проблемы развития информационно-телекоммуникационных систем специального назначения» (Орел, 1999 г.), а также ряде других конференций и семинаров.
Структура и объем работы. Диссертационная работа состоит из введения, шести разделов, заключения, списка литературы и пяти приложений. Диссертация изложена на 277 страницах основного текста, содержит 77 рисунков, 11 таблиц и список литературы из 194 наименований.
Современные технологии структурных модификаций распределенных баз данных
Анализ условий функционирования РБД в рамках АИУС показывает необходимость наличия не статичной, а динамически изменяемой структуры базы данных. В таком случае придание гибкости структуре РБД позволит обеспечить выполнение требований реактивности базы данных и, тем самым, повысить оперативность АИУС и своевременность информационного процесса в целом в различных условиях обстановки. Вопросы изменения структуры РБД должны рассматриваться в двух аспектах:
Во-первых, при проектировании необходимо учитывать возможность изменения физической структуры РБД в процессе эксплуатации. Следовательно, на данном этапе необходимо решать задачи оптимизации размеров ФД, определения оптимальной степени дублирования ФД по серверам в соответствии с принятым критерием и стратегией размещения, а также предусматривать средства управления их размещением;
Во-вторых, для непосредственного изменения структуры РБД в процессе ее функционирования необходимо предусмотреть средства, позволяющие СУРБД проводить оперативное изменение размещения ФД в автоматизированном или автоматическом режиме.
Если первый аспект в определенной мере исследован [20,22], то второй — практически не получил должного освещения в научных изысканиях. Учитывая, что после разработки и внедрения РБД единственным способом обеспечения выполнения требований является ее модификация, целесообразно сосредоточить внимание именно на этом вопросе.
Структурная модификация представляет собой изменение концептуальной, логической или физической структуры базы данных. Изменение концептуальной или логической структуры называется реструктурированием, а изменение физической структуры — реформатированием [20,78]. Следует заметить, что термин «реформатирование» обычно употребляют применительно к ЛБД, физическая структура которых представляется совокупностью файлов на внешних носителях компьютера. Другой смысл понятия «физическая структура» для РБД, как совокупность фрагментов данных, размещаемых в узлах компьютерной сети, позволяет в дальнейшем использовать единый термин —реструктуризация.
Проведение реструктуризации может улучшить баланс загрузки СБД, уменьшить время чтения и/или модификации данных и, следовательно, повысить эффективность использования РБД.
Необходимость реструктуризации может возникнуть по ряду оперативных (внешних) и технологических (внутренних) причин. Оперативные причины рассмотрены ранее (см. пар. 1.3).
Основными технологическими причинами проведения реструктуризации базы данных являются следующие.
Изменение связей между объектами. Это может быть следствием возложения на ДЛ органов управления дополнительных задач или корректировки перечня существующих. В свою очередь пересмотр задач может потребовать выполнения запросов новых типов, не предусмотренных на этапе проектирования РБД. Таким образом, меняются информационные потоки между узлами сети.
Добавление новых типов данных. В этом случае может потребоваться увеличение размеров логических и физических записей для включения в них новых типов элементов данных.
Создание новой базы данных на основе имеющихся. Такая ситуация возможна при разработке или модификация РБД на основе существующих самостоятельных и разнотипных ЛБД. Это характерно для ранних этапов внедрения АИУС в практику управления. При этом базы данных могут поддерживаться различными СУБД, иметь разные форматы записей, следовательно, их интеграция потребует проведения преобразований.
Изменение характера доступа к данным, например, модификация метода доступа к некоторым ФД, создание дополнительных индексов, изменение методов актуализации данных.
Увеличение объема данных. В таком случае БД может быть частично перераспределена между другими СБД или же перенесена на более быстродействующие запоминающие устройства повышенной емкости.
Результаты анализа эффективности обработки запросов к РБД. В этом аспекте может быть обнаружена необходимость настройки или повторного выбора физических параметров БД, таких, как способ индексирования или размер блока, а также перераспределение ФД.
Деградация баланса загрузки СБД. Может возникнуть в результате изменения частоты запросов к ФД, структуры и характеристик элементов сети. Изменение критериев эффективности размещения ФД по серверам базы данных.
При проведении реструктуризации РБД целесообразно выделить три основных уровня абстракции, соответствующих этапам проектирования базы данных: концептуальный, логический и физический [22]. Таким образом, допустимо вести речь о концептуальной, логической или физической реструктуризации.
Понятийный аппарат теории мобильных распределенных баз данных
Основу теории составляет понятийный аппарат, представляющий собой множество первичных терминов и формируемых на их основе новых понятий и их определений, используемых при описании объекта и предмета теоретического исследования. Введение и развитие подобного аппарата позволяет при формировании теоретических положений, корректно оперировать фиксированным набором понятий, имеющих четкое и однозначное толкование применительно к предметной области исследований.
На рис. 2.3 показан принцип формирования системы понятий, в соответствии с которым, множество первичных понятий получено путем заимствования из смежных областей терминов, необходимых для введения новых понятий теории МРБД.
Полученная в результате система понятий теории МРБД представлена рис. 2.4. Первичность заимствованных терминов определяется необходимостью сохранения их традиционного смысла при использовании в рамках новой системы понятий.
Основополагающими терминами новой теории выступают понятия «мобильность» и «мобильный». В различных областях знания эти термины трактуются по-разному. «Мобильность» означает свойство объекта, характеризующее его способность к перемещению, изменению характера своих действий в зависимости от смены обстановки [101]. Наиболее общий смысл понятия «мобильный» - это «подвижный, способный к быстрому и скорому передвижению, действию» или «способный быстро ориентироваться в обстановке, готовый быстро выполнить задачу; способный быстро действовать, принимать решения» [101]. В теории вычислительных систем термин «мобильный» является синонимом понятия «машинонезависимыи» и служит для описания способности программных средств к переводу на другие ЭВМ [102]. В ряде случаев понятие «мобильный» отождествляют с понятиями «подвижный», тем самым, сужая его смысл.
Корректным представляется подход, принятый в области систем связи. Средства и комплексы связи, способные вести работу в движении обычно называют «носимыми», «возимыми» или «бортовыми» в зависимости от назна-чения и типа транспортировки. Термин «мобильность» зарезервирован за определением свойства системы связи, характеризующим ее способность к развертыванию, свертыванию и изменению структуры во время функционироватія [103]. Таким образом, независимо от степени подвижности узлов сетей связи, система считается отвечающей требованию мобильности, если ее структура может трансформироваться, например, за счет перераспределения каналов связи между узлами. Применение такого подхода к объекту исследования позволяет перейти к определению понятия «мобильная распределенная база данных».
Собственно база данных определяется как многоаспектная идентифицированная совокупность структурированных данных, относящихся к некоторой предметной области [73,104]. Сущность концепции баз данных выражается в интеграции данных и централизации управления ими.
Под предметной областью понимают один или несколько объектов управления (или определенные их части), информация которых моделируется с помощью БД и используется для решения различных функциональных задач.
Система управления базами данных — совокупность программных средств, предназначенных для создания, ведения и совместного использования БД многими пользователями. В свою очередь, распределенная база данных — это логически интегрированная база данных, физически размещаемая на нескольких территориально распределенных компьютерах сети [72,73]. С понятием распределенных баз данных неразрывно связано понятие логической и физической структур базы данных, а также ее фрагментов. Логическая структура РБД — совокупность взаимосвязанных объектов базы данных (таблиц, запросов и т.п.), формируемых на этапе логического проектирования. Логическим фрагментом называют часть базы данных, формируемую на этапе фрагментирования логической структуры РБД. Для реляционной базы данных фрагментом может выступать набор таблиц, таблица, совокупность столбцов или строк таблицы, а также различные сочетания этих объектов. Физическим фрагментом или фрагментом данных считают копию логического фрагмента, размещаемую в узле сети. Физическая структура РБД — совокупность взаимосвязанных физических фрагментов данных, размещаемых в узлах сети; отображение логической структуры базы данных на физическую структуру сети. В этом случае мобильными фрагментами данных (МФД) называют физические фрагменты данных, которые могут перемещаться (копироваться) с одного узла сети на другой в процессе работы АИУС без непосредственного участия пользователей. Введенные понятия позволяют дать определение мобильной распределенной базе данных как распределенной базе данных, отдельные фрагменты данных которой могут перемещаться (копироваться) с одного узла сети на другой; при этом сохраняется логическая интеграция данных и их безусловная доступность пользователям в пределах прав доступа (последнее положение характерно для всех распределенных баз данных). Мобильный пользователь — это пользователь, который может менять свое пространственное положение по отношению к узлам сети, в которой размещается база данных. Реструктуризация МРБД определяется как процесс изменения физической структуры МРБД за счет миграции мобильных фрагментов данных. Проведение реструктуризации МРБД направлено на получение ее оптимальной структуры — такого варианта физической структуры, при котором обеспечивается выполнение требований к информационному процессу, реализуемому с помощью базы данных.
Модель решения задач в автоматизированнойинформационно-управляющей системе
Узел 0 является начальным, а узел к+\ — конечным. Каждому узлу ставится в соответствие вектор, определяющий параметры закона распределения времени его обработки. Дуги характеризуются вероятностями/?w перехода от к-то запроса к 7-му {к = О,К\1 = \,К +1). Если из узла выходит единственная дуга, то переход по ней идет с вероятностью, равной 1. Если из узла выходит несколько дуг (к,Г), (k,m),...,(k,w), то выбор направления рассматривается как случайное событие, характеризуемое вероятностями исходов рм, Ркт-,---,Ры, Определение вероятностно-временных показателей решения задач в АИУС состоит в нахождении значений функции распределения времени по характеристикам элементов модели. Исследование представленной модели возможно с помощью аппарата марковских цепей [127]. При этом задача сводится к расчету числовых харак- теристик многомерной случайной величины Х=(Х],х2, ... ,хм) — количества попаданий случайного процесса в состояния S], s2, ... , sKI, соответствующие выполнению запросов. На основе полученных значений и и заданных характеристик узлов (законов распределения времени обработки запросов) определяются вероятностно-временные характеристики процесса решения задач. Следует отметить, что неотъемлемым свойством непрерывного марковского процесса является экспоненциальность распределения времени пребывания запроса в состоянии sk (к = ,К + \). В общем случае законы распределения времени выполнения запросов отличны от экспоненциального. В этом случае процесс решения задач описывается с помощью вложенных марковских цепей (полумарковский процесс). Характеристики полумарковского процесса определяются значительно сложнее, чем для марковского процесса, и вычисление стационарных вероятностей состояний выливается в сложную математическую задачу.
Граф, описывающий процесс решения задачи, может быть интерпретирован разомкнутой сетью массового обслуживания, в которой характеристики СМО (параметры законов распределения времени обработки запросов) определяются на представленной ранее модели. Узел 0 представляет собой источник заявок, а узел k+l — выход из сети. Конкуренция заявок за ресурсы АИУС учитывается во временных параметрах узлов, что позволяет рассматривать процесс решения различных задач, а также одной задачи в различные моменты времени независимо друг от друга. Как было отмечено, для определения функции распределения случайной величины (в рассматриваемом случае - времени пребывания заявок в сети) достаточно знать первые четыре центральные момента этой величины. Дальнейший переход к искомой функции осуществляется с помощью семейств кривых, охватывающих различные виды распределений, конечных рядов и т.д. Рассмотрим процесс перемещения заявки по сети. После возникновения в узле 0 заявка с вероятностью р0\ поступит в узел 1, с вероятностью р02 — в узел 2 и т.д., причем p0j =1, где h — число узлов, смежных с узлом 0, т.к. 7=1 случайные события выбора различных направлений движения заявки из узла составляют полную группу. Аналогично для произвольного узла
Значения вероятностей рш существенно зависят от интенсивности потока запросов, поступающих в систему. При этом для узла к с альтернативными путями вероятности ри, рьп пропорциональны интенсивностям /-го и т-то потоков запросов. Для вероятностей выбора путей от узла 0 до узла к+\ также выполняется L условие ][]. , =1, где pi — вероятность прохождения заявки по /-му пути, 1=1 L — число путей. Из этого следует, что плотность распределения времени пребывания заяв- ки в сети определяется равенством f{t) = Pifi{t), где yj(f) - плотность рас- пределения времени прохождения заявкой /-го пути [119]. Интегрируя обе части этого равенства в пределах от 0 до tdon, и учитывая, что интеграл суммы равен сумме интегралов, получим Имея в виду допущение о независимости времени пребывания заявок на каждом элементе сети, центральные моменты времени прохождения заявкой г -го пути находятся по известным соотношениям [128]:
Использование взвешенного суммирования- (3.27) требует существенных затрат вычислительных ресурсов для многократного нахождения величины Ft(t tdon). Упростить решение данной задачи позволяют некоторые особенности исследуемой СеМО: 1) в произвольный момент в сети присутствует только одна заявка и никакая другая не поступает на вход до тех пор, пока не будет обслужена предыдущая; 2) при обслуживании заявка продвигается строго по одному пути, определяемому вероятностью его выбора. Учитывая эти особенности, можно рассматривать сеть как состоящую из независимых путей. Поскольку операция взвешенного суммирования применима по отношению к законам распределения случайных величин, уместно предположить возможность ее использования и для нахождения некоторых других числовых характеристик времени пребывания заявки в сети. Доказательством этой гипотезы выступает следующая теорема. Теорема. Начальные моменты А:-го порядка множества случайных величин равны взвешенной сумме начальных моментов того же порядка входящих в множество величин при условии, что события, заключающиеся в выборе случайных величин, несовместны.
Алгоритмы оптимизации выполнения запросов и восстановления целостности данных
Алгоритм оптимизации выполнения запросов основан на поиске множества решений с последующим выбором окончательного оптимального плана выполнения и состоит из пяти основных этапов: 1) определение типа поступившего запроса: на выборку или корректировку данных (если поступил запрос на корректировку, то решение задачи не выполняется). 2) определение всех возможных планов выполнения поступившего на обслуживание запроса. 3) проведение эксперимента по каждому возможному плану выполнения запроса с помощью модели, получение статистических данных по времени выполнения и вероятности своевременного выполнения для всех планов. 4) выбор из полученных статистических данных максимальной вероятности своевременного выполнения с минимальным временем выполнения и определение соответствующего этим показателям плана. 5) выполнение запроса по выбранному плану. Алгоритм оптимизации выполнения запросов показан в виде блок-схемы на рис. 5.9. Этот алгоритм должен работать совместно с алгоритмом восстановления целостности РБД, который обеспечивает контроль выполнения запроса и актуализирует процесс восстановления в случае возникновения аварийной ситуации. Блок-схема алгоритма восстановления целостности представлена на рис. 5.10. Основным моментом в указанном алгоритме является анализ возможности восстановления ФД (блок 6) без поиска копии и ее полного дублирования. Анализ заключается в экспресс-оценке объема утраченных данных и их взаимосвязи с оставшимися данными.
После этого определяется возможность восстановления (блок 9) утраченных данных и время, которое будет затрачено на это восстановление, а также отыскивается время, необходимое для полного копирования ФД. Затем сравниваются значения времени обоих случаев восстановления, и выбирается способ с наименьшим из них. Данный подход особенно актуален в системах, базирующихся на низкоскоростных каналах передачи данных. В них существует опасность длительного восстановления утраченных или модифицированных данных в случае полного копирования ФД. где аи — время выполнения г-той элементарной операции, входящей в состав Z-ro выражения (зависит от быстродействия ЭВМ); kLl — количество операций /-го типа в составе Z-ro расчетного выражения. Расчетные выражения для восстановления данных определяются из описания структуры МРБД и сопоставляются с атрибутами. При потере данных какого-либо атрибута реляционного отношения из служебной базы данных извлекается соответствующее ему расчетное выражение, по которому происходит восстановление. Значения а, определяются для конкретного типа ЭВМ в зависимости от ее быстродействия. После этого по соотношению (5.2) определяется набор значений времени восстановления данных для каждого Z-ro выражения и заносится в служебную базу данных на СБД. Алгоритм восстановления (см. рис. 5.7) использует эти данные (блок 6), извлекая их из служебной базы. Указанные расчеты целесообразно проводить как на этапе разработки МРБД, так и во время ее эксплуатации при изменении структуры.
Следует отметить, что рассмотренный алгоритм восстановления целостности МРБД отчасти решает задачи оптимизации выполнения запросов, так как осуществляет выбор более предпочтительного метода восстановления из двух возможных. Оценку качества представленных алгоритмов целесообразно проводить аналогично оценке алгоритмов динамического управления (см. пар. 4.5). Определенность оцениваемых алгоритмов обеспечивается применением формальных и эвристических правил направленного поиска решения. В алгоритме оптимизации выполнения запросов в СУРБД, как и в алгоритме восстановления целостности РБД, отсутствуют какие-либо ограничения на размерность задачи и представление исходных данных. Из этого следует, что оба алгоритма удовлетворяют требованию массовости.
Для,установления результативности алгоритмов следует доказать два факта — сходимость алгоритмов и возможность получениярезультатов за конечное число шагов: Сходимость алгоритма оптимизации выполнения запросов к СУРБД (см. рис. 5.9) определяется тем, что на каждой итерации осуществляется прогон одного планатыполнения запроса. Так как количество планов зависит от-числа СБД; имеющих необходимые для выполнения запроса1 ФД,. а,число СБД в АИУС — величина І конечная, то и число «возможных планов, выполнения запросов также конечно. Поскольку с каждой, итерацией число планов выполнения, по которым должен осуществиться», прогон,, уменьшается на-один,,то, в конечном счете, будет осуществлен перебор всех планов. Максимальная вычислительная сложность рассматриваемого)алгоритма т0 может быть рассчитана как где ОЇ и о? - количество итераций прогона планов на модели и последующего перебора для определения плана с максимальной вероятностью своевременного выполнения запроса соответственно; Nk— количество возможных планов выполнения к-го запроса. Приведенные рассуждения и расчеты доказывают возможность получения результата за конечное число шагов.
