Software & Systems

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

Рассмотрим задачу интегрирования схем данных. Пусть заданы две схемы данных и , – множество всех атрибутов схемы данных ; – множество всех атрибутов схемы данных ; – множество всех сущностей схемы данных ; – множество всех сущностей схемы данных . Решением задачи интегрирования схем данных можно считать бинарное отношение, заданное на множестве объектов схем данных, которое определяет соответствие между семантически сходными объектами.

В работе Ronkainen Pirjo “Attribute Similarity and Event Sequence Similarity in Data Mining” (University of Helsinki Report, 1998) показано, что для построения такого рода бинарного отношения необходимо выполнить два основных шага (рис. 1).

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

Оценка семантического сходства объектовсхем данных

Пусть – множество значений атрибута в определенном отдельно взятом отношении; – множество множеств таких значений атрибутов; – некоторый строковый шаблон. В качестве языка строковых шаблонов будем использовать общеизвестный язык регулярных выражений.

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

, (1)

где – функция, возвращающая количество строк из множества , которые удовлетворяют шаблону ; – объем множества .

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

, (2)

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

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

, (3)

где – множество значений i-го атрибута; – набор всех множеств значений атрибутов, кроме i-го.

Примем значение функции как численное выражение семантической значимости шаблона относительно атрибута в контексте атрибутов .

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

. (4)

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

Для решения задачи максимизации функции семантической значимости используем генетический алгоритм (рис. 2).

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

Исходя из указанного предположения, рассмотрим следующую функцию:

(5)

данная функция принимает значения на отрезке [0, 1]. Максимальное значение функция принимает тогда, когда для всех шаблонов из множества значение функции одинаково для атрибутов и . Если значения двух атрибутов одинаковы, то будем считать, что атрибуты семантически тождественны, значения функций для атрибутов будут равны, а значение функции будет равно единице. Другими словами, можно говорить о семантической эквивалентности рассматриваемых атрибутов в контексте множества шаблонов . Таким образом, представленная функция может быть использована как функция оценки семантического сходства атрибутов.

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

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

, (6)

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

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

Для построения бинарного отношения недостаточно нечеткой оценки сходства объектов. Необходимо из множества пар объектов выбрать наиболее подходящих кандидатов для отождествления. Рассмотрим алгоритм выбора такого рода пар объектов (рис. 3).

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

Пример решения задачи интегрированиясхем данных

Для примера рассмотрим две схемы данных и (рис. 4 и 5).

Анализируя представленные схемы данных, можно увидеть семантическую близость следующих пар объектов: student и student, faculty и faculty, student.name и student.first_last_name, student.dob и student.data_rog, student.course и student.kurs, student.phone и student.telefon, faculty.title и faculty.nazvanie, faculty.phone и faculty.phone. Результаты оценки сходства объектов схем данных предложенным методом представлены в таблицах 1 и 2.

Рис. 4. Схема данных S1

Рис. 5. Схема данных S2

Таблица 1

Оценка семантического сходства атрибутовсхем данных и

Таблица 2

Оценка семантического сходства отношенийсхем данных и

Результатом применения алгоритма отождествления объектов являются следующие пары объектов: student@student, faculty aculty, student.name@ student.first_last_name, student.dob@student.data_rog, student.course@student.kurs, student.phone@student.telefon, faculty.title@faculty.nazvanie, faculty.phone@faculty.phone.

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