Содержание к диссертации
Введение
1 Введение 4
1.1 Слабоструктурироваиные данные 6
1.1.1 Формат XML 7
1.1.2 XML и базы данных 9
1.1.3 Поддержка платформы XML производителями СУБД 10
1.1.4 Основные термины 11
1.2 Языки формулировки запросов слабоструктурированиых данных 12
1.3 Задача выполнения поиска по регулярному выражению . 14
2 Родственные работы 16
2.1 Реляционные схемы 16
2.1.1 STORED 17
2.1.2 XISS 19
2.2 Многомерные схемы 22
2.2.1 XPath Accelerator 23
2.3 Схемы на основе Trie-структур 25
2.3.1 Index Fabric 26
3 Построение распределенного документа и выполнение в нем запросов 30
3.1 Высокоуровневые требования к системе и к ее компонентам 30
3.2 Модель распределенного XML документа 31
3.2.1 Префиксное PATRICIA дерево 32
3.2.2 Нумерация вершин PATRICIA дерева 32
3.2.3 Правило нумерации 34
3.2.4 Решение проблемы выяснения родства 34
3.2.5 Типы связей между сетевыми узлами 36
3.3 Эффективность алгоритма выполнения запроса 36
3.4 Выполнение запроса 38
3.4.1 Поиск в слабо связанной системе 39
3.4.2 Поиск в сильно связанной системе 44
3.5 Реализация локального хранилища 48
3.6 Выводы 51
4 Экспериментальные результаты 52
4.1 Спецификация эталонного теста RegXPBench 52
4.1.1 Архитектура среды выполнения теста 52
4.1.2 Генерация тестовых данных 54
4.1.3 Выполнение теста: часть первая 55
4.1.4 Выполнение теста: часть вторая 58
4.2 Реализация тестовой системы 58
4.3 Эксперименты и анализ результатов 59
4.4 Выводы G2
5 Заключение 64
- Языки формулировки запросов слабоструктурированиых данных
- Схемы на основе Trie-структур
- Эффективность алгоритма выполнения запроса
- Архитектура среды выполнения теста
Введение к работе
Распределенные базы данных активно изучаются с середины 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 приведены экспериментальные результаты.
Языки формулировки запросов слабоструктурированиых данных
С момента появления понятия слабоструктурированных данных большое внимание исследователей уделялось языкам запросов [61, 75], поскольку традиционные SQL [5, 76] и OQL [3, 10] для такого рода данных были непригодными. Требовались новые языки, обладающие более мощными средствами для извлечения информации из данных с почти неизвестной структурой и для исследования самой структуры. Одним из первых языков, получившим широкую известность, стал Lorel [8], язык запросов к серверу слабоструктурированпых данных Lore [37], оперирующий с моделью данных "граф с метками" . Своим элегантным синтаксисом этот язык похож на SQL/OQL (рис. 2), кроме того, в нем реализованы довольно мощные средства навигационных выражений. Однако, из-за небогатой модели данных, в языке отсутствует поддержка некоторых важных средств, таких как, например, упорядоченные коллекции, различие отношений содержания и ассоциации между вершинами графа. Информация извлекается только "as-is", дополнительные преобразования результатов не поддерживаются. Аналогами Lorel, использующими такую же модель данных, являются языки UnQL [17] и STRUDQL [27]
Следующая группа языков [38, 32, 35] ориентируется на поиск в Web, сочетая возможность поиска по содержанию, аналогично традиционным поисковым машинам, и структурные запросы. Эти языки уже различают "внутренние" ссылки (то есть ссылки между элементами одного документа или одного сайта) и "внешние" ссылки, ведущие на иные документы или сайты. В качестве примера можно рассмотреть язык WebSQL [38], моделирующий Web как реляционную базу данных, состоящую из двух виртуальных отношений Документ и Якорь. Запросы к этим отношениям строятся при помощи языка, подобного SQL, дополненного навигационными выражениями, позволяющими частично материализовывать виртуальные отношения. Пример запроса на WebSQL, который возвращает список ссылок идущих из документов, хранимых на заданном сайте в документы, хранимые на других сайтах, показан на рис. 3.
Языки следующего поколения [26], такие как XQL [43], XML-QL [20] и Quilt [19], постепенно привели к созданию консорциумом W3C спецификаций XPath [53] и XQuery [55], которые в настоящее время являются стандартом de-facto для приложений, обрабатывающих XML данные и являются наиболее полным способом выразить возможные запросы пользователя к слабоструктурированным данным. XPath является мощным средством записи навигационных выражений, включающим, кроме основных операций навигации, операции сравнения, логические операции, операции индексного доступа, и прочее. XQuery обладает выразительными средствами для применения XPath выражений к множеству XML документов, итерирования по XML узлам, конструирования новых узлов. Спецификации XPatJi и, в особенности, XQuery, довольно объемны и сложны, и не реализованы в полном объеме, поэтому все их практические достоинства и недостатки, возможно, еще не изучены сообществом.
Регулярные выражения [62, 58, 65] до недавнего времени широко применялись, в основном, для полнотекстового поиска в текстовых файлах. С развитием языков запросов для XML, в особенности стандартов XPath и XQuery, получили распространение навигационные выражения, основанные на регулярных выражениях, алфавит которых составлен из имен узлов XML документа. Простым примером навигационного выражения может служить выражение, определяющее все теги title , лежащие внутри тегов book или article :
В дальнейшем, термином регулярное выражение будут обозначаться традиционные регулярные выражения над каким-нибудь конечным алфавитом (например, Unicode [6]), а термином навигационное выраоюеиие будут обозначаться выражения в стиле XPath. Выражения XPath предоставляют также возможности, не свойственные регулярным выражениям, такие как, например, выборка элементов по значению какого-либо атрибута: Выражения XPath являются довольно мощным средством запросов XML данных и уже широко применяются в самых разных областях, начиная от XSL преобразовании и заканчивая запросами в коммерческих СУБД (см. раздел 1.1.3). Тем не менее, при формулировке XPath выражения пользователь должен хотя бы примерно знать множество имей, используемых в документе, и не сомневаться в написании известных ему имен. Можно представить себе ситуацию, когда пользователь сомневается в написании того или иного имени. Так, например, XML документ, описывающий коллекцию статей, может выглядеть так:
Схемы на основе Trie-структур
Подход, предложенный проектом XISS, считается эффективным для выполнения запросов, попадающих иод указанный шаблон, выполняющихся как на живых, так и на синтетических данных. Поддержка регулярных выражений не была целью его разработчиков; тем не менее, частично эта поддержка реализуется достаточно легко, Одним из важных недостатков, характерных для структур, использующих вариации нумерации Дистца, является необходимость время от времени перенумеровывать элементы.
Многомерные схемы индексирования XML документов основываются па идее представления узлов или путей как точек в некотором векторном пространстве. XML документ в таком представлении является конечным множеством точек этого пространства. Такое представление должно обладать некоторыми свойствами, позволяющими использовать многомерные индексные структуры для индексации точек.
В работе XPath Accelerator [29] предложена индексная структура на основе R-дерева [30], предназначенная для быстрой навигации по осям XML документа, определенных стандартом XPath [53]. XPath определяет 13 осей, в направлении которых возможно передвижение из данного контекстного XML узла; из них наиболее часто используются оси child, descendant, parent и ancestor. Вычисление XPath выражения состоит из последовательности навигационных шагов (location steps), каждый из которых делается в направлении одной из 13 осей. Для данного контекстного узла, ось определяет подмножество узлов XML документа, называемое также областью документа (document region), элементы которого становятся контекстными при выполнении последующих шагов.
Четыре из 13-ти осей (в дальнейшем, исключительно для краткости, они будут называться основными), а именно descendant, ancestor, following и preceding, образуют разбиение XML документа, то есть, объединение контекстного узла и областей документа, определяемых этими осями, равно всему документу и каждый узел, отличный от контекстного, содержится ровно в одной из областей; области, определяемые оставшимися осями, представляют иод- или надмножества указанных четырех областей. Проект XPath Accelerator ставит задачу построения индексной структуры, которая для данного контекстного узла сможет эффективно вычислить такое разбиение. Для решения этой задачи, узлы XML документа представляются в виде точек в 5-мерном пространстве, которое обладает некоторыми свойствами, позволяющими использовать R-дерево для индексирования. Основными двумя измерениями являются номера узлов, полученные нумерацией Диетца [22], которые образуют плоскость pre-post. Если рассмотреть точку, соответствующую какому-либо узлу XML документа, и провести через нее линии, параллельные осям координат, то окажется, что полученные четверти соответствуют разбиению документа, образованному основными XPath-осями (рис. 4). Таким образом, выполнение навигационного шага вдоль одной из основных осей сводится к запросу прямоугольной области на плоскости pre-post. Кроме того, для выполнения шагов по осям following-sibling и preceding-sibling, которые накладывают на узлы, входящие в определяемые ими области документа, ограничение общности узла-родителя, необходимо поддерживать для каждого узла v документа прямой номер узла-родителя par(v), а для выполнения шага по оси attribute необходимо поддерживать флаг атрибута att(v). Поскольку в запросах часто используются проверки имени, то следует также хранить имя каждого узла tag(v). Итак, каждый узел описывается 5-мерным дескриптором вида.
Используя R-дерево или пару В-деревьев для индексирования плоскости pre-post и составляя по несложным правилам запросы прямоугольных областей можно достаточно эффективно выполнять навигационные шаги.
Очевидным недостатком предложенной индексной структуры является необходимость ее перестроения при изменении документа. Кроме того, хоть это не афишируется, но для проверок имей узлов требуются дополнительные построения, и чем более сложными будут проверки, тем более сложные нужны индексы имен, и тем сложнее становится их синхронизация со структурными индексами.
Trie-структуры являются разновидностью деревьев поиска, в которых ветвление в каждом отдельном узле определяется не всем ключом, а какой-то его частью. Кроме того, при ветвлении учитывается только значение ключа, без сравнения его с другими ключами, хранимыми в узлах [25]. В случае строковых данных, вершина высоты h соответствует позиции в строке, а выходящие из этой вершины дуги соответствуют символам, стоящим на этой позиции. Поиск в Trie начинается с корпя; ищется выходящая из корневой вершины дуга, соответствующая первому символу строки. Если дуга найдена, то производится переход по дуге и рассматривается следующий символ строки. Поиск заканчивается, если выходящей дуги, соответствующей очередному символу не существует, либо если просмотрен весь ключ и найден узел, содержащий указатель на данные. В случае строковых ключей, Trie структуры позволяют эффективно бороться с избыточностью хранения общих префиксов, и это свойство было использовано в нескольких работах.
Эффективность алгоритма выполнения запроса
В этой главе были описаны механизмы создания виртуальных распределенных XML документов и алгоритмы выполнения запросов в виде регулярных выражений в таких документах. Предложенная модель распределенного документа позволяет абстрагироваться от физического расположения различных частей документа и от программно-аппаратных платформ компонентов распределенной системы. Были даны определения эффективных и масштабируемых алгоритмов, и описаны, в терминах интерфейсов и машин состояний, алгоритмы, позволяющие реализовать эффективный поиск в сильно связанной сети и масштабируемый поиск в слабо связанной сети. Доказано свойство нумерации узлов распределенного документа, позволяющее быстро решать проблему выяснения родства узлов.
Вариант реализации локального хранилища, предложенный в этой главе, позволяет использовать существующие индексные структуры, такие как В-дерево и hash-индексы, для выполнения запросов в виде регулярных выражений в XML документах. Алгоритм выполнения таких запросов использует технику сжатия ключей в В-деревьях и правила отсечения при поиске некоторых ветвей дерева, на основании статистической информации.
В этой главе представлены описание и результаты практических экспериментов по реализации локального хранилища и алгоритма отсечения веток В-дерева, описанных в разделе 3.5. Целью экспериментов являлась проверка гипотезы о том, что использование В-дерева в качестве хранилища данных и алгоритма отсечения веток дает преимущества в скорости выполнения запросов, несущих в себе требуемую для алгоритма информацию. В качестве объекта сравнения была выбрана популярная свободная система выполнения запросов к XML документам Kweelt [2].
В настоящее время известно несколько эталонных тестов производительности XML баз данных: [56, 44, 15, 14]. Для тестирования хранилища RegXP совместно со студентом Сергеем Малеванным был разработан эталонный тест RegXPBench [72], являющийся модификацией известного теста XMach-1 [14].
Эталонный тест производительности XML баз данных XMach-1 [14] основан на веб-приложении, которое моделирует типичную работу пользователей с XML СУБД. Архитектура среды выполнения данного теста показана на рис. 14. Среда выполнения состоит из четырех компонент: XML СУБД, HTTP-сервера, загрузчиков документов в СУБД и виртуальных клиентов, имитирующих работу пользователей с веб-браузером. Тестовый набор данных состоит из большого количества относительно небольших по размеру документов-продуктов (предполагается, что они были загружены с различных интернет-источников при помощи программ-загрузчиков) и одного большого, по сравнению с остальными документами, документа-каталога, содержащего в себе информацию о документах-продуктах. Каждый документ-продукт имеет уникальный идентификатор (URI), который вместе с метаданными об этом документе, хранится в документе-каталоге.
Во время работы теста виртуальные клиенты устанавливают соединения с HTTP-сервером и посылают информацию о запросах, которые они хотели бы выполнить. Поскольку предметом теста является эффективность выполнения запросов внутри СУБД, то время, затрачиваемое на общение клиентов и HTTP-сервера не учитывается при вычислении времени обработки запросов. Временем вычисления запроса считается интервал между моментом поступления запроса на HTTP-сервер и отправкой результатов запроса клиенту. Метрикой производительности считается количество выполненных запросов за единицу времени.
Оригинальная процедура генерации тестовых данных теста XMach-І сохранилась неизменной в RegXPBench. Генератор создает заданное количество документов-продуктов, назначает каждому из них уникальный идентификатор и помещает запись о документе в каталог. Документы-продукты внешне напоминают обычные статьи и относятся к классу тексто-ориептированных (document centric) документов. Базовое DTD документа-продукта показано на рис. 15. Поскольку маловероятно, что XML документы, пришедшие с различных веб-источников, будут иметь одинаковое DTD, то генератор XMach-І порождает разнообразные DTD, модифицируя базовое путем приписывания целых чисел к каждому из имен элементов, кроме элементов author и link. Так, DTD N-ro документа будет иметь элементы с именами: documentN, chapterN, author, sectionN и т.д. Наличие в экземпляре документа-продукта необязательных элементов DTD, глубина вложенности элементов section, а также некоторые другие характеристики определяются случайным образом по заданной таблице вероятностей. Содержимое символьных секций документов-продуктов генерируется но закону Зипфа [57] из словаря, содержащего 10000 слов английского языка.
Документ-каталог относится к классу структурно-ориентированных (data centric)1 документов. Его внутренние элементы имитируют дерево доменных имен и путей внутри каждого домена, а в листьях содержится небольшое количество метаипформации о документах-продуктах (рис. 16). Таким образом, документ-каталог является ветвистым деревом высотой 5-8 элементов без символьных секций.
Архитектура среды выполнения теста
Эксперименты проводились на компьютере со следующей конфигурацией: CPU Pentium-Ill 533MHz, 192 Mb RAM, с установленной системой MS Windows 2000 Server. При проведении экспериментов для минимизации влияния операционной системы н кэша жесткого диска были приняты следующие меры: отключался кэш операционной системы, а каждый сеанс начинался на "холодном состоянии" базы данных и жесткого диска
В первой части теста было проведено два сеанса, работавших с наборами данных разного размера. В первом сеансе размер набора данных составлял 1000 XML-документов, во второй 10000 документов. Размер наборов данных, время индексирования и размер получившихся индексов в каждом сеансе отражены в табл. 8, а результаты — в таблицах 9-12.
Для оценки системы RegXPBench выполняет 100 запросов, из которых 50 — первого типа, и но 25 — второго и третьего типов. Таким количеством запросов обеспечивается стабильность результатов оценки, так как тестовые данные строятся па основе некоторого частотного словаря, и запросы представляют из себя фразы с различной частотой повторения в документах. Первый запрос предусматривает поиск подстроки в текстовом содержимом элемента, а не в самом пути. Поэтому для него не представляется возможным использовать алгоритм оптимизации выполнения запроса. Для выполнения этого запроса приходится осуществлять полный обход В-дерева и искать подстроку во всех ключах. При выполнении второго запроса частично используется предложенная техника, и система RegXP не в 2.5 раза медленнее, как в случае первого, а приблизительно в 1.5.
Третий запрос полностью использует преимущества предложенной техники. Его выполнение системой RegXP осуществляется в среднем в 2.5-3 раза быстрее, чем системой Kweelt. Даже минимальное время его выполнения системой Kweelt больше максимального времени выполнения системой RegXP.
Стоить отметить небольшой, по сравнению с Kweelt, разброс между максимальным, минимальным и средним значениями результатов при выполнении первого запроса. Отсюда следует, что даже при отсутствии возможности использовать технику оптимизации выполнения запроса, скорость работы RegXP не сильно зависит от искомой подстроки. То есть при увеличении производительности самого компьютера будет равномерно увеличиваться и производительность системы индексирования.
Во второй части тестов с запросами каждого вида было проведено по 10 сеансов. В каждом сеансе генерировались 100 запросов данного вида над описательным файлом каталога для тестового набора RegXPBench из 1000 файлов. Этот файл характерен большим количеством разнообразных меток дуг.
Результаты экспериментов для запросов 1, 2 и 3 видов показаны соответственно на графиках 18, 19 и 20. Из них следует, что при выполнении запросов 1 вида RegXP работала от 3.55 до 4.76 раз, в среднем — в 3.96 раз быстрее, чем Kweelt. Для запросов 2 вида преимущество составило от 5.62 до 7.94 раз, в среднем — 6.46 раз. И при выполнении запросов 3 вида время, затраченное Kweelt, находилось в промежутке от 0.98 до 1.73 времени, затраченного RegXP, в среднем — в 1.33 раза больше.
В целом, результаты экспериментов достаточно обнадеживающие. При выполнении запросов, позволяющих использовать технику оптимизации, RegXP показывает примерно одинаковые или лучшие результаты но сравнению с Kweelt. Серьезное отставание при выполнении запросов, исключающих оптимизацию выполнения, может быть объяснено тем, что в прототипе не были реализованы префиксное сжатие ключей В-дерева и сохранение стека состояний конечного автомата между сессиями применения выражения к ключам В-дерева, что увеличивает нагрузку как па операции ввода/вывода так и на процессор. Кроме того, код не был исследован на наличие специфичных для языка Java узких мест.
