Эффективные модели поиска в базах полуструктурированных данных на основе иерархии схем документов

• Автор: Горелов, Сергей Сергеевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 120 с. : ил.

Оглавление
Введение

Актуальность.

Цели работы
Методы.

Научные результаты.

Научная новизна

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

Доклады и научные публикации.

1 Задачи, связанные с поиском в базах полуструктурированных

данных
1.1 Модель данных
1.2 Модель ХМданных
1.3 Методы сокращения времени поиска в данных
1.4 Методы сокращения веремни поиска в Xданных
1.5 Выводы.
2 Поиск в базах документов
2.1 Усечение пространства поиска.
2.1.1 Иерархия схем
2.1.2 Вероятностное пространство запросов
2.2 Построение иерархии
2.2.1 Постановка задачи
2.2.2 Теоретическое обоснование и предпосылки к разработке алгоритма построения иерархии
2.2.3 Алгоритм построения иерархии.
2.3 Построение иерархии но потоку документов
2.3.1 Постановка задачи
2.3.2 Теоретические положения и предпосылки алгоритма построения иерархии схем по потоку документов.
2.3.3 Алгоритм построения иерархии по потоку документов
2.3.4 Сравнительный анализ.
2.4 Выводы.
3 Поиск в наборе однотипных документов при заранее неизвестной модели данных
3.1 Формальная модель поиска и индексирования
3.1.1 Поиск
3.1.2 Индексирование.
3.1.3 Стоимость индекса .
3.1.4 Построение оптимальных индексов
3.1.5 Построение индексов по потоку документов.
3.2 Модель поиска в наборах ХМЬдокументов по ХРаЬЬзаиросам.
3.2.1 Вероятностное пространство запросов.
3.2.2 Алгоритмы, реализующие интерфейсы модулей документ, схема,
запрос
3.2.3 Свойства алгоритмов
3.3 Оценки сложностей алгоритмов поиска и индексирования.
3.4 Выводы.
4 Программная система и тестовые испытания
4.1 Требования к программной системе.
4.2 Архитектурнотехнологические решения.
4.2.1 Компоненты системы.
4.2.2 Интерфейсы компонент системы.
4.3 Эксперименты с использованием программной системы поиска и индексирования полуструктурированных документов.
4.3.1 Эксперименты с вл числением запросов
4.3.2 Эксперименты с построением иерархий схем
4.4 Выводы
Заключение
Литература


Прототип программного комплекса, созданный в рамках выполнения диссертационной работы и состоящий из поисковой системы и web-интерфейса управления ею, продемонстрировал свою эффективность. Он позволяет проводить индексирование массивов OEM, XML, HTML-документов по разработанному автором и представленному в настоящей работе методу, а также осуществлять поиск по соответствующим запросам в наборах документов при помощи построенных индексов. Основные результаты диссертации докладывались на конференциях: «Ломоносовские чтения» г. Третьей международной конференции по проблемам управления г. На семинарах: «Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина на механико-математическом факультете МГУ имени М. В. Ломоносова в и г. С. Д. Кузнецова в Институте системного программирования РАН в г. Московской секции ACM SIGMOD под руководством проф. Л. А. Калиниченко в г. ПО ТЕМЕ ДИССЕРТАЦИИ опубликовано б печатных работ, из которых 3 [1-3] в списке журналов, рекомендованных в ВАК РФ. С.С. Горелов, В. А. Васенин. Усечение пространства поиска в полуструктурированных базах данных при помощи иерархии схем документов. Журнал «Программирование». Вып. С.С. Горелову принадлежат доказательства теорем 1 и 2). С.С. Горелов. Оптимальные иерархии схем для поиска по конъюнктивным регулярным путевым запросам в полуструктурированных базах данных. Журнал «Программирование». Вып. С.С. Горелов. Модели и алгоритмы для систем поиска в наборах документов. Журнал «Информационные технологии». Вып. С.С. Горелов. Построение иерархии схем по потоку полуструктурированных документов. Сборник «Информационные технологии и программирование», Выи. Gorelov S. S., Vasenin V. Nauka/Interperiodica, vol. C.C. Gorelov S. S. Optimal schema hierarchies in searching semistructured databases by conjunctive regular path queries. Nauka/Interperiodica. Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук, профессору Валерию Александровичу Васенину за постановку задач и постоянное внимание к работе. Глава 1. Первая глава является вводной и посвящена описанию модели представления ОЕМ-данных, регулярных путевых запросов, методов их вычисления и оптимизации. В главе описывается модель представления XML-данных и методы сокращения времени поиска в базах таких данных по XPath-запросам. В первом разделе главы описаны полуструктурированиыс документы, для чего используется модель OEM. Данные в ней представляются в виде ориентированного графа. Вершины этого графа — объекты, каждый из которых имеет уникальный идентификатор. Объекты, имеющие исходящие ребра, называются составными объектами. Каждое ребро имеет метку, которая описывает отношение «объект — подобъект». Изложены формальные модели языков запросов к OEM-данным, представлено понятие схемы ОЕМ-докумеитов. Второй раздел главы посвящен описанию модели представления XML-даниых и схем данных (DTD, XML Schema, структурные схемы). В контексте работы под моделью данных XML понимается модель данных XQuery 1. Дня построения прототипа системы поиска в наборах XML-документов учитываются только структурные ограничения [], накладываемые XML Schema. В третьем разделе изложены методы решения задачи сокращения времени поиска в полуструктурированных базах данных. В общем смысле, структуры данных, используемые для сокращения времени поиска называются индексами. Отмечается тот факт, что для одного документа можно выбрать несколько индексов (разных типов, различной структуры и содержания). Некоторые из них позволяют более точно проводить предварительный поиск в документе, другие имеют меньшие размеры, позволяют производить этот поиск быстрее. В качестве индексов для отдельных документов в диссертационной работе рассмотрены графовые схемы. Такое допущение делается в силу того, что графовую схему можно рассматривать как основу для формальных моделей представления таких индексов, как A(k), 1-index, DataCIuide, Index Fabric. В контексте задачи сокращения времени поиска наибольшее внимание уделено методам логической оптимизации запросов к базам данных.