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

Московский государственный университет им. М. В. Ломоносова Механико-математический факультет

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

□□3467528

Горелов Сергей Сергеевич

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

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

документов

Специальность 05.13.17 — теоретические основы информатики

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

003467528

Работа выполнена на кафедре вычислительной математики Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор Васенин Валерий Александрович

Официальные оппоненты: доктор физико-математических наук,

профессор Новиков Борис Асенович

кандидат физико-математических наук, старший научный сотрудник, Афонин Сергей Александрович

Ведущая организация: Институт системного программирования РАН

Защита диссертации состоится 29 апреля 2009 г. в 16 час. 45 мин. на заседании диссертационного совета Д 501.002.16 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП 1, Ленинские горы, д. 1, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени М. В. Ломоносова (главное здание, 14 этаж).

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

Ученый секретарь диссертационного совета Д 501.002.16 при МГУ доктор физико-математических наук

А. А. Корнев

Общая характеристика работы

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

В последнее десятилетие в области хранения, обмена и обработки информации широкое распространение получили технологии, использующие понятие полуструктурированных данных1. Такой подход обладает большей гибкостью по сравнению с традиционными, в плане моделей описания данных, поскольку не требует наличия единой структуры у однотипных (относящихся к одной предметной области) документов. Полуструктурированные данные могут использоваться при объединении разнородных информационных источников в единую систему2, для поиска информации в Интернет или в корпоративных информационных хранилищах3.

Известные на настоящее время формальные модели описания полуструктурированных данных4 и языков запросов, которые основываются на понятии регулярного путевого запроса5, приводят к необходимости

1Випешал Р. Semistructured data // 16th ACM Symposium on Principies of Database Systems. —1997.— Pp. 117-121. citeseer.ist.psu.edu/buneman97semistructured.html.

2Lore: A database management system for semistructured data / J. McHugh, S. Abiteboul, R. Goldman et al. // SIGMOD Record.— 1997.— Vol. 26, no. 3.— Pp. 54-66. citeseer.ist.psu.edu/mchugh971ore.btml.

'Васенин В. А., Афонин С. А., Коршунов А. А. К созданию концепции интегрированной системы распределённых информационных ресурсов Московского государственного университета им. М.В. Ломоносова.- М.: Изд-во МГУ, 2001.- С. 112.

^Büneman Р. Semistructured data // 16th ACM Symposium on Principies of Database Systems. — 1997. — Pp. 117-121. dteseer.ist.psu.edu/buneman976emistructured.html.

'Abiteboul S., Vianu V. Regular path queries with constraints // 16th ACM Symposium on Principies of Database Systems. — 1997. — Pp. 122-133. citeseer.ist.psu.edu/abiteboul98regular.html.

решения вычислительно трудных задач6. Под моделью полуструктурированных данных в диссертационной работе понимается Object Exchange Model (OEM)7. Документами в настоящей работе называются объекты, содержащие данные в некотором заранее определенном формате. Базой данных именуется набор изолированных документов, подразумевая при этом, что при поиске данных результат вычисления запроса на отдельном документе не зависит от данных, содержащихся в других документах базы. Используются понятия OEM, XML, HTML-документов, однако наибольшее внимание в контексте целей данной работы уделяется OEM-модели. В качестве запросов для OEM-документов рассматриваются регулярные путевые запросы и конъюнктивные регулярные путевые запросы, для XML и HTML-документов рассматриваются — XPath-выражения. В действительности документы могут быть взаимосвязаны, например, для формата данных HTML такие взаимосвязи задаются гиперссылками. Их учет — предмет отдельного исследования8, которое находится вне целей настоящей работы. В подходе, который используется в данной работе, такие взаимосвязи не учитываются. Вычисление запроса будем понимать как поиск всех документов базы, которые удовлетворяют условиям запроса.

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

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

eShasha D., Wang J. T.-L., Giugno R. Algorithmic and applications of tree and graph searching // Symposium on Principles of Database Systems.— 2002,— Pp. 39-52. citeseer.ist.psu.edu/shasha02algorithmics.html.

7 A standard textual interchange format for the object exchange model (OEM): Tech. rep. / R. Goldman, S. Chawathe, A. Crespo, J. McHugh. - Stanford, CA, USA: 1998.

8Козлов Д. Д., Белова А. А. Исследование эффективности применения методов совместного анализа текстов и гиперссылок для поиска тематических сообществ // Интернет-математика 2005: автоматическая обработка веб-данных. — 2005.— Т. 5, № 1.— С. 250-271.

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

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

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

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

• формализация понятия эффективности поиска документов в полуструктурированных базах данных с использованием индексов;

• разработка алгоритмов построения эффективных индексов для наборов полуструктурированных документов;

• разработка алгоритмов эффективного перестраивания индексов при добавлении полуструктурированных документов в базу;

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

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

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

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

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

Апробация работы и публикации. Основные результаты диссертации докладывались на конференциях: «Ломоносовские чтения» 2005 г.; на Третьей международной конференции по проблемам управления 2006 г. На семинарах: «Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина на механико-математическом факультете МГУ имени М. В. Ломоносова в 2007 и 2008 г.; на семинаре под руководством проф. С. Д. Кузнецова в Институте системного программирования РАН в 2008г.; на семинаре Московской секции ACM SIGMOD под руководством проф. Л. А. Калиниченко в 2009 г.

Публикации.

По теме диссертации опубликовано 6 научных работ [1-6], в том числе 3 работы [1-3] в журналах из перечня ведущих научных журналов и изданий рекомендованных ВАК РФ.

Структура и объем работы.

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

Краткое содержание работы.

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

Первая глава является вводной и посвящена описанию модели представления полуструктурированных данных, языков запросов, методов вычисления и оптимизации конъюнктивных регулярных путевых запросов. В главе описывается модель представления XML-данных и методы сокращения времени поиска по ХРаА-запросам в XML-данных.

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

Определение. Документом D называется ориентированный связный граф с выделенной корневой вершиной, ребра которого помечены символами заданного алфавита: D — (V, Е, Е, г>о); где V — множество вершин графа; Е — множество ребер, то есть, Е С (V х Е X V); Е — конечное множество меток ребер (алфавит); vq — корневая вершина (vq 6 V). При этом все вершины графа достижимы по исходящим ребрам из корневой.

Определение. Полуструктурированной базой данных (ПБД) DB называется конечное множество документов: DB = {DJ.

Для описания схем документов и некоторых их свойств используются графовые схемы9.

Определение. Схемой S документа называется ориентированный граф с выделенными корневыми вершинами, ребра которого помечены унарными предикатами над алфавитом Е, а именно — S = (X, К, Е, Xq) , где X — множество вершин графа (произвольной природы), К — множество рёбер, то есть К С (Хх х X), Е — алфавит, Х0 — множество корневых вершин (Х0 С X).

Здесь обозначает множество всех унарных предикатов над алфавитом Е.

Понятие схемы можно трактовать как описание структуры документа (описание взаимосвязей между вершинами) и как отображение частичной информации о его содержимом (описание символов, которыми могут быть помечены определенные ребра). В контексте методологии данной работы важной является возможность определять, соответствует ли документ D схеме S или нет. Соответствие документа D схеме S определяется, как наличие между вершинами D и 5 такого отображения, при котором для любого ребра D, помеченного символом а, и соответствующего ребра в S, помеченного предикатом 7Г, верно равенство 7г(а) =«истина».

Для описания формальной модели запросов используется понятие конъюнктивного регулярного путевого запроса и его частного случая — элементарного регулярного запроса.

'Adding structure to unstructured data / P. Buneman, S. B. Davidson, M. F. Fernandez, D. Suciu // Database Theory—ICDT'97, 6th International Conference / Ed. by F. N. Afrati, P. Kolaitis.- Vol. 1186.— Delphi, Greece: Springer, 1997. —8-10 . — Pp. 336-350. citeseer.ist.psu.edu/article/buneman97adding.html.

Определение. Конъюнктивным регулярным путевым запросом (Conjuctive Regular Path Query — CRPQ) называется ориентированный помеченный граф Q = {Z, R, К, -го), где Z — множество вершин запроса; Л С (Z х £(£) х Z) — множество ребер запроса, помеченных регулярными языками над алфавитом Е; zo — корневая вершина запроса.

Частным случаем CRP-запроса является элементарный регулярный запрос Q без корневой вершины и состоящий из одного ребра, помеченного регулярным языком L. Пара вершин (Vi,Vj) документа D удовлетворяет элементарному регулярному запросу Q, если в этом документе существует путь t(vi,vj) такой, что a(t) £ I. В общем случае результат вычисления CRP-запроса определяется следующим образом.

Определение. Инъективное отображение fj, : Z —► V вершин Z запроса Q в вершины V документа D удовлетворяет запросу, если выполняются следующие условия:

• ß{zo) = fo, где zo — корневая вершина запроса, vq — коневая вершина документа;

• V(zi,L,Zj) £ R в документе D существует путь t(ß(zi), n{zj)), такой, что cr(t) € L.

Множество отображений вершин Z запроса Q в вершины V документа D, удовлетворяющее запросу Q, называется результатом поиска по запросу Q в документе D и обозначается Q{D).

Второй раздел главы посвящен описанию модели представления XML-данных и схем данных (DTD, XML Schema, структурные схемы), В контексте работы под моделью данных XML понимается модель данных XQuery 1.0. Для построения прототипа системы поиска в наборах XML-доку ментов учитываются только структурные ограничения10, накладываемые XML Schema.

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

10Новак Л. Г., Кузнецов С. Д. Свойства схем данных xml // Труды Института системного программирования.— 2003. — Т. 4.

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

В третьем разделе главы описаны языки запросов к OEM-данным и способы сокращения времени поиска данных (A(k), 1-index, DataGuide, Index Fabric) по CRP-запросам при помощи построения индексов. Отмечается тот факт, что для одного документа можно выбрать несколько индексов (разных типов, различной структуры и содержания). Некоторые из них позволяют более точно проводить предварительный поиск в документе, другие имеют меньшие размеры, позволяют производить этот поиск быстрее. В качестве индексов для отдельных документов в диссертационной работе рассмотрены графовые схемы. Такое допущение делается в силу того, что графовую схему можно рассматривать как основу для формальных моделей представления таких индексов, как A(k), 1-index, DataGuide, Index Fabric.

Четвертый раздел посвящен языку запросов XPath, как базовому в задании более сложных и наиболее распространенных языков запросов к XML-данным, которые поддерживаются консорциумом W3C. Особое внимание в диссертационной работе уделяется методам перезаписи XPath-запросов, позволяющим сокращать время поиска данных при их вычислении.

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

В первом разделе главы описаны понятия индекса, общие принципы усечения пространства поиска для OEM-модели а также формализовано понятие эффективности индекса для набора ОЕМ-документов.

Определение. Индексом полуструктурированной базы данных DB называется ориентированное дерево I = (S,Т, So), где § — множество графовых

схем — вершин иерархии; Т С (S х §) — множество ребер иерархии; ¿о — корневая схема иерархии. При этом схемы, являющиеся вершинами иерархии, должны обладать тем свойством, что каждая схема является более общей, чем любая из её дочерних.

Для каждого OEM-документа Д из базы данных DB существует листовая схема иерархии, которой он соответствует (если таких схем несколько, то учитывается лишь одна). Для какой-либо некорневой схемы S из иерархии I её родительскую схему обозначим S. Далее термины «иерархия схем документов» и «индекс» употребляются в одном и том же смысле.

Усечение пространства поиска на основании анализа набора схем документов опирается на следующий факт; если известно множество схем, которым соответствуют все документы из базы данных, то, проверяя запрос на какой-либо одной из них (пусть £), можно отсечь множество документов, на которых поиск по запросу заведомо не даст положительного результата. Проверка документа на схеме представляет собой применение алгоритма, который по запросу Q и графу схемы S позволяет определить факт того, что ни один документ, соответствующий схеме S, не удовлетворяет запросу Q. Если результат такой проверки положительный, то этот факт обозначается как <5(5) ф 0.

Алгоритм усечения пространства поиска представляет собой итерационный процесс. На каждом шаге алгоритма для рассматриваемой вершины S индекса I (для первого шага S, — это корневая схема) проверяем условие Q(S) — 0. Если условие выполняется, то «отсекаем» рассматриваемую ветвь индекса, в противном случае переходим к проверке дочерних схем. Продолжаем такие итерации до тех пор, пока не будут рассмотрены все ветви индекса. После обхода дерева получим множество схем (являющихся листьями индекса), для которых Q(S) Ф 0. Для остальных листовых схем возьмем все соответствующие им документы и исключим эти документы из пространства поиска.

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

иной запрашиваемой информации. Чтобы учесть отмеченные обстоятельства, запросы рассматриваются, как случайные величины. Формально, под эффективностью индекса понимается математическое ожидание стоимости вычисления запросов при поиске. В таких терминах вероятностное пространство принимает вид ( Q , 9", Р ), где Q — множество случайных событий (запросов); 3" — сигма-алгебра над Q; У — сигма-аддитивная мера над Q.

Определение. Вероятность схемы (P{S}) — есть вероятность появления такого события, что Q(S) Ф 0.

С целью учесть стоимость поиска в документах, при вычислении стоимости иерархии, считается, что документы также являются её вершинами, а ребра от них проведены к тем схемам, которым они соответствуют.

Утверждение. Математическое ожидание стоимости вычисления запросов на иерархии равно

М(7)= £ P{S} * |S|,

Sei\S0

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

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

Теорема. Существует иерархия схем 1ь такая, что для любой иерархии I выполняется неравенство М(1) > М(Д). Данная иерархия называется наилучшей.

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

Утверждение (о локальной оптимальности наилучшей иерархии). Если в наилучшей иерархии, выбрать какую-либо вершину S, рассмотреть её дочерние схемы S[,...,S'n то выражение * l^k, * l^l должно быть не больше такого же выражения, вычисленного для иерархии, в которой на место S поставили какую-либо другую схему.

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

Для случая поиска в ОЕМ-документах по СИР-запросам в диссертационной работе доказывается ряд теорем, которые позволяют без ограничений общности переходить от рассмотрения бесконечного вероятностного пространства к конечному. При этом результаты вычисления запросов на рассматриваемом наборе документов сохраняются.

Теорема. Для любого документа £> и языка Ь существует натуральное число М такое, что Ьм{0) = Ь(Б), где Ьм есть язык, состоящий из слов языка Ь длины меньше М.

Для СИР запросов вводится отношение эквивалентности, которое позволяет сделать вывод о том, что результаты их вычисления будут совпадать на базе полуструктурированных данных.

Определение. Будем называть СЯР-запросы <3 и Ц' эквивалентными на документе V, если результаты поиска по запросу в этих документах равны.

Определение. Конъюнктивный регулярный путевой запрос <У является приближением порядка N запроса С}, если \/£) : \П\ < N запросы С} и С}' эквивалентны на документе В.

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

Теорема. Возьмем произвольное натуральное число N. Рассмотрим множество Ъ документов Б таких, что \В\ < N. Тогда число классов эквивалентности СЛР-запросов построенных по результатам поиска в выбранном множестве документов, будет конечно.

Теорема. Для любого СИР-запроса <9 и натурального N, существует такое М, что запрос (из языков которого убраны все слова длины большей либо равной М) представляет собой приближение порядка N запроса С}.

Таким образом, можно ограничиться рассмотрением конечного множества запросов, количество вершин и длина слов в регулярных языках которых ограничены заранее известными числами. Алгебра & задается как множество подмножеств 0. В силу конечности последнего, 7 является сигма-алгеброй. Конечность рассматриваемого вероятностного пространства для ОЕМ-модели позволяет предложить алгоритм вычисления вероятности схемы и построить оценку его сложности. Такая оценка входит в качестве базового элемента в оценку сложности поиска по иерархии схем документов. Кроме того, конечность рассматриваемого вероятностного пространства позволяет задавать конкретные значения запросов на основе статистики обращения к СУБД.

После описанных выше теоретических положений во второй главе рассматривается постановка задачи построения индекса и предлагается разработанный автором алгоритм её решения. Задача построения индекса сформулирована таким образом, что для заранее известной базы полуструктурированных данных ЭВ = {£) 1, Дг, ■ ■ •, А^} необходимо разработать алгоритм, позволяющий строить иерархии со свойствами, приближающими её к наилучшей при поиске в ВВ.

Поскольку доказанные теоремы позволяют находить наилучшую иерархию лишь перебором, в работе предложен более эффективный подход. Основная идея построения индекса заключается в том, что процесс необходимо осуществлять, исходя из свойств локальной оптимальности наилучшего индекса. Алгоритм построения индекса представляет собой итерационный процесс. Построение иерархии схем производится снизу-вверх. Согласно этой методологии изначально рассматриваются все документы; затем находят ся группы в определенном смысле «близких» документов; для этих групп строятся более общие родительские схемы, и так далее, до тех пор, пока не будет построена корневая схему иерархии. В работе доказана оценка сверху сложности этого алгоритма.

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

Задача построения индекса для потока документов формулируется следующим образом. В начальный момент времени дана ПБД. Из ограниченного набора документов БВ — (£>1... Оп) последовательно (по одному) извлекаются документы и добавляются в ПБД, организуя, таким образом, поток документов в базу. Необходимо разработать алгоритм, который после добавления в ПБД каждого нового документа будет строить иерархию схем для полученной ПБД.

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

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

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

• поиск подходящей ветви в иерархии;

• добавление документа в найденную ветвь;

• проверка — переполнена ли ветвь, или нет;

• модификация переполненной ветви иерархии.

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

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

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

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

• документом Б называется некоторый объект — элемент множества I);

• под базой данных ИВ будем понимать конечное множество документов, ЮВ = {£>};

• запросом называется некоторый объект С} — элемент множества £3.

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

Определение. Функцией поиска документа называется отображение <§а!: Ъ х 0 -> {0,1}.

Если для документа И и запроса ф верно равенство СЦс1(0, ф) = 1, этот факт означает, что документ соответствует запросу <3, а равенство (¿эф, = 0 означает обратное.

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

Определение. Обозначая какую-либо схему как 5", будем при этом полагать, что каждая схема 5 задает множество документов (соответствующих 5), которое обозначим [5]. Множество всех схем обозначим как §.

Различие в обозначениях 5 и [5] делается по той причине, что в частных случаях (например, при поиске в ОЕМ-документах) схемы задаются конструктивно.

Определение. Схема ¿>1 называется более общей чем ¿>2, если [¿У С [¿х]. Будем обозначать это отношение ^ 5г.

Определение. Индексом I для базы данных DB называется ориентированное дерево I = (S,T,Sq), где S представляет собой множество схем — вершин иерархии; Т С (S х §) — множество ребер иерархии; So — корневая схема иерархии. При этом схемы, являющиеся вершинами иерархии, должны обладать тем свойством, что каждая схема является более общей, чем любая из её дочерних.

Для каждого документа Di из базы данных DB существует листовая схема иерархии, которой он соответствует.

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

Определение. Функцией поиска по схеме будем называть отображение Qs: § х Q -> {0,1}. При этом Qs(S,Q) = 1, если 3D е S : Qd(D,S) = 1 и Qs{S, Q) = 0, если VD € [S) : Qd(D, S) = 0.

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

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

Определение. Функция Cost : 8 х Q —► Е задает сложность операции вычисления запроса Q на схеме S.

С целью вычисления стоимости индекса, вводятся понятия, описывающие среднюю сложность вычислений на схеме и вероятность схемы.

Определение. Величина M(Cost(S, Q)) обозначается как |5| и называется размером схемы, имея ввиду, что величина характеризует сложность вычислений на схеме.

Определение. Вероятность того, что по схеме S будет что-то найдено называется вероятностью схемы и обозначается P{S}.

Утверждение. Стоимость индекса равна:

М(1) = P{S}\S\, sei\s0

где сумма берется по всем вершинам индекса, кроме корневой схемы So-

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

Определение. Будем считать, что для множеств Ф, Q, § задана модель оптимизированного поиска, если заданы изоморфизм S —► 2° и вероятностное пространство (fl, 3", У), а также формально определены функции:

• построение схемы по документу — S(D): D —» S;

• вычисление размера схемы — |>?|: S —* R;

• отношение на схемах — Si > S2: § х § —> {0,1};

• объединение схем — Si 4- S2: S х S —* S;

• вычисление вероятности схемы — P{S}: S —► R]

• вычисление запроса на документе — Qd(D,Q): D х Q —► {0,1};

• вычисление запроса на схеме — Qs(S, Q): § х Q -+ {0,1}.

• проверка соответствия документа схеме — S D: § х D —* {0,1}.

При этом для заданных функций выполняются следующие свойства:

• вычисление отношений Si ¿>2, S D и операции Si + S2 соответствует заданному изоморфизму множества S и подмножества 2V посредством функции

• если верно Qs(S, Q) — 1, то существует D е S : Qd(D, S) = 1;

• если верно Qs(S, Q) = 0, то для любого D е S : Qd(D, S) = 0.

• Функции P{S} и |S| соответствуют своим определениям и заданы для вероятностного пространства Q.

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

Построенная формальная модель, позволяет производить поиск и построение индекса для различных моделей документов, запросов и схем. Во втором разделе изложены теоретические положения, позволяющие использовать предложенную автором модель применительно к задаче поиска в наборах ХМЬ-документов по ХРаЛ-залросам. Для задания такой модели строго определены понятия документа, схемы и запроса, описаны алгоритмы, реализующие требуемый (в формальной модели) список базовых функций и их свойств.

В третьем разделе главы представлена оценка сложности предложенного автором алгоритма построения индекса, доказанная в предположении, что сложности вычисления |5|, -Р{5}, Б (В), оцениваются как С|5|, С/>{5},

Со, С^+Зз! соответственно.

Утверждение. Предположим, что база данных состоит из N документов, а размер схемы оценивается сверху как |5(. Тогда сложность алгоритма построения индекса для поиска в наборе документов можно оценить сверху как О (ЩСщ + Со) + ЛГ2(С<?1+52 + СЗД + ^ 1п(ЛГ)).

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

Утверждение. Предположим, что мощность множества запросов равна М, все запросы равновероятны, при этом все результаты их вычисления различаются между собой.

Тогда не существует индекса (в смысле, определенном настоящей работой), стоимость которого меньше 1пг(М). При этом, существует алгоритм поиска, сложность которого есть 0(1пг(Л/)).

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

Тогда математическое ожидание вычислительной сложности поиска с использованием индекса больше либо равно половине значения, определяющего математическое ожидание сложности поиска без его использования.

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

Четвертая глава посвящена изучению эффективности предложенной автором формальной модели на практике. На основании базовых положений модели целевой системы, с учетом предъявляемых к ней требований реализован прототип программного комплекса для вычисления запросов на наборах однотипных документов (далее сокращенно «система»). С его помощью выполнена представительная серия экспериментов, направленных на поиск данных по регулярным конъюнктивным путевым запросам на наборах полуструктурированных документов,а также по XPath-запросам на наборах XML документов.

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

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

• построение индекса по базе данных;

• построение индекса по потоку документов;

• поиск по запросу в базе данных с использованием индекса.

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

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

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

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

Анализируя результаты тестов более детально, следует отметить, что алгоритм построения иерархии схем документов имеет верхнюю оценку сложности О (N{0до + Са) + ЛГ2(С<?1+52 + С/^}) + ЛГ31п(Л^)). Эта оценка является существенной по отношению к величине времени поиска ХМЬ-данных по ХРаШ-запросам. Причина в том, что для большого числа ХРа<;Ь-запросов, используемых на практике (например, ХРаШ-запросы, составленные только с использованием оси / и без предикатов), такая зависимость линейна по отношению к размеру базы. Тестовые испытания показали, что время, затрачиваемое на построение индексов для ХМЬ-баз, неприемлемо велико для использования программной системы на практике в том виде, в котором она существует на настоящее время. Для поиска ХМЬ-данных необходимо использовать более эффективные алгоритмы. Данный вопрос требует детального изучения и выходит за рамки исследований, результаты которых представлены в данной диссертационной работе. Однако, они могут быть использованы как отправные (исходные) для продолжения исследований на рассматриваемом направлении.

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

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

Основные результаты диссертации выносимые на защиту

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

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

• Для поиска в наборах ХМЬ-документов представлены алгоритмы, позволяющие оценивать эффективность индексов с позиции временных

затрат на вычисление XPath-запросов.

• Разработан алгоритм построения эффективных индексов для поиска данных в наборах полуструктурированных документов. Разработан алгоритм построения эффективных индексов для поиска данных в потоках полуструктурированных документов.

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

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

Список опубликованных работ по теме диссертации

1. С.С. Горелов, В.А. Васенин. Усечение пространства поиска в полуструктурированных базах данных при помощи иерархии схем документов. Журнал «Программирование». Вып. 6, 2005, стр.41-55. (С.С. Горелову принадлежат доказательства теорем 1 и 2).

2. С.С. Горелов. Оптимальные иерархии схем для поиска по конъюнктивным регулярным путевым запросам в полуструктурированных базах данных. Журнал «Программирование». Вып. 4, 2006, стр.38-56.

3. С.С. Горелов. Модели и алгоритмы для систем поиска в наборах документов. Журнал «Информационные технологии». Вып. 1, 2009, стр.61-66.

4. С.С. Горелов. Построение иерархии схем по потоку полуструктурированных документов. Сборник «Информационные технологии и программирование», Вып. 3(12), 2004, стр.45-64.

5. 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. (С.С. Горелову принадлежат доказательства теорем 1 и 2).

6. 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.

Подписано в печать 05. (33 Формат 60x90 1/16. Усл. печ. л. {,5 Тираж /ОО экз. Заказ

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имени М.В.Ломоносова

Введение

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

Цели работы.

Методы.

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

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

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

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

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

1.1 Модель OEM-данных.

1.2 Модель XML-данных.

1.3 Методы сокращения времени поиска в OEM-данных.

1.4 Методы сокращения веремни поиска в XML-данных.

1.5 Выводы.

2 Поиск в базах OEM-документов

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 Модель поиска в наборах XML-документов по XPath-запросам.

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 Выводы.

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

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

В последнее десятилетие в области хранения, обмена и обработки информации широкое распространение получили технологии, использующие понятие полуструктурированных данных [21]. Такой подход обладает большей гибкостью по сравнению с традиционными, в плане моделей описания данных, поскольку не требует наличия единой структуры у однотипных (относящихся к одной предметной-области) документов. Полуструктурированные данные могут использоваться при объединении разнородных информационных источников в единую систему [46], для поиска информации в Интернет или в корпоративных информационных хранилищах [2]. Известные на настоящее время формальные модели описания полуструктурированных данных [30, 21] и языков запросов, которые основываются на понятии регулярного путевого запроса [14], приводят к необходимости решения вычислительно трудных задач [55]. Под моделью полуструктурированных данных в диссертационной работе понимается Object Exchange Model (OEM) [56].

Документами в контексте настоящей работы будем называть объекты, содержащие данные в некотором заранее определенном формате. Базой данных будем именовать набор изолированных документов, подразумевая что при поиске данных результат вычисления запроса на отдельном документе не зависит от данных, содержащихся в других документах базы. Далее используются понятия OEM, XML, HTML-документов, однако наибольшее внимание в контексте целей данной работы уделяется OEM-модели. В качестве запросов для OEM-документов рассматриваются регулярные путевые запросы и конъюнктивные регулярные путевые запросы, для XML и HTML-документов рассматриваются ХРаШ-выражения. В действительности документы могут быть взаимосвязаны, например, для формата данных HTML такие взаимосвязи задаются гиперссылками. Их учет — предмет отдельного исследования [9], которое находится вне целей настоящей работы. В подходе, который используется в данной работе, такие взаимосвязи учитываться не будут. Вычисление запроса будем понимать как поиск всех документов базы, которые удовлетворяют условиям запроса.

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

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

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

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

Цели работы

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

• формализация понятия эффективности поиска документов в полуструктурированных базах данных с использованием индексов;

• разработка алгоритмов построения эффективных индексов для наборов полуструктурированных документов;

• разработка алгоритмов эффективного перестраивания индексов при добавлении полуструктурированных документов в базу;

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

Методы

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

• математическая логика, включая исчисление предикатов, теория алгоритмов;

• дискретная математика, в том числе комбинаторика, теория графов, теория автоматов и регулярных языков;

• теория вероятности.

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

В диссертационной работе получены следующие результаты.

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

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

• Для поиска в наборах XML-документов представлены алгоритмы, позволяющие оценивать эффективность индексов с позиции временных затрат на вычисление XPath-запросов.

• Разработан алгоритм построения эффективных индексов для поиска данных в наборах полуструктурированных документов. Разработан алгоритм построения эффективных индексов для поиска данных в потоках полуструктурированных документов.

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

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

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

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

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

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

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

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

Основные результаты диссертации докладывались на конференциях: «Ломоносовские чтения» 2005 г.; на Третьей международной конференции по проблемам управления 2006 г. На семинарах: «Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина на механико-математическом факультете МГУ имени М. В. Ломоносова в 2007 и 2008 г.; на семинаре под руководством проф. С. Д. Кузнецова в Институте системного программирования РАН в 2008г.; на семинаре Московской секции ACM SIGMOD под руководством проф. Л. А. Калиниченко в 2009 г.

ПО ТЕМЕ ДИССЕРТАЦИИ опубликовано 6 печатных работ, из которых 3 [1-3] в списке журналов, рекомендованных в ВАК РФ.

1. С.С. Горелов, В.А. Васенин. Усечение пространства поиска в полуструктурированных базах данных при помощи иерархии схем документов. Журнал «Программирование». Вып. 6, 2005, стр.41-55. (С.С. Горелову принадлежат доказательства теорем 1 и 2).

2. С.С. Горелов. Оптимальные иерархии схем для поиска по конъюнктивным регулярным путевым запросам в полуструктурированных базах данных. Журнал «Программирование». Вып. 4, 2006, стр.38-56.

3. С.С. Горелов. Модели и алгоритмы для систем поиска в наборах документов. Журнал «Информационные технологии». Вып. 1, 2009, стр.61-66.

4. С.С. Горелов. Построение иерархии схем по потоку полуструктурированных документов. Сборник «Информационные технологии и программирование», Вып. 3(12), 2004, стр.45-64.

5. 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).

6. 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.

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

4.4. Выводы

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

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

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

Заключение

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

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

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

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

Разработан алгоритм построения эффективных индексов для поиска данных в наборах полуструктурированных документов. Разработан алгоритм построения эффективных индексов для поиска данных в потоках полуструктурированных документов.

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

1. Афонин С. А. Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов // Вычислительные технологии. — 2007. — Т. 12, № 2. — С. 23-32.

2. Васенин В. А., Афонин С. А., Коршунов А. А. К созданию концепции интегрированной системы распределённых информационных ресурсов Московского государственного университета им. М.В. Ломоносова. — М.: Изд-во МГУ, 2001.— С. 112.

3. Вирт Н. Алгоритмы и структуры данных. — Москва «МИР», 1989.— С. 286-301.

4. Горелов С. С. Построение иерархии схем по потоку полуструктурированных документов // Информационные технологии и программирование. — 2004. — Т. 12, № 3. — С. 4564.

5. Горелов С. С. Оптимальные иерархии схем для поиска по конъюнктивным регулярным путевым запросам в полуструктурированных базах данных // Программирование. — 2006. Т. 4. - С. 38-56.

6. Горелов С. С., Васенин В. А. Усечение пространства поиска в полуструктурированных базах данных при помощи иерархии схем документов // Программирование. — 2005. — Т. 6.-С. 41-55.

7. Гринев М., Кузнецов С., Фомичев А. XML-СУБД Sedna: технические особенности и варианты использования // Открытые системы. — 2004. — Т. 4. — С. 36-43. http: //www.citforum.ru/database/articles/sedna/.

8. Дейт К. Д. Введение в системы баз данных. — М: издательский дом Вильяме, 2001.— С. 1328.

9. Козлов Д. Д., Белова А. А. Исследование эффективности применения методов совместного анализа текстов и гиперссылок для поиска тематических сообществ // Интернет-математика 2005: автоматическая обработка веб-данных.— 2005.— Т. 5, № 1.— С. 250-271.

10. Липаев В. В. Программная инженерия. Методологические основы. — М.: изд-во ТЕИС, 2006.-С. 609.

11. Марков А. А., Нагорный Н. М. Теория алгоритмов. — Наука, 1984.— С. 304.

12. Новак JJ. Г., Кузнецов С. Д. Свойства схем данных XML // Труды Института системного программирования. — 2003. — Т. 4.

13. Смит Б. Методы и алгоритмы вычислений па строках. — Вильяме, 2006. — С. 496.

14. Abiteboul S., Vianu V. Regular path queries with constraints // 16th ACM Symposium on Principles of Database Systems. — 1997. — Pp. 122-133. cite-seer.ist.psu.edu/abiteboul98regular.html.

15. Afonin S., Khazova E. Membership and finiteness problems for rational sets of regular languages // International Journal of Foundations of Computer Science.— 2006.— Vol. 17, no. 3. Pp. 493-506.

16. Afonin S., Khazova E. Semigroups of regular languages over one letter alphabet are rational // 12th International Conference on Automata and Formal Languages, AFL'08. — 2008. — Pp. 112.

17. Borgelt C., Berthold M. R. Mining molecular fragments: Finding relevant substructures of molecules // ICDM '02: Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02). —Washington, DC, USA: IEEE Computer Society, 2002. — P. 51.

18. Buneman P. Semistructured data // 16th ACM Symposium on Principles of Database Systems.— 1997.— Pp. 117-121. citeseer.ist.psu.edu/buneman97semistructured.html.

19. Chen Q., Lim A., Ong K. W. D(k)-index: An adaptive structural summary for graph-structured data 11 SIGMOD. — 2003. Pp. 134-144.

20. Chung C., Min J., Shim K. Apex, an adaptive path index for xml data // SIGMOD. — 2002. — Pp. 121-132.

21. Clark J. XSL Transformations (XSLT) Version 1.0. — 1999. http://www.w3.org/TR/xslt.

22. Clark J., DeRose S. XML Path Language (XPath) Version 1.0.— 1999. http://www.w3.org/TR/xpath.

23. Clark J., Murata M. RELAXNG Tutorial, OASIS Working Draft. — 2001. http://www.oasis-open.org/committees/relax-ng/tutorial.html.

24. Cowan J., Tobin R. XML Information Set. — 2001. http://www.w3.org/TR/xml-infoset/.

25. Deutsch A., Fernandez M., Suciu D. Storing semistructured data with stored // SIGMOD '99: Proceedings of the 1999 ACM SIGMOD international conference on Management of data. — New York, NY, USA: ACM, 1999. Pp. 431-442.

26. Exploiting local similarity for efficient indexing of paths in graph structured data / R. Kaushik, P. Shenoy, P. Bohannon, E. Gudes // ICDE. — 2002. cite-seer.ist.psu.edu/kaushik02exploiting.html.

27. Bray Т., Paoli J., Sperberg-McQueen С. M. et al. Extensible Markup Language (XML) 1.0 (Fourth Edition). — 16 August 2006. http://www.w3.org/TR/2006/REC-xml-20060816/.

28. A fast index for semistructured data / B. Cooper, N. Sample, M. J. Franklin et al. // The VLDB Conference. — 2001. — Pp. 341-350. citeseer.ist.psu.edu/cooper01fast.html.

29. Fernandez M., Malhotra A., Marsh J. XQuery 1.0 and Xpath 2.0 Data Model.— 2003. http://www.w3.org/TR/xpath-datamodel/.

30. Fernandez M. F., Suciu D. Optimizing regular path expressions using graph schemas // ICDE. — 1998. — Pp. 14-23. citeseer.ist.psu.edu/fernandez98optimizing.html.

31. Florescu D., Kossmann D. A performance evaluation of alternative mapping schemes for storing XML data in a relational database: Tech. rep.: 1999. cite-seer.ist.psu.edu/florescu99performance.html.

32. Gorelov S. S. Optimal schema hierarchies in searching semistructured databases by conjunctive regular path queries // Programming and Computer Software. — 2007. — Vol. 32, no. 4. — Pp. 215-227.

33. Gorelov S. S., Vasenin V. A. Search optimization in semistructured databases using hierarchy of document schemas // Programming and Computer Software. — 2006.— Vol. 31, no. 6.— Pp. 321-331.

34. Henzinger M. R., Henzinger Т. А., Корке P. W. Computing simulations on finite and infinite graphs // IEEE Symposium on Foundations of Computer Science. — 1995.— Pp. 453-462. citeseer.ist.psu.edu/henzinger96computing.html.

35. High Performance MySQL / Z. Peter, S. Baron, T. Vadim et al. — O'Reilly, 2008. — P. 708.

36. IBM DB2 9 New Features / P. Zikopoulos, G. Baklarz, L. Katsnelson, C. Eaton. — McGraw-Hill Professional, 2007. — P. 422.

37. Inokuchi A., Washio Т., Motoda H. An apriori-based algorithm for mining frequent substructures from graph data. // PKDD. — 2000.— Pp. 13-23.

38. IS О/IE С 19757-3:2004. Document Schema Definition Languages (DSDL). — 2004. http://dsdl.org/.

39. Kawaguchi K. W3C XML Schema Made Simple.— 2001. http: //www.xml.com/pub / a /2001/06/06/schemasimple.html.

40. Kuramochi M., Karypis G. Frequent subgraph discovery // ICDM. — 2001.— Pp. 313-320. citeseer.ist.psu.edu/kuramochi01frequent.html.

41. Kwong A., Gertz M. Schema-based optimization of XPath expressions.— 2002. cite-seer.ist.psu.edu/kwong02schemabased.html.

42. Lore: A database management system for semistructured data / J. McHugh, S. Abiteboul, R. Goldman et al. // SIGMOD Record1997.- Vol. 26, no. 3.— Pp. 54-66. cite-seer.ist.psu.edu/mchugh9 71or e .ht ml.47