Инженер Гудков К.С.
Государственный научно-исследовательский институт
авиационных систем, Россия
Выделение изменений в версиях открытых баз данных при построении
автоматизированной системы импорта внешних справочников
В работах [1, 2] был предложен механизм управления
нормативно-справочной информации в корпоративных информационных системах. Он
включает в себя:
· создание консолидированной базы данных нормативно-справочной информации
(КБД НСИ);
· создание автоматизированной системы импорта данных внешних справочников
(АСИВС);
· создание гетерогенной системы репликации данных.
При таком подходе внешние справочники, извлекаемые из открытых баз
данных, импортируются КБД НСИ при помощи АСИВС, а затем экспортируются
территориально удалённым участкам корпоративной информационной системы при
помощи гетерогенной системы репликации данных. Было показано [3], что процесс
импорта данных описывается следующей формулой:
Функция осуществляет перенос внешних справочников во внутренний
формат данных АСИВС. В авторской реализации АСИВС в качестве такого внутреннего
формата выбран CSV. Функция
сравнивает предыдущую и текущую версию
справочников и выделяет произошедшие в справочниках изменения. Функция
видоизменяет таблицы КБД НСИ в соответствии с изменениями,
выделенными при помощи
. Вычисление каждой из этих функций
программное. Задача данной работы – предложить алгоритм для вычисления
.
Открытые базы данных содержатся на WEB-сайтах и доступны для скачивания. На одном из компьютеров локальной
сети, в которой расположена КБД НСИ, устанавливается АСИВС. АСИВС имеет внутренние
папки OLD, NEW, CHANGES, в которые помещаются справочники, преобразованные к формату CSV. Рассмотрим процесс выделения изменений на примере произвольного
справочника . Перед выполнением
в папке NEW располагается текущая версия
, а в папке OLD – предыдущая. Папка CHANGES – пустая. Предлагается следующий алгоритм выделения изменений:
· Данные предыдущей версии справочника в виде текстовых строк заносятся в
красно-чёрное дерево [4].
· Для каждого кортежа текущей версии справочника проверяется его наличие в
красно-чёрном дереве. Если он есть в красно-чёрном дереве, то никаких действий
не предпринимается. Если его нет, то кортеж добавляется к файлу добавленных
строк в составе папки CHANGES.
· Данные текущей версии справочника в виде текстовых строк заносятся в
красно-чёрное дерево.
· Для каждого кортежа предыдущей версии справочника проверяется его
наличие в красно-чёрном дереве. Если он есть в красно-чёрном дереве, то никаких
действий не предпринимается. Если его нет, то кортеж добавляется к файлу
удалённых строк
в составе папки CHANGES.
Возникает вопрос: «Насколько эффективен
предложенный алгоритм?». Для ответа на него был выполнен теоретический анализ
при помощи теории сложности и практический анализ при помощи компьютерного
моделирования с дальнейшим использованием методов прикладной математической
статистики. Основная операция в составе предложенного алгоритма – это поиск в
заданной структуре данных. Рассмотрим следующие альтернативные структуры
данных, которые могли бы быть использованы в алгоритме:
·
красно-чёрное дерево;
·
AVL-дерево [5];
·
хэш-таблица;
·
бинарное дерево поиска;
·
линейный список.
С точки зрения теории сложности операция поиска для
каждой из рассматриваемых структур данных относится к классу сложности P. Поиск элемента в линейном списке занимает время порядка . В худшем случае такое же время затрачивается
и в случае использования бинарного дерева поиска. Однако, в среднем, на поиск
элемента в бинарном дереве поиска затрачивается время
. Таким образом, алгоритм, использующий
бинарное дерево поиска, более быстрый, чем алгоритм, использующий линейный
список. Поиск элемента в AVL-дереве и в
красно-чёрном дереве занимает время порядка
. Проверка содержания элемента в
хэш-таблице в худшем случае требует времени порядка
, а в среднем ‑
. Следовательно, с точки зрения теории
сложности наилучшая производительность может быть достигнута при использовании
хэш-таблицы,
AVL-дерева и красно-чёрного дерева. Выбор конкретной структуры
данных зависит от специфики исходных данных.
Ранее в работе указывалось, что данными для
алгоритма служат CSV-строки, соответствующие кортежам таблиц баз данных. Определим структуру
данных, работающую наиболее быстро для этого типа данных. Для этого было
реализовано 5 алгоритмов (по одному для каждой из структур данных), выполняющих
. Они были запущены для выделения
изменений в справочниках административно-территориального деления. В
результате, было получено 5 массивов значений, содержащих времена работы каждого
из алгоритмов на фиксированных обрабатываемых данных. Следовательно, данные
экспериментов для анализа носят количественный характер (времена работы
алгоритмов), а критерий разбиения на группы ‑ качественный (тип
используемого алгоритма). После логарифмического преобразования данные прошли
тест на гомогенность дисперсии Левена и тест на нормальность д’Агостино.
Следовательно, к ним можно применить дисперсионный анализ. В соответствии с
критерием Фишера была показана значимость различий между группами. При помощи
критериев Ньюмана-Кейлса и Тьюки был определён следующий предпочтительный
порядок структур данных: красно-чёрное дерево, AVL-дерево, хэш-таблица, бинарное дерево поиска, линейный
список. Данный порядок согласован с теоретическими результатами, полученными
при помощи теории сложности.
В работе был представлен алгоритм выделения
изменений в версиях открытых баз данных, используемый при построении
автоматизированной системы импорта внешних справочников. Предложенный алгоритм
базируется на использовании красно-чёрного дерева, предложенного Байером в 1972
году. Эффективность алгоритма была показана сравнением с альтернативными
структурами данных: AVL-деревом, хэш-таблицей, бинарным деревом поиска и линейным списком. Для
доказательства эффективности были использованы методы теории сложности и
прикладной математической статистики.
Литература:
1. Бондаренко А.В., Гудков К.С. Создание таблиц нормативно-справочной
информации на основе разнородных внешних справочников. // Модели и методы
обработки информации: Сб.ст. МФТИ. – 2009. – С.148-152.
2. Гудков К.С. Управление внешней нормативно-справочной информацией в
распределённых информационных системах. // Материалы XVI Международной
конференции студентов, аспирантов и молодых учёных "Ломоносов-2009",
секция "Вычислительная математика и кибернетика". – 2009. – С.23.
3. Гудков К.С. Моделирование импорта данных разнородных внешних
справочников в консолидированную базу данных нормативно-справочной информации.
// Актуальные проблемы гуманитарных и естественных наук: Сб.ст. – 2009. –
С.11-14.
4.
Bayer
R. Symmetric binary B-trees: Data Structure and maintenance algorithms. // Acta
Informatica. – 1972. – P.290-306.
5. Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации
информации. // Доклады АН СССР. – 1962. – №2(146). – С.263-266.