Содержание к диссертации
Введение
Глава 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. Сравнение алгоритмов вычисления FGetChanges 87
Глава 6. Анализ разработанных алгоритмов по результатам компьютерного моделирования 95
6.1. Описание среды моделирования 95
6.2. Сравнение применения АСИДВИ для цельных данных с применением АСИДВИ совместно с хранением предыдущей версии справочников 103
6.3. Сравнение с алгоритмом прямого применения АСИДВИ на всех участках информационной системы 107
6.4. Сравнение алгоритмов Вычисления FoetChanges 109
Заключение 124
Список использованных источников 125
- Классификация видов репликации с точки зрения взаимодействия двух выбранных участков информационной системы
- Практические методы слияния внутренних справочников
- Сравнение алгоритмов вычисления FGetChanges
- Сравнение алгоритмов Вычисления FoetChanges
Введение к работе
В работе проводится комплексное исследование проблемы управления обработкой нормативно-справочной информации с применением современной технологии математического моделирования и вычислительного эксперимента. Строятся математические модели для импорта внешних справочников, интеграции внутрикорпоративных справочников и тиражирования справочников. Доказанные в рамках моделей теоремы иллюстрируются вычислительными экспериментами и используются при разработке алгоритмов и комплекса программ. Комплекс программ для решения задачи управления обработкой нормативно-справочной информации включает автоматизированную систему импорта данных из внешних источников, интегратор справочников внутренних источников, систему репликации баз данных. В ходе решения задачи импорта данных был разработан, обоснован и протестирован с применением современных компьютерных технологий эффективный вычислительный метод нахождения изменений между различными версиями справочников на основе красно-чёрных деревьев. В ходе решения прикладной проблемы управления обработкой нормативно-справочной информации были применены математическое моделирование, численные методы и комплексы программ.
Актуальность темы. В настоящее время корпоративные автоматизированные информационные системы, как правило, не обходятся без использования нормативно-справочной информации. Существует три метода её хранения: централизованный, децентрализованный и смешанный. В последние годы сформировалась устойчивая тенденция к отделению функциональности по управлению обработкой нормативно-справочной информации от функциональности автоматизированных информационных систем по управлению обработкой прочих корпоративных данных. Для
государственных ведомств и крупных корпораций характерно наличие центральной базы данных и разветвлённой структуры дочерних баз данных, расположенных на территориально удалённых участках корпоративной автоматизированной информационной системы. Именно централизованная структура хранения нормативно-справочной информации рассматривается в диссертационной работе. Справочники формируются в консолидированной базе данных нормативно-справочной информации, откуда тиражируются в дочерние базы данных территориально удалённых участков корпоративной автоматизированной информационной системы.
В качестве технологии тиражирования нормативно-справочной информации используется система репликации баз данных, способная функционировать в гетерогенной среде. Специфика нормативно-справочной информации накладывает дополнительные требования на системы синхронизации данных, которые на сегодняшний день не были всесторонне исследованы. Исследование этого вопроса позволит выбрать подходящую для тиражирования нормативно-справочной информации систему репликации баз данных применительно к гетерогенной среде.
Использование системы репликации позволяет обеспечить согласованность данных между консолидированной базой данных нормативно-справочной информации и дочерними базами данных территориально удалённых участков корпоративной автоматизированной информационной системы. Поэтому для актуальности, полноты и непротиворечивости нормативно-справочной информации в корпоративной автоматизированной информационной системе необходимо обеспечить её актуальность, полноту и непротиворечивость в консолидированной базе данных нормативно-справочной информации. Решение этой задачи зависит от источника справочников. При формировании справочников консолидированной базы данных нормативно-справочной информации на основе справочников из внешних источников возникают вопросы, связанные с выбором подходящих справочников из внешних источников, поддержки
синхронизации данных консолидированной базы данных с ними, модификации их структуры для соответствия принятым корпоративным стандартам. В настоящее время не существует чётких механизмов решения перечисленных задач, а одним из частых подходов является адаптация справочников корпоративной автоматизированной информационной системы к справочникам из внешних источников, а не наоборот. Разработка математической модели импорта справочников из внешних источников и реализация на её основе комплекса программ позволят упростить управление импортом нормативно-справочной информации. В случае формирования справочников консолидированной базы данных нормативно-справочной информации на основе справочников внутренних источников возникают вопросы, связанные со слиянием содержащейся в них нормативно-справочной информации и с устранением противоречий в данных. Полная автоматизация этих процессов вряд ли возможна, но частичная автоматизация для справочников определённого вида позволяет упростить управление обработкой нормативно-справочной информации.
Предлагаемые в диссертационной работе методы для решения перечисленных проблем могут применяться при первичном внедрении системы управления обработкой нормативно-справочной информации, при слиянии и поглощении корпоративных информационных систем.
Применение рекомендуемых в диссертационной работе подходов позволит:
избежать финансовых потерь, связанных с неактуальностью, противоречивостью и неполнотой данных;
построить отчётность, соответствующую предъявляемым к ней требованиям достоверности и актуальности;
принимать на основе этой отчётности правильные управленческие решения;
повысить интеграцию бизнес-процессов.
Цель работы. Целью диссертационной работы является решение проблемы управления обработкой нормативно-справочной информации в корпоративных автоматизированных информационных системах с помощью математического моделирования, численных методов и комплексов программ.
Задачи исследования. Основные задачи диссертационной работы:
создание математических моделей для управления обработкой нормативно-справочной информации в корпоративных автоматизированных информационных системах;
выявление с помощью моделей соответствующих характеристик вычислительных алгоритмов и комплексов программ;
разработка комплекса программ для интеграции справочников внутренних источников, импорта справочников из внешних источников, тиражирования информации между территориально удалёнными участками корпоративной автоматизированной информационной системы.
Методы исследования. В работе использовались методы теории баз данных, реляционной алгебры, теории репликации баз данных, теории множеств, теории графов, вычислительной математики и прикладной математической статистики.
Научная новизна полученных результатов. Научная новизна диссертационного исследования состоит в следующем:
Для управления обработкой нормативно-справочной информации в корпоративных автоматизированных информационных системах предложены новые математические модели на основе реляционной алгебры, позволяющие осуществлять операции импорта и экспорта нормативно-справочной информации, обеспечивая согласованность, актуальность и полноту данных.
Разработан метод импорта данных в консолидированную базу данных нормативно-справочной информации, использующий двухступенчатый
механизм переноса данных, когда вначале выделяются требуемые данные справочников из внешних источников и они представляются в промежуточном формате, а затем осуществляется перенос данных в консолидированную базу данных нормативно-справочной информации, что позволяет упростить процесс согласования форматов данных. 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 наименования.
Классификация видов репликации с точки зрения взаимодействия двух выбранных участков информационной системы
В данном параграфе считается, что информационная система состоит только из двух участков А и В. Задача системы репликации -синхронизировать их данные.
По направлению передачи данных системы репликации делятся на однонаправленные (односторонние) и двунаправленные (двусторонние) [45]. Если информация передаётся только от участка А к участку В, но не от участка В к участку А, то репликация считается однонаправленной [47]. Если информация может передаваться и от участка А к участку В, и от участка В к участку А, то репликация считается двунаправленной. Если система репликации поддерживает только однонаправленную репликацию, то она считается однонаправленной. Если система репликации поддерживает и одностороннюю, и двустороннюю репликацию, то она считается двунаправленной. Основное назначение двунаправленной репликации -; распределение нагрузки между серверами - при решении проблемы масштабируемости. Масштабируемость (scalability) - это способность системы сохранять свою производительность даже при увеличении нагрузки на неё путём наращивания используемых ресурсов. Если используется один сервер, то при нарастании количества запросов к нему, время отклика для каждого из клиентов начинает неизбежно падать. При дублировании информации между группой серверов и обеспечении синхронности данных при помощи двунаправленной системы репликации время отклика становится достаточным для решения возникающих в информационной системе практических задач, то есть проблема масштабируемости решена. Хотя двунаправленные системы репликации обеспечивают большую гибкость, чем однонаправленные системы репликации, их использование понижает надежность синхронизации данных. При использовании консолидированной базы данных и централизованного хранения НСИ достаточно однонаправленной системы репликации. Поэтому для увеличения надёжности передачи данных для тиражирования нормативно-справочной информации предпочтительно использование однонаправленных систем репликации. В качестве примера однонаправленной системы репликации можно указать Slony-I для PostgreSQL [48]. В качестве примера двунаправленной системы репликации можно указать PGCluster для PostgreSQL [49].
По моменту проведения синхронизации данных системы репликации подразделяются на следующие группы [45, 50]:
Репликация, основанная на сеансах (session-based replication)
Репликация, основанная на сообщениях (message-based replication, store-and-forward replication, message queueing)
Репликация, основанная на непосредственном соединении (connection-based replication).
Последовательность этапов синхронизации при использовании системы репликации, основанной на сеансах:
Установка соединения между сайтами А и В в заданный по расписанию момент времени Т.
Сеанс репликации в режиме реального времени.
Разрыв соединения между сайтами А и В после завершения сеанса.
После завершения сеанса синхронизации обеспечивается максимальная согласованность данных. Репликация, основанная на сеансах, применима даже для мобильных компонентов корпоративной автоматизированной информационной системы и требует меньших финансовых затрат, чем репликация, основанная на непосредственном соединении.
Последовательность этапов синхронизации при использовании системы репликации, основанной на сообщениях:
Изменения в базе данных сайта А.
Отправка сообщения об изменениях к сайту В.
Проверка сообщений на сайте В в заданный по расписанию момент времени.
Внесение изменений на сайте В в соответствии с сообщением от сайта А.
Репликация, основанная на сообщениях, не даёт гарантии согласованности данных. Следовательно, она не может быть использована для тиражирования данных НСИ.
Репликация, основанная на непосредственном соединении, подразумевает наличие устойчивого канала связи между сайтами А и В. Наличие такого канала не всегда возможно. В частности, данный тип репликации невозможен при наличии мобильных компонентов корпоративной автоматизированной информационной системы. Даже в тех случаях, когда устойчивый канал существует, его поддержка достаточно дорога.
Так как применение репликации, основанной на сообщениях, и репликации, основанной на непосредственном соединении, не подходит для тиражирования нормативно-справочной информации, то рекомендуется использование репликации, основанной на сеансах. В качестве примера репликации, основанной на постоянном соединении, можно привести Sybase Replication Server [51]. В качестве примера сеансовой системы репликации можно привести SBSS-синхронизацию [45, 52-55]. В качестве примера репликации, основанной на сообщениях, можно привести Sybase SQL Remote [56].
По количеству передаваемой в рамках синхронизации данных информации системы репликации можно разделить на следующие группы [45]:
Репликация моментальных снимков
Репликация слиянием
Транзакционная репликация
В рамках репликации моментальных снимков передаются все данные тиражируемой таблицы. Возможна ситуация, когда значительное количество дочерних сайтов использует один и тот же большой справочник, в котором происходят частые, но незначительные изменения (типичная для НСИ картина). В качестве примера такого справочника можно привести таблицы административно-территориального деления. При использовании репликации моментальных снимков огромный справочник будет постоянно передаваться целиком от КБД НСИ к локальным базам данных дочерних сайтов корпоративной автоматизированной информационной системы, приводя к чрезмерным нагрузкам на сеть. Поэтому использование репликации моментальных снимков приведёт к неэффективному по критерию 3 тиражированию НСИ. Следовательно, рассмотренный метод синхронизации не подходит для тиражирования нормативно-справочной информации в корпоративных автоматизированных информационных системах.
Репликация слиянием подразумевает передачу всех изменённых записей таблицы, целостность данных гарантируется только на уровне записей. В качестве плюсов такого подхода можно указать возможность поддержания большого числа сайтов корпоративной автоматизированной информационной системы, а также возможность работать с часто, но незначительно изменяющимися таблицами НСИ с большим числом записей, такими как таблицы административно-территориального деления. Репликация транзакций имеет тот же механизм, что и репликация слиянием, но гарантирует целостность данных на уровне транзакций. Данный механизм является наиболее предпочтительным при тиражировании НСИ. Система управления базами данных Microsoft SQL Server поддерживает все три типа репликации [45].
Практические методы слияния внутренних справочников
Далее будут рассмотрены возможные различия в структуре справочников-источников и методы их объединения в каждом из рассматриваемых случаев.
Случай 1: объединение справочников с совпадающими естественными ключами и различным списком атрибутов,
R{A],...,A„,Bl,...,Bm) - первое из объединяемых отношений.
5(Д,...,! „,С,,...,Ск) - второе из объединяемых отношений.
T(Al,...,An,Bl,...,Bm,Cl,...,Ck) -результирующее отношение.
Некоторое подмножество атрибутов АХ,...,А„ образует естественный первичный ключ. Атрибуты Dv...,Dn отличаются от атрибутов А1,...,Ап только наименованием.
Предлагается следующая схема объединения справочников:
Применение оператора переименования pS(A 4 с, Ct)(S) - наименование отношения сохраняется, а имена атрибутов Д,..., „ заменяются на АХ,...,А„. В результате, совпадающие в отношениях Л и 5 атрибуты имеют одинаковые имена.
і(4,...,л,Д!-, ,с1,...,сі) = л(4,..., ,і?1,...,ги)х5(д,...,л,с1,... сі) декартово произведение исходных отношений.
Вычисление ас {К). Из отношения R выбираются только те кортежи, для которых не существует соответствующих значений атрибутов А1,...,Ап в отношении S.
Вычисление ас (S). Из отношения S выбираются только те кортежи, для которых не существует соответствующих значений атрибутов Аи...,Ап в отношении R.
Вычисление ас (L). С3 - предикат равенства значений атрибутов Av...,An из отношений R и S.
T(Al,...,An,Bl,...,Bm,C1,...,Ck) = aQ(R) aCz(S) JaC2(L).
Общая формула выглядит следующим образом:
T(Av...,An,Bv...,Bm,Ci,...,Ct)= jCi(R) crQ(/7S(4_ ЛAt...jQ)(S))u ffq( R(Al,...,An,B1,...,Bm)xpSiAAQ Q)(S)).
Программный продукт, реализующий данное слияние, был реализован в среде программирования Delphi для слияния таблиц различных баз данных, находящихся под управлением СУБД MS SQL Server. В каждом конкретном случае программа создает SQL-сценарии для слияния конкретных таблиц на основе заданных параметров. Приведём пример созданного программой кода на языке Transact SQL, реализующего описанный выше алгоритм. В коде осуществляется слияние двух таблиц: MergeTablel(Field 1, Field2, Field3) и MergeTable2(Fl, F2, F3). Обе таблицы находятся в базе данных Ехр. Наборы полей (Fieldl, Field2) и (Fl, F2) отличаются только названиями и являются естественными первичными ключами для своих таблиц. Пример сгенерированного кода:
declare SMyTablel table(Fieldl int,Field2 int,Field3 varchar(lO)) declare @MyTable2 table(Fieldl int,Field2 int,F3 float) use Exp insert into SMyTablel select Fieldl,Field2,Field3 from [dbo].[MergeTablel] use Exp insert into @MyTable2 select Fl as Fieldl,F2 as Field2,F3 from [dbo].[MergeTable2] select 1.Fieldl,1.Field2,1.Field3,r.F3 from SMyTablel as 1, @MyTable2 as r where (1.Fieldl = r.Fieldl) and (l.Field2 « r.Field2) union select 1.Fieldl,l.Field2,l.Field3,null as F3 from SMyTablel as 1 where not exists (select from @MyTable2 as r where (1.Fieldl = r.Fieldl) and (l.Field2 = r.Field2)) union select r.Fieldl,r.Field2,null as Field3,r.F3 from @MyTable2 as r where not exists (select from SMyTablel as 1 where (1.Fieldl = r.Fieldl) and (l.Field2 = r.Field2) )
Если первое отношение состоит из кортежей (1, 1, а) и (1, 2, Ь), а второе отношение состоит из кортежей (1, 1, 2.7) и (1, 7, 3.4), то результирующее отношение состоит из кортежей (1, 1, а, 2.7), (1, 2, b, null) и (1, 7, null, 3.4).
Случай 2: используются суррогатные первичные ключи, но существует набор атрибутов, который может быть использован в качестве естественного первичного ключа. В данном случае нельзя руководствоваться методикой, характерной для случая 1, так как равенство значений суррогатных первичных ключей в кортежах источников внутренних справочников не гарантирует совпадения самих кортежей. Поэтому предлагается следующий алгоритм слияния:
Удаление суррогатных первичных ключей из объединяемых справочников.
Объединение, аналогичное случаю 1, для совпадающих атрибутов, включающих естественные первичные ключи-кандидаты.
Создание для объединённого отношения суррогатного первичного ключа.
Перенос справочника в КБД НСИ.
Стандартизация суррогатного первичного ключа внутреннего справочника в рамках предприятия. В результате, в дальнейшем этот суррогатный первичный ключ используется в качестве естественного первичного ключа в рамках всей корпоративной автоматизированной информационной системы.
Случай 3: наличие противоречий в справочниках-источниках. В этом случае рекомендуется каждый случай решать индивидуально на основе знаний предметной области с привлечением составителей обоих справочников. Автоматизация обработки подобных случаев находится за пределами диссертационной работы.
Сравнение алгоритмов вычисления FGetChanges
Для вычисления реляционной разности между двумя CSV-файлами используются три основных класса подходов:
Использование специализированных программных продуктов.
Использование существующих в базах данных подходов для выполнения реляционной операции разности двух отношений.
Выбор одного из файлов и занесение его в выбранную структуру данных. Затем линейный проход по другому файлу и проверка наличия значения в выбранной структуре данных. Затем выполнение этих же действий со сменой файлов.
Далее каждый из этих классов подходов будет проанализирован по отдельности.
В настоящее время существует достаточно много продуктов сторонних разработчиков, предоставляющих функциональность по вычислению реляционной разности между двумя CSV-файлами. В частности, можно указать продукт CSVDiff [74]. Минусы, характерные для использования сторонних продуктов:
Выходной формат сторонних программ не согласован с АСИДВИ. При их использовании в АСИДВИ необходимо будет добавлять функциональность по вызову стороннего средства и по преобразованию выходного формата.
Не все сторонние программы являются свободно распространяемыми.
Не все сторонние программы оптимизированы под сравнение именно CSV-файлов, представляющих собой кортежи реляционного отношения.
Не все сторонние программы оптимизированы под обработку больших объёмов файлов. В частности, размер справочников административно-территориального деления может превышать 100МВ.
Не все сторонние программы сохраняют порядок изменений. Нарушение порядка изменений приводит к невозможности использования программ для иерархических справочников.
В результате сравнения предлагаемых на рынке программных продуктов, было принято решение о собственной реализации функции FGelChanges.
Операторы пересечения множеств (INTERSECT) и разности множеств (EXCEPT) были включены в стандарт SQL-92 [75]. Некоторые реляционные СУБД включили оператор EXCEPT в средства своих SQL-диалектов, некоторые - нет. В частности, MS SQL Server 2000 не поддерживает оператор EXCEPT, a MS SQL Server 2005 и Oracle (оператор MINUS языка PL/SQL) поддерживают его [76, 77]. Сначала будут рассмотрены возможности реализации оператора EXCEPT средствами SQL в СУБД, которые его не поддерживают, а затем будут рассмотрены детали реализации оператора в поддерживающих его СУБД.
В качестве примера будут рассмотрены таблицы А и В, которые имеют одинаковое число столбцов сравнимых типов, расположенных в совпадающем порядке. Варианты реализации оператора EXCEPT средствами SQL в СУБД, которые его не поддерживают
Данный вариант эквивалентен используемому в АСИДВИ алгоритму для получения разности двух CSV-файлов. В отличие от АСИДВИ, в СУБД MS SQL Server для поиска элемента в наборе данных используются хэш-таблицы.
Оператор соединения JOIN.
В результате проведённых сравнений производительности, выяснилось, что второй вариант работает медленнее в MS SQL Server 2000, чем первый вариант. Поэтому использование первого варианта предпочтительно.
Варианты реализации EXCEPT в поддерживающих его СУБД:
Выполнение одного из двух предыдущих подходов. Не даёт выигрыша в производительности, но упрощает программный код. Данный подход используется в MS SQL Server 2005.
В ORACLE для выполнения поиска оптимизатор запросов проводит предварительный анализ данных и выбирает лучший для каждого конкретного случая алгоритм. Данный подход даёт выигрыш в производительности по сравнению с EXISTS-сценариями, но не может быть адаптирован для выполнения в АСИДВИ над CSV-файлами. Для выполнения быстрого поиска в СУБД Oracle могут быть использованы индексы на основе В-деревьев, хэш-таблиц и битовых карт (использование двоичной индексации) [78].
В большинстве случаев SQL-сценарии с использованием оператора EXCEPT работают быстрее, чем заменяющие его SQL-сценарии на основе EXISTS и JOIN. Это связано с тем, что оптимизатор запросов имеет большую априорную информацию о специфике выполняемых действий.
Для выделения изменений в данных наиболее эффективно с точки зрения скорости работы использовать следующий обобщённый алгоритм:
Данные IDold заносятся в структуру данных.
Осуществляется линейный проход по кортежам IDnew. Для каждого кортежа проверяется, содержится ли он в структуре данных. Если нет, то он присоединяется к множеству IDchangesadd .
Данные IDnm. заносятся в структуру данных.
Осуществляется линейный проход по кортежам IDM. Для каждого кортежа проверяется, содержится ли он в структуре данных. Если нет, то он присоединяется к множеству IDchangesdel.
Условия применимости алгоритма:
В папке NEW располагаются элементы множества Юнт .
В папке OLD располагаются элементы множества Юм.
Далее будет проведено сравнение различных структур данных (линейный список, бинарное дерево поиска, хэш-таблица, AVL-дерево, красно-чёрное дерево) на основе теоретических оценок скорости выделения изменений в разных версиях справочников в CSV-формате.
Шаги алгоритма реализации FGachangeMdni doi) с использованием линейного списка:
Данные Юм заносятся в линейный список.
Осуществляется линейный проход по кортежам IDmw. Для каждого кортежа проверяется, содержится ли он в линейном списке. Если нет, то он присоединяется к множеству IDchmgesadd.
Данные ID„ew заносятся в линейный список.
Осуществляется линейный проход по кортежам IDold. Для каждого кортежа проверяется, содержится ли он в линейном списке. Если нет, то он присоединяется к множеству IDchangesdd.
Проверка содержания кортежа в линейном списке - это операция поиска в линейном списке. Поиск узла в линейном списке занимает время порядка O(N).
Шаги алгоритма реализации FGaChcmges(idnl,idol) с использованием бинарного дерева поиска:
Данные Юм заносятся в бинарное дерево поиска.
Осуществляется линейный проход по кортежам IDnew. Для каждого кортежа проверяется, содержится ли он в бинарном дереве поиска. Если нет, то он присоединяется к множеству IDchangesadd.
Данные Ю заносятся в бинарное дерево поиска.
Осуществляется линейный проход по кортежам Юм. Для каждого кортежа проверяется, содержится ли он в бинарном дереве поиска. Если нет, то он присоединяется к множеству IDchangesdd.
Проверка содержания кортежа в бинарном дереве поиска - это операция поиска в бинарном дереве. Поиск узла в бинарном дереве занимает в худшем случае время порядка O(N). Однако данный алгоритм лучше предыдущего, так как в среднем случае операция поиска занимает время порядка 0(log2 N).
Сравнение алгоритмов Вычисления FoetChanges
Сравнивается использование красно-чёрного дерева, AVL-дерева, хэш-таблицы с хэш-функцией в виде суммы ASCII-кодов всех символов, входящих в CSV-строку, бинарного дерева поиска и линейного списка.
Исходя из теории сложности, можно ожидать, что самые медленные результаты будут показаны с использованием линейного списка, предпоследние результаты - с использованием бинарного дерева поиска. Хэш-таблица, AVL-дерево, красно-чёрное дерево могут располагаться в разном порядке в зависимости от специфики исходных данных. Поэтому их взаимный порядок может быть получен только по результатам компьютерного моделирования.
Цель сравнения - для каждой страны проверить, влияет ли изменение выбора структуры данных на скорость работы алгоритма на CSV-строках, соответствующих кортежам данных административно-территориального деления. Если выбор структуры данных влияет на скорость работы, то требуется отсортировать структуры данных по скорости работы для заданной страны. В случае если расположение алгоритмов по качеству окажется идентичным для большинства стран, то будет сделан обобщающий вывод о порядке предпочтительности использования алгоритмов для достаточно длинных CSV-строк, соответствующих кортежам данных.
Значения в таблице показывают математическое ожидание времени выполнения функции FGetChanges в миллисекундах в зависимости от выбранного алгоритма и выбранной страны. Файлы с данными в промежуточном формате фиксированы для каждой страны. Размеры файлов с данными указаны в столбце с заголовками стран. Значимость различий между математическими ожиданиями показана при помощи дисперсионного анализа. Методы определения значимости различий в показателях алгоритмов будут показаны на примере данных административно-территориального деления Бразилии.
Данные могут носить количественный, порядковый или качественный характер. Критерий разбиения на группы может быть количественным или качественным. В зависимости от характера данных и критерия разбиения данных на группы для исследования выбирают различные статистические методы. В данном случае данные представляют собой времена работы алгоритмов в миллисекундах, то есть носят количественный характер. Критерий разделения на группы - тип алгоритма - качественный. На время работы алгоритма влияет только один фактор - тип алгоритма (каждый раз используется один и тот же файл с данными одной и той же страны). Следовательно, наиболее предпочтительным для использования является метод дисперсионного анализа, изобретенного Рональдом Фишером в 20-ые годы 20-го века [82, 83]. Общий метод работы выглядит следующим образом:
Сбор данных. При выполнении сбора данных необходимо обеспечить условие независимости. Эксперименты проводились в разные дни и разное время. Поэтому их можно считать независимыми и не влияющими друг на друга. Кроме того, выборка должна быть представительной. Было проведено по 20 экспериментов для каждого из 5 алгоритмов. Поэтому критерии независимости и представительности выполнены. Применим к исходным данным преобразование в виде двоичного логарифма. Проверим, что после его применения преобразованные данные пройдут тесты на гомогенность дисперсии и нормальность распределения, а, следовательно, к ним можно будет применить дисперсионный анализ. После применения логарифмического преобразования данные выглядят следующим образом
Для доказательства значимости различий между группами был использован критерий Фишера [82, 83]. Нулевая гипотеза: «выбранный алгоритм не влияет на скорость выполнения функции F(3elCkm».
Следовательно, нулевая гипотеза отвергается (вероятность, что различия между алгоритмами обуславливаются случайными факторами меньше 0,01). Данный вывод согласуется с хорошо видимыми на глаз расхождениями между временами работы выбранных алгоритмов.
Следовательно, можно утверждать, что проведённых экспериментов достаточно, чтобы утверждать, что бинарное дерево работает быстрее, чем линейный список. Хэш-таблица работает быстрее, чем бинарное дерево. AVL-дерево работает быстрее, чем хэш-таблица. Красно-чёрное дерево работает быстрее, чем AVL-дерево. Вероятность ошибки не более 0,05.
Аналогичные исследования были проведены для данных административно-территориального деления Германии, Китая, Чехии, Испании, Финляндии, Индонезии, США, российских городов и улиц. Для всех исследуемых стран структуры данных расположились в порядке і увеличения скорости работы следующим образом: линейный список, бинарное дерево, хэш-таблица, AVL-дерево, красно-чёрное дерево. То есть, можно сделать следующий обобщающий вывод: алгоритм сравнения файлов, содержащих кортежи данных в виде достаточно длинных CSV-строк, становится всё более быстрым при переходе линейный список - бинарное дерево поиска - хэш-таблица - AVL-дерево - красно-чёрное дерево.
Выведем формулы, связывающие время работы алгоритма и число обрабатываемых записей для хэш-таблицы, AVL-дерева и красно-чёрного дерева. Будем искать зависимость времени работы алгоритмов от числа обрабатываемых записей в линейном виде AN log2 N, где через N обозначено число записей. В уравнении прямой не используется коэффициент В, так как при нуле записей алгоритм сразу же заканчивает работу. Экспериментальные данные по времени работы и Nlog2 N занесены в таблицу.
Во всех приведённых формулах последняя цифра значащая. Таким образом, получено независимое доказательство следующего утверждения: алгоритм сравнения файлов, содержащих кортежи данных в виде достаточно длинных CSV-строк, становится всё более быстрым при переходе хэш-таблица - AVL-дерево - красно-чёрное дерево. Далее будет рассмотрена возможность применения полученных результатов для количественной оценки времени работы описанных алгоритмов на произвольных компьютерах.
Используя заданный набор тестов для текущего компьютера и известные результаты этих тестов для тестового компьютера, можно получить точную количественную оценку производительности алгоритмов. Набор рекомендуемых тестов для сравнения производительности приведён в книге [92]. Там же приводятся аргументы против использования тактовой частоты процессора для оценки производительности компьютера. В качестве простейшего теста сравнения производительности можно привести инкрементирование переменной от единицы до миллиарда. Для тестового компьютера для выполнения теста требуется порядка 700 миллисекунд. Если для текущего компьютера для выполнения теста требуется порядка 600 миллисекунд, то отношение Результаты анализа разработанных для вычисления функции FGetChanges алгоритмов, полученные при помощи компьютерного моделирования, согласованы с теоретическими оценками, полученными с использованием теории сложности. Как и ожидалось, линейный список и бинарное дерево поиска оказались менее вычислительно эффективны, чем хэш-таблица, AVL-дерево и красно-чёрное дерево. Для рассматриваемого вида данных красно-чёрное дерево оказалось вычислительно эффективнее и хэш-таблицы, и AVL-дерева. Для рассматриваемого вида данных AVL-дерево оказалось вычислительно эффективнее, чем хэш-таблица. Следовательно, на основании проведённого анализа быстродействия алгоритмов, для включения в АСИДВИ для сравнения предыдущей и текущей версий справочников был выбран алгоритм вычисления FCetChanges, основанный на использовании красно-чёрных деревьев.
