Инженер Гудков К.С.

Государственный научно-исследовательский институт авиационных систем, Россия

Выделение изменений в версиях открытых баз данных при построении автоматизированной системы импорта внешних справочников

В работах [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.