На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
09 Сентября 2024

Метод интегрирования схем данных на основе семантического описания атрибутов

Статья опубликована в выпуске журнала № 1 за 2008 год.
Аннотация:
Abstract:
Авторы: Комар Ф.В. () - , Погодаев А.К. () -
Ключевые слова: интегррование, семантика, атрибуты, сеть
Keywords: , semantics, attributes, network
Количество просмотров: 14182
Версия для печати
Выпуск в формате PDF (1.92Мб)

Размер шрифта:       Шрифт:

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

 

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

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

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

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

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

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

, (1)

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

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

, (2)

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

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

, (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.

student

name

dob

course

email

phone

Ivan Petrov

11/12/86

1

ivan@mail.ru

89102758912

Nikolaj Frolov

13/01/86

1

nfrolov@gmail.com

89033335639

Petr Vasiljev

05/04/85

3

petr@iomega.org

89230235612

Natalja Gorbunova

21/04/86

2

gorb@den.com

79120452198

…..

….

….

….

….

professor

first_last_name

date_of_birth

elektr_addr

telefon

Dmitrij Kuznecov

05-03-58

kuzdim@ptu.ru

235476

Izja Shpicman

22-05-64

izja2000@shpicman.com

876564

Vladimir Leontjev

09-04-74

daemdream@mail.org

329972

Irina Teljatina

11-02-55

irtel@temp.org

765747

….

….

….

….

proekt

 

faculty

title

date

budget

 

title

phone

avt lab

20-10-07

20000

 

FAI

758912

razr uch plan

15-01-07

145890

 

FTF

335639

razr web saita

08-04-08

4986

 

FIT

235612

prov stud vesn

12-06-09

500321

 

EF

452198

….

….

….

 

….

….

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

student

first_last_name

data_rog

kurs

telefon

Kolja Van

11/12/86

2

89342758912

Ira Kon

13/01/86

2

89343335639

Elja Butova

05/04/85

4

99054235612

Sergej Titov

21/04/86

5

89178452198

…..

….

….

….

faculty

nazvanie

phone

MMF

345765

OZF

934765

FIT

123233

EF

835832

….

….

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

Таблица 1

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

Атрибуты схемы

данных

Атрибуты схемы данных

student.

first_last_name

student.

data_rogd

student.

kurs

student.

telefon

faculty.

nazvanie

faculty.

phone

student.name

0.895

0.045

0.045

0.045

0.045

0.045

student.dob

0.045

1.0

0.045

0.045

0.045

0.045

student.course

0.025

0.025

0.985

0.025

0.025

0.025

student.email

0.045

0.045

0.045

0.045

0.045

0.045

student.phone

0.045

0.045

0.045

0.645

0.045

0.045

professor.first_last_name

0.045

0.045

0.045

0.045

0.045

0.045

professor.date_of_birth

0.045

0.045

0.045

0.045

0.045

0.045

professor.elektr_addr

0.045

0.045

0.045

0.045

0.045

0.045

professor.telefon

0.045

0.045

0.045

0.045

0.045

0.495

proekt.title

0.045

0.045

0.045

0.045

0.045

0.045

proekt.date

0.045

0.045

0.045

0.045

0.045

0.045

proekt.budget

0.045

0.045

0.045

0.045

0.045

0.29

faculty.title

0.045

0.045

0.045

0.045

0.98

0.045

faculty.phone

0.085

0.045

0.045

0.045

0.045

0.985

Таблица 2

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

Отношения схемыданных

Отношениясхемы данных

student

faculty

student

0.209

0.041

professor

0.045

0.101

proekt

0.045

0.085

faculty

0.050

0.513

Результатом применения алгоритма отождествления объектов являются следующие пары объектов: 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.

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


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=100
Версия для печати
Выпуск в формате PDF (1.92Мб)
Статья опубликована в выпуске журнала № 1 за 2008 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: