Введение
1 Платформа XML и функциональные методы 10
1.1 Платформа XML 10
1.1.1 Расширяемый язык разметки - XML 10
1.1.2 Пространства имен в XML 12
1.1.3 Язык XML Path (XPath) 15
1.1.4 Язык ссылок XML (XLink) 20
1.2 Обработка XML-данных п проблема потери соответствия 23
1.3 SXML: XML-документ как S-иыраженне 27
1.3.1 XML, информационное пространство XML и SXML 27
1.3.2 Спецификация SXML 29
1.3.3 Пространства имен в SXML 32
1.3.4 Свойства SXML 34
1.4 Библиотека SXPath: реализация некоторых конструкций языка XPath
функциональными методами 37
1.4.1 Низкоуровневые функции SXPath 37
1.4.2 Высокоуровневая функция SXPath 41
2 Интеграция XPath с языком функционального программирования и язык запросов к XML-данным 43
2.1 Статический анализ и динамическое вычисление выражений XPath 43
2.2 Расширение набора примитивов библиотеки SXPath 50
2.3 Отображение выражения XPath на суперпозицию функции 52
2.3.1 Лексический и синтаксический анализ выражении XPath 53
2.3.2 Грамматическое правило "выражение пути" 55
2.3.3 Грамматическое правило "абсолютный путь доступа" 57
2.4 Расширение XPath за счет интеграции со Scheme 58
2.5 SXPath как язык запросов 62
2.6 Абстрактное синтаксическое дерево вираження XPatli в пиде SXML Go
3 Расширенно языка запросов для обработки соїюкупііостсіі XML- докумептоп, снизанных ссылками XLink С8
3.1 Мотивация поддержки XLink її языке запросов 68
3.2 Пример связанных ХМ L-документе в 69
3.3 Родственные работы в области обработки связанных ХМL-документов . 72
3.3.1 XQuery 72
3.3.2 Браузеры с поддержкой XLink 73
3.3.3 Интерфейсы прикладного программирования 73
3.4 Расширение XPatli переходами по дугам языка XLink 74
3.5 Адресация к дугам языка XLink 78
3.5.1 Дуга XLink г> виде информационной единицы 79
3.5.2 Оси для адресации к дугам XLink 85
3.6 Реализация 88
3.6.1 Разбор разметки языка XLink 88
3.6.2 Реализация предложенных осей как расширение библиотеки SXPath . 90
3.7 Ограничения предлагаемого языка запросов 93
4 Оптимизация выполнения запросов 95
4.1 Эксперименты в отношении существующих промышленных реализации XPatli 95
4.1.1 Эксперимент 1: дублирующие узлы 96
4.1.2 Эксперимент 2: глубоко вложенные предикаты 100
4.2 Оптимизация вычислении обратных осей XPatli ввиду отсутствия и SXML уч<азателсн на родительские узлы 101
4.2.1 Родственные работы в области вычисления обратных oceli XPatli . 104
4.2.2 Иллюстрация предлагаемого подхода 105
4.2.3 Алгоритм вычисления выражении XPatli, содержащих обратные осп . 106
4.2.4 Свойства предложенного алгоритма 11G
4.2.5 Ограничения алгоритма 120
4.2.6 Эксперименты 121
4.3 Удаление дублирующих узлов при вычислении oceii XPatli 124
4.3.1 Предварительные соглашения 124
4.3.2 Оси ancestor и ancestor-or-sclf 126
1.3.1 Ось attribute 133
4.3.1 Oct, child 134
4.3.2 Оси descendant и dcscendant-or-sclf 139
4.3.3 Оси following и preceding 144
4.3.7 Осп following-sibling it preceding-sibling 147
4.3.8 Ось namespace 152
4.3.9 Ось parent 153
4.3.10 Ось self 157
4.4 Вычисление осей XPath для случая расположения узлов на одном уровне . 158
4.4.1 Осп child, descendant и desccndant-or-self 1G1
4.4.2 Оси following п preceding 1G3
4.4.3 Оси following-sibling и preceding-sibling 104
4.4.4 Ось parent 1G6
4.5 Вычисления occii XPatli u присутствии в шаге доступа позиционных предикатов 1G7
4.5.1 Выявление позиционных предикатов с помощью статического вывода типов 171
4.G Оптимизация вычисления глубоко вложенных предикатов 172
4.7 Оптимизация вычисления операции обобщенного сравнения 177
4.7.1 Вычисление обобщенного сравнения сортировкой слиянием 178
4.7.2 Вычисление обобщенного сравнения поразрядной сортировкой 180
4.8 Верхняя оценка сложности выполнения запросов ввиду предложенных способов оптимизации 185
4.9 Детали реализации , 204
4.10 Эксперименты 209
4.10.1 Эксперимент 1: устранение дублирующих узлов 209
4.10.2 Эксперимент 2: глубоко вложенные предикаты 211
4.10.3 Сравнительные тесты производительности 213
Заключение 218
Список литературы
