Содержание к диссертации
Введение
ГЛАВА 1. Распределенные базы данных и их роль в корпоративных информационных системах. 14
1.1. Исследование подходов к организации баз данных в распределенных корпоративных информационных системах 14
1.1.1 Применение концепции компьютеризированного интегрированного производства в распределенных корпоративных информационных системах 14
1.1.2 Исследование методов интеграции данных в базах данных распределенных корпоративных информационных систем 17
1.2 Исследование архитектурных решений распределенных баз данных 22
1.2.1 Исследование проблемы преобразования глобальной схемы в мультибазах данных 25
1.3 Архитектура мультибазы данных корпоративной информационной системы на примере КИС нефтепромыслового предприятия 31
1.4 Моделирование процесса обработки распределенных запросов в мультибазе данных ОАО "Газпромнефть-Муравленко" 32
1.5 Постановка задачи исследования 37
Выводы по главе 1 39
ГЛАВА 2. Разработка графо-аналитической модели процесса формирования глобальной схемы мультибазы данных, с учетом этапов ее реструктуризации 41
2.1 Выбор и обоснование графового представления глобальной схемы мультибазы данных 41
2.2 Разработка обобщенного графового представления информационно-логической модели глобальной схемы мультибазы данных 44
2.3 Разработка графовой модели глобальной схемы мультибазы данных 48
2.4 Моделирование процесса формирования глобальной схемы мультибазы данных с учетом этапов ее реструктуризации 51
2.4.1 Разработка графовой модели схемы реструктуризации 52
2.4.2 Выбор и обоснование алгоритмов формирования глобальной схемы мультибазы данных с учетом этапов ее реструктуризации 54
2.5 Графо-аналитическая модель процесса формирования глобальной схемы мультибазы данных с учетом этапов ее реструктуризации 60
Выводы по главе 2: 61
ГЛАВА 3. Комплекс алгоритмов децентрализованного формирования глобальной схемы мультибазы данных, учитывающих ее реструктуризацию, базирующихся на математической модели функционирования пиринговой сети 63
3.1 Процесс реструктуризации мультибазы, основанный на алгоритмах формирования копии данных их восстановления 63
3.2 Этапы методики децентрализованного управления глобальной схемой мультибазы 64
3.2.1 Обобщенная методика децентрализованного управления глобальной схемой мультибазы 64
3.2.2 Состав этапа Э1 ("мониторинг") 67
3.2.3 Состав этапа Э2 ("ожидание") 69
3.2.4 Состав этапа Э3 ("реконфигурация") 71
3.3 Способы организации информационного обмена в процессе выполнения реструктуризации глобальной схемы мультибазы 73
3.4 Математическая модель протокола взаимодействия узлов мультибазы torrent-вида для оценки времени выполнения реструктуризации 76
3.5 Оценка алгоритмов формирования схемы реструктуризации и восстановления данных 80
3.5.1 Постановка задачи статистического эксперимента для оценки влияния исходных данных на использованный алгоритм 81
Выводы по главе 3 88
4 ГЛАВА 4. Результаты имитационного моделирования процесса децентрализованного формирования глобальной схемы мультибазы данных 90
4.1. Анализ структуры распределенных запросов в типовых мультибазах данных. 90
4.2. Разработка имитационных моделей мультибаз данных 94
4.2.1 Построение формальных моделей МБД с сервером репликации и МБД с узловыми диспетчерами 96
4.2.2 Проверка гипотезы об экспоненциальном законе распределения времени поступления распределенных запросов 99
4.2.3 Проверка гипотезы об экспоненциальном распределении времени выполнения распределенных запросов 103
4.2.4 Построение формальных моделей МБД с сервером репликации и МБД с узловыми диспетчерами на основе языка моделирования GPSS 105
4.2.5 Оценка адекватности экспериментальных моделей МБД с сервером репликации и реструктуризации и МБ с узловыми диспетчерами. 107
4.3. Принцип функционирования экспериментальной модели МБД с сервером репликации и реструктуризации 111
4.4. Принцип функционирования экспериментальной модели МБ с узловыми диспетчерами. 118
4.5. Выбор показателя и критерия оценки эффективности процесса реструктуризации мультибазы с глобальной схемой. 124
4.6. Экспериментальная оценка процесса децентрализованного управления реструктуризацией мультибазы с глобальной схемой. 127
Выводы по главе 4: 129
Заключение 131
- Исследование проблемы преобразования глобальной схемы в мультибазах данных
- Моделирование процесса формирования глобальной схемы мультибазы данных с учетом этапов ее реструктуризации
- Процесс реструктуризации мультибазы, основанный на алгоритмах формирования копии данных их восстановления
- Проверка гипотезы об экспоненциальном законе распределения времени поступления распределенных запросов
Введение к работе
Актуальность темы. В настоящее время базовой тенденцией развития существующих и создания новых корпоративных автоматизированных информационных систем (КАИС) промышленных предприятий являются подходы, направленные на интеграцию данных и развитие соответствующих технологий.
Широта спектра применимости КАИС в промышленности определяет номенклатуру эксплуатируемых информационных систем и сложность применяемых в них алгоритмов обработки данных.
Для обеспечения различных информационных процессов, протекающих таких КАИСтребуется согласованное функционирование систем различных классов – геоинформационных, диагностических, информационно-справочных, систем поддержки принятия решений, систем автоматизированного проектирования и т.д.
Использование распределенных баз данных, поддерживающих единую информационную модель всей предметной области современного производства, яв-ляется,как правило, нецелесообразным. В настоящее время все шире используются подходы, предполагающие создание и эксплуатацию систем интеграции данных различных типов.
В современных информационных системах часто приходится строить распределенную базу данных на основе уже имеющихся унаследованных баз данных (БД), т.е. "снизу-вверх". При этом необходимо учитывать низкую степень интеграции хранящихся в них данных. Такие системы часто строятся по принципу мультибаз данных, как совокупность локальных БД и управляющих ими СУБД, имеющих глобальную схему (ГС). При этом каждый узел мультибазы является независимой в администрировании локальной БД, а информация обо всей структуре мультибазы данных с целью реализации распределенных запросов хранится в виде метаданных на каждом узле. Каждая локальная БД имеет свою структуру, не зависящую от других, при этом межузловые связи поддерживаются на уровне глобальной схемы.
Особенностью процесса эксплуатации мультибаз данных является потенциальная возможность проведения реструктуризации узлов, входящих в ее состав. Реструктуризация – изменение структуры глобальной схемы в рамках одной модели данных: схемы отношений, включая функциональные зависимости, преобразуется в схемы с теми же зависимостями.
Процесс выполнения распределенного запроса в мультибазе данных имеет ряд особенностей. В случае централизованного управления реструктуризацией время, затраченное на ее выполнение, является задержкой выполнения распределенного информационного запроса. Для мультибаз с небольшим количеством узлов и низкой интенсивностью потока запросов на реструктуризацию, проводимую, как правило, централизованно, задержка, вызванная ее проведением, оказывает несущественное влияние на среднее время выполнения распределенного запроса, а для реализации реструктуризации, как правило, бывает достаточно средств административного управления. Однако при увеличении количества уз-
лов мультибазы и возрастания интенсивности потока запросов на реструктуризацию, время, затраченное на ее реализацию, начинает оказывать заметное влияние на среднее время выполнения распределенного запроса, направленного на удовлетворение информационных потребностей пользователей мультибазы.
Таким образом, существует противоречие между требованием, предъявляемым к времени выполнения распределенного запроса, и возрастающими задержками, возникающими вследствие проводимых процессов реструктуризации при увеличении количества узлов мультибазы.
Не смотря на то, что исследования в данной области ведутся достаточно давно и им посвящено большое количество публикаций известных специалистов как российских – Калиниченко Л.А., Когаловского М.Р., Гаврилова Д.А., Мами-конова А.Г., Кузнецова С.Д., Кульбы В.В., так и зарубежных – Ульмана, Лензери-ни, Уидома, Саймона, Вельдью, Селко, Шаша, Бонне, – проблема разработки моделей и алгоритмов интеграции данных, обеспечивающих требуемые значения показателей эффективности процессов функционирования мультибаз продолжает оставаться актуальной.
Ряд исследований посвящен изучению влиянию процессов реструктуризации узлов мультибазы на общую эффективность информационной системы, а также проблеме формирования оптимальных глобальных схем мультибаз. Значительно меньшее внимание уделено вопросам исследования динамических характеристик процесса эксплуатации мультибазы с глобальной схемой.
В частности процесс реструктуризации информационных структур локальных БД входящих в ее состав оказывает существенное влияние на временные характеристики процесса обработки распределенных запросов.
В связи с этим актуальным является проведение анализа информационных процессов, возникающих в мультибазе с глобальной схемой на этапе реструктуризации и обоснованный выбор методов, алгоритмов и используемых при этом структур данных, с учетом требований к временным характеристикам процесса обработки распределенных запросов.
Объект исследования диссертационной работы - мультибаза данных с глобальной схемой.
Предмет исследования – модели и алгоритмы формирования глобальной схемы мультибазы данных, учитывающие реструктуризацию информационных структур локальных баз данных, входящих в ее состав.
Научная задача исследования заключается в разработке комплекса алгоритмов формированияинформационной структуры глобальной схемы мультибазы данных, обеспечивающего требуемую эффективность процесса обработки распределенных запросов.
Цель исследования – повышение оперативности процесса обработки распределенных запросов в мультибазе данных с глобальной схемой, учитывающего реструктуризацию информационных структур локальных БД, входящих в ее состав.
Для решения научной задачи и достижения цели исследования были определены частныезадачи диссертационного исследования:
-
На основе анализа литературных источников провести сравнение существующих методов и технологий интеграции данных.
-
Разработать графо-аналитическую модель мультибазы данных с глобальной схемой, учитывающую этапы реструктуризации локальных баз данных, входящих в ее состав.
-
Разработать комплекс алгоритмов, обеспечивающих реализацию процесса децентрализованной репликации метаданных в мультибазе данных для поддержания ее глобальной схемы в актуальном состоянии.
-
Спланировать и провести имитационный эксперимент для оценки степени влияния процессов реструктуризации на оперативность выполнения распределенных запросов в мультибазах с централизованным и децентрализованным подходом к формированию глобальной схемы.
-
Разработать научно-технические предложения для администраторов системы с мультибазами, основанные на результатах имитационного моделирования процесса реструктуризации глобальной схемы мультибазы с централизованным и децентрализованным управлением репликацией метаданных.
Методы исследования, использованные в процессе выполнения диссертационной работы: исследования операций, теории множественной модели деревьев, планирования статистических экспериментов, теории вычислительных машин и сетей.
Гипотеза исследования заключается в предположении о том, что среднее время выполнения распределенного запроса в мультибазе данных может быть уменьшено за счет применения децентрализованного подхода к поддержанию глобальной схемы мультибазы данных в актуальном состоянии.
Научная новизна диссертационной работы заключается в:
1) представлении процесса реструктуризации глобальной схемы мультибазы
данных графо-аналитической моделью, основанной на известном методе графово-
гоопределения структур реляционных баз данных, базирующемся на множествен
ных деревьях, отличающейся способом представления в виде совокупности ги
перграфового определения структуры мультибазы и алгоритмов рекурсивного об
хода графа и попарного сравнения строк.
2) использованиикомплекса алгоритмовформирования глобальной схемы
мультибазы данных, учитывающихпроцессые реструктуризации, базирующихся
на известных методах репликации данных, отличающихся применением децен
трализованного подхода, основанного на введении в структуру узла мультибазы
функций локального диспетчирования, реализуемых по torrent-подобному прото
колу.
3) выработке научно-технических предложений по применению алгоритмов
децентрализованного управления процессом формирования глобальной схемы
мультибазы данных с учетом этапов ее реструктуризации, базирующихся на ме
тодах планирования и проведения имитационного эксперимента.
Область исследования. Содержание диссертации соответствует паспорту специальности 05.13.17 – "Теоретические основы информатики" по следующим областям исследований:пункт 2: Исследование информационных структур, разработка и анализ моделей информационных процессов и структур.
Положения, выносимые на защиту:
-
Графо-аналитическая модель информационного процесса формирования глобальной схемы мультибазы данных.
-
Алгоритмы децентрализованного формирования глобальной схемы мультибазы данных, учитывающие процессые реструктуризации.
-
Результаты имитационного моделирования процесса формирования глобальной схемы мультибазы данныхс учетом этапов ее реструктуризации.
Теоретическая значимость полученных решений заключается в разработке нового децентрализованного подхода к процессу репликации метаданных в мультбазах данных, позволяющего за счет применения torrent-подобного протокола повысить актуальность глобальной схемы мультибазы данных с целью снижения среднего времени выполнения распределенного запроса.
Практическая значимость результатов диссертационной работы заключается в получении решений по децентрализованному управлению процессом формирования глобальной схемы мультибазы данных, с учетом этапов ее реструктуризации, что подтверждается Патентом на полезную модель № RU 126161 U1 от 20.03.13, Свидетельством о государственной регистрации программы для ЭВМ № 2012619081 от 5.10.12.
Полученные результаты могут быть использованы администраторами систем с мультибазами данных, входящих в состав автоматизированных систем управления предприятиями, с целью повышения оперативностиобеспечения информационных потребностей пользователей за счет уменьшения среднего времени выполнения распределенных запросов при заданных ограничениях на временные параметры функционирования мультибазы.
Достоверности результатов проведенных исследований. Обоснованность предлагаемых решений верифицирована путем имитационного моделирования и получения статистически значимых результатов. Обоснованность и достоверность теоретических исследований, результатов математического моделирования и экспериментальной проверки предлагаемых решений подтверждается строгой постановкой общей и частных задач исследования и корректным применением апробированного математического аппарата.
Личный вклад соискателя. Все изложенные в диссертации результаты исследования получены либо соискателем лично, либо при его непосредственном участии.
Публикации.По теме диссертационного исследования опубликовано 10 работ, в том числе 3 в изданиях, рекомендованных ВАК при Минобрнауки РФ.
Результаты проведенных диссертационных исследований изложены в 4-х печатных статьях, 6 тезисах докладов.
Апробациярезультатов диссертационного исследования.Основные
положения и результаты диссертационной работы докладывались и обсуждались на XIV Международной открытой научной конференции "Современные проблемы информатизации" (г. Воронеж, 2009 г.), XV Международной открытой научной конференции "Современные проблемы информатизации" (г. Воронеж, 2010 г.), XVI Международной открытой научной конференции "Современные проблемы информатизации" (г. Воронеж, 2011 г.), XVII Международной
открытой научной конференции "Современные проблемы информатизации" (г. Воронеж, 2012 г.), Всероссийской научно-технической конференции "Научная сессия ТУСУР 2012" (г. Томск, 2012 г), XVIII Международной открытой научной конференции "Современные проблемы информатизации" (г. Воронеж, 2013 г.).
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и четырех приложений. Диссертация содержит 146 стр., 44 рисунка, 11 таблиц. Список литературы содержит 93 наименования.
Исследование проблемы преобразования глобальной схемы в мультибазах данных
Как было указано выше, РБД (в частности мультибазы данных) могут быть, как однородными, так и неоднородными.
При этом неоднородность определяется следующими обстоятельствами:
использование в локальных базах данных (ЛБД)разных моделей данных; отличие в синтаксисе и семантике даже одного вида моделей (например, реляционных);
разные методы управления ЛБД (резервирование и восстановление, синхронизация, блокировка).
Независимо от однородности мультибаз данных в общем случае данные из любойЛБД в ее составе с одной моделью данных должны быть переданы в любую ЛБД с другой моделью данных.
Ранее основным подходом, связанным с преобразованием моделей данных в мультибазах, являлось использование процедур выгрузки-загрузки на физическом уровне хранения данных. Этот подход был основан на выгрузке данных из исходной ЛБД, их сохранении в некотором промежуточном (объектном) формате и дальнейшая загрузка в целевую ЛБД [68].
Такой подход существенно влиял на показатели оперативности функционирования мультибазы и требовал существенных временных и вычислительных ресурсов для его реализации.
В связи с этим распространение получил подход, связанный с преобразованием данных на логическом уровне путем формирования ГС мультибазы данных (рисунок 1.3). При этом в литературе [68]выделяются следующие направления такого формирования:
1. Построение схем попарного взаимодействия моделей данных для ЛБД всех узлов мультибазы. То есть, при наличии nЛБД требуется n(n-1) таких схем попарного взаимодействия, что делает структуру ГС мультибазы очень громоздкой.
2. Разработка ГС мультибазы в виде виртуальной (динамически обновляемой) промежуточной модели данных.
При этом для каждого из этих направлений, формируемая ГС должна удовлетворять условиям [68]:
полной определенности – любое состояние модели данных ЛБДi представимо в модели данных ЛБДj; интерпретируемости - любой оператор языка модели данных (ЯМД) в
ЛБДi имеет интерпретацию в ЯМД ЛБДj;
воспроизводимости- любое изменение в модели данных ЛБДi выполняется некоторым оператором изменения, воспроизводимого средствами в модели данных ЛБД j.
Соблюдение этих условий в РБД с архитектурой, представленной на рисунке 1.2, не представляет проблем. Однако в мультибазах данных, ЛБД которых обладают существенной автономностью, удовлетворение этих условий требует решения дополнительны задач, связанных с процессом формирования ГС мультибазы.
В общем случае эта проблема отражается выражением (1.1):
SS - структура исходной ГС мультибазы при отсутствии внесения изменений в модели данных ее ЛБД ;
ST - структура требуемой ГС после внесения изменений в модели данных одной или более ЛБД.
Решение этой проблемы возможно различными способами, основные из которых представлены в литературе [38, 68]. На рисунке 1.4 представлена блок-схема методики выбора способов преобразования (выражение 1.1) в зависимости от архитектурных особенностей мультибазы данных.
Из рисунка 1.4 видно, что выбор способа формирования ГС мультибазы связан с проверкой трех типов условий:
1. Условие А - единый ЯМД, используемый в моделях данных ЛБД мультибазы.
2. Условие Б - изоморфизм SSи ST.
Моделирование процесса формирования глобальной схемы мультибазы данных с учетом этапов ее реструктуризации
Разработанные в п. 2.3 графовая модель ГС мультибазы данных определяет статическое состояние ИЛМ ЛБД каждого узла мультибазы.
При этом любое автономное изменение ИЛМ ЛБД любого из узлов мультибазы данных приводит к потере актуальности графовой модели ГС мультибазы данных и требует выполнения этапа ее реструктуризации. Результатом этого этапа является формирование нового графа ГС, учитывающего множество изменений ИЛМ ЛБД подмножества узлов мультибазы.
Таким образом, процесс формирования ГС мультибазы данных можно представить как решение задачи оптимизации текущего варианта ее графовой модели.
Для решения подобной задачи требуется определить формальное представление отдельного этапа реструктуризации ГС мультибазы данных.
С точки зрения формального представления, этап реструктуризации ГС мультибазы данных фактически является формированием производной графовой модели ГС, отражающей только изменения вершин и связей графа, основанных на изменении второго уровня иерархии модели (уровень ИЛМ ЛБД) (рисунок 2.4). При этом внесение этих изменений, в соответствии со связями иерархии будут находить отражение в изменениях третьего уровня иерархии модели (физический уровень ЛБД).
Таким образом, для формального представления этапа реструктуризации требуется определить некоторую промежуточную графовую модель, отражающую изменения в обобщенной графовой модели ГС мультибазы данных.
Для этого определим совокупность всех изменений в ИЛМ ЛБД мультибазы данных, как некоторую частную модель данных уровня ИЛМ отдельной ЛБД, описывающую ее изменения в момент реструктуризации. Назовем такую частную модель данных схема реструктуризации (СР).
Очевидно, что, являясь частной моделью данных, схема реструктуризации также должна быть представлена графовой моделью.
Однако, в отличие от графовой модели ГС мультибазы данных, в графовой модели схемы реструктуризации должны быть учтены горизонтальные отношения между элементами сущностей, как на втором, так и на третьем уровне иерархии графовой модели.
Поскольку на этапе реструктуризации ИЛМ ЛБД отдельных узлов мультибазы внесение изменений уровня иерархии ИЛМ отражается на изменении содержимого отдельных строк и ключевых полей физического уровня иерархии графовой модели ГС, то требуется формально определить эти особенности. Определим экземпляр информационного объектаО (запись) таблицы?, как: где place - элемент множества Place = {db,pk}, определяющий расположение изменяемой строки: в ГС мультибазы (элемент db), или в СР (элемент ). Тогда, исходя из выражений 2.20 и 2.22, можно определить значение ключевого поля Id для строки о: учетом того, что г =(е;.,ек),і = \.т; е.,ек є Vsc.
В отличие от графовой модели ГС, графовая модель СР отображает не только сами сущности ИЛМ ЛБД, в рамках которой проводится реструктуризация, но и конкретные объекты физического уровня иерархии (строки), подвергаемые изменению. Таким образом, в ее рамках можно выделить корневую сущность
Формирование графовой модели СР на этапе реструктуризации ГС мультибазы данных позволяет определить множество изменений, которые требуется внести в ГС. При этом на основе сформированной СР имеется возможность получения данных, требующих модификации на физическом уровне иерархии графовой модели ГС мультибазы данных.
Таким образом, на графовой модели СР необходимо выполнить операцию поиска и сохранения данных, подлежащих модификации в графовой модели ГС. На графовой модели ГС, соответственно, требуется выполнение операции модификации найденных и сохраненных данных.
Таким образом, для моделирования процесса формирования ГС мультибазы данных с учетом этапов ее реструктуризации важным является поиск и обоснование пригодности алгоритмов:
А 1– создания копии данных по заданной графовой модели схемы СР;
А2- восстановления сохраненных данных на графовой модели ГС мультибазы данных. В общем виде использование указанных алгоритмов представлено на рисунке 2.5.
Как было отмечено в п. 2.4.1, на этапе реструктуризации ГС мультибазы данных изменяется, фактически, информационно-логическая модель ГС. Что, в свою очередь, приводит к изменению структуры данных, которыми обмениваются узлы мультибазы данных.
Таким образом, создаваемая на этапе реструктуризации ИЛМ ЛБД некоторого узла мультибазы данных копия данных должна содержать не только информацию о сущности (выражение 2.24), которую нужно передать на другие узлы мультибазы, но также должна содержать подмножество дочерних сущностей, связанных с корневой сущностью. Благодаря этому, на этапе реструктуризации будут выполняться требования по целостности и непротиворечивости модели данных мультибазы.
При этом из всего подмножества дочерних сущностей должны быть выбраны только те, которые имеют отношение корневой сущности, подвергаемой модификации. Кроме того, указанная корневая сущность должна иметь ссылки на свои родительские сущности. Подобная структура графа СР (выражение 2.24) может быть получена путм редукции его вершин, не включенных в схему реструктуризации. Эта операция выполняется путем удаления неиспользуемых вершин из множества вершин Vi и дуг, инцидентных этим вершинам.
Очевидно, что указанные условия соответствуют постановке варианта задачи Штейнера [56, 58], для решения которой разработан ряд эффективных алгоритмов [59].
Процесс реструктуризации мультибазы, основанный на алгоритмах формирования копии данных их восстановления
Предлагаемые в 2.4.2.1 и 2.4.2.2 алгоритмы A1 и А2 позволяют привести процесс управления формированием глобальной схемы мультибазы данных к децентрализованному виду. Общий принцип такого подхода представлен на рисунке 3.1. Данный принцип подразумевает множественное взаимодействие каждого узла с другими узлами, заинтересованными в получении метаданных от узла инициатора. При этом на узле-инициаторе с помощью алгоритма Ai происходит формирование корневой сущности и объекта, а также подмножества дочерних сущностей. Вместе они образуют схему реструктуризации (СР). При передаче сформированных на основе СР метаданных на узле-получателе начинает функционировать алгоритм А2, осуществляющий обновление атрибутов.
Обобщенная методика децентрализованного управления глобальной схемой включает в себя 3 этапа - этап мониторинга ИЛМ "своего" узла или наступления события реструктуризации выше по графу схемы реструктуризации (Эі); этап реконфигурации "своего" узла при приеме информации об изменениях в ИЛМ базы данных "чужого" узла (Эг); этап ожидания приема сообщений о завершении реструктуризации на узлах ниже по графу схемы реструктуризации (Э3). Обобщенная методика схематично представлена на рисунке 3.2.
Обобщенная диаграмма состояний УД при выполнении децентрализованного алгоритма управления ИЛМРБД, реализованная в виде простой транзитивной сети, представлена на рис. В основе методики формирования глобальной схемы мульти-БД лежит система мониторинга с децентрализованной организацией.
Функции мониторинга распределяются на все узлы, входящие в состав мульти-БД, для этого на каждом узле реализуется свой узловой диспетчер (УДi).
Состояния узлов:
I – Состояние мониторинга локальной БД;
II – Инициализации процесса внесения изменений;
III – Ожидания входных данных;
IV – Ожидания подтверждений;
V – Выполнения изменений на узле;
Сообщения:
"Начало"– Информирует о начале процесса внесения изменений в ИЛМ мульти-БД, содержит номер узла на котором возникли изменения и его граф обхода.
"Новая схема" – содержит информацию конфигурации ИЛМ узла.
"Конец" – подтверждения о завершении процесса реструктуризации на данном узле, и узлах находящихся ниже по графу обхода. Переходы:
1 - Произошло изменение в логической структуре локальной БД;
2 - Принято сообщение "Начало";
3 - Приняты сообщения "Новая схема" от всех узлов множества;
4 - Узел является листом графа обхода;
5 - Приняты сообщения "Конец" от всех узлов множества;
6 - Передано сообщение "Новая схема" всем узлам множества;
7 - Передано сообщение "Новая схема" всем узлам множества; Методика реализуется алгоритмами узлового диспетчера. При этом будем считать, что УДг (/ =1,7V) имеет в распоряжении:
- программу реструктуризации ИЛМ БД узла в зависимости от изменений, возникших в системе;
- программу диагностирования ИЛМ "своей" БД;
- таблицу Тг размерами М М, где M=\Q\, содержащую информацию об инцидентности вершин графа 0(Ф,Х), или иными словами, информацию о топологии графа;
- каждый УДг должен иметь таблицу Т} размерами М М, где M=\Q\, содержащую информацию о смежности вершин графа 0/Ф,Х). Данный граф является вариантом направленного графа 0(Ф,Х). Он показывает, в какой последовательности должна происходить реструктуризация на узлах системы. Данный граф можно формировать с помощью алгоритма поиска в глубину;
- таблицу Т2 размерами N1. Каждая строка таблицы соответствует номеру узла. Если фрагмент находится на Ф, то T2(i,l) = j. Таблица содержит для каждого узла номер фрагмента мульти-БД, который за ним закреплен;
- список R номеров узлов, на которых возникли изменения в ИЛМ БД;
- список О номеров всех узлов приславших подтверждение.
Номер фрагмента РБД закрепленного за узлом Yu определяются из таблицы Т2. Для того чтобы узел приступил к реструктуризации ИЛМ своей БД, ему необходимо получить "новые" ИЛМ узлов в соответствии с графом обхода. Получить номера узлов стоящих выше по графу обхода можно из таблиц Т} (граф обхода) и Т2. Если эти данные получены, то локальный диспетчер может приступить к реструктуризации локальной БД. Результат реструктуризации в виде ИЛМ локальной БД должен быть передан дальше по графу. Данные об узлах, которым необходимо передать информацию дальше, можно получить из таблиц Tj и Т2.
Базовым состоянием, в котором каждый узел РБД находится большую часть времени функционирования, является состояние мониторинга. В этом состоянии узел находится до момента принятия сообщения"Начало", либо"Новая схема" от какого-либо узла.
В режиме мониторинга ИЛМ УД должен выполнять следующие функции:
1. Построение графа ИЛМ БД "своего" узла;
2. Если присутствуют локальные изменения, передача другим УД информации о состоянии локальной ИЛМ "своего" узла, а также граф обхода;
3. Прием сообщений от УД других узлов.
Формальное представление этапаЭ методики представлен на рис. 3.4.
Поясним рисунок 3.4.
Шаг 1. Из таблицы Т2 происходит выбор фрагмента мультибазы, задействованный в реструктуризации, номер которого присваивается].
Шаг 2. Выбранный на предыдущем шаге номер фрагмента определяет столбец, который считывается из таблицы Th Значения данного столбца определяют подмножество инцидентных к вершин.
Шаг 3. Происходит определение узлов, за которыми закреплены вершины, входящие в подмножество 0jt определение их узлов в соответствии с таблицей по номеру строки, в которой элемент данного столбца равен единице. Эти номера формируют список О.
Проверка гипотезы об экспоненциальном законе распределения времени поступления распределенных запросов
Определение закона распределения времени поступления распределенных запросов в мультибазе данных является важной задачей для построения адекватной модели выполнения этих запросов в рассматриваемой системе.
Для проверки соответствия закона распределения времени выполнения распределенных запросов экспоненциальному закону необходимо доказать гипотезу Н0- время поступления распределенных запросов распределено по экспоненци альномузакону распределения. В ходе обследования предметной области была получена статистика поступления распределенных запросов в случайные моменты времени для 500 наблюдений.
Проверка гипотезы о виде распределения случайной величины может производится с использованием следующих критериев согласия: %2 Пирсона, Колмогорова и др. Наиболее применимым для данной предметной области является критерий х2 Пирсона, так как его применение не накладывает ограничений на размерность и вид распределения случайной величины[88].
Для начала было произведено построение вариационного ряда. Для этого интервал измерения наблюдаемых значений случайной величины разбивают наTV непересекающихся интервалов. Число N выбирается в соответствии с условием, представленным ниже:
Для достоверных статистических выводов интервал измерения наблюдаемых значений случайной величины необходимо разбить на 10 непересекающихся частичных интервалов. В таблице bookmark37представлен группированный вариационный ряд для выборки из генеральной совокупности случайной величины - числа выполнения распределенных запросов в интервалы наблюдения:
Распределение х2 Пирсона зависит от числа степеней свободы г, которое определяется, как число значений случайной величины ( = 10) минус единица (первое условие и, =l) и минус еще единица - совпадение статистического и гипотетического математических ожиданий случайной величины поступления распределенных запросов в наблюдаемые временные интервалы: г = 10 -1 -1 = 8.
По таблице значений х1ыб в зависимости отr и p определяется значение р дляг = 8 и %1б = 2,55. Полученное значение вероятности р лежит в диапазоне (0,95..0,9)[91]. Следовательно, закон распределения поступления распределенных запросов соответствует экспоненциальному закону.
Проверка гипотезы об экспоненциальном распределениивремени выполнения распределенных запросов.
Следующей важной задачей для дальнейшего проведения эксперимента является определение закона распределения времени выполнения распределенных запросов.
Для решения задачи был произведен ряд предварительных экспериментов на реальной МБД в рамкахкоторых была собрана статистика выполнения 500 распределенных запросов.
Для начала было произведено построение вариационного ряда. Для этого интервал измерения наблюдаемых значений случайной величины разбивают наТУ непересекающихся интервалов.
В соответствии с гипотезой Н0 согласно формуле 4.6:
Отсюда, для достоверных статистических выводов интервал измерения наблюдаемых значений случайной величины необходимо разбить на 10 непересекающихся частичных интервалов. В таблице 4.3 представлен группированный ва 104 риационный ряд для выборки из генеральной совокупности случайной величины
- числа выполнения распределенных запросов в интервалы наблюдения:
