Содержание
Введение
1 Платформа X и функциональные методы
1.1 Платформа X.
1.1.1 Расширяемый язык разметки X
1.1.2 Прострамстиа имен и X
1.1.3 Язык X X
1.1.4 Язык ссылок X Xi
1.2 Обработка Xданных и проблема потери соответствия.
1.3 X Xдокумсит как ныражеиис
1.3.1 X, информационное пространство X и X .
1.3.2 Спецификация X
1.3.3 Пространстиа имен и X.
1.3.4 Свойства X
1.4 Библиотека X реализация некоторых конструкций языка X
функциональными методами.
1.4.1 Низкоуровневые функции X
1.4.2 Высокоуровневая функция X.
2 Интеграция X с языком функционального программирования и язык запросов к Xданным
2.1 Статический анализ и динамическое вычисление выражений X
2.2 Расширение набора примитивов библиотеки X
2.3 Отображение выражения X на суперпозицию функций.
2.3.1 Лексический и синтаксический анализ выражений X
2.3.2 Грамматическое правило выражение пути
2.3.3 Грамматическое правило абсолютный путь доступа
2.4 Расширение X за счет интеграции со .
2.5 X как язык запросов
2. Абстрактное синтаксическое дсрсно иыражении X п виде X.
3 Расширение яз.1ка запросов для обработки совокупностей Xдокументоп, связанных ссылками Xi
3.1 Мотивация поддержки Xi в языке запросов
3.2 Пример связанных Xдоку ментов
3.3 Родственные работы п области обработки связанных ХМдокументов
3.3.1 X
3.3.2 Браузеры с поддержкой Xi.
3.3.3 Интерфейсы прикладного программирования.
3.1 Расширение Xi переходами по дугам языка Xi 7
3.5 Адресация к дугам языка Xi.
3.5.1 Дуга Xi и виде информационной единицы
3.5.2 Оси для адресации к дугам Xi.
3. Реализация
З.С.1 Разбор разметки языка Xi.
3..2 Реализация предложенных осей как расширение библиотеки Xi. .
3.7 Ограничения предлагаемого языка запросов
Л Оптимизация выполнения запросов
4.1 Эксперименты в отношении существующих промышленных реализаций X
4.1.1 Эксперимент 1 дублирующие узлы. 9
4.1.2 Эксперимент 2 глубоко вложенные предикаты.
4.2 Оптимизация вычисления обратных осей X ввиду отсутствия и X
указателей па родительские узлы
4.2.1 Родственные работы и области вычисления обратных осей X .
4.2.2 Иллюстрация предлагаемого подхода
4.2.3 Алгоритм вычисления выражений X, содержащих обратные оси .
4.2.4 Свойства предложенного алгоритма.
4.2.5 Ограничения алгоритма
4.2. Эксперименты.
4.3 Удаление дублирующих узлов при вычислении осей X.
4.3.1 Предварительные соглашения.
4.3.2 Осп ii и .
4.3.3 Ось i
4.3.4 Ось i
4.3.5 Оси и .
4.3. Осп i и iii.
1.3.7 Оси iii и iiii 1
1.3.8 Ос .
1.3.9 Ос .
1.3. Ось
1.4 Вычисление осей Xi для случая расположения узлов на одном уровне . . .
4.4.1 Оси i, н . 1
4.4.2 Оси i и i 1
4.4.3 Оси iii и iii
4.4.4 Ось 1
4.5 Вычисления осей Xi и присутствии в шаге доступа позиционных преднкатов 1
4.5.1 Выявление позиционных предикатов с помощью статического вывода
типов.
4. Оптимизация вычисления глубоко вложенных предикатов.
4.7 Оптимизация вычисления операций обобщенного сравнения.
4.7.1 Вычисление обобщенного сравнения сортировкой слиянием
4.7.2 Вычисление обобщенного сравнения поразрядной сортировкой
1.8 Верхняя оценка сложности выполнения запросов ввиду предложенных
способов оптимизации.
4.9 Детали реализации
4. Эксперименты
11 Эксперимент 1 устранение дублирующих узлов
42 Эксперимент 2 глубоко вложенные предикаты
43 Сравнительные тесты производительности
Заключение
Список литературы