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

• Автор: Федоркова, Галина Олеговна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Липецк
• Количество страниц: 158 с.

ОГЛАВЛЕНИЕ
Введение

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. Алгоритм выполнения операции нестрогого соединения на основе Ыедеревьев.
2.5.1. Соединение на основе Ыедеревьев.
2.5.2. Анализ вычислительной сложности алгоритма нестрогого соединения .
2.5.3. Анализ вычислительной сложности алгоритма построения Ыедерева .
2.6. Анализ количества ошибок.
2.6.1. Связь расстояния между строками с вероятностью появления ошибки
2.6.2. Количество ошибок первого рода.
2.6.3. Количество ошибок второго рода
2.7. Заключение
3. Разработка библиотеки программ для реализации нестрогих операций
3.1. Введение.
3.2. Структура программного обеспечения.
3.3. Процедуры и функции для работы с системой управления базами данных
3.3.1. Типы данных
3.3.2. Процедуры и функции, доступные пользователю .
3.3.3. Закрытые процедуры и функции доступные внутри пакета.
3.4. Библиотека внешних функций.
3.4.1. Типы данных
3.4.2. Функции, отвечающие за загрузку и сохранение данных
3.4.3. Функции, отвечающие за работу с Ыедеревом
3.4.4. Функции, выполняющие построение индекса
3.4.5. Функции, выполняющие операцию нестрогого соединения.
3.4.6. Диаграммы вызовов функций
3.5. Вызов функций нестрогих реляционных операций.
3.5.1. Нестрогое соединение.
3.5.2. Нестрогая разность.
3.5.3. Нестрогое объединение
3.6. Заключение.
4. Практическое применение алгоритмов отождествления записей баз данных
4.1. Введение.
4.2. Информационные потоки в страховой медицинской организации
4.3. Анализ быстродействия выполнения основных функций библиотеки
4.3.1. Время выполнения операции нестрогого соединения .
4.3.2. Время построения индекса.
4.4. Отождествление записей баз данных страховой компании и лечебнопрофилактических учреждений.
4.4.1. Используемые таблицы.
4.4.2. Примеры применения операции нестрогого соединения
4.4.3. Эффективность процедуры отождествления записей .
4.5. Заключение
Заключение
Список литературных источников


Интеграция баз данных может идти двумя принципиально различными способами. Первый заключается в создании единой БД, основанной на универсальной модели, в которую интегрируются данные отдельных БД. БД между собой. Этот способ приводит к созданию хранилища данных []. При использовании другого способа данные остаются в прежнем месте и неизменном формате, а интеграция заключается в организации доступа к ним. Среда интеграции отвечает за декомпозицию запроса, приведение частичного запроса к виду, используемому в частной БД, и формирование общего результата. Этот способ соответствует мультибазам данных и федеративным БД []. Основной проблемой при интеграции БД является различие в моделях и схемах данных [5]. В то же время вопрос интеграции самих данных остается открытым. Помимо выполнения процедур отождествления, интеграция данных предполагает выполнение преобразования данных к используемой в другой локальной БД схеме [2]. Это могут быть как преобразования формата данных - например, формата записи даты, так и более сложные функции - например, разбиение атрибута на несколько или выделение в качестве атрибута логического значения - предиката на множестве домена исходной БД (наличие телефона в строковом описании квартиры). На рис. БД. Необходимость построения процедур отождествления отмечается и в работах [, , , , 9]. Так, в [] отмечается, что новая ситуация, включая существенный и заранее нерегламентированный поток информации из информационной магистрали в корпоративную БД, потребует разработки “процедур отождествления” экземпляров информационных структур, то есть определения того, что эти экземпляры описывают один и тот же предмет реального мира. То же отмечается и в [9]. Рис. Кроме того, процедуры отождествления необходимы и при асинхронной репликации БД, когда в нескольких офисах организации одновременно происходит ввод информации. С уверенностью можно сказать, что задача отождествления при интеграции БД на настоящее время не имеет сколько-нибудь известного решения. Таким образом, требуется разработать процедуру отождествления экземпляров сущностей, хранящихся в различных БД. Рассмотрим вопрос моделирования в базах данных [, , ]. Под моделью часто понимают как парадигму моделирования (различаются реляционные, сетевые, иерархические, объектные, объектно-реляционные, функциональные и многие другие виды моделей данных), так и результат моделирования, то есть схему данных. Структурная трактовка полностью согласовывалась с математическим определением понятия модели как множества с заданными на нем отношениями []. В процессе развития теории систем баз данных термин “модель данных” приобрел новое содержание []. Проблемы отображения данных потребовали решения на метауровне, позволяющего оперировать множествами всевозможных допустимых представлений баз данных в рамках заданной СУБД, или, что эквивалентно, инструментальными средствами, используемыми для их спецификации. В этой связи возникла потребность в термине, который обозначал бы инструмент, а не результат моделирования, и воплощал бы, таким образом, множество всевозможных баз данных некоторого класса. Для этих целей стал использоваться все тот же термин “модель данных”. Поскольку инструмент моделирования баз данных должен по необходимости включать не только средства структурирования данных, но и операционные возможности для манипулирования данными, модель данных в инструментальном смысле стала пониматься как алгебраическая система — множество всевозможных допустимых типов данных, а также определенных на них отношений и операций. Позднее в это понятие стали включать еще и ограничения целостности. Модель БД стали называть схемой БД, хотя иногда по-прежнему используют неоднозначный термин “модель”. В результате проблема отображения данных в многоуровневых СУБД и системах распределенных баз данных стала рассматриваться как проблема отображения моделей данных []. Сказанное в п. ГсЬ2іпіго о необходимости построения общей модели при интеграции БД требует, с одной стороны, выбрать средство моделирования, с другой, построить схему общей БД.