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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Барашев Дмитрий Валерьевич

ОПТИМИЗАЦИЯ ВЫПОЛНЕНИЯ ЗАПРОСОВ В РАСПРЕДЕЛЕННЫХ НЕОДНОРОДНЫХ СИСТЕМАХ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Санкт-Петербург - 2004

Работа выполнена на Кафедре исследования операций

Математико-механического факультета Санкт-Петербургского государственного университета

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

Официальные оппоненты: доктор физико-математических наук, профессор Терехов Андрей Николаевич кандидат физико-математических наук Мартынов Максим Геннадьевич

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

Защита состоится сипрых 2004 г. в № час. ОО МИн.

на заседании диссертационного совета Д.212.232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский просп.,28, Математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке им. М.Горького Санкт-Петербургского государственного университета по адресу:

199034, г. Санкт-Петербург, Университетская набережная, 7/9.

Автореферат разослан

Ученый секретарь диссертационного совета,

доктор физ.-мат. наук., Мартыненко Б. К.

профессор

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

Актуальность темы. Данная работа посвящена:

♦ Изучению способов построения распределенных виртуальных XML документов, объединяющих разнородные источники слабоструктурированных данных.

♦ Исследованию алгоритмов выполнения запросов в виде регулярных выражений в распределенных XML документах

♦ Составлению эталонных тестов производительности для СУБД, поддерживающих запросы в виде регулярных выражений к XML документам.

Актуальность этой темы в настоящее время подтверждается:

♦ огромной популярностью формата XML как средства для обмена информацией между различными приложениями

♦ возрастающим интересом к распределенным базам данных

♦ большим количеством исследований в области языков запросов XML данных

Целями работы являются:

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

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

♦ построение эффективных алгоритмов выполнения запросов в виде регулярных выражений

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

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

Научная новизна. В работе получены следующие основные результаты:

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

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

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

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

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

Апробация работы Основные результаты работы докладывались:

♦ на Шестой Восточно-Европейской конференции "Advances in Databases and Information Systems" (Братислава, Словакия, сентябрь 2002)

♦ на семинаре Documentographic Information Systems в Чешском Техническом Университете (Прага, декабрь 2002)

♦ t на семинаре Московской секции ACM SIGMOD (Москва, март 2003)

♦ на семинарах группы теории баз данных при лаборатории исследования операций НИИММ СПбГУ

Публикации. Основные результаты опубликованы в работах [1]-[3]

Структура и объем работы Диссертация состоит из введения, трех глав, заключения и списка литературы. Основной текст диссертации занимает 65 страниц машинописного текста. Библиография содержит 77 наименований. Общий объем диссертации 74 страницы. В диссертации содержится 20 рисунков и 12 таблиц.

Содержание работы

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

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

Эти работы разбиты на группы по признаку наличия некоторой ключевой технологии. В первом разделе приведен обзор работ, базирующихся на идее реляционной декомпозиции слабоструктурированных данных. Рассмотрены проекты STORED и XISS. Во втором разделе описывается проект XPath Accelerator, использующий многомерные структуры данных для представления XML документов и многомерные индексы для выполнения запросов. В третьем разделе рассматривается проект Index Fabric, использующий принципы динамического хеширования, а именно trie-структуры, для хранения документов.

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

Во втором разделе формулируются правила построения модели распределенного документа. Распределенным документом db называется дерево XML документа, вершины которого разбиты на т непересекающихся множеств где каждое dbt хранится на отдельном сетевом узле Ni. Любые две вершины, принадлежащие одному сетевому узлу, должны быть соединены цепью, не содержащей перекрестных ссылок. Перекрестной ссылкой называется направленная дуга между вершинами V е dbi и и е dbj,i Ф j. Если для двух сетевых узлов

существует перекрестная ссылка то эти узлы находятся в отношении родитель-ребенок.

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

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

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

1. Операции вставки и удаления из дерева не приводят к перенумерации

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

Номера вершин являются рациональными числами, определяемыми следующим правилом:

где а является меткой входящей в вершину v дуги, depth(v) глубиной вершины v в дереве, a Num(a) является порядковым номером а в алфавите Корень дерева получает номер q(root) = 0.

Доказывается теорема о том, что вершины v and и находятся в отношении предок-потомок тогда и только тогда, когда выполняются неравенства:

q(v) = q{parent(v)) +

Num(a)

(|Е| + l^P'M«-)

q(v) < q(u) < q(v) + 7

1

Пользуясь утверждением 1, алгоритмы выполнения запроса могут мгновенно решать задачу выяснения родства двух вершин trie-структуры.

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

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

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

1. Состояние ожидания

2. Локальные вычисления

3. Делегирование запроса другим узлам

4. Возврат, результатов вызывающему узлу

5. Обработка полученных результатов

В слабо связанной сети каждый узел, получивший управление, проходит через состояния 1-2 и в состоянии 3 передает управление видимым ему узлам, если таковые имеются. Собрав результаты, узел обрабатывает их в состоянии 5 и возвращает обработанный результат вызывающему узлу.

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

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

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

тей; сжатие позволяет более эффективно использовать дисковое пространство.

Запросами к хранилищу являются регулярные выражения, в алфавит S которых внесены дополнительные символы-разделители меток и символьных данных. Примером запроса может быть:

library/. */article (si'P/ti.tle

Считается, что в хранилище поступают запросы одного из трех видов:

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

Для ответа на запросы 1-го типа в В-дереве выполняется поиск по диапазону [Л, Ле), где е - символ,, больший чем любой другой символ алфавита XJ. Благодаря упорядоченности ключей В-дерева, мы найдем таким образом все ключи, начинающиеся с заданного префикса А, что и будет ответом.

Запросы 2-го типа обрабатываются в два шага. Сначала выполняется поиск по диапазону [А, Ле), который, однако, не доходит до листовых страниц В-дерева, а останавливается во внутренних страницах, как только определит лес страниц, листья которого содержат только ключи из указанного интервала за исключением, может быть, листьев, содержащих концы интервала. После этого в лесу выполняется запрос 3-го типа.

Обработка запросов 3-го типа начинается с вычисления величины rdepth(Q,l) - глубины имени узла Z, имеющегося в фиксированном суффиксе В запроса относительно начала суффикса. Относительной глубиной имени считается позиция начала имени узла относительно начала суффикса. Верно утверждение, что если суффикс строки S, начинающийся в позиции удовлетворяет суффиксу В запроса 3-го типа то

п < depth(l) — rdepth(Q, I)

10

для любого имени 1 из суффикса В. Из этого утверждения следует, что в строке S удовлетворять запросу может только префикс длиной

min depth(l) — rdepth(Q, I) + length[B)

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

Четвертая глава посвящена практическим экспериментам по реализации локального хранилища и алгоритма отсечения веток В-дерева, описанного в третьей главе. Целью экспериментов является проверка гипотезы о том, что использование В-дерева в качестве хранилища данных и алгоритма отсечения веток дает преимущества в скорости выполнения запросов, несущих в себе требуемую для алгоритма информацию. Реализация предложенных алгоритмов, называемая RegXP, написана на языке Java. В качестве объекта сравнения была выбрана популярная свободная система выполнения запросов к XML документам Kweelt.

В первом и втором разделах представлена спецификация эталонного теста производительности СУБД, поддерживающих выполнение запросов в виде регулярных выражений к XML документам. Тест является модификацией известного эталонного теста XMach-1.

Среда выполнения теста состоит из четырех компонент: XML СУБД, HTTP-сервера, загрузчиков документов в СУБД и виртуальных клиентов, имитирующих работу пользователей с веб-браузером. Клиенты, пользуясь протоколом HTTP последовательно посылают серверу информацию о запросах, которые они хотели бы выполнить. Jam-сервлеты разбирают запрос клиента и конструируют запросы к XML СУБД. Для проведения экспериментов написан код сервлетов, осуществляющих связь с системами

Время, затрачиваемое на общение клиентов и HTTP-сервера не учитывается при вычислении времени обработки запросов. Временем вычисления запроса считается интервал между мо-

ментом поступления запроса на HTTP-сервер и отправкой результатов запроса клиенту.

Тестовый набор данных, являющихся объектом запросов, состоит из большого количества относительно небольших по размеру документов-продуктов и одного большого, по сравнению с остальными документами, документа-каталога, содержащего в себе информацию о документах-продуктах. Структура документов-продуктов напоминает структуру статьи или книги, в то время как структура документа-каталога имитирует структуру URL и других "регистрационных данных" документов-продуктов. Генерация тестового набора оставлена неизменной по сравнению с оригинальным тестом XMach-1

Тест состоит из двух частей. В первой части, являющейся сужением оригинального теста XMach-1, виртуальный клиент поочередно отправляет на сервер запросы одного из трех типов, которые на естественном языке выражаются так:

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

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

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

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

Номер Вид запроса

1 random-label-sequence/.*

2__random-label-sequence/.*/random-label-sequence

3 .*/random-label-sequence

Части random-label-sequence запросов состоят из случайной ' последовательности меток, разделенных символом-разделителем '/'. Метки, входящие в последовательности, чаще всего действительно встречаются в документе-каталоге, но иногда туда включаются не существующие в каталоге метки. Запросы разных видов не смешиваются во время выполнения теста.

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

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

Время выполнения запросов второго и третьего типов сравнимо или меньше, по сравнению с системой Kweelt

Графики, визуализирующие результаты второй части теста, говорят о том, что система RegXP выполняет генерируемые этой частью теста запросы стабильно быстрее чем Kweelt.

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

Основные положения диссертации, выносимые на защиту

♦ Способ организации распределенных неоднородных данных во множество виртуальных распределенных XML документов.

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

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

♦ Алгоритмы выполнения запросов в виде регулярных выражений в сильно и слабо связанных сетях.

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

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

[1] D.Barashev, B.Novikov Indexing XML to support path expressions Proceedings of the Sixth East-European Conference on Advances in Databases and Information Systems Vol.2. Bratislava, Slovakia, 2002

[2] D. Barashev, M. Kratky, T. Skopal Modern Approaches to Indexing XML Data Sbornik vedeckych ргасг VEB-Technickd univerzita Ostrava, Ostrava, Czech Republic, 2003

[3] Барашев Д.В. Поддержка регулярных выражений в запросах к распределенным XML документам Труды Пятой Всероссийской научной конференции "Электронные Библиотеки" Санкт-Петербург, 2003

ЛР № 040815 от 22.05.97.

Подписано к печати 03.03.2004 г. Формат бумаги 60X84 1/16. Бумага офсетная. Печать ризографическая. Объем 1 усл. п.л. Тираж 100 экз. Заказ 3181. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26.

«-И1Т1

1 Введение

1.1 Слабоструктурироваиные данные

1.1.1 Формат XML.

1.1.2 XML и базы данных.

1.1.3 Поддержка платформы XML производителями СУБД

1.1.4 Основные термины.

1.2 Языки формулировки запросов слабоструктурированиых данных.

1.3 Задача выполнения поиска по регулярному выражению

2 Родственные работы

2.1 Реляционные схемы

2.1.1 STORED.

2.1.2 XISS.

2.2 Многомерные схемы.

2.2.1 XPath Accelerator.

2.3 Схемы на основе Trie-структур.

2.3.1 Index Fabric.

3 Построение распределенного документа и выполнение в нем запросов

3.1 Высокоуровневые требования к системе и к ее компонентам

3.2 Модель распределенного XML документа.

• 3.2.1 Префиксное PATRICIA дерево . ■.

3.2.2 Нумерация вершин PATRICIA дерева.

3.2.3 Правило нумерации.

3.2.4 Решение проблемы выяснения родства.

3.2.5 Тины связей между сетевыми узлами.

3.3 Эффективность алгоритма выполнения запроса.

3.4 Выполнение запроса.

3.4.1 Поиск в слабо связанной системе.

3.4.2 Поиск в силыю связанной системе.

3.5 Реализация локального хранилища.

3.6 Выводы.

4 Экспериментальные результаты

4.1 Спецификация эталонного теста RegXPBench.

4.1.1 Архитектура среды выполнения теста.

4.1.2 Генерация тестовых данных.

4.1.3 Выполнение теста: часть первая.

4.1.4 Выполнение теста: часть вторая.

4.2 Реализация тестовой системы.

4.3 Эксперименты и анализ результатов.

4.4 Выводы .G

Распределенные базы данных активно изучаются с середины 70-х годов. Различным аспектам распределенных БД, таким как выявление тупиков [24], моделирование производительности [41], посвящено множество работ. Однако, по многим техническим и маркетинговым причинам, распределенные БД до недавнего времени не были широко востребованы. Сейчас интерес к распределенным БД возрождается. Для этого есть несколько причин [33]:

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

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

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

4. Рынок, требующий от компаний более гибкой структуры их бизнеса.

Сеть World Wide Web предоставила удобную инфраструктуру для создания распределенных баз данных, однако для хранения данных в настоящее время используется множество форматов, далеко не всегда совместимых между собой и удобных для запросов. Так, например, информация о цепах на компьютерные комплектующие может быть представлена в виде набора генерируемых базой данных HTML страниц на специальном сайте, в виде документов Microsoft Excel па сайтах компаний, торгующих комплектующими; описания и пресс-релизы могут существовать в форматах HTML, PDF и прочих; вся эта информация разбросана но десяткам сайтов. Формулирование и выполнение запросов в такой среде крайне затруднено. Единый формат хранения данных решил бы проблему, однако, требовать перевода всей информации в какой-то единый формат уже практически невозможно; настолько же невозможно требовать, чтобы все данные удовлетворяли какой-то единой структурированной метамодели. Появившийся в середине 90-х годов термин слабоструктурированные данные [64, 73], обозначающий данные, не имеющие четко определенной структуры, но являющиеся вместо этого самоописывающими, предоставил новую абстракцию для интеграции разрозненной информации. Исследования в этой области привели к созданию многих вариантов модели данных, формата хранения и языков запросов [75]. В настоящее время стандартами de-facto являются формат XML и языки запросов XPath и XQuery. Появилась "мечта" об универсальном представлении распределенной, разнородной, но семантически схожей информации в виде виртуального XiML документа, который поддерживается совместно участниками распределенной БД и позволяет выполнять XPath или XQuery запросы [23]. Данная работа посвящена исследованию возможности построения таких документов и выполнению в них запросов в виде регулярных выражений.

Работа организована следующим образом: в разделе 1.1 приводится введение в слабоструктурированные данные и XML; разделы 1.2 и 1.3 посвящены запросам слабоструктурированных данных вообще и запросам в виде регулярных выражений в частности. В главе 2 дай обзор методов храпения и индексирования слабоструктурировапиых данных, использующих существующие наработки. В главе 3 онисаиы модель данных, алгоритмы и варианты реализации структур данных для выполнения поиска по регулярному выражению в распределенном документе, а в главе 4 при веде и ы э кс и ери м е и тал ы i ы е резул ьтаты.

З.б Выводы

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

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

4 Экспериментальные результаты

В этой главе представлены описание и результаты практических экспериментов по реализации локального хранилища и алгоритма отсечения веток В-дерева, описанных в разделе 3.5. Целью экспериментов являлась проверка гипотезы о том, что использование В-дерева в качестве хранилища данных и алгоритма отсечения веток дает преимущества в скорости выполнения запросов, несущих в себе требуемую для алгоритма информацию. В качестве объекта сравнения была выбрана популярная свободная система выполнения запросов к XML документам Kweelt [2].

4.1 Спецификация эталонного теста RegXPBench

В настоящее время известно несколько эталонных тестов производительности XML баз данных: [56, 44, 15, 14]. Для тестирования хранилища RegXP совместно со студентом Сергеем Малеванным был разработан эталонный тест RegXPBench [72], являющийся модификацией известного теста XMach-1 [14].

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

Эталонный тест производительности XML баз данных XMach-1 [14] основан на веб-приложении, которое моделирует типичную работу пользователей с XML СУБД. Архитектура среды выполнения данного теста показана на рис. 14. Среда выполнения состоит из четырех компонент: XML СУБД, HTTP-сервера, загрузчиков документов в СУБД и виртуальных клиентов, имитирующих работу пользователей с веб-браузером. Тестовый набор данных состоит из большого количества относительно небольших по размеру докумс?тов-продукгпов (предполагается, что они были загружены с различных интернет-источников при помощи программ-загрузчиков) и одного большого, по сравнению с остальными документа

Тестируемая система

База данных

Поисковый механизм О

API базы данных каталог

Документы продукты

HTTP сервер

Servlet

Виртуальные клиенты О

Протокол HTTP

Загрузчики документов

Рис. 14: Архитектура среды выполнения эталонного теста RegXPBench ми, документа-каталога, содержащего в себе информацию о документах-продуктах. Каждый документ-продукт имеет уникальный идентификатор (URI), который вместе с метаданными об этом документе, хранится в документе-каталоге.

Во время работы теста виртуальные клиенты устанавливают соединения с HTTP-сервером и посылают информацию о запросах, которые они хотели бы выполнить. Поскольку предметом теста является эффективность выполнения запросов внутри СУБД, то время, затрачиваемое на общение клиентов и HTTP-сервера не учитывается при вычислении времени обработки запросов. Временем вычисления запроса считается интервал между моментом поступления запроса на HTTP-сервер и отправкой результатов запроса клиенту. Метрикой производительности считается количество выполненных запросов за единицу времени.

4.1.2 Генерация тестовых данных

Оригинальная процедура генерации тестовых данных теста XMach-1 сохранилась неизменной в RegXPBench. Генератор создает заданное количество документов-продуктов, назначает каждому из них уникальный идентификатор и помещает запись о документе в каталог. Документы-продукты внешне напоминают обычные статьи и относятся к классу тпексто-ориеитированных (document centric) документов. Базовое DTD документа-продукта показано на рис. 15. Поскольку маловероятно, что XML документы, пришедшие с различных веб-источников, будут иметь одинаковое DTD, то генератор XMach-1 порождает разнообразные DTD, модифицируя базовое путем приписывания целых чисел к каждому из имен элементов, кроме элементов author и link. Так, DTD N-ro документа будет иметь элементы с именами: documentN, chapterN, author, sectionN и т.д. Наличие в экземпляре докумепта-иродукта необязательных элементов DTD, глубина вложенности элементов section, а также некоторые другие характеристики определяются случайным образом по заданной таблице вероятностей. Содержимое символьных секций документов-продуктов генерируется но закону Зипфа [57] из словаря, содержащего 10000 слов английского языка.

Документ-каталог относится к классу структурно-ориентированных (data centric)1 документов. Его внутренние элементы имитируют дерево доменных имен и путей внутри каждого домена, а в листьях содержится небольшое количество метаипформации о документах-продуктах (рис. 16). Таким образом, документ-каталог является ветвистым деревом высотой 5-8 элементов без символьных секций. Пример каталога, содержащего 1 документ показан па рис. 17 термины тсксто-ориентированный и структурно-ориентированный противоречат встречающимся в русских переводах [GO] терминам документ, ориентированный па документ и документ, ориентированный на данные, однако, мы считаем маши термины более короткими и благозвучными и рассматриваем их как попытку дополнить русскую терминологию платформы XML [СУ]

ELEMENT document (title, chapter+)>

ATTLIST document author CDATA #IMPLIED doc.id ID #IMPLIED>

ELEMENT author (#PCDATA)>

ELEMENT title (#PCDATA)>

ELEMENT chapter (author?, head, section+)>

ATTLIST chapter id ID #REQUIRED>

ELEMENT section (head, paragraph+, section*)>

ATTLIST section id ID #REQUIRED>

ELEMENT head (#PCDATA)>

ELEMENT paragraph (#PCDATA I link)*>

ELEMENT link EMPTY>

ATTLIST link xlink:type (simple) #FIXED "simple" xlink:href CDATA #REQUIRED>

Рис. 15: Базовое DTD документа-продукта 4.1.3 Выполнение теста: часть первая

В первой части теста запускается виртуальный клиент, который поочередно отправляет на сервер запросы одного из трех типов, указанных в табл. 6. Эти запросы являются подмножеством запросов теста XMach-1, которое можно переписать, используя регулярные выражения. Количество генерируемых запросов каждого типа определяется перед началом тестового сеанса, а порядок генерации запросов определяется случайным образом. Запросы каждого тина выполняются при помощи регулярных выражений следующим образом:

Тип 1 Документы-продукты поочередно перебираются и на каждом их них выполняется запрос phrase/.*

ELEMENT directory (host+) > <!ELEMENT host (host+ I path+) > <!ATTLIST host name CDATA # REQUIRED > <!ELEMENT path (path+ I docinfo) > <!ATTLIST path name CDATA # REQUIRED > <!ELEMENT docinfo EMPTY > <!ATTLIST docinfо docid ID # REQUIRED loader CDATA # REQUIRED inserttime NMTOKEN # REQUIRED update.time NMTOKEN # IMPLIED >

Рис. 16: DTD документа-каталога

Если результатом запроса является непустое множество, то выполняется второй запрос */value-of(docid) который возвращает атрибут docid документа

Тин 2 Документы-продукты поочередно перебираются и па каждом их них выполняется запрос */docid =doc idpararneter который проверяет, совпадает ли docid очередного документа с искомым. Если результатом' является непустое множество, то выполняется второй запрос */section7mm&er/headmtm&er/value-of(. *) возвращающий требуемый результат directory> ahost name=5com'> bhost name='test-company'> <chost name='www'> apath name='products'> bpath name='overview.xml'> <docinfo docid='2' loader='robot1' inserttime='20000110152530'/> bpath> </apath> </chost> </bhost> </ahost> </directory>

Рис. 17: Пример доку мента-каталога

Тип 3 Запросы третьего типа применяются к документу-каталогу. Регулярное выражение запроса имеет общий вид: ahost / bhost / chost / apath/bpath / cpath /. *

Поскольку количество параметров данного запроса является переменным, что на практике означает, что отсутствующие в конкретном экземпляре запроса параметры' не определены, то неопределенные параметры пропускаются при составлении регулярного выражения. Так, запрос с тремя переданными параметрами ahost, bhost и apath записывается следующим образом: ahost / bhost /. */apath /. *

Тип Описание Параметры

1 Получить идентификаторы всех документов, содержащих данную фразу Фраза

2 Вернуть список элементов документа с заданным id, которые являются детьми элементов section с заданным номером Идентификатор документа и номер раздела

3 Выдать имена документов, URL которых соответствует заданному образцу От 1 до всех 6 компонент URL

5 Заключение

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

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

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

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

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

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

• Реализован прототип локального хранилища слабоструктурировап-пых данных.

• Разработаны эталонные тесты производительности выполнения запросов в виде регулярных выражений. Тесты являются адаптированным подмножеством эталонных тестов производительности XML баз данных XMach-1.

• Проведена серия экспериментов по сравнению RegXP с системой выполнения запросов к XML документам Kweelt. Полученные результаты говорят об эффективности предложенного в RegXP алгоритма оптимизации выполнения запроса.

1. GNU Regexp Java Library.http://www.cacas.org/j ava/gnu/regexp/.2. Kweelt.http://kweelt.sourceforge.net.

2. Object Data Standard: ODMG 3.0. http://www.iso.org.4. Oracle XML DB.http://otn.oracle.com/tech/xml/techinfо.html.

3. SQL 1999 standard, http://www.iso.org.

4. G. The Unicode Standard, http://www.Unicode.org.

5. Serge Abiteboul. Querying semi-structured data. In Database Theory -ICDT '97, 6th International Conference, Delphi, Greece, January 8-10, 1997, Proceedings, volume 1186 of Lecture Notes in Computer Science, pages 1-18. Springer, 1997.

6. Serge Abiteboul, Dalian Quass, Jason McHugh, Jennifer Widom, and Janet L. Wiener. The Lorel query language for semistructured data. International Journal on Digital Libraries, l(l):68-88, 1997.

7. Apache Software Foundation. XIndice User Manual. http://xml.apache.org/xindice.

8. Francois Bancilhon. Object databases. ACM Computing Surveys (CSUR), 28(1): 137—140, 1996. http://doi.acm.org/10.1145/234313.234373.

9. Dmitry Barashev. Supporting regular expressions in queries to distributed XML documents. In Proceedings of the Fifth Russian Conference on Digital Libraries, 2003.http://rcdl2003.spbu.ru.

10. Dmitry Barashev, Michal Kratky, and Tomas Skopal. Modern approaches to indexing XML data. Sbornik vedeckych praci, 2003.

11. Dmitry Barashev and Boris Novikov. Indexing XML to support path expressions. In Proceedings of the Sixth East-European Conference on Advances in Databases and Information Systems, volume 2, 2002. http://www.dcs.elf.stuba.sk/adbis2002.

12. Timo B5hme and Erhard Rahm. XMach-1: A Benchmark for XML Data Management. In Datenbanksysteme in Biiro, Technik und Wissenschaft (BTW), 9. GI-Fachtagung, Oldenburg, 7.-9. Marz 2001, Proceedings, Informatik Aktuell. Springer, 2001.

13. Peter Buneman. Semistructured data. In Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 117-121. ACM Press, 1997.

14. Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, and Dan Suciu. A query language and optimization techniques for unstructured data. In Proceedings of the 1996 ACM SIGMOD International Conference on

15. Management of Data, Montreal, Quebec, Canada, June Jr6, 1996, pages 505-516. ACM Press, 1996.

16. Brian Cooper, Neal Sample, Michael J. Franklin, Gisli R. Hjaltason, and Moshe Shadmon. A fast index for semistructured data. In Proceedings of 27th International Conference on Very Large Data Bases, pages 341350. VLDB, 2001.

17. J. Robie D. D. Chamberlin and D. Florescu. Quilt: An XML Query Language for Heterogeneous Data Sources. In Proceedings of the 3rd ACM SIGMOD WebDB Workshop, pages 53-62, 2000.

18. Alin Deutsch, Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. A query language for XML. Computer Networks, 31(11-16):1155-1169, 1999.

19. Alin Deutsch, Mary Fernandez, and Dan Suciu. Storing semistructured data with STORED. In Proceedings of the 1999 ACM SIGMOD international conference on Management of data, pages 431-442. ACM Press, 1999.

20. Paul F. Dietz. Maintaining order in a linked list. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pages 122-127, 1982.

21. Edd Dumbill. Distributed XML.http://www.xml.com/pub/a/ws/2000/09/06/distributed.html.

22. Ahmed K. Elmagarmid. A survey of distributed deadlock detection algorithms. ACM SIGMOD Record, 15(3):37-45, 1986.

23. R. J. Enbody and II. C. Du. Dynamic hashing schemes. ACM Computing Surveys (CSUR), 20(2):850-113, 1988.http://doi.acm.org/10.1145/46157.330532.

24. M. Fernandez, J. Simeon, P. Wadler, S. Cluet, A. Deutsch, D. Florescu, A. Levy, D. Maier, J. McHugh, J. Robie, D. Suciu, and J. Widom. XML query languages: Experiences and exemplars. 1999.http: //www-db. research. belllabs. com/user/simeon/xquery. ps.

25. Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. A query language for a web-site management system. ACM SIGMOD Record, 26(3):4-ll, 1997.http://doi.acm.org/10.1145/262762.262763.

26. Daniela Florescu and Donald Kossmann. Storing and querying XML data using an RDMBS. IEEE Data Eng. Bull., 22(3):27-34, 1999.

27. Torsten Grust. Accelerating XPath location steps. In Proceedings of ACM SIGMOD 2002, June 4-6, Madison, USA, 2002.

28. Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of ACM SIGMOD 1984, Annual Meeting, Boston, USA, pages 47-57. ACM Press, 1984.

29. IBM. XML Extender Brochure, 2000.http://www-3.ibm.com/software/data/db2/extenders/xmlext/.

30. David Konopnicki and Oded Shmueli. W3QS: A query system for the World-Wide Web. In VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland, pages 54-65. Morgan Kaufmann, 1995.

31. Donald Kossmann. The state of the art in distributed query processing. ACM Computing Surveys (CSUR), 32(4):422-469, 2000.http://doi.acm.org/10.1145/371578.371598.

32. Quanzhong Li and Bongki Moon. Indexing and querying XML data for regular path expressions. In Proceedings of 27th International Conference on Very Large Data Bases. Morgan Kaufmann, 2001.

33. Wen-Syan Li, Junho Shim, K. Selguk Candan, and Yoshinori Hara. WebDB: A web query system and its modeling, language, and implementation. In Proceedings of the IEEE Forum on Reasearch and Technology Advances in Digital Libraries, IEEE ADL '98, 1998.

34. David Lomet. The evolution of effective B-tree: page organization and techniques: a personal account. ACM SIGMOD Record, 30(3):64-69, 2001.

35. Jason McHugh, Serge Abiteboul, Roy Goldman, Dallas Quass, and Jennifer Widom. Lore: a database management system for semistructured data. ACM SIGMOD Record, 26(3):54-66, 1997.http://doi.acm.org/10.1145/262762.262770.

36. Alberto Mendelzon, George Mihaila, and Tova Milo. Querying the World Wide Web. International Journal on Digital Libraries, l(l):54-67, 1997.

37. M.Ley. How to mirror DBLP.http: //www. inf ormatik.uni-trier.de/-ley/db/about/instr.html.

38. Donald R. Morrison. PATRICIA Practical Algorithm To Retrieve Information Coded in Alphanumeric. J ACM, 15(4):514-534, 1968. http://doi.acm.org/10.1145/321479.321481.

39. Matthias Nicola and Matthias Jarke. Performance modeling of distributed and replicated databases. IEEE Transactions on Knowledge and Data Engineering, 12(4):645-672, 2000.

40. Yannis Papakonstantinou, Hector Garcia-Molina, and Jennifer Widom. Object exchange across heterogeneous information sources. In

41. Proceedings of the Eleventh International Conference on Data Engineering, March 6-10, 1995, Taipei, Taiwan, pages 251-260. IEEE Computer Society, 1995.

42. Jonathan Robie, Joe Lapp, and David Schach. XML Query Language (XQL). Technical report.http://www.w3.org/TandS/QL/QL98/pp/xql.html.

43. Albrecht Schmidt, Florian Waas, Martin L. Kersten, Michael J. Carey, Ioana Manolescu, and Ralph Busse. XMark: A Benchmark for XML Data Management. In Proceedings of 28th International Conference on Very Large Data Bases, VLDB'2002, 2002.

44. Dan Suciu. Management of semistructured data. ACM SIGMOD Record, 26(4) :4-7, 1997.

45. Dan Suciu. Distributed query evaluation on semistructured data. ACM Transactions on Database Systems (TODS), 27(l):l-62, 2002.

46. W3C. CSS. http://www.w3c.org/Style/CSS.49. W3C. XScliema.http://www.w3c.org/XML/Schema.50. W3C. XSL.http://www.w3c.org/Style/XSL.

47. W3C. Extensible Markup Language (XML) 1.0, 1998. http://www.w3.org/TR/REC-xml.

48. W3C. HTML 4.01 Specification, 1999. http://www.w3.org/TR/html4.

49. W3C. XML Path Language (XPath) Version 1.0, 1999. http://www.w3.org/TR/xpath.

50. W3C. XML Linking Language (XLink) Version 1.0, 2001. http://www.w3.org/TR/2001/REC-xlink-20010627/.

51. G. K. Zipf. The Psychobiology of Language. Houghton Miffin, Boston, 1935.

52. Альфред Ахо, Рави Сети, и Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Addison-Wesley Вильяме, 2001.

53. Дмитрий Барашев, Сергей Малеванный, н Борис Хвостиченко. RegXP.http://sourceforge.net/projects/regxp.

54. GO. Рональд Буро. XML и базы данных. Открытые системы, (10), 2000.http://www.osp.ru/os/2000/10/062.htm.

55. Даниэла Флорсску, Алон Леви, и Альберто Мендельсон. Технологии баз данных для World Wide Web: обзор. СУБД, (04-05), 1998.

56. Дж. Фридл. Регулярные выражения. Библиотека программиста. O'Reilly Питер, 2001.

57. Александр Фролов and Григорий Фролов. Базы данных в Интернете. Microsoft Press, Русская Редакция, 2000.

58. Максим Гринев. Системы управления полуструктурированными данными. Открытые системы, (5-6), 1999.http://www.osp.ru/os/1999/05-06/09.htm.

59. Джон Хопкрофт, Раджив Мотвани, и Джеффри Ульман. Введение в теорию автоматов, языков и вычислений. Addison-Wesley Вильяме, 2002.

60. Борис Хвостиченко. Индексирование путей в слабоструктурироваи-ных данных. Дипломная работа, СПбГУ, мат.-мех. факультет, кафедра информатики, 2003.

61. Борис Хвостиченко и Борис Новиков. Индексирование путей в слабоструктурированных данных. Труды четвертой всероссийской конференции 'Электронные Библиотеки', 2002.

62. Дональд Кнут. Все про ТеX. Вильяме, 2003.

63. Михаил Р. Когаловский. Глоссарий по стандартам платформы XML. http: //www. elbib.ru/index.phtml?page=elbib/rus/methodology/xmlbase.

64. Михаил Р. Когаловскии. XML: Возможности и перспективы. Директор И С, 2001.

65. Михаил Р. Когаловскии. Стандарты платформы XML и базы данных. Труды Третьей Всероссийской конференции 'Электронные Библиотеки\ 2001.

66. Сергей Малеванный. Реализация эталонного теста для XML СУБД, поддерживающих запросы с регулярными выражениями. Дипломная работа, СПбГУ, мат.-мех. факультет, кафедра информатики, 2003.

67. Дмитрий Палей. Моделирование квазиструктурированных данных. Открытые системы, (9), 2002.http://www.osp.ru/os/2002/09/057.htm.

68. Александр Печерский. Язык XML практическое введение, http://www.citforum.ru/internet/xml/index.shtml.

69. Андрей Суслов. Языки запросов для XML данных. Открытые системы, (2), 2001.http://www.osp.ru/os/2001/02/065.htm.

70. Джеффри Ульман, Гектор Гарсиа-Молина, и Дженнпфер Упдом. Систелш баз данных. Полный курс. Williams, 2003.

71. Джонатан Эйиджел. XML: время пришло. LAN/Журнал сетевых решений, 1999.http://www.citforum.ru/internet/articles/xml009.shtml.