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

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

ФЕДОРКОВА Галина Олеговна

РАЗРАБОТКА СПЕЦИАЛЬНОГО МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ ДЛЯ ОТОЖДЕСТВЛЕНИЯ ЗАПИСЕЙ В БАЗАХ ДАННЫХ НА ОСНОВЕ ОПЕРАЦИЙ НЕСТРОГОГО СООТВЕТСТВИЯ

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Воронеж 2005

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

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

доктор технических наук, профессор Погодаев Анатолий Кирьянович

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

доктор технических наук, профессор Кравец Олег Яковлевич кандидат технических наук Недикова Татьяна Николаевна

Ведущая организация:

Институт проблем управления имени В.А. Трапезникова РАН, г. Москва.

Защита диссертации состоится «_30_» июня 2005 г. в 1200 часов в конференц-зале на заседании диссертационного совета Д 212.037.01 Воронежского государственного технического университета по адресу: 394026, г.Воронеж, Московский проспект, 14.

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

Автореферат разослан 27 мая 2005 г.

Ученый секретарь диссертационного совета

Питолин В.М.

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

Актуальность темы. Обеспечение обмена данными между удаленными организациями требует установления соответствий распределенных отношений -множеств однотипных объектов баз данных (БД) и элементов этих множеств -отдельных объектов. В первом случае говорят об интеграции схем баз данных, во втором о построении процедур отождествления объектов БД.

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

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

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

Работа выполнения в соответствии с научным направлением ЛГТУ "Современные сложные системы управления".

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

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

- провести анализ методов и моделей, возникающих при интеграции объектов в базах данных;

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

- разработать программное обеспечение, реализующее специальные реляционные операции и дополняющее реляционные СУБД возможностями отождествления записей;

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

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

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

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

- операции нестрогого реляционного соединения, объединения и разности, отличающиеся использованием условия непревышения расстоянием Левенштейна заданного порогового значения, реализация которых позволяет снизить информационные потери, обусловленные наличием ошибок операторского ввода в ключевых полях;

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

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

- алгоритм выполнения нестрогих реляционных операций над таблицами большого объема, отличающийся применением в реляционных базах данных tгie-деревьев.

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

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

Реализация и внедрение результатов работы. Разработанный программный комплекс внедрен при модернизации информационных систем страховых обществ г. Липецка: 000 "Новолипецкая страховая компания", 000 СМК «Арго-Шанс».

Библиотека программ зарегистрирована в Государственном фонде алгоритмов и программ.

Результаты диссертационной работы используются в учебном процессе ЛГТУ при подготовке инженеров по специальности "Прикладная математика".

Апробация работы. Теоретические и практические результаты, полученные в процессе исследования, докладывались и обсуждались на XXXV Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 1997), П-й Республиканской электронной научной конференции «Современные проблемы информатизации» (Воронеж, 1997), Ш,УЬй Международных электронных научных конференциях «Современные проблемы информатизации» (Воронеж, 1998), Научно-технической студенческой конференции технических ВУЗов центральной России (Орел, 1999), У[,УШ-й Международных электронных научных конференциях «Современные проблемы информатизации в технике и технологиях» (Воронеж, 2001, 2003), Международной научно-практической конференции «Современные сложные системы управления CCCy/HTCS'2005» (Тула, 2005).

Положения работы поддержаны грантами по фундаментальным исследованиям:

- Министерством образования РФ - Г00 4.1-68 "Разработка теории оптимизации проектирования информационных систем";

- Российским фондом фундаментальных исследований - N03-01-96487 "Оптимизация схем баз данных и запросов на основе теории преобразований реляционных выражений", N 03-01-96487 "Формализация алгоритма оптимизации реляционных запросов" и N05-01-96402 "Совершенствование методологии проектирования информационных систем для управления производственными объектами".

Публикации. По материалам диссертационной работы опубликовано 18 работ, из них 10 без соавторов. В [4,5,8] автором предложен алгоритм построения конечных алгебр; в [7] разработан алгоритм синтеза тождеств; в [2,16,17] введена операция нестрогого реляционного соединения и предложена реализация введенной операции на основе хэширования по сигнатуре; в [18] предложен основанный на использовании tгie-деревьев алгоритм выполнения операции нестрогого соединения.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка из 121 наименования, приложений. Основная часть работы изложена на 117 страницах машинописного текста, содержит 19 рисунков и 11 таблиц.

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

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

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

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

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

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

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

Для построения всех пар записей, отвечающих условию строгого равенства значений поля, в СУБД существует специальная операция естественного соединения. Задача построения всех пар записей, отвечающих условию нестрогого равенства (допускает 1-2 опечатки), требует создания специальных операций нестрогого соединения, нестрогого объединения и нестрогой разности.

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

по порядку совпадает с размером словаря. В настоящее время отсутствуют СУБД, включающие в себя описанные операции.

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

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

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

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

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

Затем зависимость

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

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

Представим схему каждой базы данных в виде алгебраической модели следующим образом. Кортежи реляционной алгебры (РА) будем считать элементами основного множества алгебраической модели (АМ), отношения РА -унарными отношениями алгебраической модели. Элемент-кортеж принадлежит унарному отношению АМ-отношению БД, если это отношение содержит указанный кортеж. Кроме того, отношения БД, содержащие внешние ключи, будем считать (п+1)-арными отношениями АМ, где и — число внешних ключей.

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

ф: А -> В: Зфл и (а,.....а„) (ф(а,).....ф(ап)) еЯвсВ".

Требуется найти такое соответствие, которое отождествляет «похожие» кортежи и при этом является морфизмом. Таким образом, задача сводится к алгебраической проблеме, близкой к проблеме нахождения изоморфных алгебраических систем. Она решается в три этапа:

1) для обеих БД выполняется построение алгебраических моделей, как это было описано выше;

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

3) находятся вложенные в него в теоретико-множественном смысле соответствия, сохраняющие отношения алгебраической модели.

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

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

где - расстояние между строковыми значениями Я. а и 5". а,

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

По аналогии с нестрогим соединением, введем операцию нестрогой разности (-) как отношения, составленного из всех кортежей отношения Я, для

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

и пара операций нестрогого объединенияп -левое (Ц*) И Правое (О'):

ди'я^лиоя-д); лО^сд-язия. (3)

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

= Л — (Л — 5), так что введение нестрогой разности порождает и пару операций нестрогого пересечения, левую

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

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

= Л0Г5 = 50'Л. (6)

Эти свойства полезны для работы с введенными нестрогими операциями, поскольку позволяют не обращаться каждый раз к громоздким формулам (1)-(5). В СУБД алгебраические законы необходимы для работы преобразователей выражений, используемых в оптимизаторах запросов. Разработки собственных преобразователей выражений и оптимизаторов запросов при реализации предложенных нестрогих реляционных операций можно избежать, поскольку любое выражение, использующее нестрогие реляционные операции, может быть записано как обыкновенное выражение реляционной алгебры.

Для вычисления расстояния между строками был выбран алгоритм Укконена, хорошо работающий в случае, если расстояние между строками мало (или если нужно только проверить условие В этом

алгоритме на основе метода динамического программирования последовательно находится расстояние между подстроками а и Ъ увеличивающихся длин / и} соответственно:

= тт{ </,чу + н<а,, е),

где И^а,Р) - стоимость замены символа а на с ^, И-

стоимости вставки и удаления. При этом рассматриваются не все элементы

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

(8)

где квадратные скобки обозначают целую часть числа, У>тт - минимально возможное значение функции У).

Чтобы выбрать согласно (1) из всех пар записей таблиц объемами Ми N близкие, потребуется вызвать функцию вычисления расстояния M-N раз. Проблема заключается в том, что время выполнения такого количества проверок слишком велико. Таким образом, требуется разработка более быстрых алгоритмов выполнения нестрогого соединения.

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

Положим С<*> е {0;1} равным единице для таких пар и нулю - в противном случае.

Пусть т/ (П)) - количество записей Я (5), хэш-функция значения а для которых равна / (/). Тогда вместо прямого произведения объемом

достаточно проверить только пар,

(=1 М

2*

I

М

■г 2*

Л^ ' ^ МЫ — У, У, 1ЩП, (к - количество бит в значении хэш-функции).

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

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

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

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

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

В целом, хэширование по сигнатуре позволяет только уменьшить количество проверок, оставляя сложность алгоритма равной

Поиск по сходству одного термина в словаре может быть осуществлен при помощи trie-дерева более эффективно. Именно, значения первых q столбцов таблиц d,j при вычислении расстояния совпадают у терминов, имеющих одинаковые первые q символов. Обход дерева в глубину позволяет сохранять вычисленную часть таблицы, а не вычислять ее заново для каждого слова.

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

m^diq>hAtBm.dpj>h=>dma>h. (9)

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

Оценка временной сложности алгоритма, не использующего условие (9), для двух таблиц одинакового объема N составляет вместо при

последовательной проверке всех пар записей (/-длина строкового значения). При использовании условия (9) время работы алгоритма будет составлять где

D - объем результата выполнения операции нестрогого соединения. В практически важных случаях D имеет порядок не более ®{hN).

Время построения trie-дерева в оперативной памяти оценивается как ®{N), при использовании вспомогательного запоминающего устройства для более точной оценки можно использовать

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

Обозначим Pj — вероятность того, что при отождествлении записей, принадлежащих нестрогому соединению с заданным значением h, пара описывающих один объект записей не будет отождествлена (ошибка первого рода). Это есть вероятность того, что при вводе некоторого слова длины п будет сделано больше, чем h ошибок. В главе показано, что величина Pj стремится к

нулю при

Рис. 2. Алгоритм выполнения нестрогого соединения на основе trie-деревьев

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

Таблица. Значения Р(к), полученные моделированием операторского ввода строк длиной 20 символов с вероятностью ошибки q в одном символе.

ь Ч

0.01 0.005 0.001 0.0005 0.0001

0 0.1790 0.1080 0.0383 0.0192 0.0199

1 0.0182 0.0059 0.0008 0.0002 0.0001

2 0.0014 0.0001 0.0000 0.0000 0.0000

3 0.0001 0.0000 0.0000 0.0000 0.0000

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

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

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

ошибочных сопоставлений в Я X Я в расчете на одну запись Я (10):

|Л><Д|

Рп(Ь)=1--Ш-

(10)

На рисунке 3 приведены оценки Рц для поля ФИО при различных к для разного объема словаря. Можно видеть, что вероятность ошибки второго рода зависит от порогового значения к, и зависимость имеет S-образную форму. Таким образом, можно сделать вывод, что значение к следует выбирать, руководствуясь оценкой для

Рис. 3. Оценка вероятности ошибки 2-го рода от порогового значения к при разном объеме словаря

Выбор функции стоимости операций редактирования представляется разумным назначать исходя из соотношения (11):

w{a,P) = -]n(p(cc,P)), (И)

где р(а,/3) - вероятность замены при вводе символа а символом Р. Другой подход заключается в минимизации оценки величины Рц.

Таким образом, разработаны нестрогие реляционные операции, позволяющие выполнять отождествление записей БД и разработан алгоритм на основе trie-деревьев, позволяющий выполнить операцию нестрогого соединения таблиц за время, пропорциональное мощности результата, проведен анализ и предложены рекомендации по выбору параметров

Третья глава посвящена разработке программного обеспечения, реализующего специальные реляционные операции и дополняющего СУБД возможностями отождествления записей. Эта разработка предназначена для выполнения нестрогих реляционных операций под управлением СУБД Oracle версий 8.* по условию близости строковых значений атрибутов.

Основу интерфейса пользователя с библиотекой программ представляет функция к результату выполнения которой можно обращаться как к

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

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

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

Функции, взаимодействующие с СУБД и вызываемые пользователем посредством обращения к СУБД, реализованы на процедурном языке PL/SQL, или объявлены как внешние функции. Основу интерфейса пользователя с библиотекой программ предоставляют процедура

Процедура производит построение индекса на основе trie-

дерева для указанного поля таблицы. Она создает запись в таблице trie_idx, содержащую BLOB-поле для хранения индекса, и вызывает написанную на языке С функцию c_build_idx.

Функция реализует операцию нестрогого реляционного соединения.

Она возвращает таблицу, состоящую из двух полей а и b. В поле а находятся ROWID записей таблицы 1, в поле b - таблицы 2. Кортежи соответствуют парам близких записей. Функция проверяет наличие индексов для одного и другого поля, вызывает процедуру и затем повторяет в цикле вызов функции

cj>et_next_pair.

Работа со сложными структурами данных, такими как деревья, более эффективно реализуется на алгоритмических языках (например, на языке С), чем на процедурных языках СУБД (таких, как PL/SQL). Поэтому внешние функции, выполняющие основные действия по работе с trie-деревьями, реализованы на языке С.

В С-библиотеке внешних функций определены структуры данных для работы с trie-деревом, структуры для хранения индекса. Функции библиотеки решают следующие задачи:

- получение данных из БД и сохранение данных в БД;

- операции над trie-деревом (добавление и удаление вершин, проверка условий);

- построение индекса;

- нестрогое соединение.

Структура библиотеки программ приведена на рисунке 4.

Рис. 4. Структура библиотеки программ

Для выполнения операции нестрогого соединения RXS, где отношение R

представлено в БД таблицей tablel, S -таблицей table2, соединение производится по полю str, h - некоторое число, следует выполнить следующий запрос:

SELECT tablel.*, table2.* FROM tablel, table2, (SELECT * FROM THE (

SELECT CAST( nsjoin(h,'tablel','stf, ,table2','strl) AS rowid_pair_table_type) FROMduaI))j WHERE tablel.ROWID = j a AND table2.ROWID = j b.

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

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

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

Задача отождествления хранимых объектов в распределенной базе данных возникает при обмене данными между географически удаленными организациями. Страховые медицинские компании (СМК) получают от лечебно-профилактических учреждений (ЛПУ) данные по оказанным медицинским услугам (реестр ЛПУ) в формате, определяемом областным фондом обязательного медицинского страхования (ОФОМС). Формат различается для разных типов ЛПУ и даже для отдельных ЛПУ. Страховая компания сверяет данные реестра с собственной базой застрахованных, то есть проверяет, что указанный пациент застрахован.

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

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

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

реляционных операций. Анализ показал, что время построения tгie-дерева согласуется с приведенной в главе 2 оценкой (см. рис. 6) и имеет место линейная зависимость времени выполнения операции нестрогого соединения от объема результирующего отношения (см. рис. 7).

40000 50000 60000 Количество записей п, шт

Рис. 6. Время построения tгie-дерева для поля ФИО в зависимости от объема таблицы

Рис. 7. Зависимость времени выполнения нестрогого соединения от объема результирующего отношения

Приложение, внедренное в деятельность страховых обществ г. Липецка ООО "ИСК" и 00 0 СМК "Арго-Шанс", использует операцию нестрогого

реляционного соединения для отождествления записей реестров лечебно-профилактических учреждений (ЛПУ) с записями в БД застрахованных лиц.

На рисунке 8 приведены доли записей реестров ЛПУ за 2003 г., имеющих строгое, нестрогое, или не имеющих соответствия в базе данных ООО «НСК». Применение реализации введенных нестрогих реляционных операций позволило увеличить количество принятых записей и уменьшить количество отвергнутых: помимо записей, имеющих строгое соответствие, начали приниматься записи с нестрогим.

стоматологии

поликлиники

стационары

1 41% нити 35%

1 12% ШШШЖШЩ 24%

1 46% ; НМ 14%

---1-1-

0%

20%

40%

60%

80%

100%

■ строгое соответствие И нестрогое соответствие □ соответствие отсутствует

Рис. 8. Соответствие записей реестров ЛПУ и БД ООО «НСК»

Таким образом, количество отброшенных записей при отождествлении с использованием операции нестрогого соединения сократилось в 2-5 раз, а количество отождествленных записей увеличилось на 30%-200%. Эффект от использования предложенных нестрогих операций тем выше, чем больше ошибок содержат исходные данные.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

5. Разработан алгоритм выполнения нестрогих реляционных операций над таблицами большого объема, использующий trie-деревья.

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

7. Разработана библиотека программ, реализующая операции нестрогого реляционного соединения, объединения, разности.

8. Разработан и внедрен в ООО "ИСК" и 0 0 0 СМК "Арго-Шанс" программный комплекс, осуществляющий отождествление записей застрахованных и пациентов лечебно-профилактических учреждений, в 2-5 раз сокративший количество обрабатываемых вручную данных за счет интеграции информационной системы и реализации разработанного специального математического обеспечения.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ

1. Федоркова Г. О. Комбинаторные алгоритмы генерирования тождеств и многообразий конечных алгебраических систем // Вестник молодых ученых, 2003. - № 2. - Серия «Прикладная математика и механика». С.59-66.

2. Погодаев А.К., Федоркова Г.О. Нестрогое соединение реляционных таблиц: хеширование по сигнатуре // Системы управления и информационные технологии, 2005, № 2(19). С.93-95.

3. Федоркова Г.О. Применение метода нечеткого поиска в операции соединения реляционных таблиц баз данных. Электронный журнал «Исследовано в России», 188, стр. 2002-2013,2004 г.

[http://zhumal.ape.relam.ru/articles/2004/188.pdi]

4. Блюмин С.Л., Иванова (Федоркова) Г.О. Компьютерная классификация группоидов // Тезисы докладов Всеросс. науч.-технич.конф., посвящ. 40-летию ЛГТУ. - Липецк, ЛГТУ, 1996. с.404-406.

5. Блюмин С.Л., Иванова (Федоркова) Г.О . Компьютерное генерирование группоидов // Современные проблемы информатизации: тез. докл. II Респ. электрон, науч. конф. - Воронеж: Изд-во Воронежского педуниверситета, 1997. С.121.

6. Иванова (Федоркова) Г.О. Применение рекуррентных алгоритмов к проблеме классификации алгебраических структур // Студент и научно-технический прогресс: математика. Материалы XXXV Междунар. науч. студенческой конференции, - Новосибирск, 1998. С.38-39.

7. Блюмин С.Л., Иванова (Федоркова) Г.О. Анализ и синтез тождеств в алгебрах произвольной сигнатуры на основе комбинаторных алгоритмов // Современные проблемы информатизации: тез. докл. III Междунар. электрон, науч. конф. - Воронеж: Изд-во Воронежского педуниверситета, 1998. С.122-123.

8. Блюмин С.Л., Иванова (Федоркова) Г.О. Алгоритм построения конечных алгебр // Современные проблемы информатизации: тез. докл. III Междунар. электрон, науч.конф. - Воронеж: Изд-во Воронежского педуниверситета, 1998. С.167-168.

9. Иванова (Федоркова) Г.О. Многообразия алгебраических систем // Региональная молодежная научн. и инженерная выставка «Шаг в будущее» -Центр России: Сборник тез. докл. С.3-4.

10. Иванова (Федоркова) Г.О. Тождества в алгебраических системах // Сборник тез. докл. Науч.-технич. студенческая конф. технич. ВУЗов Центральной России. - Орел, Россия. С. 173.

11. Иванова (Федоркова) Г.О. Подход к анализу тождеств и многообразий алгебраических систем // Вестник ЛГТУ-ЛЭГИ № 3(4), 1999. - С.201-204.}

12. Иванова (Федоркова) Г.О. Тождества произвольного вида // Вестник ЛГТУ-ЛЭГИ № 3(4), 1999. - С.205-209.

13. Иванова (Федоркова) Г.О. Конгруэнции алгебраических систем в задачах различения объектов при неполной информированности // Современные проблемы информатизации в технике и технологии: сб. трудов. Вып. 6. -Воронеж: ВЭПИ, 2001. с.66-67.

14. Иванова (Федоркова) Г.О. Открытый-замкнутый мир, внешнее соединение и семантика ER-модели // Современные проблемы информатизации в технике и технологии: сб. трудов. Вып. 8. - Воронеж: ЦЧКИ, 2003. с.42-43.

15. Иванова (Федоркова) Г.О. Операция нечеткого реляционного соединения для интеграции данных разнородных локально автономных БД // Современные проблемы информатизации в технике и технологии: сб. трудов. Вып. 8. - Воронеж: ЦЧКИ, 2003. с. 106-107.

16. Погодаев А.К., Федоркова Г.О. Нестрогое соединение таблиц в базах данных информационных систем // Теория и практика производства листового проката / Сб. науч. тр. - Липецк: ЛГТУ, 2005.4.2. С.170-176.

17. Погодаев А.К., Федоркова Г.О. Метод нестрогого соединения реляционных таблиц баз данных // Современные сложные системы управления CCCy/HTCS'2005: Сб. трудов международной научн.-практ. конф. - Тула: ТулГУ, 2005.Т.1.С.252-259.

18. Погодаев А.К., Федоркова Г.О. Библиотека программ «Нестрогое реляционное соединение». М.: ФАП ВНТИЦ, 2005. Per. № 50200500374 от

30.03.2005.

Подписано в печать й"- 0£2ОО5г. Формат 60 х 84 1/16. Бумага офсетная. Ризография. Печ.л. 1,0 Тираж 100 экз. Заказ № 409. Типография ЛГТУ 398600 Липецк, ул. Московская, 30

•I

Q

09 Ш 2»

1608

Введение

1. Идентификация объектов в базах данных

1.1. Направления развития современных баз данных.

1.2. Модели данных для интеграции баз данных.

1.2.1. Реляционная модель данных и ограничения целостности

-1.2.2. Операции реляционной математики.

1.3. Расстояние между строками.

1.3.1. Способы определения расстояния.

1.3.2. Алгоритмы вычисления расстояния Левенштейна

1.4. Методы поиска строк по сходству.

1.5. Средства обработки текстовых данных.

1.6. Постановка цели и задач исследования.

2. Нестрогие реляционные операции

2.1. Введение.

2.2. Построение морфизма алгебраических систем.

2.3. Нестрогие реляционные операции.

2.3.1. Нестрогие алгебраические выражения

2.3.2. Свойства нестрогих реляционных операций.

2.4. Алгоритм выполнения операции нестрогого соединения на основе хэширования по сигнатуре.

2.4.1. Применение хеширования по сигнатуре к задаче нестрогого соединения

2.4.2. Объем промежуточной таблицы.

2.4.3. Определение оптимальной хеш-функции.

2.4.4. Анализ эффективности метода хеширования по сигнатуре.

2.5. Алгоритм выполнения операции нестрогого соединения на основе trie-деревьев.

2.5.1. Соединение на основе trie-деревьев.

2.5.2. Анализ вычислительной сложности алгоритма нестрогого соединения

2.5.3. Анализ вычислительной сложности алгоритма построения trie-дерева

2.6. Анализ количества ошибок.

2.6.1. Связь расстояния между строками с вероятностью появления ошибки.

2.6.2. Количество ошибок первого рода

2.6.3. Количество ошибок второго рода

3.2. Структура программного обеспечения.63

3.3. Процедуры и функции для работы с системой управления базами данных.65

3.3.1. Типы данных.65

3.3.2. Процедуры и функции, доступные пользователю . 65

3.3.3. Закрытые процедуры и функции (доступные внутри пакета) .67

3.4. Библиотека внешних функций.67

3.4.1. Типы данных.67

3.4.2. Функции, отвечающие за загрузку и сохранение данных 72

3.4.3. Функции, отвечающие за работу с trie-деревом . 73

3.4.4. Функции, выполняющие построение индекса.75

3.4.5. Функции, выполняющие операцию нестрогого соединения.76

3.4.6. Диаграммы вызовов функций .78

3.5. Вызов функций нестрогих реляционных операций.78

3.5.1. Нестрогое соединение.78

3.5.2. Нестрогая разность.81

3.5.3. Нестрогое объединение.81

3.6. Заключение.82

4. Практическое применение алгоритмов отождествления записей баз данных 83

4.1. Введение.83

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

4.3. Анализ быстродействия выполнения основных функций библиотеки.87

4.3.1. Время выполнения операции нестрогого соединения . 87

4.3.2. Время построения индекса.89

4.4. Отождествление записей баз данных страховой компании и лечебно-профилактических учреждений.91

4.4.1. Используемые таблицы.91

4.4.2. Примеры применения операции нестрогого соединения 93

4.4.3. Эффективность процедуры отождествления записей . 98

4.5. Заключение.100

Заключение 101

Список литературных источников 103

ВВЕДЕНИЕ

Актуальность темы. Обеспечение обмена данными между удаленными организациями требует установления соответствий распределенных отношений - множеств однотипных объектов баз данных (БД) и элементов этих множеств - отдельных объектов. В первом случае говорят об интеграции схем баз данных, во втором о построении процедур отождествления объектов БД.

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

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

Работа выполнения в соответствии с научным направлением ЛГТУ "Современные сложные системы управления".

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

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

- провести анализ методов и моделей, возникающих при интеграции объектов в базах данных;

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

- разработать программное обеспечение, реализующее специальные реляционные операции и дополняющее реляционные СУБД возможностями отождествления записей;

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

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

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

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

- операции нестрогого реляционного соединения, объединения и разности, отличающиеся использованием условия непревышения расстоянием Левенштейна заданного порогового значения, реализация которых позволяет снизить информационные потери, обусловленные наличием ошибок операторского ввода в ключевых полях;

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

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

- алгоритм выполнения нестрогих реляционных операций над таблицами большого объема, отличающийся применением в реляционных базах данных trie-деревьев.

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

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

Реализация и внедрение результатов работы. Разработанный программный комплекс внедрен при модернизации информационных систем страховых обществ г. Липецка: ООО "Новолипецкая страховая компания", ООО СМК "Арго-Шанс".

Результаты диссертационной работы используются в учебном процессе ЛГТУ при подготовке инженеров по специальности "Прикладная математика".

Апробация работы. Теоретические и практические результаты, полученные в процессе исследования, докладывались и обсуждались на XXXV Международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибирск, 1997), П-й Республиканской электронной научной конференции "Современные проблемы информатизации" (Воронеж, 1997), Ш,У1-й Международных электронных научных конференциях "Современные проблемы информатизации" (Воронеж, 1998), Научно-технической студенческой конференции технических ВУЗов центральной России (Орел, 1999), VI,VIII-ft Международных электронных научных конференциях "Современные проблемы информатизации в технике и технологиях" (Воронеж, 2001, 2003), Международной научно-практической конференции "Современные сложные системы управления CCCy/HTCS'2005" (Тула, 2005).

Положения работы поддержаны грантами по фундаментальным исследованиям:

- Министерством образования РФ - Г00 4.1-68 "Разработка теории оптимизации проектирования информационных систем";

- Российским фондом фундаментальных исследований - N 03-01-96487 "Оптимизация схем баз данных и запросов на основе теории преобразований реляционных выражений", N 03-01-96487 "Формализация алгоритма оптимизации реляционных запросов" и N 05-01-96402 "Совершенствование методологии проектирования информационных систем для управления производственными объектами".

Публикации. По материалам диссертационной работы опубликовано 18 работ, из них 10 без соавторов. В [7, 9, 10] автором предложен алгоритм построения конечных алгебр; в [8] разработан алгоритм синтеза тождеств; в [54, 55, 56] введена операция нестрогого реляционного соединения и предложена реализация введенной операции на основе хэширования по сигнатуре; в [57] предложен основанный на использовании trie-деревьев алгоритм выполнения операции нестрогого соединения.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка из 121 наименования, приложений. Основная часть работы изложена на 117 страницах машинописного текста, содержит 19 рисунков и 11 таблиц.

ЗАКЛЮЧЕНИЕ

В ходе исследования были получены следующие результаты:

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

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

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

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

5. Разработан алгоритм выполнения нестрогих реляционных операций над таблицами большого объема, использующий trie-деревья.

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

7. Разработана библиотека программ, реализующая операции нестрогого реляционного соединения, объединения, разности.

8. Разработан и внедрен в ООО "НСК"и ООО СМК "Арго-Шанс"программный комплекс, осуществляющий отождествление записей застрахованных и пациентов лечебно-профилактических учреждений, в 2-5 раз сокративший количество обрабатываемых вручную данных за счет интеграции информационной системы и реализации разработанного специального математического обеспечения.

1. Алгоритмы. Методы. Исходники http://algolist.manual.ru/.

2. Арсеньев Б. П. Интеграция распределенных баз данных / Арсеньев Б. П., Яковлев С. А. М.: Лань, 2001. - 464 с.

3. Аткинсон М. Манифест систем объектно-ориентированных баз данных / Аткинсон М., Бансилон Ф., ДеВитт Д., Диттрих К., Майер Д., Здоник С. Ц Системы управления базами данных. 1995. - N 04.

4. Ахо А. Структуры данных и алгоритмы / Ахо А., Хопкрофт Дж., Ульман Дж. М.: Диалектика, 2000. - 384 с.

5. Банди Б. Основы линейного программирования. М.: Радио и связь, 1989. - 176 с.

6. Белкин П.Ю. Есть ли цена у опечатки? // Вопросы интернет-образования. N 12.http://vio.fio.ru/vio12/cdsite/Articles/art25.htm.

7. Иванова Г. О. Алгоритм построения конечных алгебр / Блюмин С. Л., Иванова Г. О. // Современные проблемы информатизации: тез. докл. III Междунар. электрон, науч.конф. 1998. - С. 167-168.

8. Иванова Г. О. Анализ и синтез тождеств в алгебрах произвольной сигнатуры на основе комбинаторных алгоритмов / Блюмин С. Л., Иванова Г. О. // Современные проблемы информатизации: тез. докл. III Междунар. электрон, науч.конф. 1998. - С. 122-123.

9. Иванова Г. О. Компьютерное генерирование группоидов / Блюмин С.

10. JI., Иванова Г. О. // Современные проблемы информатизации: тез. докл. II Респ. электрон, науч.конф. 1997. - С. 121.

11. Иванова Г. О. Компьютерная классификация группоидов / Блюмин С. Л., Иванова Г. О. // Тезисы докладов Всеросс. науч.-технич.конф., посвящ. 40-летию ЛГТУ. 1996. - С. 404-406.

12. Бойцов Л. М. Использование хеширования по сигнатуре для поиска по сходству // Прикладная математика и информатика. 2000.- N 7.

13. Бойцов Л. М. Поиск по сходству в документальных базах данных: хеширование по сигнатуре оптимальное соотношение скорости поиска, простоты реализации и объема индексного файла. // Программист. - 2001. - N 1.

14. Брюхов Д. О. Интероперабельные информационные системы: архитектуры и технологии / Брюхов Д. О., Задорожный В. И., Калиниченко Л. А., Курошев М. Ю., Шумилов С. С. // Системы Управления Базами Данных. 1995. - N 4. - С. 96-113.

15. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский Диалект, 2001. - 352 с.

16. Грахам А. Стефан. Анализ строк. перевод М.С.Галкиной, под ред. П.Н.Дубнера. - 1992. - 100 с.http://masters.donntu.edu.ua/2002/fvti/ vasylenko/diss/lib/alg.zip.

17. Гринев M. Н. UQL: язык запросов к интегрированным данным в терминах UML / Гринев М. Н., Кузнецов С. Д. // Программирование. 2002. - N 4. - С. 9-19.

18. Дейт К. Дж. Введение в системы баз данных, 7-е издание. Пер. с англ. - М.: Издательский дом Вильяме, 2001. - 1072 с.

19. Ермаков А. Е. Полнотекстовый поиск: проблемы и их решение // Мир ПК. 2001. - N 05.

20. Запрос совпадающих и наиболее близких строк // Рассылка в рамках проекта "Открыто об Oracle". Выпуск 72.http://ln.com.ua/~openxs/projects/oracle/ora072.html.

21. Зильбершац А. Стратегические направления в системах баз данных / Зильбершац А., Здоник С. // Системы управления базами данных. -1997. N 04.

22. Зиндер Е. 3. Проектирование баз данных: новые требования, новые подходы // Системы управления базами данных. 1996. • N 3. • С. 10-22.

23. Зыкин С. В. Соответствие состояний реализации исходной и целевой моделей данных // Материалы конф., посвященной 90-летию со дня рождения А. А. Ляпунова. 2001. - 6 с.

24. Иванова Г. О. Конгруэнции алгебраических систем в задачах различения объектов при неполной информированности // Современные проблемы информатизации в технике и технологии: сб. трудов. Вып. 6. 2001. - С. 66-67.

25. Иванова Г. О. Многообразия алгебраических систем // Региональная молодежная научн. и инженерная выставка "Шаг в будущее" Центр России: Сборник тез. докл. - 1999. - С. 3-4.

26. Иванова Г. О. Операция нечеткого реляционного соединения для интеграции данных разнородных локально автономных БД // Современные проблемы информатизации в технике и технологии: сб. трудов. Вып. 8. 2003. - С. 106-107.

27. Иванова Г. О. Открытый-замкнутый мир, внешнее соединение и семантика ER-модели // Современные проблемы информатизации в технике и технологии: сб. трудов. Вып. 8. 2003. - С. 42-43.

28. Иванова Г. О. Подход к анализу тождеств и многообразий алгебраических систем // Вестник ЛГТУ-ЛЭГИ. 1999. - N 3(4). -с. 201-204.

29. Иванова Г. О. Применение рекуррентных алгоритмов к проблеме классификации алгебраических структур // Студент и научно-технический прогресс: математика. Материалы XXXV Междунар. науч. студенческой конференции. 1998. - С. 38-39.

30. Иванова Г. О. Тождества в алгебраических системах // Сборник тез. докл. Науч.-технич. студенческая конф. технич. ВУЗов Центральной России. 1999. - С. 173.

31. Иванова Г. О. Тождества произвольного вида // Вестник ЛГТУ-ЛЭГИ.- 1999. N 3(4) . - с. 205-209.

32. Калиниченко Л. А. Методы и средства интеграции неоднородных баз данных. М.: Наука, 1983. - 423 с.

33. Калиниченко Л. А. Десять Лет Московской Секции ACM SIG-MOD / Калиниченко Л. А., Когаловский М. Р., Кузнецов С. Д. // Программирование. 2002. - N 6.

34. Кнут Д. Искусство программирования (3 тома). М.: Вильяме, 2000.- 2472 с.

35. Кодд Е. Ф. Реляционная модель данных для больших совместно используемых банков данных // Системы управления базами данных.- 1995. N 1. - С. 145-160.

36. Когаловский М. Р. Абстракции и модели в системах баз данных // Системы управления базами данных. 1998. - N 04-05. - С. 73-81.

37. Когаловский М. Р. Очерк отечественной истории технологий баз данных (отрывок из книги "Энциклопедия технологий баз данных") // Открытые системы. 2002. - N 1.

38. Кодд Э. Ф. Расширение реляционной модели для лучшего отражения семантики // Системы управления базами данных. 1996. - N 5. -С. 163-192.

39. Системы баз данных третьего поколения: Манифест / Комитет по развитию функциональных возможностей СУБД // Системы управления базами данных. 1995. - N 2. - С. 143-159.

40. Концепция информатизации здравоохранения липецкой области на 2004-2010 годы. Приложение N 1 к распоряжению администрации Липецкой области от 12 апреля 2004 г. N 288-р.

41. Кормен Т. Алгоритмы: построение и анализ / Кормен Т., Лейзерсон Ч., Ривест Р. М.: МЦНМО, 2001. - 960 с.

42. Коровин С. Е. Моделирование семантики и прагматики документа в нотации языка XML / Коровин С. Е., Мельников А. В., Кафтанников И. Л. // Известия Челябинского научного центра. 2002. - вып. 3(16).- С. 9-13.

43. Крёнке Д. Теория и практика построения баз данных, 8-е изд. СПб.: Питер, 2003. - 800 с.

44. Кузнецов С. Д. Введение в информационные системы // Системы управления базами данных. 1997. - N 02.

45. Кузнецов С. Д. Направления исследований в области управления базами данных: краткий обзор // Системы управления базами данных.- 1995. N 1.

46. Кузнецов С. Д. Основы современных баз данных // Информационно-аналитические материалы Центра информационных технологий, http: / /www. citforum, ru/ .

47. Мальцев А. И. Алгебраические системы. М.: Наука, 1970. - 392 с.

48. Максимов В. Алгоритмы поиска, или "Как искать неизвестно что" // Монитор. -1995. N 6.

49. Марчук А. Г. К вопросу об идентификации электронных документов и коллекций / Марчук А. Г., Осипов А. Е. // Программирование. -2000. N 3. - С. 53-62.

50. Мейер Д. Теория реляционных баз данных. Пер. с англ. М. К. Валиева и др.; - М.: Мир, 1987. - 608 с.

51. Мюллер Р. Дж. Базы данных и UML. М.: Лори, 2002. - 420 с.

52. Плоткин Б. И. Универсальная алгебра, алгебраическая логика и базы данных. М.: Наука, 1991. - 446с.

53. Федоркова Г. О. Метод нестрогого соединения реляционных таблиц баз данных / Погодаев А. К., Федоркова Г. О. // Современные сложные системы управления CCCy/HTCS'2005: Сб. трудов международной научн.-практ.конф. 2005. - Т.1. - С. 252-259.

54. Федоркова Г. О. Нестрогое соединение реляционных таблиц: хеширование по сигнатуре / Погодаев А. К., Федоркова Г. О. // Системы управления и информационные технологии. 2005. - N 2(19).- С. 93-95

55. Федоркова Г. О. Нестрогое соединение таблиц в базах данных информационных систем / Погодаев А. К., Федоркова Г. О. // Теория и практика производства листового проката: Сб. науч. тр. 4.2. 2005.- С. 170-176.

56. Погодаев А. К., Федоркова Г. О. Программный комплекс "Нестрогое реляционное соединение". М.: ФАП ВНТИЦ, 2005. Per. N 50200500374 от 30.03.2005.

57. Послед Б. С. Borland С++ Builder 6. Разработка приложений баз данных. М.: ДиаСофтЮП, 2003. - 320 с.

58. Пржиялковский В. В. Абстракции в проектировании баз данных // Системы управления базами данных. 1998. - N 1-2. - С. 90-97

59. Про SELECT из хранимой процедуры // Рассылка в рамках проекта "Открыто об Oracle". Выпуск 11.http://In.com.ua/~openxs/projects/oracle/oraOll.html.

60. Программа исследований в области баз данных на следующее десятилетие / Асиломарский отчет о направлениях исследований в области баз данных // Открытые системы. 1999. - N 01.

61. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Рутковская Д., Пилиньский М., Рутковский JI. Изд-во: Горячая линия-Телеком, Радио и связь, 2004. - 452 с.

62. Тони Стаблибайн Регулярные выражения. Карманный справочник. -Питер, 2004. 160 с.

63. Бьерн Страуструп Язык программирования С++. Специальное издание. Невский Диалект, 2004. - 1104 с.

64. Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 1983. - 334 с.

65. Федоркова Г. О. Комбинаторные алгоритмы генерирования тождеств и многообразий конечных алгебраических систем // Вестник молодых ученых. Серия "Прикладная математика и механика". 2003. - N 2. -С. 59-66.

66. Федоркова Г. О. Применение метода нечеткого поиска в операции соединения реляционных таблиц баз данных. Электронный журнал "Исследовано в России", 188, стр. 2002-2013, 2004 г. http://zhurnal.аре.relarn.ru/articles/2004/188.pdf

67. Ходоровский В. В. К вопросу нормализации отношений в реляционных базах данных // Программирование. 2002. - N 1. - С. 55-71.

68. Цаленко М. Ш. Моделирование семантики в базах данных. М.: Наука, 1989. - 287 с.

69. Цаленко М. Ш. Реляционная модель данных с оценками в гейтинговых алгебрах // Программирование. 1995. - N 2. - С. 3-8.

70. Чен, Питер Пин-Шен Модель "сущность-связь" — шаг к единому представлению данных // Системы управления базами данных. 1995.- N 3. С. 137-158.

71. Шилд Г. Программирование на BORLAND С++ для профессионалов.- Пер. с англ. М.: ООО "Попурри", 1998. - 800 с.

72. Aho А. V., Beeri С., Ulman J. D. The Theory of Joins in Relational Databases // ACM Transactions on Database Systems, 4(3), 1979.

73. Atkinson M., Francois Bancilhon F., et al. The Object-Oriented Database System Manifesto // Proceedings of the First International Conferenceon Deductive and Object-Oriented Databases. Kyoto, Japan, 1989, pp. 223-240.

74. Baeza-Yates, R. and Navarro, G. A practical q-Gram Index for Text Retrieval Allowing Errors // CLEI Electronic Journal, 1(2), 1998.

75. Baeza-Yates, R. and Navarro, G. Faster Approximate String Matching // Algorithmica 23 (2), 1999, p. 127-158.

76. Baeza-Yates, R. and Soza-Pollman, H. Analysis of Linear Hashing Revisited // Nordic Journal on Computing 5, 1998, p. 70-85.

77. Bagai R., Orgun M. A. A Temporal Paraconsistent Relational Algebra for Incomplete and Inconsistent Information // Proceedings of the 33rd Annual ACM Southeast Conference, 1995, pp.240-248.

78. A. P. Berman A new data structure for fast approximate matching // Technical Report 1994-03-02. Department of Computer Science, University of Washington. March, 1994.

79. D. Chamberlin, J. Robie, and D. Florescu Quilt: An XML Query Language for Heterogeneous Data Sources // Lecture Notes in Computer Science, Springer-Verlag, 2000. http://www.almaden.ibm.com/cs/people/chamberlin/ quiltilncs.pdf.

80. Chen P. P-S. The Entity-Relationship Model — Toward a Unified View of Data // ACM Transactions on Database Systems, 1(1), 1976. p.9-36.

81. Chen P.P.S. A Preliminary Framework for Entity-Relationship Models // Entity-Relationship Approach to Information Modeling and Analysis, Saugus, Calif., 1981.

82. Codd E. F. A Relation Model of Data for Large Shared Data Banks // Comm. ACM 13, 6, ACM, New York, London, Amsterdam, June 1970. P. 377-387.

83. Codd E. F. Does Your DBMS Run By the Rules? // ComputerWorld, Oct 21, 1985.

84. Codd E. F. Further Normalization of the Data Base Relational Model // Courant Computer Sci. Symposia (vol. 6: "Data-Base System"), ed. by R. Rustin, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1972.

85. Codd, E. F. Extending the Relational Database Model to Capture More Meaning // IBM Research Report RJ2599 (August 6th, 1979). Republished in ACM Transactions on Database Systems 4(4), December 1979.

86. Codd E. F. Is Your DBMS Really Relational? // ComputerWorld, Oct 14, 1985.

87. Codd, E. F. The Relational Model for Database Management Version 2. Reading, Mass.: Addison-Wesley, 1990.

88. Cohen, William W. Integration od Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity // Proc. ACM Sigmod-98, ACM Press, New York, 1998, pp. 201-212.

89. Cohen, William W., Hirsh, Haym Joins that Generalize: Text Classification Using WHIRL // In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, August, 1998.

90. Date, C.J. The Extended Relational Model RM/T // In C.J.Date, Relational Database Writings 1991-1994. Reading, Mass.: Addison-Wesley, 1995.

91. Darwen H., Date С. J. The Third Manifesto // SIGMOD Record, Vol. 24, No. 1, March 1995. pp.39-49.

92. Date, C.J. and Hugh Darwen A Guide to the SQL Standard (4th edition) // Reading, Mass.: Addison-Wesley, 1997.

93. Date. C. J. Thirty years of relational: Extending the Relational Model // Intelligent Enterprise, June 1, 1999, Volume 2, Number 8.

94. Date, C. J. What is a Distributed Database System // Date C. J. Relational Database writings 1985-1989. — Reading, Mass.: Addison-Wesley, 1990.

95. Date C. J. When's an extension not an extension? // Intelligent Enterprise, June 1, 1999, Volume 2, Number 8

96. Dayal, U., Goodman N., Kata R.H. An Extended Relational Algebra with Control Over Duplicate Elimination // Proc. ACM PODS 1982.

97. Debabrata Dey, Sumit Sarkar A Probabilistic Relational Model and Algebra // ACM Trans. Database Syst. 21(3), 1996. p.339-369.

98. Fundamental Algorithms for a declarative Pattern matching, Stefan Kurtz. Ph. D. Thesis.

99. J. Galindo, J. M. Medina, M. Carmen Garrido Fuzzy Division in Fuzzy Relational Databases. An Approach // Fuzzy Sets and Systems, Volume 121, Number 3, 1 August 2001. P. 471-490.

100. Janifer Gatenby Internet, Interoperability and Standards Filling the Gaps // National Information Standards Organization, August 23, 2000. Available: http://www.niso.org/press/whitepapers/Gatenby.html

101. Farshad Hakimpour, Andreas Geppert Resolving Semantic Heterogeneity in Schema Integration: an Ontology Based Approach // International Conference on Formal Ontology in Information Systems (FOIS-2001), pp. 297-308, ACM press.

102. L. Kalinichenko, M. Kogalovsky, S. Kuznetsov and B. Novikov. Database Research Activities in Russia: a Brief Overview. // Proc. of the ADBIS-DASFAA Symposium, 234-245, Prague, Chech, September 2000.

103. Kent, William Solving Domain Mismatch and Schema Mismatch Problems with an Object-Oriented Database Programming Language // 17th International Conference on Very Large Data Bases, 1991, p. 147 160.

104. MySQL Documentation http://www.mysql.com/documentation/.

105. Oracle Documentation http://docs.oracle.com/.

106. PHP documentation http://www.php.net/docs.php/.

107. PostgreSQL: Documentation http://www.postgresql.org/docs/.

108. H. Shang & Т. H. Merrett Tries for Approximate String Matching // IEEE Trans, on Knowledge and Data Engineering, special issue on Digital Libraries, Nabil R. Adam, ed., 8 4(August, 1996) pp. 540-547.

109. Snodgrass R.T. The Temporal Query Language TSQL2 // Dortrecht, Netherlands: Kluwer Academic Pub., 1995.

110. SQL Server 2000 Books Online (Updated 2004) http://www.microsoft.com/sql/I

111. ISO/IEC 9075:1992 "Database Language SQL"

112. ISO/IEC 9075:1999 "Database Language SQL"