Software & Systems

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

На сегодняшний день есть средства, которые автоматически предлагают соответствия между схемами на основе их синтаксического анализа (см.: E. Rahm, P.A. Bernstein. A survey of Approaches to Automatic Schema Matching. VLDB Journal. 10(4):334-350, 2001) либо на основе семантических данных, задаваемых экспертами (см.: S. Spaccapietra, C. Parent. View Integration: A Step Forward in Solving Structural Conflicts. TKDE. 6(2):258-274. 1994). Однако применение этих средств не дает ответа на вопрос о гарантированной возможности решения той или иной задачи интеграции данных. В случае определения соответствий на основе семантических данных от экспертов обычно требуется абстрактное высокоуровневое проектирование: детальное описание объектной модели предметной области либо определение формальной онтологии разрешения конфликтов (см.: S. Ram, J. Park. Semantic Conflict Resolution Ontology (SCROL): An Ontology for Detecting and Resolving Data and Schema-Level Semantic Conflict, TKDE. 16(2). 189-202, 2004). Подход, описанный в данной статье, напротив, не требует от экспертов ничего, кроме указания конкретных взаимосвязей между атрибутами.

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

Пусть некоторая сущность описывается в первой схеме данных отношением A, содержащим кортежи , а во второй схеме данных отношением B, содержащим кортежи . Отношения A и B могут быть как отдельными таблицами в реляционной схеме данных, так и переменными-отношениями. Запишем формально условие, что A и B содержат одни и те же физические сущности. Будем считать, что в этом случае существуют взаимосвязи между отдельными атрибутами  и . Рассмотрим различные типы таких взаимосвязей между двумя скалярными атрибутами x и y, определенными на конечных доменах X и Y соответственно.

Классификация взаимосвязей доменов

1. Смысловая взаимосвязь доменов. Наиболее общим типом взаимосвязи можно считать случай, когда мы хотя бы можем определить, совпадают ли объекты по атрибутам x и y или не совпадают. Другими словами, задана функция смысловой эквивалентности: . , если по атрибутам x и y объекты совпадают,  в противном случае.

2. Существует конвертирующее отображение из X в Y, если для любого значения  существует значение , такое что по атрибутам x и y объекты будут совпадать. Другими словами, существует отображениетакое, что для всех  выполняется равенство

.                                                      (1)

3. Существует обобщающее отображение из X в Y (Y – обобщение X), если для любого значения  существует ровно одно значение , такое что по атрибутам x и y объекты будут совпадать. Другими словами, существует отображение, такое что для всех  выполняются условие (1) и неравенство

 для всех .                         (2)

4. Существует обобщающее отображение X на Y (X – детализация Y), если для любого значения  существует ровно одно значение , и для любого y существует хотя бы одно значение x, такое что по атрибутам x и y объекты будут совпадать. Другими словами, существует отображение , такое что для всех  существует , такой что ; и для всех  выполняются условия (1) и (2).

5. Изоморфизм доменов, если существуют отображение , удовлетворяющее условиям (1) и (2), и обратное к нему , также удовлетворяющее условиям (1) и (2).

Кроме приведенных типов взаимосвязей, рассмотрим следующие.

2¢. Существует конвертирующее отображение из Y в X.

3¢. Существует обобщающее отображение из Y в X.

4¢. Существует обобщающее отображение Y на X.

Нетрудно доказать следующие свойства приведенной классификации.

·     Классы взаимосвязей, определяемые условиями 1-5, 2¢-4¢, не совпадают между собой.

·     Каждое условие с меньшим номером следует из условия с большим номером (в отдельности для условий без штрихов и со штрихами).

·     Из условия 4 следует 2¢, а из 4¢ следует 2.

·     Если условия 3 и 3¢ выполняются одновременно, то выполняется условие 5.

Классификация взаимосвязей схем данных

Будем считать, что объект, заданный кортежем  в одной схеме данных, совпадает с объектом, заданным кортежем b=  в другой схеме данных, если они совпадают по всем взаимосвязанным атрибутам, то есть для всех функций смысловой взаимосвязи  верно равенство . Множество пар индексов , для которых заданы функции , обозначим . Тогда можно задать функцию соответствия объектов  следующим образом:

, если

для всех ;                                                     (3)

, если существует ,

такие что.                                           (4)

Замечание. Для задачи устранения дублирования можно рассматривать не бинарную функцию P, а отображение на отрезок. . В этом случае P задается некоторой формулой от функций . В самом простом случае – это среднее арифметическое:

.

В прикладных задачах к этой формуле могут добавляться весовые коэффициенты или использоваться более специфические формулы. Например, если мы решаем задачу сопоставления списков юридических лиц и у нас заданы функции смысловой взаимосвязи:  – совпадение ИНН,  – похожесть наименования, – совпадение даты регистрации. Условие, что  дает нам полную уверенность, что юридические лица совпадают, а условия  и  используются, только если , чтобы определить степень похожести. В этом случае функцию P можно задать следующим образом:

.

Обозначение. Множество пар индексов , для которых существует взаимосвязь доменов второго типа (существует конвертирующее отображение из  в ), обозначим . Для третьего типа – . Для типа 2¢ – обозначим  и так далее для всех типов взаимосвязей между доменами. Множество индексов i, входящих в одно из этих множеств , обозначим , множество индексов j обозначим .

Перейдем к классификации взаимосвязей между схемами данных.

1. Соответствие объектов. Если  не пусто, и задана функция , будем говорить, что установлено соответствие объектов. Пусть  и  являются первичными ключами отношений A и B. Тогда, если выбрать все пары , для которых  , получим таблицу соответствия N с заголовком . Имея такую таблицу, можно делать запросы, получающие данные из обеих схем, следующим образом:

Select

From

Where  and

2. По кортежу из A можно определить кортеж в B. Если существует потенциальный ключ , будем говорить, что по кортежу из отношения A можно определить кортеж в отношении B. Условие  означает, что существует набор конвертирующих отображений , для всех . Используя эти отображения, можно по кортежу построить набор атрибутов . И поскольку K – это потенциальный ключ, в отношении B может существовать не более одного кортежа b, содержащего атрибуты k. Таким образом, можно по кортежу a из отношения A быстро найти в отношении B кортеж b такой, что , не создавая и не используя таблицу соответствия.

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

1)       переменная-отношение B должна быть обновляемой (либо это должна быть таблица);

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

3. По кортежу из A можно однозначно определить кортеж в B. Если существует потенциальный ключ , будем говорить, что по кортежу из отношения A можно однозначно определить кортеж в отношении B. Смысл этого условия раскрывает следующая теорема.

Теорема. Если в B существует потенциальный ключ K, такой что для всех  существует обобщающее отображение  из  в , то каждое значение первичного ключа  входит в таблицу соответствия N не более одного раза.

Пример. Проиллюстрируем действие теоремы задачей сопоставления юридических лиц. Предположим, что во второй из интегрируемых систем реализовано устранение дублирования, не допускающее в переменной-отношении B двух кортежей с одинаковым значением ИНН в атрибуте , то есть  является потенциальным ключом. И пусть обобщающее отображение  оставляет ИНН без изменений. Тогда, применяя теорему, можно заключить, что если построить таблицу соответствия, то каждая запись из переменной-отношения A будет входить в нее не более одного раза.

4. Отношения A и B синхронизируемы. Если по кортежу из A можно однозначно определить кортеж в B и по кортежу из B можно однозначно определить кортеж в A, будем говорить, что отношения A и B синхронизируемы. Смысл этого условия в том, что если перенести некоторый кортеж a из A в B, а потом обратно, то гарантировано не будет создано новой записи a¢, дублирующей a. Этот факт следует из предыдущей теоремы. Действительно, если по кортежу из B можно однозначно определить кортеж в A, то первичный ключ кортежа b может входить в таблицу соответствия не более одного раза и, следовательно, не может соответствовать кортежам a и a¢ одновременно.

Замечание. Не требуется, чтобы потенциальные ключи A и B лежали в . Для того чтобы A и B были синхронизируемы, достаточно, чтобы потенциальный ключ A лежал в , а потенциальный ключ B лежал в .

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

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

Автор благодарит своего руководителя чл.-корр. РАН, д.ф.-м.н. С.М. Абрамова за постановку задачи и полезные обсуждения.