автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Высокоуровневые методы и алгоритмы классификации интеграционных взаимосвязей структур данных

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

Николай Валерьевич Юмагужин

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

Переславль-Залесский 2008

о5йЕПдаз

003456206

Работа выполнена в Учреждении Российской академии наук Институте программных систем РАН.

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

Официальные оппоненты:

• Знаменский Сергей Витальевич, доктор физико-математических наук,

• Новиков Федор Александрович кандидат физико-математических наук.

Ведущая организация: Саратовский государственный технический университет

Защита состоится «19 » декабря_2008 г. в _14_ часов на заседании

Диссертационного совета ДМ 002.084.01 при Учреждении Российской академии наук Институте программных систем РАН по адресу: 152020, Ярославская обл., Переславский район, с. Веськово, ул. Петра Первого, д. 4а.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института программных систем РАН.

Автореферат разослан «_»_2008 г.

Автореферат размещен на сайте ИПС РАН http://www.botik.ru/PSI

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

диссертационного совета,

Общая характеристика работы

Актуальность проблемы

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

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

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

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

Одним из подходов, позволяющих решить высокоуровневые задач информационного обмена, является создание централизованной систем ведения справочников, стандартизирующей и унифицирующей справочн; информацию. Обобщенно класс таких систем называют Master Dat Management (MDM-системы) или более распространенным в Россш термином - системы Нормативно Справочной Информации (НСИ). Ochobhoi проблемой при использовании данного подхода является то, что создани централизованной надстройки над всеми системами должно, с одно стороны, производиться на основе единых архитектурных решений, а другой стороны, требует учета особенностей предметных областей все интегрируемых систем. В настоящее время данную проблему нельзя считат решенной. Требуются предметно-независимые методы и алгоритмь позволяющие формализовать процесс интеграции баз данных и знаний стандартизировать процессы проектирования и анализа взаимосвязей схемах данных, а также оценивать качество интеграционных программш систем.

Цель работы

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

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

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

2. Построить классификацию взаимосвязей между переменными-отношениями в различных схемах данных.

3. Построить алгоритм сопоставления текстовых строк учитывающий «веса» замены одного символа на другой, а также возможность перестановки слов в строке.

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

распределенные по разным системам.

Предметом исследования являются модели, методы и алгоритмы интеграции данных, хранящихся в различных базах данных и знаний.

Диссертационная работа выполнена в рамках паспорта научных специальностей ВАК 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», п. 3. -Организация баз данных и знаний, построение систем управления базами данных и знаний.

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

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

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

Основные положения диссертации, выносимые на защиту:

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

2. Построение классификации взаимосвязей между переменными-отношениями в различных схемах данных. Выделены следующие классы: соответствие кортежей, возможность по кортежу в переменной-отношении А определить кортеж в переменной-отношении В, возможность по кортежу в А однозначно определить кортеж в В, возможность синхронизации переменных-отношений. Доказаны необходимые и достаточные условия для определения класса взаимосвязей между переменными отношениями. Исследованы свойства, определяющие практическую значимость выделенных классов взаимосвязей, приведены соответствующие примеры.

3. Построение алгоритма сопоставления текстовых строк, учитывающего «веса» замены одного символа на другой, а также возможность перестановки слов в строке.

4. Два примера выполненных проектов, использующих технологию интеграции данных, основанную на построенной классификации. Проекты относятся к различным предметным областям: в первом примере рассматривается задача интеграции данных о физических и юридических лицах, во втором примере рассматривается задача интеграции данных о материально-технических ресурсах.

б

Научная новизна работы

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

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

Практическая значимость

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

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

Апробация работы и публикации

Основные результаты диссертации были доложены на научных конференциях [4, 5] и опубликованы в рецензируемых журналах [1, 2, 3], в том числе одна публикация в издании из списка рекомендованных ВАК. Основные результаты диссертационной работы были использованы в практических проектах по интеграции данных [2,3].

Структура и объем работы

Диссертация состоит из введения, теоретической работы (включающей пять разделов), экспериментальной работы (включающей два примера), заключения и списка литературы. Содержание работы изложено на 134 страницах. Список литературы включает 20 наименований. В работе содержится б рисунков.

Содержание работы

В главе 1 (Введение) приводится постановка задачи и краткое резюме проделанной работы, дается подтверждение актуальности и новизны работы, кратко описываются методы исследования и полученные результаты.

В главе 2 (Теоретическая работа) описывается область исследований, дается краткая характеристика смежных научных работ и публикаций. Исследуются проблемы сопоставления схем данных и сопоставления записей. В качестве результата приводится предметно-независимая классификация взаимосвязей в схемах баз данных, значимых для интеграции информационных систем. Кроме того, в этой главе приводится общее

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

В разделе 2.1 приводится обзор публикаций по смежным научным работам. Рассматриваются исследования в области сопоставления схем данных и в области сопоставления записей. Дается подтверждение научной новизны настоящей работы.

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

1. Смысловая взаимосвязь доменов

Наиболее общим типом взаимосвязи считается случай, когда есть возможность определить, совпадают ли объекты по атрибутам х и у или не совпадают. Другими словами, задана функция смысловой эквивалентности: P:XxY-*{ 0,1}

Р{х, у) = 1, если по атрибутам х и у объекты совпадают Р(х,у) = 0, в противном случае

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

В этом случае функция Р отражает степень эквивалентности ("похожести") объектов по атрибутам х и у.

2. Существует конвертирующее отображение тХвУ

Если для любого значения хеХ существует значение уеУ, такое что по атрибутам х и у объекты будут совпадать. Другими словами, существует отображение F:X-± У такое, что для всех xGX выполняется равенство:

P(x,F(x)) = 1 (1)

3. Существует обобщающее отображение из Хв У (У- обобщение Л? Если для любого значения x<s.X существует ровно одно значение увУ, такое что по атрибутам х и у объекты будут совпадать. Другими словами, существует отображение

F: X -> Утакое, что для всех хеХ выполняются условие (1) и неравенство:

Р(х, у) < 1 для всех у F(x) (2)

4. Существует обобщающее отображение Хна У (Х- детализация У) Если для любого значения хеХ существует ровно одно значение уеУ, и для любого у существует хотя бы одно значение х, такое что по атрибутам х и у объекты будут совпадать. Другими словами, существует отображение F:Х-*Утакое, что для всех уеУ существуетхвХ, такой что F(x) = у; и для всех х€Xвыполняются условия (1) и (2).

5. Изоморфизм доменов

Если существуют отображение F:X->Y, удовлетворяющее условиям (1) и (2), и обратное к нему F'1 :У—>Х, также удовлетворяющее условиям (1) и (2).

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

1. Из условия 5 следует 4, из 4 следует 3, из 3 следует 2, и из 2 следует 1.

2. Из условия 5 следует 4', из 4' следует 3', из 3' следует 2', и из 2' следует 1. Тут условие 2' означает, что существует конвертирующее отображение из Y в X; 3' означает что существует обобщающее

10

отображение из У в X; 4* означает что существует обобщающее отображение У на X.

3. Из условия 4 следует 2'. (Аналогично, из 4* следует 2).

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

5. Для любых двух условий из приведенной классификации можно подобрать атрибуты х и у, определенные на доменах X и У, такие, что для них выполняется одно из условий, но не выполняется второе.

Таким образом доказывается, что приведенная классификация является корректной, то есть классы взаимосвязей, определяемые условиями 1-5,2'-4', не совпадают между собой. Схема вложения классов друг в друга приведена на рисунке 1.

Рисунок 1. Схема вложения классов взаимосвязей

Во второй части раздела строится классификация взаимосвязей между схемами данных. Считается, что объект, заданный кортежем а = {хих2,...хп}

в одной схеме данных, совпадает с объектом, заданным кортежем Ь — {У\,Уг>—Ут) в Другой схеме данных, если они совпадают по всем взаимосвязанным атрибутам, то есть для всех функций смысловой взаимосвязи Р^ :X, х Yj —>{0,1} верно равенство = 1. Множество

пар индексов (/,у) , для которых заданы функции Р1) , обозначаются ^ = • На основе этого задается функция соответствия объектов

Р : Ах В ->{0,1} следующим образом:

Р(а,Ь) = 1,есляРи(х„у^ = 1 длявсех (/,/') б О (3)

Р(а, Ь) = 0, если существует (/, у) 6 О такие, что Р, у (х,, у}) * 1 (4) Далее вводятся дополнительные обозначения. Множество пар индексов (1,7) , для которых существует взаимосвязь доменов второго типа (существует конвертирующее отображение из X, в У^) обозначается О2. Для третьего типа - П3. Для типа 2' (существует конвертирующее отображение из У,- в Х1

) — обозначается О2 . И так далее, для всех типов взаимосвязей между доменами. Множество индексов /, входящих в одно из этих множеств Пх, обозначается П^, множество индексов] обозначается Пд.

Всего выделяется 4 класса взаимосвязей между переменными-отношениями в различных схемах данных:

1) Соответствие объектов, если а не пусто, и задана функция смысловой взаимосвязи Р'АхВ-* {0,1}.

2) По кортежу из А можно определить кортеж в В, если выполняются следующие условия множество £2^ не пусто и для всех атрибутов у} где

у Щ С1д, задано значение по умолчанию или автоматическая нумерация Ое/у.

3) По кортежу из А можно однозначно определить кортеж в В, если выполняются следующие условия:

a) Существует потенциальный ключ К ей \

b) Для всех атрибутов где ] задано значение по умолчанию или автоматическая нумерация

4) Отношения А и В синхронизируемы, Если по кортежу из А можно однозначно определить кортеж в В, и по кортежу из В можно однозначно определить кортеж в А

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

1) Соответствие объектов означает, что есть возможность делать запросы, получающие данные из обеих схем;

2) По кортежу из А можно определить кортеж в В означает, что есть возможность переносить данные из одной системы в другую;

3) По кортежу из А можно однозначно определить кортеж в В означает, что есть возможность переносить данные из одной системы в другую и при этом гарантированно не появляются дубликаты;

4) Отношения А к В синхронизируемы означает, что возможна синхронизация объектов без создания дубликатов.

В разделе 2.3 исследуются способы сопоставления записей. Рассматриваются функции степени эквивалентности («похожести») записей Р:АхВ-± [0,1], где 1 означает точную эквивалентность, а 0 означает точную неэквивалентность. В работе не придается степени эквивалентности какого-то определенного смысла. Это не вероятность и не степень совпадения записей. Как правило, система поиска дубликатов вычисляет степень

13

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

Особое внимание в работе уделяется алгоритмам сопоставления строковых атрибутов. Сначала приводится традиционный алгоритм вычисления расстояния Левенштейна (дистанции редактирования). Далее приводится алгоритм Смита-Ватермана1. Этот алгоритм был изначально разработан для поиска эволюционных взаимосвязей в биологических протеинах и цепочках ДНК. Он позволяет особым образом обрабатывать «зазоры» из символов не несущих смысловой нагрузки, и вычислять расстояние редактирования с учетом «стоимости» замены одного символа на другой.

Далее описана оптимизация алгоритма Смита-Ватермана применительно к текстовым атрибутам, сокращающая время работы алгоритма более чем на 50%. Смысл данной оптимизации в том, что можно быстро определить, что строки отличаются «достаточно сильно» не вычисляя точно, на сколько сильно они отличаются.

В ходе работы алгоритм Смита-Ватермана вычисляет матрицу весов Е. Одна из строк помещается по горизонтальной оси матрицы, а вторая - по вертикальной оси. Элемент Е(У) матрицы — это лучший вес сопоставления подстрок 51(1.л) первой строки и 52(1.-У) второй строки. Формально значение Е(1о) вычисляется следующим образом:

1 T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147:195-197,1981.

14

E(i,j) = max

E(i - l,j -1) + mÇs^Q.SiW) E(i - l,j) + с, если alignai - 1 ,j - 1) = зазор E(i - l,f) + s, если alignai - l,j — 1) = совпадение E(i,j - 1) + с, если alignai - 1 ,j - 1) = зазор \E{i,j - 1) + s. если alignai - l,j — 1) = совпадение

Тут т- это матрица содержащая стоимость замены символов алфавита один на другой, скалярный параметр в - это стоимость начала зазора, параметр с - это стоимость продолжения зазора. Если строки и б2 совпадают, то наименьший вес соответствия строк будет лежать на главной диагонали. Если строки отличаются незначительно, то наименьший вес будет расположен на небольшом удалении от главной диагонали. Поэтому достаточно вычислять элементы матрицы Е только в небольшой окрестности главной диагонали. Для строк длинной в 50 символов эксперименты показывают, что если вычислять элементы на главной диагонали плюс минус 15 символов, то точность алгоритма Смита-Ватермана для задачи сопоставления строковых атрибутов практически не изменяется.

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

Строка 1: Институт Программных Систем, переславль-Залесский строка 2: Переславль-Залесский, институт программных Систем строка 3: институт программирования и систем управления

то для всех трех стандартным алгоритмом Смита-Ватермана будет выдано примерно одинаковое расстояние. Хотя первые две строки по смыслу похожи гораздо больше. Для того чтобы учесть возможность перестановки подстрок в строке предлагается повторно анализировать зазоры оставленные алгоритмом Смита-Ватермана. Для приведенного примера при первом проходе алгоритма для первых двух строк сопоставляются следующие подстроки:

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

В разделе 2.4 рассматриваются способы устранения дубликатов. Задача устранения дублирования возникает после сопоставления записей и нахояадения дубликатов в одной из интегрируемых систем. Выбор способа устранения дублирования зависит от того, какой имеется доступ к базе данных, и от распределенности системы. В работе выделяются четыре основных подхода:

1. Полное устранение дублирования с удалением всех упоминаний о дублирующихся записях.

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

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

a) Удаление объекта-дубликата из текущей базы данных

b) Замена идентификатора объекта-дубликата на идентификатор эталонного объекта во всех таблицах текущей базы данных.

с) Сохранение пары идентификаторов эталонного объекта и объекта

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

3. Пометка дубликатов в БД. Данный способ подразумевает, что в объекте-дубликате мы устанавливаем некоторый признак, что данный объект не должен использоваться в дальнейшем. Иногда при этом говорят, что объект перенесен в архив, хотя фактически он остается в той же таблице, просто для него устанавливается флаг «архивный». Кроме того, в объекте-дубликате указывается ссылка на эталонный объект, который должен использоваться вместо объекта-дубликата. При создании других объектов в базе данных у пользователя не должно быть возможности связывать вновь созданные объекты с объектом-дубликатом, у которого установлен флаг «Архивный». Тем не менее, объект-дубликат может быть связан с созданными ранее объектами.

4. Хранение информации о дублировании только на уровне НСИ. Данный способ применяется в случае, если полностью отсутствует доступ к структуре БД, а доступ к данным в справочнике есть только на чтение. Способ заключается в том, что мы храним информацию о дублировании вне системы и используем ее при формировании отчетов для консолидации данных по дублирующимся объектам.

Также в работе приводятся критерии для применения того или иного способа устранения дублирования:

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

2. Территориальная распределенность системы; ^

3. Наличие полного описания всех связанных структур данных;

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

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

В разделе 2.5 рассматриваются организационные моменты проекта по внедрению системы ведения централизованных справочников и интеграции данных.

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

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

¡1 MU ггшл Ы. W6PH.4 С«ак слым ЖЖ

© О *«порт 1 Imeimn Информация из Лянк'я (тереме 500)

Коиоо*ишм| улутш

Г Поиск ООГЮСнОпу шмидонтй строки

Homo л<ж*тнг1; f Hot*? кЛтятвлного счет»:

HIIMMWI'гиятвяеа: Г"

Код оп«сации; I

Код млмты: Г

ЬИКвжжа г-

оглелйитвллДюптматв«: 1

Состояние: Затрут ф«йп«:

Cvet

Отправит «ль Аккучаталь: Сумапштож*

cir^^ronAjm^reiiM:

Датл пдоожа:

. |«&с* jeonoi» .{<<6» 5»П»Ю1»

гзг

г—

•Р» •' il nojr"

-3

wr I Сwwnw _I Загружу »«fcw_ Гноя*ра<хти«~ ¡Httnt mm* nu... I n»*t> 1 "I

Я1 Vlft inull^k ЛГАиытлЛ! П UIIUA M ) 1 1Г1 lT-'N'M П li П -.tvri й-ГП>. МЫКП imi M1II1 V'^1 МН1Л1C.

I» удел«» OCOHMprvi»».

Скяттргирпплмл г.клжм^гирлл.^ил Скл'ны-ргпроплил

Смлмргцютвм Скдпхи ivvfen-a

fll Сквимргиро»*.« fl2 Сглниртв«»«« 113 CKewpiwum 1 14 Г.К11ЖМ!ПГИ0Л«ЛНЛ СКЯИЯАртНрЛАЛНЛ

ilfi

13 VIDOR .0Ы19X1 .VJ 2« VIBOtt.Otf 21.11.03 10:24... 1 VIAOI».DAr77.l<U>3 17:37:10 I VIAOP.OW 77.10 03 17:37:10 I У1АО«.ППГ 77.10J>3 17:37:10 1 VIRC« ПЛГ 77.10.03 17:37:10 1 VltCRXtBT 27.10.03 17:37.10 1 VI&OA.OW 2740.03 17:37:10 1 VHK*.OB* Z/.lO-u? 17:97:10 1 VlttOft.Ott* 27 ¿0-03 17:37:10 1 VIOW.OW CI \QSTi 17:37:10 1 VlOCft-UW r; .lcl.07 17:37:10 1 V160*.00r Г7.10.03 17:37:10 1 V1MM.OAF 77.10-03 17:37:10 I VlAOfl.GAF77.|OjQ3 17:37:10 I VIAOCI np.F .'7.10.0.3 17:37:10

4.11.2003 24. 10.2003 07.10.2003 07.10.7003 14.10 700.1 06.10.2003 16.10.2083 0j.1o.ior 03.1U-20B I7I.10.2W

16.10.

16.10.200.

14.10.700

A:CTlb АВИЛХО... Л0вX«1101 V>»1 (Ж1001Л

Д:14Л4Д«в*А... 400IM101SS41900012?

д:КЛ2.1*>в* p... «oaiiato«SR3ftoooni3i

A:1S.10.14SS* A... 40B1OS104SS3AOO0O133

Д:17ЛГМ W (Ц.. 401114S107SS38OOOOI34

A:l«j».1«sr A... 40alB«tOtS531W00013?

Д:1«-05.1*5Г A.„ 40«im0l»380000il2

Д;18.05.1*52* A... 408l»tl01S33S0000132

ятяьлпо' a.«, 41»хо*1«»*зтмл)1эо

й:2ЬЖЛ1ТЬ* A... 40UiOSmttSVJW»OTX.3{.

А:гГМ9.1П7* л... 4UM««10»i!.3tW000131

Д:7/-в9.1Л/* A... 40U1<K>1«№^WOUOU131

ОПЛАТА ЗА A»c... 4001001047330000013 3

ОП ПАТА ЗА A7f... 40В1IMU04SS3MOOOl13

П: ^окумемты... 4Л91М1О4«КЗА0О«ШЗ

П: ;CMu0S/J<V0- 40f»ie«lft4S53A000OI33

Рисунок 2. Интерфейс переноса данных из банковской системы

Для юридических лиц в контрольной системе потенциальными ключами являются наборы реквизитов Ki = {ИНН} и Кг = {БИК, р/с}. В соответствии с построенной классификацией, чтобы по юридическому лицу из банковской системы можно было однозначно определить юридическое лицо в контролирующей системе необходимо, чтобы выполнялось одно из условий: Кг с или К2 с Причем, не обязательно, чтобы выполнялось условие Кх U К2 <= Далее приводится функция соответствия юридических лиц, удовлетворяющую таким условиям:

Р(ЮЛХ, ЮЛ2) = (ИННх = ИНН2) V ((БИК! = БИК2) А (р/сг = р/с2)) Условие Кг с означает, что функция соответствия юридических лиц Р(ЮЛ1#ЮЛ2) = 1 , если ИННХ = ИНН2 и Р(ЮЛ1,ЮЛ2) < 1> если ИНН! * ИНН2 . Условие К2 с означает, что Р(ЮЛ1/ЮЛ2) = 1 , если БИК! = БИК2 и p/ci = р/с2 ; Р(ЮЛХ,ЮЛ2) < 1 , если БИКа * БИК2 и p/ci Ф р/с2.

Аналогично рассматривается случай физических лиц. Для физических лиц потенциальными ключами являются наборы реквизитов К1 = (ФИО, дата рождения} и К2 = (ФИО, паспортные данные}. Приводится функция соответствия физических лиц, позволяющая по физическому лицу из банковской системы однозначно определить физическое лицо в контролирующей системе:

Р(ФЛ1(ФЛ2) = (ФИО! = ФИ02) А А ((дата рождения! = дата рождения2) V V (паспортные данные! = паспортные данные2)) Далее в этом разделе приводятся технические требования по реализации выгрузки и загрузки данных при переносе между системами, а также требования по реализации устранения дублирования.

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

На одном из этапов интеграции в данном примере требуется пополнение справочника товаров на основе заявок направляемых территориально-распределенными дочерними обществами. Заявка на добавление товара содержит следующую информацию:

- Группа номенклатуры (код из централизованного справочника)

- Подгруппа номенклатуры (код из централизованного справочника)

- Наименование

- ГОСТ

- Технические характеристики

- Код ОКП (Общероссийский классификатор продукции)

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

Р(а,ЪУ.Ах В -»[ОД] Поля группа, подгруппа и код ОКП не задают товар однозначно, а задают только некоторый класс (группу) товаров. Кроме того нельзя полагаться на то, что сотрудники дочернего общества укажут эти три кода правильно. Поэтому их совпадение может учитываться при сопоставлении записей, но однозначного совпадения не задает. Точное совпадение полей Наименование, ГОСТ и Технические характеристики (ТХ) можно считать совпадением записей, так как это вся информация о товаре, которой мы располагаем. То есть эти три поля мы считаем потенциальным ключом К = {Наименование, ГОСТ, ТХ}, причем если эти наборы реквизитов в таблицах А и В совпадают Ка = Кь , то записи тоже совпадают Р{а,Ъ) — 1. Функция соответствия, удовлетворяющая этим критериям задается следующим образом:

^(а.Ь) = -(Р^^ (Наименование^ Наименование;,) +

+Р5„д (ГОСТа, ГОСТь) + В случае, когда Р^а, Ь) < 1 так же учитываются поля Группа номенклатуры, Подгруппа номенклатуры и код ОКП:

Р2(а,Ь) = ^((Группаа == Группа,,) +

+(Подгруппа,, == Подгруппай) + (ОКПа == ОКПь)) Но если Рг(а, Ь) < 1, то условие Р2(а,Ь) = 1 не может однозначно говорить о совпадении товаров, поэтому окончательная функция соответствия задается следующим образом:

Р(а,Ь) = Р^а,Ь) + Р2(Д,6)1~Р*('Х,Й)

Далее производится анализ взаимосвязи записей в списке заявок на добавление номенклатуры А и записей в справочнике товаров В в соответствии с построенной в пункте 2.2 классификацией. В данном случае потенциальный ключ К с fi| но не выполнено условие К с П|. На основе этого делается вывод, что по кортежу из А можно определить кортеж в В, но нельзя определить его однозначно. Следовательно, если реализовать автоматический перенос данных, то в справочнике товаров В могут появиться дубликаты.

Чтобы избежать возникновения дубликатов реализуется перенос записей в полуавтоматическом режиме. Если для заявки на добавление номенклатуры а в справочнике товаров В найден такой товар Ъ, что P(a,b) = 1, то можно в автоматическом режиме установить, что товар уже существует и закрыть заявку. Если такой товар Ь не найден, то решение о существовании товара в справочнике остается за пользователем. Для этого в интерфейсе системы отображается некоторое множество товаров F (а), «похожих» на а:

Fda) = {b\PCa,b)>k} Где к -фиксированная константа. Если (а, Ь) = 0, то имеет смысл видеть все товары, входящие в группу и подгруппу номенклатуры указанные в заявке на добавление номенклатуры. Чтобы этого достичь устанавливается к = Варьируя коэффициент к можно регулировать количество записей отображаемых пользователю в интерфейсе (см. Рисунок 3).

№ 1091 - Товар Заявка Обработка

но........... .Г

г-

Товар Но. . . . .... |

1091

Ствтус.........[Открыта

Код Дочернего Обще... |сВ0ЛГА

Группа Нсяежлатуры . |МЕТАЛЛ

Подгруппа Нонемсла... ¡ОПОРА

Наименование Напен... ¡Опора анкерная кошева!!

ГОСТ. ....

..г

Технические ¡Саракте... |А10-1 т.п. 3.407.1-143.1.10 Баз. Едмнша Иэнере,.. ¡ШТ 2 Комюнтарии. ..... [

требует ут... | Добавить | Дублисат |

Но. [Описание

зщ

Т001004 Т001006 Т001007 Т002297 Т002298 Т002304 Т002Э05 Т002307 Т002309 Т002313 Т002320 Т002321

и.

Опора Опора Опора Опора Опора Опора Опора Опора Опора Опора Опора Опора

Опора _|

неподвижная неподвижная неподвижная для т.. неподвижная для т..

анкерная

анкерная угловая

вертикальная

горизонтальная

горизонтальная

неподвижная

подвижная

Рисунок 3. Интерфейс обработки заявок на добавление номенклатуры.

Пользователь просматривает список товаров И {а) и принимает решение: если товар а уже есть среди ^(а) , то заявка закрывается с пометкой дубликат; если данных указанных в заявке а не достаточно, то заявка получает статус «Требуется уточнение» и опять передается в ДО; если товара а в справочнике нет и все данные в заявке заполнены правильно, то товар добавляется в справочник, при помощи тождественных отображений /¡(аг) = К

В главе 4 (Заключение) подводится итог проведенной работе, рассматриваются достоинства и недостатки построенной классификации взаимосвязей в схемах данных, а также описывается возможное продолжение работ в данном направлении.

Основные результаты работы

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

2. Построена классификация взаимосвязей между переменными-отношениями в различных схемах данных.

3. Построен алгоритм сопоставления текстовых строк учитывающий «веса» замены одного символа на другой, а также возможность перестановки слов в строке (расширение алгоритма Смита-Ватермана).

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

Публикации по теме диссертации

1. Н.В. Юмагужин. Классификация взаимосвязей в схемах данных. //Программные продукты и системы, № 3,2007,204-212.

2. Н.В. Юмагужин. Сопоставление записей и интеграция данных о физических лицах. //Программные системы: теория и приложения, Т.1, Переславль-Залесский, 2008,251-260.

3. Н.В. Юмагужин. Анализ задачи централизованных закупок в территориально распределенном холдинге. // Труды конференции «Технологии Microsoft в теории и практике программирования», Москва, 2006,98-102.

4. Н.В. Юмагужин. Исследование возможностей работы с ERP-системой Microsoft Navision в режиме offline. //Труды конференции «Технологии Microsoft в теории и практике программирования», Москва, 2005,154-158.

5. Н.В. Юмагужин. Построение системы сбора данных без использования централизованных справочников. //Информационные технологии моделирования и управления, 6 (24), «Научная книга», Воронеж, 2005,251-263.

а 4

¿(j

1. Введение.

1.1. Постановка задачи.

1.2. Содержание диссертации.

1.3. Актуальность и новизна.

1.4. Методы исследования.

2. Теоретическая работа.

2.1. Обзор.

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

2.2.1. Примеры взаимосвязей.

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

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

2.3. Способы сопоставления записей.

2.3.1. Алгоритм Смита-Ватермана Р$н>.

2.3.2. Оптимизированный алгоритм Р8\\/о.

2.3.3. Обобщенный алгоритм РБюд.

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

2.4.1. Полное устранение дублирования.

2.4.2. Устранение дубликатов с сохранением истории.

2.4.3. Пометка дубликатов в БД.

2.4.4. Хранение информации о дублировании в НСИ.

2.5. Организационные вопросы.

2.5.1. Разрешение организационных конфликтов.

3. Экспериментальная работа.

3.1. Пример 1: Задача учета ЮЛ и ФЛ.".

3.1.1. Описание предметной области и проекта.

3.1.2. Интеграция банковской и контрольной систем.

3.1.3. Интеграция регистрирующей и контрольной систем.

3.1.4. Устранение дублирования.

3.2. Пример 2: Задача централизованных закупок.

3.2.1. Описание предметной области и проекта.

3.2.2. Анализ процесса планирования закупок.

3.2.3. Формирование справочника-прейскуранта.

3.2.4. Бизнес-процесс формирования плана закупок.

3.2.5. Задача расчета цен.

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

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

1. Делать запросы, для обработки которых требуется информация из нескольких баз;

2. Конвертировать данные для передачи между базами;

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

4. Заключение

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

4.1. Планируемое продолжение работы

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

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

2. Источники данных доступны по протоколу SOAP Основной сценарий:

1. Пользователь указывает путь к источникам данных А и В.

2. Прототип загружает структуры и генерирует метаданные, описывающие найденные схемы данных.

3. Пользователь указывает взаимосвязи между таблицами и атрибутами обоих источников, определяет типы конфликтов и вводит конвертирующие функции.

4. Прототип генерирует таблицу НСИ Конечные условия:

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

1. Rahm, Bernstein, 2001. E. Rahm, P.A. Bernstein. "A survey of Approaches to Automatic Schema Matching". VLDB Journal, 10(4):334-350, 2001

2. Roth at al., 2006. M. Roth, M.A. Hernandez, P. Coulthard, L. Yan, L. Popa, H.C.-T. Ho, and C.C. Salter "XML Mapping Technology: Making Connections in an XML-centric World". IBM Sys. J. (45,2), 389-409, 2006.

3. Bernstein, Melnik, 2007. Bernstein, P.A., Melnik, S., "Model Management 2.0—Manipulating Richer Mappings," Proc. SIGMOD, 1-12, 2007.

4. Ram, Park, 2004. Ram, S., Park, J. "Semantic Conflict Resolution Ontology (SCROL): An Ontology for Detecting and Resolving Data and Schema-Level Semantic Conflict", TKDE, 16(2), 189-202, 2004

5. Kim et al., 1993. W. Kim, I. Choi, S. Gala, and M. Scheevel. On resolving schematic heterogeneity in multidatabase systems. Distributed and Parallel Databases, 1(3):251-279, July 1993.

6. Madhavaram et al., 1996. M. Madhavaram, D. L. Ali, and Ming Zhou. Integrating heterogeneous distributed database systems. Computers & Industrial Engineering, 31 (l-2):315-318, October 1996.

7. Song et al., 1996. W. W. Song, P. Johannesson, and J. A. Bubenko Jr. Semantic similarity relations and computation in schema integration. Data & Knowledge Engineering, 19(l):65-97, May 1996.

8. Newcombe, 1988. Howard B. Newcombe. Handbook of record linkage: methods for health and statistical studies, administration, and business. Oxford University Press, 1988.

9. Hernandez and Stolfo, 1995. M. Hernandez and S. Stolfo. The merge/purge problem for large databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 127-138, May 1995.

10. Левенштейн, 1966. В.И. Левенштейн. Двоичные коды, обеспечивающие синхронизацию и исправление ошибок. Тезисы кратких научных сообщений Международного конгресса математиков, Секция 13, Москва, 1996, 24.

11. Ямпольский, 1973. М.И. Ямпольский, А.Е. Горбоносов. Поиск дублирующих документов. Научно-техническая информация, серия 1, №8, 1973.

12. Galil and Giancarlo, 1988. Z. Galil and R. Giancarlo. Data structures and algorithms for approximate string matching. Journal of Complexity, 4:33-72, 1988.

13. Chang and Lampe, 1992. W. I. Chang and J. Lampe. Theoretical and empirical comparisons of approximate string matching algorithms. In CPM: 3rd Symposium on Combinatorial Pattern Matching, pages 175-84, 1992.

14. Du and Chang, 1994. M.-W. Du and S. C. Chang. Approach to designing very fast approximate string matching algorithms. IEEE Transactions on Knowledge and Data Engineering, 6(4):620-633, August 1994.

15. Smith and Waterman, 1981. T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147:195-197, 1981.