Введение
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
