Комар Ф.В. Разработка математического и программного обеспечения для автоматизированного отождествления объектов схем баз данных

Подождите немного. Документ загружается.

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

КОМАР Феликс Викторович

РАЗРАБОТКА МАТЕМАТИЧЕСКОГО И ПРОГРАММНОГО

ОБЕСПЕЧЕНИЯ ДЛЯ АВТОМАТИЗИРОВАННОГО ОТОЖДЕСТВЛЕНИЯ

ОБЪЕКТОВ СХЕМ БАЗ ДАННЫХ

Специальность: 05.13.11 – Математическое и программное обеспечение

вычислительных машин, комплексов

и компьютерных сетей

АВТОРЕФЕРАТ

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

кандидата технических наук

Воронеж – 2009

Работа выполнена в ГОУ ВПО «Липецкий государственный технический

университет»

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

профессор

Погодаев Анатолий Кирьянович

Официальные оппоненты: доктор технических наук,

профессор

Харин Валерий Николаевич;

кандидат технических наук

Дорофеев Александр Николаевич

Ведущая организация ГОУ ВПО «Московский

государственный индустриальный

университет»

Защита состоится «24» сентября 2009 г. в 10

часов в конференц-зале на

заседании диссертационного совета Д>212.037.01 ГОУ ВПО «Воронежский

государственный технический университет» по адресу: 394026, г. Воронеж,

Московский просп., 14.

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

ГОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «__» августа 2009 г.

Ученый секретарь

диссертационного совета Питолин В.М.

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

Актуальность темы. Для решения задачи интеграции баз данных

необходимо решение двух подзадач: интеграция схем баз данных и интеграция

самих данных. Задача интеграции данных может быть решена с использованием

нестрогого соединения реляционных таблиц. Задача интеграции схем баз данных

требует отождествления объектов схем баз данных. В настоящее время нет

методов, автоматически решающих эту задачу.

Наиболее известны два основных подхода к решению задачи

отождествления объектов схем баз данных (объектами схем баз данных являются

сущности, их атрибуты и связи между сущностями). Первый подход основан на

расчете расстояния между строковыми значениями (названиями отношений,

названиями атрибутов, значениями атрибутов и т.д.). Данный подход в очень

малой степени учитывает семантику объектов и далеко не всегда дает

удовлетворительные результаты. Второй подход основан на построении

онтологий предметной области рассматриваемых схем баз данных. Такой подход

требует больших трудозатрат и слабо поддается автоматизации. Ни один из

существующих методов не позволяет строить отождествления составных

атрибутов.

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

строковые шаблоны. Однако в настоящее время нет алгоритмов, решающих

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

строк. Разработка алгоритма решения такой задачи позволит автоматически

строить обобщенную характеристику объектов схем баз данных в виде множества

строковых шаблонов, а уже на основе этой характеристики определять сходство

объектов. Также на текущий момент окончательно не решена задача

автоматического отождествления объектов схем баз данных.

Таким образом, актуальна проблема разработки и внедрения специального

математического и программного обеспечения, которое позволит решать задачи

автоматического построения обобщенной характеристики объектов схем баз

данных, определения сходства объектов, а также построения отождествлений

объектов схем баз данных, в том числе и составных атрибутов. Разработка такого

математического и программного обеспечения позволит снизить затраты и

ускорить процесс интеграции баз данных.

Работа выполнена в соответствии с научным направлением ГОУ ВПО

«Липецкий государственный технический университет» «Информационные

системы и базы данных».

Цель исследования состоит в разработке специального математического

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

и создании на его основе программного обеспечения.

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

 анализ методов и моделей, возникающих при автоматизированном

отождествлении объектов схем баз данных;

 разработка способов, моделей и алгоритмов автоматического построения

обобщенной характеристики, численной оценки сходства и отождествления

объектов схем баз данных, в том числе и составных атрибутов;

 разработка специального программного обеспечения для

автоматизированного отождествления объектов схем баз данных;

 анализ разработанного математического и программного обеспечения, а

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

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

Методы исследования базируются на теории множеств, теории графов,

дискретной математике, математической статистике, эволюционном

моделировании, объектно-ориентированном программировании, реляционной

алгебре, теории баз данных, методах модульного и структурного

программирования.

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

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

 способ описания строковых атрибутов сущностей схем баз данных,

позволяющий формально представлять синтаксические особенности

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

обобщенной характеристики множества строковых шаблонов;

 функция численной оценки значимости строкового шаблона,

отличающаяся использованием частоты появления рассматриваемого шаблона на

множестве значений строкового атрибута, позволяющая свести задачу построения

обобщенной характеристики строкового атрибута к оптимизационной задаче;

 функция численной оценки сходства объектов схем баз данных,

отличающаяся использованием в качестве обобщенной характеристики

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

основе множества экземпляров объектов;

 алгоритм отождествления объектов схем баз данных, отличающийся

применением численной оценки сходства объектов на основе обобщенной

характеристики в виде строковых шаблонов, позволяющий строить

отождествления составных атрибутов.

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

методов и алгоритмов специального программного обеспечения, позволяющего

автоматизировано отождествлять объекты схем баз данных. Использование

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

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

для решения задачи интеграции баз данных.

Реализация и внедрение результатов работы. Разработанное

программное обеспечение внедрено при реализации проекта интеграции

информационных систем предприятий холдинга ООО «ПРОДО Менеджмент»

компанией ООО «Л-ком», а также прошло апробацию при реализации проекта

интеграции информационных систем ООО «Дойче банк».

Программное обеспечение зарегистрировано в Государственном фонде

алгоритмов и программ.

Результаты диссертационной работы используются в учебном процессе

ГОУ ВПО «Липецкий государственный технический университет» при

подготовке инженеров по специальности «Прикладная математика».

Апробация работы. Теоретические и практические результаты,

полученные в процессе исследования, докладывались и обсуждались на XI-й

Международной научно-практической конференции «Проблемы экологии и

экологической безопасности Центрального Черноземья РФ» (Липецк, 2007),

Межрегиональном молодёжном научно-практическом форуме «Молодежная

инициатива – 2007» (Липецк, 2007), Всероссийской электронной научной

конференции «Современные системы автоматизации» (Москва, 2007), XIII-й

Международной открытой научной конференции «Современные проблемы

информатизации» (Воронеж, 2008), IX-й Всероссийской научно-технической

конференции «Теоретические и прикладные вопросы современных

информационных технологий» (Улан-Удэ, 2008), V Всероссийской школе-

семинаре молодых ученых «Управление большими системами» (Липецк, 2008).

Положения работы поддержаны грантами Российского фонда

фундаментальных исследований № 05-01-96402 "Совершенствование

методологии проектирования информационных систем для управления

производственными объектами", № 07-07-96403 "Разработка специальных

реляционных операций и алгоритмов для отождествления объектов в

распределенных информационных системах".

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

работ, в том числе 2 – в изданиях, рекомендованных ВАК РФ.

В работах, опубликованных в соавторстве и приведенных в конце

автореферата, лично соискателю принадлежат: [2] – алгоритм решения задачи

максимизации функции значимости строкового шаблона; [3] – метод формального

описания синтаксических особенностей строковых атрибутов сущностей баз

данных с использованием множества строковых шаблонов; [5] – архитектура

классов для реализации специального программного обеспечения; [6] – алгоритм

поиска множества строковых шаблонов для формального описания

синтаксических особенностей значений атрибутов реляционных баз данных; [7] –

функция оценки значимости строкового шаблона; [11] – анализа качества методов

интеграции схем баз данных и сравнительный анализ с существующими

методами; [12] – алгоритм выбора пар объектов схем данных для отождествления.

Структура и объем работы. Диссертационная работа состоит из введения,

четырех глав, заключения, библиографического списка из>124 наименований, 2

приложений. Основная часть работы изложена на 132 страницах, содержит 33

рисунка и 1 таблицу.

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

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

исследования, формулируются цель, научная новизна и практическая значимость

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

В первой главе анализируются задачи, возникающие при отождествлении

объектов схем баз данных.

В настоящее время актуальна проблема интеграции информационных

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

инфраструктуру для доступа к данным, опирающуюся на единые стандарты и

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

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

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

время нет методов автоматически решающих эту задачу. Схемы баз данных

производственного масштаба могут содержать тысячи сущностей и атрибутов,

что делает отождествление трудоемким процессом, а проблему создания

автоматизированных методов решения данной задачи актуальной. Существующие

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

между строковыми значениями, что не учитывает синтаксические и

семантические особенности рассматриваемых объектов, или требуют построения

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

Таким образом, показано, что существующее математическое и

программное обеспечение не позволяет эффективно осуществлять

отождествление объектов схем баз данных, а сформулированная проблема

является актуальной научной задачей.

Во второй главе излагаются основные положения разработанного метода

отождествления объектов схем баз данных.

В работе предложен метод численной оценки сходства объектов схем баз

данных, основой которого является алгоритм автоматического построения

обобщенной характеристики строковых атрибутов (рис. 1).

Рис. 1. Численная оценка сходства атрибутов на основе автоматически

построенной характеристики в виде строковых шаблонов

Обобщенную характеристику атрибутов предлагается строить в виде

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

выражений. Рассмотрим подробнее алгоритм построения обобщенной

характеристики. Пусть

},...,,,{

321 n

aaaaA 

– множество атрибутов,

–

множество значений атрибута



– некоторый шаблон. Определим функцию:

),(







, (1)

где

),(



– количество строк из множества

, которые соответствуют

шаблону



– объем множества

. Пусть

},...,,,{

321 m

DDDDD 



– набор

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







),(



. (2)

Пусть

}...,,...,,,{

,1,1321 niii

DDDDDDD







– набор множеств значений

атрибутов, кроме

-ого, определим функцию значимости шаблона



для

атрибута

в контексте атрибутов

}...,,,...,,,{

,11321 niii

aaaaaaA







),(),(),,(

iiii

DDDD









. (3)

Автоматическое

построение обобщенной

характеристики

Численное значение

сходства атрибутов

Множество

значений

атрибута 1

Численное значение

сходства составных

атрибутов

Множество

значений

атрибута 2

Пусть

},...,,,{

321 n





– некоторое множество строковых шаблонов.

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











iijii

DDU

),,(



. (4)

Пусть

– множество всех возможных строковых шаблонов. Рассмотрим

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

),,(max),(

DDUDD













. (5)

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

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

атрибута. Будем использовать такой набор строковых шаблонов в качестве

обобщенной характеристикой атрибута. Для решения поставленной задачи

разработан генетический алгоритм, позволяющий автоматически построить

обобщенную характеристику атрибута (рис. 2).

Рис. 2. Генетический алгоритм построения обобщенной характеристики

атрибута в виде строковых шаблонов

В работе описан способ кодирования шаблонов в виде генов. Оператор

скрещивания определяется как случайный обмен хромосомами между двумя

особями. Рассматриваются следующие операции над шаблонами: добавление

подшаблона, удаление подшаблона, изменение минимального количества

ложь

истина

Ввод множеств , и величины

Формирование начальной популяции

Расчет значения

Отсев шаблонов с наименьшими

значениями

Скрещивание шаблонов

Мутации шаблонов

Вывод набора



V

Начало

Конец

вхождения подшаблона, изменение максимального количества вхождения

подшаблона, уточнение множества символов подшаблона, обобщение множества

символов подшаблона, добавление символа во множество символов подшаблона,

удаление символа из множества символов подшаблона. Определяется оператор

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

случайной хромосоме особи.

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

заданы атрибуты

, а также множества их значений

. Пусть

},...,,,{

321

kkk





– набор шаблонов для атрибута

, найденный с

использованием генетического алгоритма. Определим функцию:







ilk

),(),(

1),(



, (6)

данная функция принимает значения на отрезке [0, 1]. Если частота появления

значений из множества

, соответствующих шаблонам, близка к частоте

появления значений из множества

, соответствующих шаблонам, то значение

функции

),(



близко к единице. Функция обладает свойством

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

Пусть функция

),(



, возвращает количество строк из множества

содержащих в себе подстроки, соответствующие шаблону



. Определим

функцию:

),(







, (7)

данная функция дает численную оценку того, насколько часто в множестве

встречаются строки, которые содержат в себе подстроки, соответствующие

шаблону



Определим функцию:







ilk

),(),(

1),(



, (8)

данная функция принимает значения на отрезке [0, 1]. Если частота появления

значений из множества

, соответствующих шаблонам, близка к частоте

появления значений из множества

, содержащих в себе подстроки,

соответствующие шаблонам, то значение функции

),(



будет близко к

единице. При значении функции близкой к единице можно предположить, что

атрибут

является некоторой составной частью атрибута

Предложенная функция оценки сходства атрибутов может быть

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

Рассмотрим две сущности

},...,,,{

321

kkk

aaaaA 

– множество атрибутов

сущности

},...,,,{

321

lll

aaaaA 

– множество атрибутов сущности

Рассмотрим следующую функцию:

)),(max),(max(

),(

..1









aaaa



. (9)

Далее в работе рассматривается задача построения отождествления

объектов схем баз данных на основе рассчитанных численных оценок сходства.

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

Рис. 3. Алгоритм отождествления объектов схем данных

Рассмотрим подробнее отождествление составных атрибутов. Расчет

значений функции

),(



позволяет выявлять составные атрибуты. Для

построения отождествлений составных атрибутов разработан алгоритм,

представленный на рис. 4. Структура Match представляет собой два набора

атрибутов (левый, правый) и значение функции

),(



, а также методы для

манипулирования левым и правым наборами атрибутов. ArrayList представляет

собой стандартную реализацию массива.

Начало

Расчет значений и попарно для всех атрибутов схем и

Применение генетического алгоритма для построения

обобщенной характеристики атрибутов схем и

Расчет для всех сущностей схем и

Выбор пар объектов, для которых , и выше порогового значения

Отождествление составных атрибутов

Отбор пар с максимальным значением сходства многократно

вошедших в набор отождествлений

Конец

Ввод исходных данных (схемы , , пороговое

значение )

Вывод кандидатов для отождествления

объектов схем данных

Выбор

кандид

атов

для

отожде

ствлен

ия

Числен

ная

оценка

сходст

ва

объект

ов

Рис. 4. Алгоритм отождествления составных атрибутов

Третья глава посвящена разработке специального программного

обеспечения, реализующего предложенный метод построения обобщенной

характеристики атрибутов сущностей и алгоритм отождествления объектов схем

баз данных.

Основой для разработанного специального программного обеспечения

является библиотека классов, реализованная на языке программирования Java.

Общая структура классов библиотеки представлена на рис. 5. Основу интерфейса

пользователя с библиотекой классов представляет класс dIntegrator, который

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

рассматриваемых схем баз данных. Данный класс реализует механизм построения

отождествления объектов схем баз данных.

истина

ложьистина

истина

Начало

i = 0

j = i+1

a1 == a2

Attr a1 = m.get(i).getAttrLeft()

Attr a2 = m.get(j).getAttrLeft()

ArrayList<Match<SubSim>> m

j = j+1

Attr a = m.get(j).getAttrRigth()

m.get(i).addRigthAttr(a)

m.remove(j)

j<m.size

Конец

i = i+1

i<m.size

ложь