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

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

Гудков Кирилл Сергеевич

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ УПРАВЛЕНИЯ ОБРАБОТКОЙ ИНФОРМАЦИИ В КОРПОРАТИВНЫХ АВТОМАТИЗИРОВАННЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

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

2 2 [±*Р 20(2

Москва-2012

005013308

005013308

Работа выполнена на кафедре управляющих и информационных систем Московского физико-технического института (государственного университета)

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

профессор

БОНДАРЕНКО Александр Викторович

Официальные оппоненты: ВИЗИЛЬТЕР Юрий Валентинович,

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

БОНДАРЕВ Александр Евгеньевич, кандидат физико-математических наук, Институт прикладной математики им. М.В. Келдыша РАН, старший научный сотрудник

Ведущая организация: Вычислительный центр имени

A.A. Дородницына РАН

Защита диссертации состоится « IЭ » скж/^хл^-_2012 года

в ]о, ч. МО мин, на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская область, г. Долгопрудный, Институтский пер., д. 9, ауд. 903 кпм.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан « | Ч » J^^-vtw^._2012 года

Ученый секретарь диссертационного совета ^ Д 212.156.05

¿^Z^y—— Федько Ольга Сергеевна

Общая характеристика работы

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

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

3

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

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

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

4

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

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

Применение рекомендуемых в диссертационной работе подходов позволит:

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

• построить отчётность, соответствующую предъявляемым к ней требованиям достоверности и актуальности;

• принимать на основе этой отчётности правильные управленческие решения;

• повысить интеграцию бизнес-процессов.

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

Задачи исследования. Основные задачи диссертационной работы:

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

2. выявление с помощью моделей соответствующих характеристик вычислительных алгоритмов и комплексов программ;

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

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

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

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

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

6

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

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

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

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

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

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

работает на 15% быстрее метода, использующего AVL-деревья, и до трёх раз быстрее метода, использующего хэш-таблицы.

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

• L, LI, LII научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2007, 2008, 2009),

• XVI международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009», (Москва, МГУ, 2009),

• VI международной научно-практической конференции «Ключевые проблемы современной науки - 2010», (Болгария, София, 2010),

• VII международной научно-практической конференции «Актуальные научные достижения - 2011», (Чехия, Прага, 2011),

• юбилейной всероссийской научно-технической конференции «Моделирование авиационных систем», (Москва, 2011),

• а также на научных семинарах базовой кафедры МФТИ «Управляющие и информационные системы», научных семинарах ВЦ РАН и на научно-техническом совете ФГУП «ГосНИИАС» (Москва, 2011-2012).

Доклады на L и LI научных конференциях МФТИ, как лучшие в секции, были отмечены дипломами победителя.

Публикации. Основные положения работы отражены в 11 публикациях, в том числе двух, [6,7], в издании из списка, рекомендованного ВАК РФ.

Структура и объём диссертации. Диссертация состоит из введения, шести глав, заключения и списка использованных источников. Объём работы составляет 133 страницы. Список использованных источников содержит 92 наименования.

Краткое содержание работы

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

1. Корпоративные справочники должны формироваться на основании данных открытых внешних источников во всех случаях, когда эти данные удовлетворяют корпоративным требованиям надёжности, актуальности и полноты.

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

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

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

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

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

1. загрузки справочников из открытых источников;

2. разархивации данных;

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

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

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

6. переноса изменений.

На первых двух этапах формируется множество OD справочников из внешних источников. В консолидированной базе данных используется лишь часть этих справочников SOD = {odt,...,odN}czOD. На основе справочников из множества SOD формируется множество справочников в промежуточном формате ID = {«/, ,..Jd4N} = JDnew u Юм и lDchungm. В множестве lDnew

10

содержится текущая версия справочников, а в множестве Юм содержится сохранённая предыдущая версия справочников. Структура справочников совпадает со структурой таблиц консолидированной базы данных нормативно-справочной информации, наполнение справочников совпадает с наполнением справочников из внешних источников. Множество IDchangcs

^changa = IDchange.mdJ U Ща,angcsJcl

разбивается на два подмножества:^ , где

(J^changcsaU П ^changesdel = ^

Udcd„eIDch Jel ¡idea,, е Юс1М

< и ^ . Таким образом, множество

\idcdn = idon -idn^/n \jdcan = idnn -idonVn

lDchan);es содержит изменения, которые необходимо внести в

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

\RCDB = DRCDB и CRCDB разбивается на два подмножества: < , где

{DRCDfí глСЯСПВ = <2

DRCDB = {drl,...,drK}- справочники, формируемые на основе внешних

данных, содержащихся в множестве ID, a CRCDB- {а\,...,сгк}-

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

Посредством lk обозначено число справочников внешних источников,

отвечающих заданному справочнику drK е DRCDB. Тогда для

синхронизации данных между внешним источником и консолидированной

базой данных необходимо для каждого drK выполнить:

1. Перенос /* -справочников в промежуточном формате из множества IDnew в множество Юм. Функция, выполняющая данный этап, обозначена

^Manipúlale '■ ~~► •

2. Преобразование -справочников из множества SOD к промежуточному формату. Результаты фиксируются в множестве lDnew. Функция, выполняющая данный этап, обозначена F0l: SOD —> IDnew.

3. Сравнение lk-справочников из множества Ю„т с 1к-справочниками из множества Юм. Результаты фиксируются в множестве IDchimges. Функция, выполняющая данный этап, обозначена ^Ge,o,anges :HID-+HIDchanges, где множество HID с JDmw хЮиЫ состоит из пар (idnn,ido„)<r>od„, а множество HIDchanges^IDchangesaddxIDdiangesM состоит из пар (idca„,idcdn) <-»od„.

4. Модификация справочника drk в соответствии с 21к -справочниками из множества IDdtanges. Результаты фиксируются в множестве DRCDB.

Множество SlDchanscs = {sid1,...,sidK} с 2!Щк"'!" включает в себя подмножества пар изменений, отвечающие заданным справочникам drk. Множество CIDDR определено следующим образом: C/DDR ç SIDchanges х DRCDB. Каждая тройка в составе C1DDR включает в себя справочник консолидированной базы данных и изменения, которые над ним необходимо сделать. С учетом введенных обозначений, функция, выполняющая данный этап, определена следующим образом: Fm : CIDDR DRCDB.

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

F = * FCeiaianges(idn,,ido,)*Fm{idcahidcdhdrk).

к 1

Далее в главе 2 математическая модель иллюстрируется на примере импорта данных российского административно-территориального деления. После этого рассматриваются особенности реализации функций Flh„ipu!ale, b'(n, FGelClu2„ges и Fm в рамках построения автоматизированной системы импорта данных из внешних источников. Вычисление FKhnjpulale представляет

лишь технические сложности. Вычисление F01 не может быть полностью автоматизировано. Шаги, предпринятые к частичной автоматизации, описаны в тексте диссертационной работы. Приведём алгоритм вычисления функции J'ce,Changes '■

1. Данные из справочника ido е ЮоЫ заносятся в красно-чёрное дерево.

2. Осуществляется линейный проход по кортежам справочника idneIDliew. Для каждого кортежа проверяется, содержится ли он в красно-чёрном дереве. Если нет, то он присоединяется к справочнику idea е IDchansesadd.

3. Данные из справочника idneIDnew заносятся в красно-чёрное дерево.

4. Осуществляется линейный проход по кортежам справочника ido е lDoU. Для каждого кортежа проверяется, содержится ли он в красно-чёрном дереве. Если нет, то он присоединяется к справочнику ided ^IDchangesdd .

Автоматизированная система импорта данных из внешних источников позволяет использовать 3 режима вычисления FK, каждый из которых может оказаться полезным для конкретной практической задачи:

1. по файлам изменений создаются SQL-сценарии для добавления или удаления записей, которые затем выполняются;

2. по мере обработки файлов изменений SQL-сценарии создаются в памяти и выполняются;

3. перенос данных осуществляется при помощи сервисов Microsoft SQL Server (DTS, SSIS).

В главе 3 рассматривается задача интеграции справочников внутренних источников и формирования на их основе таблиц консолидированной базы данных нормативно-справочной информации. Выводится общая формула для объединения справочников с совпадающими естественными первичными ключами и различным списком атрибутов: T(^,...,Aa,Bl,...,Bm,Q,...,Ck) = aCi(R)uaCj(pSiAr_^A.....Ci)(S))u aCj(

R(4>»--4,A—>Bm)xPs<Ar..j,jcl..jct)(S))> где С, =Ц...а„ gS),

С2 = g Л), С3 = (Лл,...ая = ^Л|...а„). Далее рассматривается обобщение на случай применения суррогатных первичных ключей при наличии атрибутов, которые можно использовать в качестве естественных первичных ключей. В конце главы обсуждается решение проблем, связанных с наличием противоречий в исходных данных.

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

Корпоративной автоматизированной информационной системе ставится в соответствие ориентированный граф G(V,E), где V - это множество участков информационной системы, а Е - множество каналов связи между ними. Рассматривается информационная система, имеющая «звёздную топологию»:

(3!v° s V : Vv * v° (v°,v) e £) & (Vv1 ф v°Vv2 (((v',v2) г E) &((v2,v') g П))). v° - это участок с консолидированной базой данных, v',/"*0 -территориально удалённый участок корпоративной автоматизированной информационной системы.

Множества TOAD'= {tdQ,ld[...,td'^,...}содержат времена согласования

данных участка с консолидированной базой данных v° и территориально удалённого участка v'./VO. Множество TOA = {t0,tl,...,tJ,...} содержит времена синхронизации консолидированной базы данных и внешних источников. Взаимное расположение этих времён можно представить следующим образом:

К ''/o+i'-'O,>idi>tM+i'--->bP>td'p'bP^'--tbp>tdP'tjp+i>--'tJ'"- Функции 113

множеств SFC ={SFC[,...,SFC'K} выполняют изменения в справочниках из

множества ОКСО В в интервале времени (и1'р,1с]'р+1). Любая из этих функций может быть представлена следующим образом: $17С'к =х/с[ Если у +1 = }р, то ЗРС'к - тождественное преобразование. Функции из множеств SFCS'={SFCS,^,SFCS2,...,SFCS'M|} выполняют необходимые для синхронности данных изменения в справочниках х'т территориально удалённого участка у'. Любая из этих функций может быть представлена следующим образом: . Если _//)+1 = }р, то

81'"С$'т - тождественное преобразование. Связь между справочниками в смежные моменты синхронизации выражается следующим образом:

= ЯРС^й/,)) = **М *...*

Любая из функций я/си л/с.упроизводит два типа изменений над справочниками: добавление кортежа и удаление кортежа. Модификация кортежа - это суперпозиция перечисленных операций. Поэтому любая из функций л/си я/ся изоморфна отношению, в котором к столбцам операнда добавлен ещё один целочисленный столбец, означающий тип операции. Справедлива теорема 4.1 об изоморфизме.

Теорема 4.1. Изменения, происходящие в справочниках в составе КЕД НСИ, могут быть представлены в реляционных таблицах.

Предлагается следующий порядок тиражирования информации:

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

2. Справочники х'т и с1гк связаны при помощи операторов проекции,

переименования и выбора реляционной алгебры:

15

XL = <Jc(^Ay1^.A,.(Ps(AlAl...AL)(cirk))) ■ Связь между таблицей cs'm, изоморфной SFCS'm, и справочником crk е CRCDB выглядит следующим образом: CSL = M^AlA2...AjPs<AlA:../l)(crk)))- В результате, таблицы cs'm формируются как наборы данных в памяти на сервере репликации. Сервер репликации расположен на участке корпоративной автоматизированной информационной системы с центральной консолидированной базой данных нормативно-справочной информации.

3. Сформированные таблицы передаются клиенту репликации, установленному в территориально удалённом участке корпоративной автоматизированной информационной системы. В конкретной реализации системы репликации данных для этого могут использоваться DCOM, сокеты поверх TCP/IP или HTTP.

4. Каждая из функций SFCS'm получается на основе изоморфизма с таблицей

т

5. Справочники s'm изменяются при помощи функций SFCSlm.

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

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

Теорема 5.1. Время работы и объём передаваемых к КБД НСИ данных алгоритма, использующего хранение предыдущей версии справочника, меньше времени работы и объёма передаваемых к КБД НСИ данных алгоритма, не использующего его.

Теорема 5.2. Объём передаваемых данных между КБД НСИ и территориально удалёнными участками корпоративной автоматизированной информационной системы меньше при использовании алгоритма с хранением предыдущей версии справочников.

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

Теорема 5.3. Объём передаваемых по сети данных при использовании КБД НСИ и системы репликации данных меньше, чем при использовании автоматизированной системы импорта данных из внешних источников на каждом из территориально удалённых участков корпоративной автоматизированной информационной системы, причём разность объёмов увеличивается с ростом их числа и размеров используемых справочников.

Далее проводится сравнение производительности авторского алгоритма /гСй0шяуа. на основе использования красно-чёрных деревьев с

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

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

При создании справочников международного административно-территориального деления необходимо обеспечить поддержку исторической информации, поддержку иерархической информации и поддержку возможности репликации данных. Предлагается ко всем таблицам, работающим с историческими данными, добавить поле, содержащее время создания кортежа, и таблицу-дубликат, содержащую суррогатный первичный ключ, поля исходной таблицы, поле, содержащее время удаления кортежа и специфичные для конкретного случая дополнительные поля. Тогда отношение, соответствующее содержимому справочника на заданный момент времени, вычисляется по следующей формуле: Т = А (<тС] (Я) и (Я)), где С, = Б1агФа1е < СиггепЮаСе, С2=

Шп & (Я1агЮа1е < СиггШПШе) & (Ве1е1сЮа1е > СиггепЮШе). Я используется для обозначения исходной таблицы, Я - для обозначения таблицы-дубликата. Предикат ЬМт проверяет, является ли запись самой ранней из удовлетворяющих условию {ОеШсВсИе > СиггепЮа1е). Для поддержки работы с иерархическими данными предлагается модификация существующего подхода, основанного на добавлении родительского идентификатора РагепШ) и дочернего идентификатора Ю. В диссертационной работе рекомендуется использование ЫЮ-репликации. При её использовании для поддержки репликации не требуется изменять структуру справочников.

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

Для выбора структуры данных, наиболее эффективной с точки зрения скорости работы использующего её авторского алгоритма вычисления РСа0ю„еех, было проведено статистическое сравнение линейного списка,

бинарного дерева поиска, хэш-таблицы, АУЬ-дерева и красно-чёрного

дерева. Результаты эксперимента - это количественные данные, то есть замеры времени работы алгоритмов на конкретных данных международного административно-территориального деления. Предполагается разбиение этих данных на группы в зависимости от качественного параметра - типа используемого алгоритма. После прохождения логарифмического преобразования данные компьютерных экспериментов прошли тесты на гомогенность дисперсии Левена и на нормальность распределения Д'Агостино. В результате, к ним стало возможным применить дисперсионный анализ Фишера, который показал значимость различий между группами. Применение критериев Ньюмана-Кейлса и Тыоки позволило расположить алгоритмы по порядку скорости их работы: красно-чёрное дерево, АУЬ-дерево, хэш-таблица, бинарное дерево поиска, линейный список. Вычислительные эксперименты и их обработка методом наименьших квадратов позволили получить численные оценки сложности алгоритмов. Результаты компьютерного моделирования оказались согласованы с ожиданиями на основе теоретических оценок, полученными с использованием теории сложности.

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

Основные результаты работы

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

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

19

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

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

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

Список публикаций по теме диссертации

1 .Бондаренко A.B., Гудков К.С. Математическое моделирование миграции нормативно-справочной информации в корпоративных информационных системах // Моделирование авиационных систем: Сб. аннотаций докладов / НИИАС. - М., 2011. - С. 110-111.

2. Бондаренко A.B., Гудков К.С. Создание таблиц нормативно-справочной информации на основе разнородных внешних справочников // Модели и методы обработки информации: Сб.ст. / МФТИ. - М., 2009. - С. 148-152.

3. Гудков КС. Выделение изменений в версиях открытых баз данных при построении автоматизированной системы импорта внешних справочников // Основни проблеми на съвременната наука - 2010. Том 22 Съвременни технологии на информации Математика Здание и архитектура. -София, 2010.-С. 16-19.

4. Гудков КС. Консолидация нормативно-справочной информации в распределённых информационных системах // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды 51-й научной конференции МФТИ. / МФТИ. - М., 2008. -С. 86-88.

5. Гудков КС. Математическая модель управления нормативно-справочной информацией в распределенных информационных системах // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды 52-й научной конференции МФТИ. / МФТИ. - М., 2009. - С. 123-125.

6. Гудков КС. Математическая модель управления справочниками административно-территориального деления стран СНГ в корпоративных информационных системах // Прикладная информатика. - 2010. - № 5(29). -С. 117-124.

7. Гудков КС. Механизмы интеграции внутрикорпоративных справочников // Прикладная информатика. - 2011. - № 6(36). - С. 14-22.

8. Гудков КС. Моделирование импорта данных разнородных внешних справочников в консолидированную базу данных нормативно-справочной информации // Актуальные проблемы гуманитарных и естественных наук. -2009.-№9.-С. 11-14.

9. Гудков КС. Оценка времени работы одного алгоритма, находящего разность в версиях открытых внешних справочников // Aktuální vymozenosty vÊdy - 2011. Dil 20. Technické vëdy. Moderní informaöni technologie. - Прага, 2011.-С. 59-62.

10. Гудков КС. Решение проблемы готовности в рамках построения системы репликации баз данных // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды 50-й научной конференции МФТИ. / МФТИ. - М., 2007. -С. 62-64.

11 .Гудков КС. Управление внешней нормативно-справочной информацией в распределённых информационных системах // Материалы XVI Международной конференции студентов, аспирантов и молодых ученых "Ломоносов-2009", секция "Вычислительная математика и кибернетика". / МГУ.-М., 2009.-С. 23.

В работах с соавторами [1, 2] лично соискателем выполнено следующее:

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

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

Гудков Кирилл Сергеевич

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ УПРАВЛЕНИЯ ОБРАБОТКОЙ ИНФОРМАЦИИ В КОРПОРАТИВНЫХ АВТОМАТИЗИРОВАННЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ

Автореферат

Подписано в печать 12.03.2012. Формат 60x84 1/16. Усл. печ. л. 1,0. Тираж 80 экз. Заказ № 303.

ФГУП Государственный научно-исследовательский институт авиационных систем 125319, Москва, ул. Викторенко, 7

61 12-1/743

Московский физико-технический институт (государственный университет) Кафедра управляющих и информационных систем

На правах рукописи УДК 004.65

ГУДКОВ Кирилл Сергеевич

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

Специальность 05.13.18 «Математическое моделирование, численные методы и комплексы программ»

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

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

доктор физико-математических наук

профессор А.В. Бондаренко

МОСКВА 2012

СОДЕРЖАНИЕ

СПИСОК СОКРАЩЕНИЙ.....................................................................................4

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

ГЛАВА 1. АНАЛИЗ ДОСТОИНСТВ И НЕДОСТАТКОВ ИЗВЕСТНЫХ МЕТОДОВ УПРАВЛЕНИЯ ОБРАБОТКОЙ НОРМАТИВНО-СПРАВОЧНОЙ ИНФОРМАЦИИ....................................................................................................13

1.1. Формулировка задачи........................................................................................13

1.2. Задача хранения нормативно-справочной информации и доступа к ней .... 17

1.3. Задача наполнения справочников данными....................................................20

1.4. Задача тиражирования данных из КБД НСИ в локальные базы данных территориально удалённых участков корпоративной автоматизированной информационной системы..........................................................................................22

1.5. Классификация видов репликации с точки зрения взаимодействия двух выбранных участков информационной системы.....................................................23

1.6. Классификация видов репликации с точки зрения взаимодействия участков корпоративной автоматизированной информационной системы в целом............28

1.7. Общие выводы по задаче тиражирования нормативно-справочной информации..................................................................................................................30

1.8. Выбор структуры справочников......................................................................31

1.9. Математический аппарат для описания работы с реляционными данными32 ГЛАВА 2. ПЕРЕНОС ДАННЫХ СПРАВОЧНИКОВ ИЗ ВНЕШНИХ ИСТОЧНИКОВ В КОНСОЛИДИРОВАННУЮ БАЗУ ДАННЫХ НОРМАТИВНО-СПРАВОЧНОЙ ИНФОРМАЦИИ.........................................38

2.1. Формальная постановка задачи........................................................................38

2.2. Иллюстрация математической модели на конкретном примере..................47

2.3. Графическая иллюстрация математической модели......................................50

2.4. Алгоритмическое решение...............................................................................50

2.5. Программное решение.......................................................................................55

ГЛАВА 3. ПЕРЕНОС ДАННЫХ СПРАВОЧНИКОВ ВНУТРЕННИХ ИСТОЧНИКОВ В КОНСОЛИДИРОВАННУЮ БАЗУ ДАННЫХ НОРМАТИВНО-СПРАВОЧНОЙ ИНФОРМАЦИИ.........................................60

3.1. Графическая иллюстрация модели интеграции внутренних справочников 61

3.2. Практические методы слияния внутренних справочников...........................61

ГЛАВА 4. МЕТОДЫ ТИРАЖИРОВАНИЯ ДАННЫХ В ДОЧЕРНИЕ САЙТЫ КОРПОРАТИВНОЙ АВТОМАТИЗИРОВАННОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ...................................................................65

4.1. Формальная постановка задачи........................................................................65

4.2. Программное решение.......................................................................................74

4.3. Тиражирование программного обеспечения...................................................81

ГЛАВА 5. СРАВНИТЕЛЬНЫЙ АНАЛИЗ РАЗРАБОТАННЫХ АЛГОРИТМОВ С ТОЧКИ ЗРЕНИЯ ИХ ПРОИЗВОДИТЕЛЬНОСТИ И СОЗДАВАЕМОЙ НАГРУЗКИ НА КАНАЛЫ СВЯЗИ НА ОСНОВЕ ТЕОРЕТИЧЕСКИХ ОЦЕНОК.............................................................................84

5.1. Оценка целесообразности хранения предыдущей версии справочников.... 84

5.2. Оценка целесообразности создания КБД НСИ...............................................86

5.3. Сравнение алгоритмов вычисления Роею™^.................................................87

ГЛАВА 6. АНАЛИЗ РАЗРАБОТАННЫХ АЛГОРИТМОВ ПО РЕЗУЛЬТАТАМ КОМПЬЮТЕРНОГО МОДЕЛИРОВАНИЯ.........................95

6.1. Описание среды моделирования......................................................................95

6.2. Сравнение применения АСИДВИ для цельных данных с применением

АСИДВИ совместно с хранением предыдущей версии справочников................ 103

6.3. Сравнение с алгоритмом прямого применения АСИДВИ на всех участках

информационной системы........................................................................................107

6.4. Сравнение алгоритмов вычисления РсйОм^...............................................109

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.........................................125

СПИСОК СОКРАЩЕНИЙ

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

ERP = Enterprise Resource Planning; LRO = Linked Replica Objects; MDM = Master Data Management;

АСИДВИ = Автоматизированная система импорта данных из внешних

источников;

БД = База данных;

ИСВИ = Интегратор справочников внутренних источников;

КАИС = Корпоративная автоматизированная информационная система;

КБД = Консолидированная база данных;

КБД НСИ = Консолидированная база данных нормативно-справочной информации;

КСП НСИ = Корпоративная система поддержки НСИ; НСИ = Нормативно-справочная информация; СУБД = Система управления базами данных.

ВВЕДЕНИЕ

Актуальность темы

В настоящее время корпоративные автоматизированные информационные системы (КАИС), как правило, не обходятся без использования нормативно-справочной информации (НСИ, master data). В значительном количестве предприятий не существует корпоративной системы поддержки НСИ (КСП НСИ, MDM) [1]. В результате, в базах данных (БД) подразделений предприятий используются разрозненные справочники, содержащие неполную, неактуальную, а зачастую и противоречивую информацию. В целях исключения дублирования справочников в различных БД и устранения противоречий в содержащейся в них НСИ необходимо решить задачу создания и поддержки консолидированной базы данных нормативно-справочной информации (КБД НСИ). Задачу наполнения КБД НСИ данными необходимо возложить на специализированное программное обеспечение, способное контролировать актуальность и непротиворечивость информации, содержащейся в справочниках. Для решения этой задачи были созданы автоматизированная система импорта данных из внешних источников (АСИДВИ) и интегратор справочников внутренних источников (ИСВИ). Внутренние справочники -это таблицы НСИ, данные которых формируются в процессе деятельности самого предприятия. Внешние справочники - это таблицы НСИ, формирование которых не зависит от специфики деятельности предприятия. Для управления обработкой нормативно-справочной информации в рамках всей КАИС необходимо также обеспечить надёжное тиражирование данных. Для решения этой задачи была создана система репликации баз данных применительно к гетерогенной среде. Предлагаемая схема управления обработкой нормативно-справочной информации показана на рис. 1:

Внутренние КБД НСИ Подразделения

справочники предприятия

Рисунок 1 Схема управления обработкой НСИ

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

• определить справочники из внешних источников, которые могут быть использованы в качестве справочников КБД НСИ;

• создать согласованную с КАИС структуру внешних справочников КБД НСИ;

• создать АСИДВИ, способную осуществлять синхронизацию изменяющихся во времени внешних справочников и внешних справочников в составе КБД НСИ;

• создать согласованную с КАИС структуру внутренних справочников в составе КБД НСИ;

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

Применение созданной КСП НСИ позволит предприятию поддерживать в справочниках КАИС актуальную, полную и непротиворечивую информацию.

Методы, используемые в процессе создания КБД НСИ и внедрения МОМ-системы, могут применяться при слиянии нескольких корпоративных автоматизированных информационных систем. При этом интеграция внутренних справочников принципиально не отличается от слияния внутренних справочников нескольких подразделений одного предприятия. Если в объединяющихся предприятиях используются одни и те же внешние данные, то порядок создания внешних справочников также остаётся прежним. Те же методы используются и при поглощении предприятий. Ещё одно практическое применения предложенных методов - это создание информационной системы предприятия при его открытии. Разработанные методы позволяют:

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

• построить отчётность, соответствующую предъявляемым к ней требованиям достоверности и актуальности;

• принимать на основе этой отчётности правильные управленческие решения;

• повысить интеграцию бизнес-процессов.

Цель работы

Целью диссертационной работы является решение проблемы управления обработкой нормативно-справочной информации в

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

Задачи исследования

Основные задачи диссертационной работы:

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

• выявление с помощью моделей соответствующих характеристик вычислительных алгоритмов и комплексов программ;

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

Методы исследования

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

Научная новизна полученных результатов

Научная новизна диссертационного исследования состоит в следующем:

• Для управления обработкой нормативно-справочной информации в корпоративных автоматизированных информационных системах

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

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

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

Практическая значимость исследования

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

Апробация работы

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

• Ь, Ы, Ы1 научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2007, 2008, 2009),

• XVI международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009», (Москва, МГУ, 2009),

• VI международной научно-практической конференции «Ключевые проблемы современной науки -2010», (Болгария, София, 2010),

• VII международной научно-практической конференции «Актуальные научные достижения - 2011», (Чехия, Прага, 2011),

• юбилейной всероссийской научно-технической конференции «Моделирование авиационных систем», (Москва, 2011),

• а также на научных семинарах базовой кафедры МФТИ «Управляющие и информационные системы», научных семинарах ВЦ РАН и на научно-техническом совете ФГУП «ГосНИИАС» (Москва, 2011-2012).

Доклады на Ь и И научных конференциях МФТИ, как лучшие в секции, были отмечены дипломами победителя.

Публикации

Основные положения работы отражены в 11 публикациях [2-12]. В том числе две работы [9, 12] опубликованы в издании из списка, рекомендованного ВАК РФ.

Краткое содержание работы

Во введении даётся общая характеристика работы.

В главе 1 задача управления обработкой нормативно-справочной информации разбивается на 4 подзадачи: хранение и использование нормативно-справочной информации; выбор структуры внешних и внутренних справочников в составе КБД НСИ; заполнение внешних и

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

В главе 2 рассматривается задача переноса данных из внешних источников в таблицы КБД НСИ. Строится математическая модель на основе реляционной алгебры. Даётся алгоритмическое решение задачи, а также описание программного продукта (АСИДВИ), в котором предложенные алгоритмы реализованы на практике.

В главе 3 рассматривается задача интеграции справочников внутренних источников и их переноса в таблицы КБД НСИ. Строится математическая модель на основе реляционной алгебры. Даётся алгоритмическое решение задачи, а также описание программного продукта (ИСВИ), в котором предложенные алгоритмы реализованы на практике.

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

информационной системы для работы с их локальными базами данных. При этом рассматривается два подхода: использование тиражированных? справочников территориально удалённых подразделений предприятия и применение \УЕВ-приложений ^еЬНсайош).

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

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

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

ГЛАВА 1. АНАЛИЗ ДОСТОИНСТВ И НЕДОСТАТКОВ ИЗВЕСТНЫХ МЕТОДОВ УПРАВЛЕНИЯ ОБРАБОТКОЙ НОРМАТИВНО-СПРАВОЧНОЙ ИНФОРМАЦИИ

1.1. Формулировка задачи

Существует два вида программных систем - вычислительные системы и информационные системы [13]. В рамках информационных систем решаются задачи сбора, хранения и обработки информации. Существуют различные определения распределённых информационных систем. В частности, согласно Ладыженскому [14, 15] информационная система считается распределённой, если она удовлетворяет 12 правилам Дейта [16, 17]. При другом подходе для того, чтобы считать информационную систему распределённой достаточно, чтобы её фрагменты были расположены в территориально удалённых точках и имели возможность взаимодействовать между собой посредством сетевых технологий [18]. Фрагменты (участки, компоненты, отделы) рассматриваемой в работе информационной системы имеют собственные согласованные между собой локальные базы данных и расположены в территориально удалённых точках. Поэтому рассматриваемая в данной работе корпоративная автоматизированная информационная система является распределённой согласно второму определению, но не является распределённой согласно первому