Дипломная работа студента icon

Дипломная работа студента


Смотрите также:
Дипломная работа студента 544 группы...
Методические рекомендации по написанию дипломной работы Специальность 080...
Дипломная работа студента...
Дипломная работа студента 5 курса...
Дипломная работа студента...
Дипломная работа студента 544 группы...
Дипломная работа студента 544 группы...
Дипломная работа студента отделения экстернат...
Дипломная работа студента 544 группы...
Дипломная работа студента 544 группы...
Дипломная работа студента 545 группы...
Дипломная работа студента...



Загрузка...
скачать
Санкт-Петербургский государственный университет

Математико-механический факультет

Кафедра системного программирования


Сравнение подходов к индексированию XML документов


Дипломная работа студента

Шикина В. Ю.


Научный руководитель: Барашев Д. В.

к. ф.-м.н.



Рецензент: Глиненко Д. Г.


«Допустить к защите» Терехов А. Н.
зав. кафедрой:

д. ф.-м.н., профессор


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

Оглавление



ВВЕДЕНИЕ 3

^ ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ 7

1.1 Описание задачи 7

1.1.1 Понятие алгоритма индексирования 7

В данной работе будут рассматриваться индексы, позволяющие улучшить время исполнения запросов XPath[5] к XML базе данных. Предполагается, что хранилище XML данных представляет собой множество соответствий вида: 7

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

1.1.2 Общие требования к системе сравнения 7

1.1.3 Операция массовой смены префиксов 10

1.2 Обзор алгоритма ViST 12

1.3 Обзор алгоритма BB-деревьев 20

^ ГЛАВА 2. РЕШЕНИЕ ПРОБЛЕМЫ 27

2.1 Общее описание 27

2.2 Описание компонентов системы сравнения 27

2.3 Описание модификации алгоритма ViST 29

Алгоритм ViST был модифицирован для поддержки операции массовой смены префиксов. Предложенная в данной работе модификация опирается на метки, хранимые в дереве D-предков. Основная идея модификации состоит в изменении префиксов дерева D-предков. Алгоритм, реализующий операцию массовой смены префиксов, приведён ниже: 29

2.4 Описание реализации алгоритма BB-деревьев 31

^ ГЛАВА 3. ПАРАМЕТРЫ И РЕЗУЛЬТАТЫ СРАВНЕНИЯ 33

3.1 Исходные данные 33

3.2 Параметры сравнения 33

3.3 Результаты сравнения 34

3.4 Анализ результатов 40

ЛИТЕРАТУРА 44

ВВЕДЕНИЕ


Актуальность проблемы. Сегодня технологии XML получают всё более широкое распространение. Разрабатываются новые алгоритмы хранения и индексации XML данных; как в научной среде, так и на рынке встаёт проблема сравнения эффективности тех или иных алгоритмов или продуктов.


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


С увеличением популярности запросов вида XPath распространение получили XML индексы, ускоряющие поиск по конкретному пути в каждом из документов базы [13, 14]. Существует, однако, и другой подход: индексы, которые ускоряют поиск по любому пути документа [1, 15]. Подобный индекс позволит ускорить все запросы к базе, а не только те, которые содержат некоторый конкретный путь.


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


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


^ Выбор алгоритмов. Данная работа рассматривает алгоритмы ViST[1] и алгоритм, описанный в дипломной работе Сергея Оршанского [2]. Оба алгоритма создают индекс, охватывающий все элементы всех документов XML хранилища. Более того, оба алгоритма основываются на B+ деревьях.


Подход Сергея Оршанского, далее упоминаемый как алгоритм на основе BB деревьев, охватывает более широкий круг задач. Этот алгоритм позволяет эффективно работать с произвольными структурированными строками и поддеревьями. Поскольку любой XML документ представим как совокупность структурированных строк (что будет показано ниже), этот алгоритм применим и для индексирования XML баз данных.


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


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

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


^ Цель работы. Определить, какой из подходов будет эффективнее при использовании одинаковой реализации B+ деревьев. Исследовать операции чтения и изменения структуры хранимых данных.


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


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


^ Научная новизна. Алгоритм Сергея Оршанского до сих пор не был реализован и сравнён с другими алгоритмами индексирования.

Добавление в алгоритм ViST операции перемещения поддеревьев является модификацией оригинального алгоритма. Добавление этой операции является расширением возможностей алгоритма.


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


^ Практическое значение. Оба алгоритма, алгоритм Сергея Оршанского и ViST, достаточно новые. До сих пор эти алгоритмы не сравнивались. Оба алгоритма могут найти применение как в промышленных, так и научных областях, где необходимо работать с большими объёмами XML данных.


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


^ Структура работы. Данная работа изложена на 42 страницах и состоит из введения, трёх глав и заключения. Список литературы содержит 11 наименований. Работа иллюстрирована 15 рисунками и содержит 9 таблиц.
^

ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ

1.1 Описание задачи

1.1.1 Понятие алгоритма индексирования

В данной работе будут рассматриваться индексы, позволяющие улучшить время исполнения запросов XPath[5] к XML базе данных. Предполагается, что хранилище XML данных представляет собой множество соответствий вида:


уникальный идентификатор документа <--> документ

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

^

1.1.2 Общие требования к системе сравнения


Тестовая среда удовлетворяет следующим требованиям:

  • исполняемый код и сопутствующие файлы соответствуют стандарту модульной архитектуры XAnswer [6]

  • тестовая среда бинарно не зависит от конкретных реализаций тестируемых компонент, общаясь с ними посредством программных интерфейсов и точек расширения (extension points [12])

Участниками тестовой среды могут быть следующие классы компонент:

  1. хранилище – компонента, отвечающая за долговременное хранение XML документов

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

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

  4. генератор тестовых данных – компонента, предоставляющая XML документы для тестирования.


С точки зрения пользователя, разработанная среда предоставляет следующие интерфейсы:

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

  • web-интерфейс – интерфейс, написанный на основе servlet’ов и jsp, для контейнера Tomcat. Интерфейс позволяет пользователю выбирать хранилище, индекс, генератор тестовых данных, число и размер документов, частоту запросов. Интерфейс запрашивает вышеперечисленные данные и отображает результаты тестов.

  • консольный интерфейс – интерфейс, ничем не уступающий web-интерфейсу и реализованный как приложение под IDE Eclipse [9].


Типичный тестовый сценарий выглядит следующим образом:

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

  2. Выбирается набор имеющихся в среде хранилищ и индексов.

  3. Выбирается исполнитель запросов.

  4. Генератор записывает документы в текстовом виде на диск.

  5. Выполняется пакетная загрузка (bulk loading) сгенерированных данных в хранилище и в индекс.

  6. Произвольно выбирается запрос из множества запросов.

  7. Процессор обращается к индексу для ускорения выполнения запроса.

  8. Процессор обращается к хранилищу, используя данные из индекса, если таковые были получены.

  9. Записываются время исполнения и результат.

  10. Исполняется столько запросов, сколько указал пользователь.

  11. Результаты тестирования возвращаются пользователю.
^

1.1.3 Операция массовой смены префиксов


Для определения операции массовой смены префиксов (далее ОМСП), введём следующее представление XML документов:

Документ


Child1_Value

Child2_Value


представим как набор


(/Parent/Child1/@attribute/value, /Parent/Child1/Child1_Value, /Parent/Child2/Child2_Value)


^ Операция массовой смены префиксов – это операция, принимающая на вход текущий префикс (pref_old), новый префикс (pref_new) и XML документ во введённом выше представлении (seq_1, seq_2, seq_3, ..., seq_N), и создающая новый документ, в котором все элементы набора старого документа, начинавшиеся с pref_old, начинаются с pref_new, а остальные элементы набора остаются без изменения.

Например, для приведённого выше документа ОМСП, где текущий префикс - /Parent/Child1, а новый префикс - /Parent/NewChild, вернёт:


(/Parent/NewChild/@attribute/value, /Parent/NewChild/Child1_Value, /Parent/Child2/Child2_Value)


Это представление соответствует следующему документу:


Child1_Value

Child2_Value


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

1.2 Обзор алгоритма ViST


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

Для обзора алгоритма ViST необходимо вести некоторые определения.

Как было упомянуто выше, любой XML документ можно представить в виде дерева. Рассмотрим документ 1:

<A>

<B x="v1" y="v2">

<C x="v3" w="v4"/>

B>

<D x="v5" y="v6"/>

A>


Для него дерево будет выглядеть следующим образом:




Рисунок 1: Дерево XML документа 1


Аналогично, запросы XPath [5] представимы в виде подобных деревьев. Например, для запроса 1:


/A/B[@x="v1" and y="v2"]/C/@x


дерево будет выглядеть так:





Рисунок 2: Дерево запроса XPath


Будем представлять документы (и запросы) в следующем виде:
«(суффикс1,префикс1. . . (суффиксk,префиксk

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


(A,/)(B,/A)(x,/A/B)(v1,/A/B/x)(y,/A/B)(v2,/A/B/y) (C,/A/B)(x,/A/B/C)


Для подобного представления XML документов введём понятие суффиксного дерева.


Будем рассматривать документ 2:


(A,/)(F,/A)(G,/A/F)(v0,/A/F/G)


И документ 3:


(A,/)(B,/A)(C,/A/B)(v1, /A/B/C)(D,/A/B)(v2,/A/B/D)


На рисунке 3 представлен пример суффиксного дерева для документов 2 и 3:





Рисунок 3: Cуффиксное дерево для документов 2 и 3


Узлы этого дерева являются как узлами суффиксного дерева, так и узлами XML-дерева. Вполне естественно выделить два типа отношения предшествования:

1. D
-предок – отношение предшествования для узлов, как элементов XML-дерева

2. S
-предок – отношение предшествования для узлов, как элементов суффиксного дерева

Таким образом, элемент (B,/A) является D-предком для элемента (C,/A/B), а элемент (v2,/A/B/D) есть S-предок для элемента (C,/A/B).


Основная цель, достигаемая алгоритмом ViST, – динамическое присвоение индексов элементам S-дерева. Алогритм ViST достигает этой цели, используя структуру, далее называемую охватом элемента (element scope).

Охватом элемента S-дерева называется отрезок натуральных чисел, удовлетворяющий следующим свойствам: индекс элемента равняется левому краю его охвата, и охваты его элементов-потомков вкладываются в его охват. Это наглядно проиллюстрировано на рисунке 5:




Рисунок 4: Пример охвата S-дерева




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

Для индексирования XML-документа, мы будем рассматривать следующие B+ деревья:

  • дерево идентификаторов документов, где некоторому числу будет соответствовать один или несколько идентификаторов

  • дерево D-предков (D-дерево), где каждой паре (суффиксi,префиксi), когда-либо добавленной в базу данных, будет соответствовать S-дерево

  • множество деревьев S-предков (S-деревьев), где в каждом дереве индексу элемента будет соответствовать его охват

Детально рассмотрим каждое из деревьев.

Дерево идентификаторов документов имеет следующий вид:




Рисунок 5: Пример дерева идентификаторов



Здесь n=1 и n=2 – различные индексы, DocId1 и DocId2 – идентификаторы документов, содержащих элементы с индексами 1 и 2.


Деревья D-предков и S-предков имеют следующий вид:




Рисунок 6: Пример взаимосвязи деревьев D-предков и S-предков


Здесь тройка <n,s,k> означает уникальный индекс элемента, размер охвата этого элемента, число вложенных элементов соответственно. Для S-деревьев ключом является индекс элемента.

На введённых структурах можно рассматривать следующие алгоритмы:


Алгоритм 1.3.1: Поиск Документа по Запросу XPath

Вход:

1. - запрос XPath, приведённый к указанной выше форме

2. дерево D-предков

3. множество деревьев S-предков

4. size – размер корневого охвата

5. дерево идентификаторов документов

Выход:

Все вхождения Q в базу данных

Реализация:

Search((0,size),1)


function Search((n,size),i)

if i<=k then

T := дерево S-предков, соответствующее , извлекаемое из дерева D-предков

N := все элементы из T, ключи которых лежат в интервале (n, n+size)

for каждого элемента do

Допустим, c имеет вид (n’, size’)

Search((n’,size’), i-1)

do

fi

end;


Алгоритм 1.3.2: Добавление Документа в Базу Данных

Вход:

1. T - документ, который следует добавить в базу данных

2. id - идентификатор добавляемого документа

Выход:

Обновлённая база данных

Реализация:

Пусть

S := (0, Max, n), где Max - максимально возможный индекс, n – число документов в базе данных

i := 1

while i<=k do

найти ключ в дереве D-предков

if найден then

e := дерево S-предков, соответствующее ключу

fi

else

e := новое дерево S-предков

Добавить e в дерево D-потомков с ключом

end

Искать в e охват r, такой, что r является прямым потомком охвата s

if не найден then

r := новый охват, являющейся под-охватом охвата s, найденный по формулам приведённым выше

Пусть r имеет вид (n,size)

Добавить (n,size) в дерево S-предков e с ключом n

fi

s := r

i := i + 1

od

end;


Мы описали базовый алгоритм ViST. Для реализации операции массовой смены префиксов алгоритм был модифицирован. Описание модификации для поддержки операции массовой смены префиксов можно найти в секции 2.3 этой работы.
^

1.3 Обзор алгоритма BB-деревьев


Алгоритм BB-деревьев является общим алгоритмом управления коллекцией записей со строковыми структурированными ключами вида:

a.b.c.d

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

Введём несколько определений из работы [2].

Коллекция записей, рассматриваемых как пары вида «ключ – дополнительные данные», называется словарем, если над ней поддерживаются операции 1 – 3:

1. Добавление. Insert(key) либо добавляет ключ, отсутствующий в индексе, либо сообщает о том, что ключ уже присутствует и добавление неудачно.

2. Удаление. Remove(key) либо удаляет из индекса присутствующий в нем ключ, либо сообщает о том, что ключ уже отсутствует и удаление неудачно.

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

Предполагается, что ключи всех записей различны.

Коллекция записей называется упорядоченным словарем, если над ней поддерживаются операции 4 – 6:

4. ^ Поиск в диапазоне. RangeSearch(key1, key2) ищет в индексе ключ: key1 ≤ key ≤ key2. Как альтернатива могут искаться все ключи из заданного диапазона. Напомним, что отношение ≤ для структурированных ключей подразумевает покомпонентное сравнение.

5. ^ Поиск следующего. FindNext(record&) ищет запись, ключ которой непосредственно следует за ключом данной записи. Получает на вход не ключ записи, а расположение ее в коллекции – например, место на диске. Операция практически аналогична поиску минимального ключа, строго большего заданного значения, но может выполняться быстрее.

6. Поиск предыдущего. FindPrev(record&) полностью аналогичен FindNext. Ищет запись, ключ которой непосредственно предшествует ключу данной записи.

Дадим несколько определений:

Р-бор – это индексная структура данных, располагаемая во внутренней памяти, оперирующая строковыми ключами. Р-бор состоит из трех частей: множества записей, множества контейнеров и бора доступа. Приведем описание р-бора из [2] без существенных изменений, включая примеры.

Записи (Records)

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

Контейнер – это небольшая совокупность записей, организованная в виде списка или двоичного дерева поиска. Для контейнера глубины k все строки, содержащиеся в нем, имеют длину как минимум k, и их первые k символов совпадают. (То есть все строки начинаются с одного и того же префикса длины k). Соответственно, нет необходимости хранить эти первые k символов в каждой строке. Каждый контейнер также имеет некоторый заголовок для хранения статистики, используемой эвристиками разрастания. Об этих эвристиках подробно рассказано в Приложении 1 работы [2].

Так некоторый контейнер глубины 3, содержащий строки “lemon” и “lemur”, может также содержать строку “lemming”, но не “leitmotiv”.

^ Бор доступа – это бор, листья которого являются контейнерами. Бор организован с помощью массивов указателей (хотя возможны вариации). Соответственно, каждая вершина содержит массив указателей, каждый из которых указывает или на другую вершину бора доступа, или на контейнер. Также каждая вершина содержит указатель, соответствующий символу «^» («конец строки»), указывающий на запись, которой соответствует строка, являющаяся конкатенацией меток ребер на пути, ведущем от корня бора к данной вершине.

Рассмотрим пример р-бора, приведенный в статье [7], стр. 198, изображенный на рисунке 7:



Рисунок 7: Р-бор с двоичными деревьями поиска в качестве контейнеров


В качестве контейнеров используются двоичные деревья поиска. В боре хранятся строки (записи с ключами) T = {came”, “car”, “cat”, “cave”, “cy”, “cyan”, “we”, “went”, “were” и “west}.

Самый левый контейнер содержит четыре записи, соответствующие строкам “came”, “car”, “cat” и “cave”. Одна из строк в самом правом контейнере – «^», - соответствует строке “we”. Строка “cy” хранится полностью внутри бора доступа.

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

Приведем определение BB-дерева, данное в работе [2]:

BB-дерево – это индексная структура, предназначенная для хранения набора структурированных строковых ключей во внешней памяти, поддерживающая ОМСП.BB-дерево отчасти повторяет р-бор. В каждый момент дерево состоит из двух частей: бора доступа и совокупности контейнеров.

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

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

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



Рисунок 8: Пример BB-дерева


На рис. 8 не отражена структура контейнеров. На самом деле, они организованы в виде B-деревьев.


Приведём основные алгоритмы над B-деревом:


Алгоритм 1.4.1: Поиск структурированного ключа

Вход:

1. - ключ, который надо найти

2. B - бор доступа

Выход:

Все вхождения Key в базу данных

Реализация:

k := 1;

T := вершина бора B

C := null

while k <= N

do

T := вершина T, ассоциированная с ребром cK

if T – существует then

k := k + 1;

fi

else

выйти из цикла

end

od

if (k == N) then

вернуть информацию, ассоциированную с пустой строкой контейнера T

fi

if (T != null ) then

найти в контейнере T

fi

else

ключ не найден

end

end;


Алгоритм 1.4.2: Добавление структурированного ключа

Вход:

1. - ключ, который надо добавить в базу данных

2. info - информация, ассоциированная с ключом

3. B- бор доступа

Выход:

Обновлённый бор доступа

Реализация:

k := 1;

T := вершина бора B

Tl := T

C := null

while k <= N

do

T := вершина T, ассоциированная с ребром cK

if T – существует then

Tl := T

k := k + 1;

else

выйти из цикла

fi

od

if (k==n) then

добавить в контейнер пустую строку и ассоциированные с ней данные info

выйти

fi

else

создать контейнер C, ассоциированный с вершиной Tl

добавить и info в контейнер C

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

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

из структуры учета статистики удалить запись (с максимальным значением)

добавить к Tl новое ребро, помеченное префиксом

на конце ребра создать вершину T* и контейнер C*

от всех строк, удаленных из контейнера C, отбросить префикс

все эти строки добавить в контейнер C*

в структуре учета статистики S* частота встречаемости префикса увеличить на 1.

выйти

end

end;


Вполне очевидно, что алгоритм BB-деревьев может быть применён к хранилищу XML данных. Для этого будем рассматривать XML документы в представлении, введённом в секции 1.1.3 этой работы.

Так, документ


Child1_Value


Child2_Value


будет соответствовать трём структурированным ключам:


/Parent/Child1/@attribute/value

/Parent/Child1/Child1_Value

/Parent/Child2/Child2_Value


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

Используя такой подход можно работать с BB-деревом как в случае обычных структурированных строк.
^

ГЛАВА 2. РЕШЕНИЕ ПРОБЛЕМЫ

2.1 Общее описание


Рассмотренные выше алгоритмы были реализованы на языке Java в рамках проекта XAnswer. XAnswer является исследовательским проектом, позволяющим его участникам реализовывать и проводить эксперименты над новыми алгоритмами для XML баз данных.
^

2.2 Описание компонентов системы сравнения


Как было указано выше, сравнение алгоритмов проводилось в разработанной в рамках данного проекта тестовой среде. Среда была спроектирована и частично реализована в рамках работы [3].

Участниками тестовой среды могут быть следующие классы компонент:

  • хранилище

  • индекс

  • исполнитель запросов

  • генератор тестовых данных


Рассмотрим детали реализации этих компонент.


Хранилище XML документов

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

С точки зрения программных интерфейсов, хранилище XML документов – это реализации определённых интерфейсов, указывающих, какие действия можно совершить с хранилищем. В данный момент существуют интерфейсы, определяющие методы загрузки xml данных в хранилище, отображения «ключ – значение» и для долговременного хранения соответствия «документ – ID документа».

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


Индекс

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

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


^ Генератор тестовых данных

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

В рамках данной работы использовался генератор проекта XMach [8], адаптированный для используемой системы сравнения. Данный генератор позволял генерировать произвольное число случайных тестовых документов заранее заданного размера.


^ Исполнитель запросов

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

В рамках данной работы использовалась сравнительно простая реализация исполнителя запросов. Алгоритм работы приведён ниже:


Алгоритм 2.2.1: Исполнение запроса

Вход:

1. Q – запрос, который необходимо исполнить на множестве документов

2. P – хранилище, содержащее множестве документов

3. I – индекс хранилища P

Выход:

result - множество документов, удовлетворяющих запросу

Реализация:

result := {}

ids := результат исполнения запроса Q на индексе I

foreach id in ids

do

document := извлечь документ с идентификатором id из P

result := {result, document}

od

end;
^

2.3 Описание модификации алгоритма ViST

Алгоритм ViST был модифицирован для поддержки операции массовой смены префиксов. Предложенная в данной работе модификация опирается на метки, хранимые в дереве D-предков. Основная идея модификации состоит в изменении префиксов дерева D-предков. Алгоритм, реализующий операцию массовой смены префиксов, приведён ниже:




Алгоритм 2.3.1: Массовая смена префиксов

Вход:

1. O=o1,o2,...,oN – префикс, который надо изменить

2. N=n1,n2,...,nM – новый префикс

3. D - дерево D-предков

Выход:

Дерево D-предков с обновлённым префиксом

Реализация:

for i := 1 to M do

S := дерево S-потомков соответствующее элементу nI

if S не существует then создать S fi

добавить S в D с ключом nI

od

for i to N do

удалить элемент, соответствующий oI из D

od

for (s,p) – ключи D do

if (p начинается с O)

p_new := заменить O на N в p

S := дерево S-потомков соответствующее элементу (s,p)

удалить (s,p) из D

добавить S в D с ключом (s,p_new)

fi

od
end;


^

2.4 Описание реализации алгоритма BB-деревьев


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


Основные классы:


Container

Интерфейс, описывающий основные методы работы с контейнерами

ContainerFactory

Класс, возвращающий одну из реализаций контейнера

BPlusTreeContainer

Класс, реализующий контейнер на основе B-Plus деревьев. Этот класс использует реализацию B-Plus деревьев проекта exist [10]

AccessTree

Класс, реализующий бор доступа. Этот класс хранит ссылку на корневой элемент дерева

AccessTree.Node

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

BBTree

Класс, содержащий логику работы с BB-деревом. Этот класс обладает методами для добавления нового структурированного ключа, нахождения существующего ключа и разрастания дерева


Вспомогательные классы:


ContainerManager

Класс, реализующий методы работы с контейнерами (создание, открытие, удаление). Этот класс хранит информацию об открытых контейнерах и отвечает за корректное закрытие всех контейнеров

TreeKey

Класс, реализующий структурированный ключ. Этот класс содержит методы для итерации по компонентам ключа и получения оставшейся части ключа

StatisticStructure

Класс, реализующий структуру статистики для данного контейнера



Классы, реализующие работу с XML данными


SAXDocumentEncoder

Класс, реализующий конвертацию XML документа во множество структурированных ключей. Этот класс использует стандартный SAX парсер для прохода по документу

SAXPathEncoder

Класс, реализующий конвертацию запроса XPath во множество структурированных ключей. Этот класс использует SAX парсер для XPath, реализованный в рамках проекта com.werken [11]

BBTreeIndexApi

Класс, реализующий интерфейсы BulkLoader и DocumentIdIndexApi. Этот класс использует текущую реализацию BB-дерева в качестве индекса

BBTreeIndexFactory

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



^

ГЛАВА 3. ПАРАМЕТРЫ И РЕЗУЛЬТАТЫ СРАВНЕНИЯ

3.1 Исходные данные


Для проведения экспериментов было использовано два типа XML документов.

Первый тип представлял собой XML документы, существенно различающиеся по размеру и структуре. Эти документы были получены в результате работы генератора XMach. Будем называть эти докумены сложными. Сложные данные делились на две группы: документы c одним элементом второго уровня и документы с пятью элементами первого уровня.

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

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

3.2 Параметры сравнения


Тестирование состояло из двух стадий.

Первая стадия: добавление сгенерированных документов в индекс. Замерялось среднее время добавления документа, а также число обращений к B+ дереву.

Вторая стадия: исполнение ста запросов четырёх типов:

  1. Запрос, не соответствующий структуре хранимых данных

  2. Запрос, имеющий глубину вложенности 4

  3. Запрос, имеющий глубину вложенности 2

  4. Запрос, включающий обращение к значению атрибута


Запросы исполнялись в случайном порядке таким образом, что запрос каждого типа выполнялся примерно одинаковое число раз (согласно случайному равномерному распределению). Замерялось среднее время исполнения запроса и число обращений к B+ дереву.
^

3.3 Результаты сравнения


На приведенных ниже диаграммах на вертикальной оси отмечено среднее время исполнения операции (в миллисекундах) в зависимости от количества документов.


^ Сложные документы

Документы, имеющие 1 элемент первого уровня

Добавление документов



Количество добавляемых документов

Среднее время добавления одного документа


Рисунок 9: Добавление сложныx документов с 1 элементом первого уровня





Исполнение запроса



Количество документов в базе

Среднее время исполнения одного запроса


Рисунок 10: Исполнение запроса на базе, содержащей сложные документы с 1 элементом первого уровня


^ Документы, имеющие 5 элемент первого уровня

Добавление документа


Количество добавляемых документов

Среднее время добавления одного документа


Рисунок 11: Добавление сложных документов с 5 элементами первого уровня


^ Исполнение запрос



Количество добавляемых документов

Количество документов в базе

Среднее время исполнения одного запроса


Рисунок 12: Исполнение запроса на базе, содержащей сложные документы с 5 элементами первого уровня



^ Простые документы

Документы, размером около 2 килобайт

Добавление документа



Количество добавляемых документов

Среднее время добавления одного документа


Рисунок 13: Добавление простых документов размером около 2 килобайт



Количество документов в базе
Исполнение запроса




Среднее время исполнения одного запроса


Рисунок 14: Исполнение запроса на базе, содержащей простые документы размером около 2 килобайт



^ Документы, размером около 20 килобайт

Добавление документа



Среднее время добавления одного документа


Рисунок 15: Добавление простых документов размером около 20 килобайт


^ Исполнение запроса


Количество добавляемых документов




Количество документов в базе

Среднее время исполнения одного запроса


Рисунок 16: Исполнение запроса на базе, содержащей простые документы размером около 20 килобайт


Далее приведены таблицы с различными количественными характеристиками использования B+ деревьев обоими алгоритмами.

В таблицах столбцы обозначены:

I – база с 15 документами сложной структуры с 5 элементами верхнего уровня

II - база с 50 документами сложной структуры с 5 элементами верхнего уровня

III – база с 50 документами простой структуры размером около 20Kb

IV - база с 500 документами простой структуры размером около 20Kb


^ Количество используемых деревьев:





I

II

III

IV

BBTree

1

1957

249

247

ViST

5

9670

1435

1452


^ Число чтений из деревьев во время добавления документов:





I

II

III

IV

BBTree

0

13923

11695

11688

ViST

210

52040

53964

53984


^ Число чтений из деревьев во время исполнения ста запросов документов:





I

II

III

IV

BBTree

75

84

73

219

ViST

5346

20352

7150

23972



^ Число записей в деревья во время добавления документов:





I

II

III

IV

BBTree

15

11967

11440

11442

ViST

43

61476

55199

55236


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




I

II

III

IV

ViST

100Mb

238Mb

76Mb

295Mb

BBTree

32Mb

72Mb

35Mb

102Mb


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





I

II

III

IV

BBTree

1ms

1ms

1ms

1ms

ViST

414ms

1375ms

151ms

1120ms



^

3.4 Анализ результатов


Операция массовой смены префиксов. Как и следовало ожидать, подход Оршанского, специально разработанный для поддержки подобных операций, является более эффективным, чем ViST. Это объясняется тем, что смена префиксов в алгоритме-победителе является не более чем изменением нескольких структур в оперативной памяти, в то время как алгоритм ViST производит довольно много операций с B+ деревьями, хранящимеся на диске.

Хочется отметить масштабируемость данной опрации для алгоритма Оршанского.


^ Операции исполнения запросов. Алгоритм ViST проигрывает в производительности из-за частого обращения к B+ деревьям, хранящимся на диске. В большинстве случаев для исплонения запроса алгоритм Оршанского использует лишь бор доступа, хранящееся в оперативной памяти.


^ Операция добавления документа. Как и в операции исполнения запросов, алгоритм ViST сохраняет всю информацию в B+ деревья, хранящиеся на диске.


Особенности реализации. Среди особенностей реализации, повлиявших на результаты сравнения, можно выделить реализацию B+ дерева. Как показал сеанс профилирования, каждое дерево занимает достаточно большое количество памяти, что могло повлиять на размер кучи для алгоритма ViST.

Другой особенностью реализации алгоритма ViST была операция конвертации строк в числовые объекты. Алгоритм использует множество B+ деревьев для сохранения охватов на диске. В них хранится структура из идентификатора и двух достаточно больших (восьми-десятизначных) чисел. Эта структура достаточно часто считывается с диска во время исполнения запросов и добавления новых документов (см. алгоритмы 1.3.1, 1.3.2, операция поиска дерева S-предков). Как следствие, возникает необходимость конвертации строковых представлений чисел охвата в машинные представления. Это повлияло на время исполнения запросов алгоритма ViST.

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

ЗАКЛЮЧЕНИЕ

В результате работы было проведено исследование по сравнению двух подходов к индексированию XML баз данных. Оба подхода позволяли ускорить все запросы к базе, а не только те, которые содержат конкретный путь. Более того, оба рассмотренных алгоритма базировались на B+ Деревьях.


Первый подход, предложенный в работе C. Оршанского [2] является более общим, так как позволяет индексировать любые структурированные ключи. В рамках данной работы был реализован компонент, превращающий XML документ во множество структурированных ключей. Таким образом, алгоритм В. Оршанского использовался для XML документов.


Второй подход, предложенный в работе [1], является изначально разработанным для индексирования хранилищ XML документов. Этот подход широко использует B+ деревья для хранения и поиска информации. Алгоритм ViST был модифицирован для поддержки операции массовой смены префиксов. Следует отметить, что приведённый в работе [1] алгоритм не поддерживает никаких модификаций хранимых данных, так что реализация операции массовой смены префиксов была уникальной модификацией.


В ходе исследования была доработана и протестирована среда, которая использовалась для сравнения алгоритмов. Среда показала удобство использования и простоту добавления новых тестируемых компонент. Разработанная система сравнения компонентов XML базы данных (в данной работе сравнивались только индексы), может использоваться в дальнейших исследованиях по производительности тех или иных компонент.


Сравнение алгоритмов показало нецелесообразность использования похода ViST. Он проиграл своему сопернику как в быстродействии, так и в количестве используемой памяти. Это объясняется активным использованием B+ деревьев и, как следствие, большим количества обращений к постоянной памяти.


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

ЛИТЕРАТУРА


  1. Haixun Wang, Sanghyun Park, Wei Fan, Philip S. Yu, ViST: A Dynamic Index Method for Querying XML Data by Tree Structures, Hawthrone, NY, 10532

  2. Оршанский С.А., Модификация структурированных ключей в индексной структуре на основе B-дерева, 2005

  3. Василий Шикин, руководитель Дмитрий Барашев, курсовая работа «Разработка среды XML Benchmark», 2005

  4. Василий Шикин, руководитель Дмитрий Барашев, курсовая работа «Применение алгоритма ViST», 2004

  5. http://www.w3.org/TR/xpath (XML Path Language Specification)

  6. http://xanswer.sourceforge.net/wiki (XAnswer project wiki page)

  7. Steffen Heinz, Justin Zobel, Hugh. E. Williams. Burst tries: a fast, efficient data structure for string keys // ACM Transactions on Information Systems. 2002, V. 20, № 2. – P. 192 – 223.

  8. http://dbs.uni-leipzig.de/en/projekte/XML/XmlBenchmarking.html (XMach project home page)

  9. http://www.eclipse.org/ (Eclipse IDE home page)

  10. http://exist.sourceforge.net/ (Exist project home page)

  11. http://sourceforge.net/projects/werken-xpath/ (werke.xpath project home page)

  12. http://www.developer.com/lang/article.php/3552481 (Eclipse plugin development guide)

  13. R. Goldman and J. Widom, DataGuides: Enable query formulation and optimization in semistructured databases, VLDB, pages 436–445, August 1997

  14. Brian F. Cooper, Neal Sample, Michael Franklin, Am Bsli Hjaltason G and Moshe Shadmon, A fast index for semistructured data, VLDB, pages 341–350, September 2001

  15. P.R. Raw and B. Moon, PRIX: Indexing and Querying XML Using Prüfer Sequences, proc. Int'l Conf. Data Eng. (ICDE), IEEE CS Press, 2004, pp. 288–300.




Скачать 226,24 Kb.
оставить комментарий
Дата02.12.2011
Размер226,24 Kb.
ТипДиплом, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх