Введение
1. Идентификация объектов в базах данных 10
1.1. Направления развития современных баз данных 10
1.2. Модели данных для интеграции баз данных 12
1.2.1. Реляционная модель данных и ограничения целостности 15
1.2.2. Операции реляционной математики 16
1.3. Расстояние между строками 19
1.3.1. Способы определения расстояния 19
1.3.2. Алгоритмы вычисления расстояния Левенштейна . 20
1.4. Методы поиска строк по сходству 23
1.5. Средства обработки текстовых данных 27
1.6. Постановка цели и задач исследования 30
2. Нестрогие реляционные операции 32
2.1. Введение 32
2.2. Построение морфизма алгебраических систем 33
2.3. Нестрогие реляционные операции 37
2.3.1. Нестрогие алгебраические выражения 37
2.3.2. Свойства нестрогих реляционных операций 39
2.4. Алгоритм выполнения операции нестрогого соединения на основе хэширования по сигнатуре 41
2.4.1. Применение хеширования по сигнатуре к задаче нестрогого соединения 41
2.4.2. Объем промежуточной таблицы 44
2.4.3. Определение оптимальной хеш-функции 45
2.4.4. Анализ эффективности метода хеширования по сигнатуре 47
2.5. Алгоритм выполнения операции нестрогого соединения на основе trie-деревьев 48
2.5.1. Соединение на основе trie-деревьев 48
2.5.2. Анализ вычислительной сложности алгоритма нестрогого соединения 51
2.5.3. Анализ вычислительной сложности алгоритма построения trie-дерева 55
2.6. Анализ количества ошибок 56
2.6.1. Связь расстояния между строками с вероятностью появления ошибки 56
2.6.2. Количество ошибок первого рода 57
2.6.3. Количество ошибок второго рода 58
2.7. Заключение 61
3. Разработка библиотеки программ для реализации нестрогих операций 62
3.1. Введение 62
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
