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

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

АФАНАСЬЕВ ВАДИМ ВЛАДИМИРОВИЧ

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

Специальность: 05.13.17 Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

21 МАЙ 2014 005548436

Орел 2014

005548436

Работа выполнена в Государственном казённом образовательном учреждении высшего профессионального образования Академия Федеральной службы охраны Российской Федерации.

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

Лебеденко Евгений Викторович

доктор технических наук, профессор Фисун Александр Павлович, заместитель директора Филиала Федерального государственного унитарного предприятия «Радиочастотный центр Центрального федерального округа» в Орловской области, г. Орел

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

Ведущая организация: Федеральное государственное бюджетное

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

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

Защита состоится 25 июня 2014 года в 15 часов 30 минут на заседании диссертационного совета Д 212.015.10 на базе ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет», по адресу: 308015 г. Белгород, ул. Победы, 85, корп. 15, ауд. 3-8.

С диссертацией можно ознакомиться в научной библиотеке ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет», по адресу: 308015 г. Белгород, ул. Победы, 85.

Автореферат разослан 12маяё 2014 г.

Ученый секретарь диссертационного совета доктор технических нрук, старший научный сотрудник

¿V%Белов С. П.

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

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

Широта спектра применимости КАИС в промышленности определяет номенклатуру эксплуатируемых информационных систем и сложность применяемых в них алгоритмов обработки данных.

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

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

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

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

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

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

Таким образом, существует противоречие между требованием, предъявляемым к времени выполнения распределенного запроса, и возрастающими задержками, возникающими вследствие проводимых процессов реструктуризации при увеличении количества узлов мультибазы.

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

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

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

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

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

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

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

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

Для решения научной задачи и достижения цели исследования были определены частные задачи диссертационного исследования:

1. На основе анализа литературных источников провести сравнение существующих методов и технологий интеграции данных.

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

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

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

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

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

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

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

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

2) использовании комплекса алгоритмов формирования глобальной схемы мультибазы данных, учитывающих процессы её реструктуризации, базирующихся на известных методах репликации данных, отличающихся применением децентрализованного подхода, основанного на введении в структуру узла мультибазы функций локального диспетчирования, реализуемых по ЮггеШ-подобному протоколу.

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

Область исследования. Содержание диссертации соответствует паспорту специальности 05.13.17 - "Теоретические основы информатики" по следующим областям исследований: пункт 2: Исследование информационных структур, разработка и анализ моделей информационных процессов и структур.

Положения, выносимые на защиту:

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

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

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

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

Практическая значимость результатов диссертационной работы заключается в получении решений по децентрализованному управлению процессом формирования глобальной схемы мультибазы данных, с учетом этапов ее реструктуризации, что подтверждается Патентом на полезную модель № 1Ш 126161 Ш от 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 наименования.

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

Во ВВЕДЕНИИ обосновывается актуальность работы, описываются объект и предмет исследования, формулируются цель и задачи диссертационной работы, перечисляются используемые в работе методы исследования, показывается научная новизна и практическая значимость результатов работы.

В ПЕРВОЙ ГЛАВЕ "Распределенные базы данных и их роль в корпоративных информационных системах" определяется понятие распределенной базы данных в составе корпоративных автоматизированных информационных систем, выполнена таксономия типов распределенных баз данных по типам интеграции схем данных, выделен и описан особый тип распределенных баз данных -

мультибаза данных.

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

Поскольку реструктуризация мультибазы затрагивает ее глобальную схему (ГС), для предотвращения коллизий при выполнении распределенных запросов, мультибаза должна блокироваться на время, необходимое для реструктуризации. Блокировка приводит к невозможности обработки распределенных запросов. При поступлении информационных запросов (поток информационных запросов - ЗИ) во время реструктуризации (поток запросов на реструктуризацию - ЗР) они помещаются в очередь, где ожидают разблокировки мультибазы. Таким образом, процесс обработки распределенных запросов мультибазой можно представить в виде одноканальной СМО с ненадежным обслуживающим прибором и неограни-

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

ченной очередью (рисунок 1).

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

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

Предложена математическая модель процесса управления обработкой распределенного 8(2Ь-запроса, с учетом этапа реструктуризации ГС:

Л'+Л/) = А{ и(()+Ву(1); ?;(г)]} (1)

Выражение (1) является обобщенным представлением математической модели процесса выполнения распределенного запроса, где: А - оператор действия системы в целом, множество м(/)= {м,(/),м2(/),...,и„(*)} входных контролируемых воздействий; В и Р - операторы управляющих и неуправляющих воздействий; £(/)={£ (г), £ (г),... ,£„(г)} - множество контролируемых, но неуправляемых воздействий (например, измеряемые параметры исходных данных, используемых в процессе); т](т) = {^(г), Т72(г),...,7„(г)} - множество неконтролируемых воздействий.

Уточнение модели применительно к предметной области исследования выполнено на этапе постановки задачи исследования.

ВТОРАЯ ГЛАВА "Графо-аналитическая модель процесса формирования глобальной схемы мульти-БД, с учетом этапов ее реструктуризации" посвящена исследованию и выбору методов описания логической структуры мультибазы данных в условиях проводимой реструктуризации и разработке на их основе графо-аналитической модели процесса формирования глобальной схемы мульти-БД.

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

ИЛМ локальной БД, являющейся узлом мультибазы, описывается графом

С(Х, и), где X = {х, =1,/} - множество вершин графа (сущностей, входящих в состав ИЛМ), и = {ит(х,,хД т = \М, / = 17, 7=1,/ - множество ребер графа

(связей между сущностями).

Введем ограничения:

1. Граф не будет иметь петель (ребер, соединяющих вершину саму с собой), если выполняется ограничение

О/.-аиД^хЛеСГ; т = Щ; к=ъТ- (2)

2. Граф не будет мультиграфом, если выполняется ограничение

02:Уит(х„х,)еи; т=\Ж\ /е 177; ]еЩ=>

-,3м,(х,,х/)е£/; 1фш\1&\М. (3)

3. Вершина-приемник связана только с одной вершиной-источником (ограничения на число связей нет)

О, :Ум„(х,,х,)ег/; т = /е177;

Приведены примеры ориентированных графов, ИЛМ БД узла мультибазы (рисунок 2).

моделирующих структуру

С(Х, и. (\ л Ог л Ог) С(ЛГ. и. л03)

а) 6)

Рисунок 2 - Примеры ориентированных графов, моделирующих структуру ИЛМ БД узла мультибазы

В состав

Схема реструктуризации

(грэфСР)

О 4=

А^-апгориш создания июлю* данных по заданному графу СР

А*-алгоритм восстановления

данных при реструктуризации

Рисунок 3 - Использование алгоритмов А[ и Кг над фафами ГС и СР на этапе реструктуризации

графоаналитической модели входят алгоритмы создания копии данных по заданной схеме реструктуризации (АО и восстановления данных при реструктуризации (А2), место которых в процессе реструктуризации показано на рисунке 3.

Приведено формальное представление графа ГС, реализованное математическими моделями данных уровня ИЛМ локальной БД, отношений сущностей, совокупность которых позволяет

(5)

данных физического уровня локальной БД,

определить множество всех вершин на физическом уровне локальной БД: Км=|умГ(е)и5(е)и

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

Схема реструктуризации (СР) - подсхема модели данных уровня ИЛМ, описывающая ее изменения в момент выполнения этапа реструктуризации.

Для создания копии данных (рк) по заданной схеме реструктуризации представлен алгоритм Аь представляющий собой алгоритм рекурсивного обхода графа СР в глубину. Исходными данными для алгоритма А! являются подмножество корневых сущностейетп и идентификатор начального объекта Ш(ом„). В результате получаем граф копии данных Срк (1'г

к,Ерк), где: Урк с Урк

,ЕрксЕр„.

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

i= J|jAir(e)uS(e)u

eel^

[)Mid(e,d)

(6)

Алгоритм восстановления данных при реструктуризации А2 представляет собой алгоритм сравнения строк в Vpk и Vph . Исходными данными для алгоритма А2 являются Vpk сК(1и, Û(t, рк). В случае успеха сравнения алгоритм выполняет

обновление значения атрибутов, иначе - добавляет объект в множество 0(t, db).

В ТРЕТЬЕЙ ГЛАВЕ "Комплекс алгоритмов децентрализованного формирования глобальной схемы мультибазы данных, учитывающих ее реструктуризацию, базирующихся на математической модели функционирования пиринговой сети" рассматриваются процессы разработки алгоритмов, представленных в виде методики, поддерживающей процесс децентрализованного управления репликацией метаданных в мультибазе данных с глобальной схемой.

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

Предлагаемая модель представлена на рисунке 4.

При этом обосновывается необходимость:

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

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

ЛЕД. = 4

Рисунок 4 - Структурно-функциональная схема системы децентрализованного управления процессом формирования ГС с учетом этапов ее реструктуризации

Рисунок 5 - Обобщенная методика децентрализованного управления реструктуризацией ГС

С

остояния узлов:

I — Состояние мониторинга локальной БД;

II - Инициализации процесса внесения изменений;

III - Ожидания входных данных;

IV - Ожидания подтверждений;

V - Выполнения изменений на узле;

Переходы:

1 — Произошло изменение в логической структуре локальной БД;

2 - Принято сообщения "Начало";

3 - Приняты сообщения "Новая схема" от всех узлов множества;

4 - Узел является листом графа обхода;

5 - Приняты сообщения "Конец" от всех узлов множества;

6 - Передано сообщение "Новая схема" всем узлам множества;

7 - Передано сообщение "Новая схема" всем узлам множества;

Этап Э] ("мониторинг") методики представлен на рисунке 6.

В режиме мониторинга ИЛМ ЛД должен выполнять следующие функции:

1. Построение графа ИЛМ БД "своего" узла;

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

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

1Г

I

Из таблицы Т1, счишваетсяу'-ый столбец и определяется номера подмножества вершин Фу, инцидентных вершине фу;

Т

Р

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

3

Принимаются подтверждения от узлов, за которыми закреплены фрагменты подмножества Ф; и номера узлов заносятся в список О,'

Если О, — О; то переходим к п. 6, иначе к п.4

И

X

Из таблицы Т], счишваетсяу-ый столбец и определяются номера подмножества вершин Ф;, инцидентных вершине фу

По номерам вершин входящих в подмножество Ф^ с помощью таблицы определяются номера узлов, за которыми данные вершины (фрагменты) закреплены. Для этого для каждого ф| 6 Ф; в таблице Тг ищется элемент таблицы равный I. Номер строки этого элемента определяет номер узла, на котором находится фрагмент ф|

X

Передача подтверждения узлам, за которыми закреплены фрагменты подмножества

X

Переход к Э2

Рисунок 6 - Состав и связи пунктов этапа Э] методики

2. Если присутствуют локальные изменения, передача другим ЛД информации о состоянии локальной ИЛМ "своего" узла, а также граф обхода;

3. Прием сообщений от ЛД других узлов.

В режиме ожидания ЛД должен выполнять следующие функции:

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

2. Если все подтверждения приняты, то передача подтверждения вверх по графу обхода;

3. Переход в режим мониторинга

Этап Э2 ("ожидание") методики представлен на рис. 7.

В режиме реконфигурации ЛД должен выполнять следующие функции:

1. Получение нового графа ИЛМ от связанных узлов в соответствии с графом обхода;

2. Выполнение изменений в структуре "своей" БД;

3. Передача данных об изменениях на другие ЛД в соответствии с топологией связей графа С(Ф,Х);

4. Переход в режим ожидания;

Этап Э3 (мониторинг) методики представлен на рис. 8.

Как видно их представленных выше обобщенных алгоритмов работы локальных диспетчеров в различных режимах, существенную долю при их реализации будут занимать процедуры обмена сообщениями между отдельными ЛД (»

=1, X)-

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

Можно предложить три подхода к проблеме организации информационного

обмена между узлами мультибазы:

обмен по принципу "каждый с каждым";

Обнуление списка узлов У,

на которых возникли изменения в ИЛМ

1

л! Формирование С! )

1

±1 Формирование О^У^.Е^) (сравнение С',(У„Е,) иС,(Г„£,))

Если О (V ,£",с)*0 , передать сообщение об изменении в

ИЛМ узла У) ДЩ 0 - # ¡)

1

2] Прием сообщений об изменениях ИЛМ узлов У, от ЛД, (/ =1,Ы;у # 0

1

±] Запись в список У номеров узлов, которые прислали сообщение, а также свой номер, если на «своем» узле возникли изменения

*

Если список У не пустой, перейти Эз, иначе - перейти к п.1

Рисунок 7 - Состав и связи пунктов эт'апа Э2 методики

- обмен по принципу "каждый со всеми";

- обмен посредством выделенных "досок объявлений".

|Очевидно, каждый из спо-

|собов имеет свои достоинства и

|недостатки. Предлагаемое в ра-

|боте решение основывается на

|интегральном подходе, когда

|информационный обмен осу-

Iществляется по принципу "каж-

Iдый со всеми заинтересованны-

!ми" в основе которого лежит ма-

!тематический аппарат пиринго-

Iвых сетей.

!Предлагаемая математиче-

!екая модель определяет меха-

!низм децентрализации глобаль-

I| ной схемы между узлами муль-

|! тибазы и описывает потоки со-

-1 общений об изменениях логиче-

1 ской структуры в локальных уз-| лах при реализации протокола их | взаимодействия Котег^-вида.

В ЧЕТВЕРТОЙ ГЛАВЕ "Результаты имитационного моделирования процесса децентрализованного формирования глобальной схемы муль-

тибазы данных" выполняется комплекс задач имитационного

моделирования процесса ре-Рисунок 8 - Состав и связи пунцов этапа Э3 ^у^ур^ации глобальной схе-

методики мы МуЛЬТИбазы с централизован-

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

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

Результаты моделирования представлены в виде полигонов частот предлагаемых альтернатив. Полученные данные позволяют рассчитать значения вероят-

Рисунок 8 - Состав и связи пунктов этапа Эз методики

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

Л

III |||

1!

Жив

а) б)

Рисунок 9 - Сравнительный анализ полигонов частот попаданий в заданный интервал среднего времени выполнения распределенного запроса с учетом реструктуризации при вероятности достижения цели 95 % при а) централизованном, б) децентрализованном управлении процессом

репликации метаданных

Сравнивая значения по выбранному критерию оценки эффективности получаем:

Рц1 (А/(/р3) < 8,4 с) = 0,8518 - вероятность того, что среднее время выполнения распределенного запроса не превысит заданного при централизованном управлении процессом репликации метаданных;

Рт (М'рз) ^ 8,4 с) = 0,9562 - вероятность того, что среднее время выполнения распределенного запроса не превысит заданного при децентрализованном управлении процессом репликации метаданных;

/Грев: 0,9562 > 0,8518

Критерий выполнен с превосходством в 10,44 %.

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

В ЗАКЛЮЧЕНИИ перечисляются основные результаты диссертационной работы. Делаются предложения по применению полученных результатов.

В ПРИЛОЖЕНИИ приводятся схемы разработанных алгоритмов моделирования.

ВЫВОДЫ ПО РЕЗУЛЬТАТАМ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Афанасьев В.В. Методика децентрализованного управления процессом репликации метаданных в мультибазе данных с глобальной схемой, учитывающая ее реструктуризацию // Системы управления и информационные технологии,

2013, №1.1(51)-С. 117-122.

2. Афанасьев В. В., Лебеденко Е. В. Использование графо-аналитических моделей для представления процесса формирования глобальной схемы мультибазы данных с учетом этапов ее реструктуризации // Интернет-журнал "Науковедение", 2013 №6 (19) [Электронный ресурс]. - Москва, 2013. - Режим доступа: http://naukovedenie.ru/PDF/59TVN613.pdf, свободный - Загл. с экрана.

3. Афанасьев В. В., Лебеденко Е. В. Графоаналитическая модель процесса формирования глобальной схемы мультибазы данных с учетом этапов ее реструктуризации // Информационные системы и технологии, 2014 № 1(81) - С. 12-18.

4. Алешин А.Д., Афанасьев В.В., Дунаев В.А., Лебеденко Е.В. Полезная модель "Система децентрализованного структурного управления распределенной базой данных". (Патент на полезную модель № 1Ш 126161 Ш от 20.03.13).

5. Афанасьев В. В., Лебеденко Е.В. Подходы к решению задачи оптимизации времени исполнения запросов в фрагментированных распределенных базах данных. // Информационные технологии моделирования и управления, 2010, №6(65) - С. 777-782.

6. Афанасьев В. В., Лебеденко Е.В. Формальная модель распределенной базы данных, использующей механизм фрагментации. // XVI Международная открытая конференция "Современные проблемы информатизации в экономике и обеспечении безопасности". Воронеж, 2011, - С. 49-51.

7. Афанасьев В.В., Алешин А.Д. Разработка системы анализа структуры распределенной базы данных, основанной на графовой модели. // XVI Международная открытая конференция "Современные проблемы информатизации в анали-

зе и синтезе технологических и программно-телекоммуникационных систем". Воронеж, 2011,-С. 393-394.

8. Афанасьев В.В., Алешин А.Д. Система децентрализованного управления структурой распределенной базы данных // Научная сессия ТУСУР-2012: Материалы Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых, Томск, 16-18 мая 2012 г. - Томск : В-Спектр, 2012: В 5 частях. -Ч. 2. - С. 242-245.

9. Afanasyev, V. V., Demchenko, А. V. Modeling of hierarchical objects in relational databases // Modern informatization problems in economics and safety: Proceedings of the XVIII-th International Open Science Conference. - Lorman, MS, USA: Science Book Publishing House, 2013. - P. 6-8.

10. Афанасьев В. В., Мешков Д. И., Силаев И. В. "Компьютерная программа для измерения времени запроса к базе данных "Query Time". Свидетельство о государственной регистрации программы для ЭВМ № 2012619081.

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

Подписано в печать 24.04.2014 г. Формат 30x42/4.

Усл. печ. л. 1. Тираж 100 экз. Отпечатано в типографии Академии ФСО России 302034, г. Орел, ул. Приборостроительная 35.

Государственное казённое образовательное учреждение высшего профессионального образования Академия Федеральной службы охраны Российской Федерации

Афанасьев Вадим Владимирович

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

Специальность 05.13.17 - Теоретические основы информатики

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

Научный руководитель кандидат технических наук Лебеденко Евгений Викторович

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

04201458991

Орел 2014

Оглавление

ВВЕДЕНИЕ......................................................................................................................5

ГЛАВА 1. РАСПРЕДЕЛЕННЫЕ БАЗЫ ДАННЫХ И ИХ РОЛЬ В

КОРПОРАТИВНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ...................................14

1.1. Исследование подходов к организации баз данных в распределенных корпоративных информационных системах...........................................................14

1.1.1 Применение концепции компьютеризированного интегрированного производства в распределенных корпоративных информационных системах..................................................................................................................14

1.1.2 Исследование методов интеграции данных в базах данных распределенных корпоративных информационных систем.............................17

1.2 Исследование архитектурных решений распределенных баз данных...........22

1.2.1 Исследование проблемы преобразования глобальной схемы в мультибазах данных..............................................................................................25

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

на примере КИС нефтепромыслового предприятия..............................................31

1А Моделирование процесса обработки распределенных запросов в мультибазе

данных ОАО "Газпромнефть-Муравленко"............................................................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 Состав этапа Эз ("реконфигурация")..........................................................71

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

3.4 Математическая модель протокола взаимодействия узлов мультибазы Шггеп^вида для оценки времени выполнения реструктуризации........................76

3.5 Оценка алгоритмов формирования схемы реструктуризации и восстановления данных.............................................................................................80

3.5.1 Постановка задачи статистического эксперимента для оценки

влияния исходных данных на использованный алгоритм................................81

Выводы по главе 3.....................................................................................................88

ГЛАВА 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

Приложение А..............................................................................................................132

Список использованных источников.........................................................................137

ВВЕДЕНИЕ

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

Широта спектра применимости КАИС в промышленности определяет номенклатуру эксплуатируемых информационных систем и обрабатываемых в них данных.

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

- сбора, обработки, хранения данных мониторинга;

- моделирования, оценки и прогнозирования состояния активов;

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

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

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

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

Такими особенностями РБД являются:

1. Поддержка модели распределенных данных, на основе некоторого структурного формализма (например, реляционного). Это отличает РБД от распределенных файловых систем.

2. Наличие единого метода доступа к распределенным данным, поддерживающего единый интерфейс высокого уровня.

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

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

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

1. Ориентированные на обеспечение независимости хранимых данных и процедур доступа к ним от конкретных реализаций сетевой среды, операционных систем и локальных СУБД, расположенных в узлах РБД.

2. Ориентированные на поддержание таких характеристик РБД, как целостность данных, их безопасность и оптимальная (по требуемым показателям) обработка распределенных запросов.

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

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

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

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

_| Распределенные базы данных

Гомогенные

Наличие глобальной схемы • Внутренние функции СУБД для обеспечения интерфейса между глобальным и локальным уровнями_

__Мультибазы дачных с глобальной схемой

Гетерогенные

Наличие глобальной схемы

Пользовательский интерфейс СУБД для отображения между глобальным и локальным уровнями_

Федеративные базы данных

Гетерогенные Частичная глобальная схема

Пользовательский интерфейс СУБД для отображения между глобальным и локальным уровнями_

Неоднородные системы мультибаз данных _с общим языком доступа_

Гетерогенные Функции языка доступа

Пользовательский интерфейс СУБД для отображения между глобальным и локальным уровнями_

Однородные системы мультибаз данных _с общим языком доступа_

Гомогенные Функции языка доступа

Пользовательский интерфейс СУБД н некоторые внутренние функции СУБД для отображения между глобальным н локальным уровнями_

Интсроперабсльные системы

Множество типов источников данных Отсутствие глобальной шггеграцин

Реализация интерфейса между глобальным и локальным уровнями средствами приложении _

Рисунок 1 - Таксономия типов распределенных баз данных

В современных информационных системах часто приходится строить распределенную базу данных на основе уже имеющихся унаследованных БД, т.е. "снизу-вверх". При этом необходимо учитывать низкую степень интеграции хранящихся в них данных. Такие системы часто строятся по принципу мультибаз данных, как совокупность локальных БД и управляющих ими СУБД, имеющих глобальную схему (ГС). При этом каждый узел мультибазы является независимой с точки зрения администрирования локальной БД, а информация обо всей структуре мультибазы данных с целью реализации распределенных запросов хранится в виде метаданных на каждом узле. Каждая локальная БД имеет свою структуру, не зависящую от других, при этом межузловые связи поддерживаются на уровне глобальной схемы [3,4].

В зависимости от степени интегрированности хранящихся в РБД данных глобальная схема может быть следующих видов [4]:

1. Централизованная схема, данные которой расположены на специально выделенном коммуникационном узле.

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

3. Секционированная схема. Децентрализованный вариант глобальной схемы, при котором на каждом узле содержится его локальный вариант схемы только для объектов, хранимых на этом узле. Общая схема является объединением всех локальных схем.

4. Секционированная схема с централизованной репликацией. В этом варианте схемы на каждом узле содержится его локальная схема, а на специально выделенном центральном узле хранятся актуальные реплики всех этих локальных схем.

Особенностью процесса эксплуатации мультибаз данных является потенциальная возможность проведения реструктуризации узлов, входящих в ее состав. Реструктуризация - изменение структуры глобальной схемы в рамках одной мо-

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

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

Таким образом, существует противоречие между требованием, предъявляемым к времени выполнения распределенного запроса, и возрастающими задержками, возникающими вследствие проводимых процессов реструктуризации при увеличении количества узлов мультибазы.

Не смотря на то, что исследования в данной области ведутся достаточно давно и им посвящено большое количество публикаций известных специалистов как российских - Калиниченко Л.А., Когаловский М.Р., Гаврилов Д.А., Мамико-нов А.Г., Кузнецов С.Д., Кульба В.В. [32,12, 18,13, 29, 34, 35], так и зарубежных - Ullman, Lenzerini М., Widom, Simon, Valduriez, Celko, Шаша, Д., Бонне Ф. [20, 36, 24, 37], - проблема интеграции данных продолжает оставаться актуальной.

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

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

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