Содержание к диссертации
Введение 4
Актуальность , . . 4
Цели работы 6
Методы 6
Научные результаты 6
Научная новизна 7
Практическая значимость 7
Доклады и научные публикации 8
1 Задачи, связанные с поиском в базах полуструктурированных
данных 10
Модель OEM-данных 11
Модель XML-данных 16
Методы сокращения времени поиска в OEM-данных 19
Методы сокращения веремни поиска в XML-данных 21
Выводы 25
2 Поиск в базах OEM-документов 26
2.1 Усечение пространства поиска 27
Иерархия схем 28
Вероятностное пространство запросов 35
2.2 Построение иерархии 40
Постановка задачи 41
Теоретическое обоснование и предпосылки к разработке алгоритма построения иерархии 41
Алгоритм построения иерархии 47
2.3 Построение иерархии по потоку документов 51
Постановка задачи 52
Теоретические положения и предпосылки алгоритма построения иерархии схем по потоку документов 53
Алгоритм построения иерархии по потоку документов 56
Сравнительный анализ 61
2.4 Выводы 61
3 Поиск в наборе однотипных документов при заранее неизвест
ной модели данных 63
3.1 Формальная модель поиска и индексирования 64
Поиск 64
Индексирование 66
Стоимость индекса 67
Построение оптимальных индексов 68
Построение индексов по потоку документов 72
3.2 Модель поиска в наборах XML-доку ментов по XPath-запросам 76
Вероятностное пространство запросов 77
Алгоритмы, реализующие интерфейсы модулей «документ», «схема», «запрос» 77
Свойства алгоритмов 79
Оценки сложностей алгоритмов поиска и индексирования 80
Выводы 86
4 Программная система и тестовые испытания 87
Требования к программной системе 87
Архитектурно-технологические решения 90
Компоненты системы 91
Интерфейсы компонент системы 92
4.3 Эксперименты с использованием программной системы поиска и индексирова
ния полуструктурированных документов 98
Эксперименты с вычислением запросов 99
Эксперименты с построением иерархий схем 107
4.4 Выводы 113
Заключение 114
Литература
Введение к работе
Актуальность
В связи с интенсивным развитием средств вычислительной техники и сетей передачи данных на основе пакетных коммуникаций вопросы организации эффективной работы с данными приобретают особую значимость. В больших и, как правило, сложно организованных хозяйствующих структурах различных форм собственности важное, а иногда и определяющее значение имеет эффективная работа с документами, регламентирующими как внутрихозяйственную деятельность, так и взаимодействие с внешними организациями, анализ информации в той или иной предметной области. Принимая во внимание существенно гетерогенную структуру организации данных в таких источниках, особенно важными и актуальными являются исследования, направленные на поиск новых, эффективных технологий работы с подобной информацией.
В последнее десятилетие в области хранения, обмена и обработки информации широкое распространение получили технологии, использующие понятие полуструктурированных данных [21]. Такой подход обладает большей гибкостью по сравнению с традиционными, в плане моделей описания данных, поскольку не требует наличия единой структуры у однотипных (относящихся к одной предметной-области) документов. Полуструктурированные данные могут использоваться при объединении разнородных информационных источников в единую систему [46], для поиска информации в Интернет или в корпоративных информационных хранилищах [2]. Известные на настоящее время формальные модели описания полуструктурированных данных [30, 21] и языков запросов, которые основываются на понятии регулярного путевого запроса [14], приводят к необходимости решения вычислительно трудных задач [55]. Под моделью полуструктурированных данных в диссертационной работе понимается Object Exchange Model (OEM) [56].
Документами в контексте настоящей работы будем называть объекты, содержащие данные в некотором заранее определенном формате. Базой данных будем именовать набор изолированных документов, подразумевая что при поиске данных результат вычисления запроса на отдельном документе не зависит от данных, содержащихся в других документах базы. Далее используются понятия OEM, XML, HTML-доку ментов, однако наибольшее
внимание в контексте целей данной работы уделяется OEM-модели. В качестве запросов для OEM-документов рассматриваются регулярные путевые запросы и конъюнктивные регулярные путевые запросы, для XML и HTML-документов рассматриваются XPath-выражения. В действительности документы могут быть взаимосвязаны, например, для формата данных HTML такие взаимосвязи задаются гиперссылками. Их учет — предмет отдельного исследования [9], которое находится вне целей настоящей работы. В подходе, который используется в данной работе, такие взаимосвязи учитываться не будут. Вычисление запроса будем понимать как поиск всех документов базы, которые удовлетворяют условиям запроса.
В качестве способа сокращения времени поиска информации во многих поисковых системах используются индексы баз данных. Следует отметить, что в работах, посвященных поиску данных в OEM-базах, большинство методик акцентируют свое внимание на построении индексов для случая, когда все данные находятся в одном OEM-документе, оставляя при этом без должного анализа ситуации случай, когда данные представляют собой набор таких документов. В настоящей работе основное внимание уделяется именно задаче построения индексов для наборов документов.
Неформально, индексом называют логическую структуру, описывающую связь между запросами и документами базы, а также позволяющую по какому-либо запросу быстрее находить необходимые документы. Однако, как правило, индекс определяют для каждой конкретной модели данных, не уточняя при этом, что представляет собой индекс в абстрактном смысле, без «привязки» к заданной модели. Как следствие, несмотря на большое число различных способов построения индексов, не существует единой методики оценки эффективности их применения. В связи с изложенным актуальна задача их обобщения и разработки единой теоретической базы, позволяющей оценивать эффективность таких индексов.
Один из наиболее распространенных способов составления электронных каталогов и баз данных в больших, сложно организованных хранилищах корпоративного масштаба и в Интернет заключается в последовательном добавлении «новых» документов в базу. При этом, возможно исключение «старых». В этой связи важной является разработка методик перестраивания индексов при изменении базы данных. Особое внимание в настоящей работе уделено задаче построения индексов для случая, когда база изменяется только посредством добавления документов. Такие базы данных в работе именуются потоками документов.
Настоящая работа направлена на решение перечисленных выше задач применительно к базам полуструктурированных данных. Принимая во внимание важную роль таких баз и методов работы с данными в различных секторах национального хозяйственного комплекса и экономики страны, тема настоящей работы безусловно является актуальной.
Цели работы
Основной целью настоящей диссертационной работы является исследование и разработка методов сокращения времени поиска документов в базах полуструктурированных данных. Для достижения этой цели сформулированы и решаются следующие задачи:
формализация понятия эффективности поиска документов в полуструктурированных базах данных с использованием индексов;
разработка алгоритмов построения эффективных индексов для наборов полуструктурированных документов;
разработка алгоритмов эффективного перестраивания индексов при добавлении полуструктурированных документов в базу;
реализация разработанных методов, создание прототипа программного комплекса для поиска данных в наборах полуструктурированных документов.
Методы
Для формализации ряда используемых в настоящей работе понятий и проведения строгих доказательств используются следующие методы:
математическая логика, включая исчисление предикатов, теория алгоритмов;
дискретная математика, в том числе комбинаторика, теория графов, теория автоматов и регулярных языков;
теория вероятности.
Научные результаты
В диссертационной работе получены следующие результаты.
Математически формализовано понятие индекса базы данных, представляющей собой набор полуструктурированных документов, дано строгое определение эффективности индексов для таких баз данных.
Для поиска в наборах OEM-документов представлены алгоритмы, позволяющие оценивать эффективность индексов с позиции временных затрат на вычисление конъюнктивных регулярных путевых запросов.
Для поиска в наборах XML-документов представлены алгоритмы, позволяющие оценивать эффективность индексов с позиции временных затрат на вычисление XPath-запросов.
Разработан алгоритм построения эффективных индексов для поиска данных в наборах полуструктурированных документов. Разработан алгоритм построения эффективных индексов для поиска данных в потоках полуструктурированных документов.
Получены оценки сложности для предложенных алгоритмов, на базе представленных в диссертации методов реализован и прошел тестовые испытания прототип системы поиска в наборах и в потоках полуструктурированных документов
Научная новизна
Предложен новый подход к решению задачи вычисления регулярных путевых запросов в полуструктурированных базах данных при помощи индексов, представляющих собой иерархии схем OEM-документов. В его рамках разработан оригинальный метод оценки эффективности индексов для таких баз данных.
В настоящей работе рассматривается не имеющая аналогов математическая модель эффективной системы поиска в наборах однотипных документов, структура которых заранее неизвестна. Для её построения формализовано понятие индекса базы данных, представляющей собой набор однотипных документов, дано строгое определение эффективности индекса, позволившее решить данную задачу. Предложены алгоритмы построения индексов по набору документов и по потоку однотипных документов. Такой подход позволяет обобщить ряд существующих методов построения индексов для наборов однотипных документов, которые до настоящего времени рассматривались отдельно для каждой конкретной модели данных и языка запросов.
Практическая значимость
Архитектура программного комплекса, предложенного в настоящей работе, может служить основой для создания подсистем индексирования данных и перезаписи запросов как
в системах управления данными с единой структурой, так и в системах интеграции разнородных данных. Представленные в диссертации методы построения индексов могут быть использованы для повышения эффективности таких систем.
Прототип программного комплекса, созданный в рамках выполнения диссертационной работы и состоящий из поисковой системы и web-интерфейса управления ею, продемонстрировал свою эффективность. Он позволяет проводить индексирование массивов OEM, XML, HTML-документов по разработанному автором и представленному в настоящей работе методу, а также осуществлять поиск по соответствующим запросам в наборах документов при помощи построенных индексов.
Доклады и научные публикации
Основные результаты диссертации докладывались на конференциях: «Ломоносовские чтения» 2005 г.; на Третьей международной конференции по проблемам управления 2006 г. На семинарах: «Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина на механико-математическом факультете МГУ имени М. В. Ломоносова в 2007 и 2008 г.; на семинаре под руководством проф. С. Д. Кузнецова в Институте системного программирования РАН в 2008г.; на семинаре Московской секции ACM SIGMOD под руководством проф. Л. А. Калиниченко в 2009 г.
ПО ТЕМЕ ДИССЕРТАЦИИ опубликовано 6 печатных работ, из которых 3 [1-3] в списке журналов, рекомендованных в ВАК РФ.
С.С. Горелов, В.А. Васенин. Усечение пространства поиска в полуструктурированных базах данных при помощи иерархии схем документов. Журнал «Программирование». Вып. 6, 2005, стр.41-55. (СС. Горелову принадлежат доказательства теорем 1 и 2).
С.С. Горелов. Оптимальные иерархии схем для поиска по конъюнктивным регулярным путевым запросам в полуструктурированных базах данных. Журнал «Программирование». Вып. 4, 2006, стр.38-56.
С.С. Горелов. Модели и алгоритмы для систем поиска в наборах документов. Журнал «Информационные технологии». Вып. 1, 2009, стр.61-66.
С.С. Горелов. Построение иерархии схем по потоку полуструктурированных документов. Сборник «Информационные технологии и программирование», Вып. 3(12), 2004, стр.45-64.
Gorelov S.S., Vasenin V.A. Search Optimization in Semistructured Databases Using Hierarchy of Document Schemas Programming and Computer Software, MAIK Nauka/Interperiodica, vol. 31, no. 6, pp. 321-331, 2005. (C.C. Горелову принадлежат доказательства теорем 1 и 2).
Gorelov S.S. Optimal schema hierarchies in searching semistructured databases by conjunctive regular path queries. Programming and Computer Software, MAIK Nauka/Interperiodica, vol. 32, no. 4, pp. 215-227, 2006.
Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук, профессору Валерию Александровичу Васенину за постановку задач и постоянное внимание к работе.
