Функциональные методы обработки XML-данных

• Автор: Лизоркин, Дмитрий Алексеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 229 с. : ил.

Содержание
Введение

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
3.5 Адресация к дугам языка Xi.
3.5.1 Дуга Xi и виде информационной единицы
3.5.2 Оси для адресации к дугам Xi.
3. Реализация
З.С.1 Разбор разметки языка Xi.
32 Реализация предложенных осей как расширение библиотеки Xi. .
3.7 Ограничения предлагаемого языка запросов
Л Оптимизация выполнения запросов
4.1 Эксперименты в отношении существующих промышленных реализаций X
4.1.1 Эксперимент 1 дублирующие узлы.
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.3.8 Ос .
1.3.9 Ос .
1.3. Ось
1.4 Вычисление осей Xi для случая расположения узлов на одном уровне . . .
4.4.1 Оси i, н .
4.4.2 Оси i и i
4.4.3 Оси iii и iii
4.4.4 Ось
4.5 Вычисления осей Xi и присутствии в шаге доступа позиционных преднкатов
4.5.1 Выявление позиционных предикатов с помощью статического вывода
типов.
4. Оптимизация вычисления глубоко вложенных предикатов.
4.7 Оптимизация вычисления операций обобщенного сравнения.
4.7.1 Вычисление обобщенного сравнения сортировкой слиянием
4.7.2 Вычисление обобщенного сравнения поразрядной сортировкой
1.8 Верхняя оценка сложности выполнения запросов ввиду предложенных
способов оптимизации.
4.9 Детали реализации
4. Эксперименты
Эксперимент 1 устранение дублирующих узлов
Эксперимент 2 глубоко вложенные предикаты
Сравнительные тесты производительности
Заключение
Список литературы


Аналогичным образом, третий шаг доступа выбирает все элементы с именем i, являющиеся дочерними для выбранного на втором шаге элемента ii в рассматриваемом документе выбираемых элементов с именем i ровно один. Наконец, четвертый шаг доступа выбирает дочерние текстовые узлы для ранее выбранного элемента с именем i. Данный шаг доступа вычисляется и набор узлов, состоящий из единственного текстового узла , что становится результатом вычисления пути доступа для данного документа. Относительно семантики полученного результата можно говорить о том, что путь доступа па рис. X доку. Помимо рассмотренного синтаксиса для записи путей доступа называемого также полным синтаксисом, в спецификации X определяется также сокраы,сшшй синтаксис vi x для наиболее употребительных конструкций языка. Ось i используется в шаге доступа по умолчанию, т. I ютом кои 0. Элементы к атрибуты в Xдокумситс в общем случае имеют квалифицированные имена М. Как обсуждалось в подразделе 1. С использованием механизма пространств имен в X имя узла моделируется парой , состоящей из локальной части и возможно, отсутствующего унифицированного идентификатора ресурса пространства имен вс вместе называется расширенным именем узла x . В спецификации о Пространствах Имен в X квалифицированно имен унифицированными идентификаторами ресурсов производится косвенным способом, основанным на идее префикса. Для выбора в Xдокументе элементов и атрибутов, имеющих квалифицированные имена, в языке X используется тест узла, который также является квалифицированным именем, т. Квалифицированное имя в тесте узла преобразуется п расширенное имя с помощью деклараций пространств имен i 9, являющихся частью контекста вычисления. Декларации пространства имен представляют собой отображение префиксов на унифицированные идентификаторы ресурсов пространств имен. Тест узла, являющийся квалифицированным именем, есть истина только для такого узла, расширенное имя которого совпадает с расширенным именем для данного квалифицированного имени, т. Процессору языка X декларации щюстранства имен передастся от приложения, и конкретный способ передачи в спецификации X не регламентирован 1С. В частности, при использовании выражений X п составе языков X или Xi декларации пространства имен формируются согласно требованиям спецификаций X и Xi соответственно . Необходимо отмстить, что декларации пространства имен в X и объявления пространств имен в Xдокумситс полностью независимы. Действительно, в Xдокументе префикс ссылается на унифицированный идентификатор ресурса, заданный в ближайшем по иерархии вложенности элементов атрибуте x, и имя префикса выбирается дизайнером Xдокумента. В пути доступа языка X префикс ссылается на декларации пространства имен i, и имя префикса выбирается разработчиком приложения. При вычислении теста узла сравниваются не имена префиксов, но соответствующие им унифицированные идентификаторы ресурсов. При задании контекста вычисления для пути доступа, рассмотри ного на рис. Так, в данном примере префикс отображается на пространство имей Модели Описания Ресурсов . Язык ссылок X X ii , далее Xi это язык описания мсжрссурснмх связей с помощью X и отдельного пространства имен 1. Современные практические приложения часто характеризуются большим многообразием хранимых и обрабатываемых ресурсов, для которых возникает желание специфицировать семантику их родства в виде системы мсжрссурснмх связей 8. В качестве мощного инструмента для решения данной задачи консорциумом 3 был разработай язык Xi , позволяющий описывать взаимосвязи между ресурсами в виде ссылок, с использованием X и отдельного пространства имев. Язык Xi начал разрабатываться консорциумом 3 вскоре после появления самого языка X, и первоначально предполагался как вторая часть спецификации X . Ii, обладающий более богатыми выразительными возможностями, нежели , и позволяющий определять входящие и сторонние ссылки, а также описывать некоторые их семантические свойстна. Язык Xi обеспечивает полную функциональность гиперссылок , и гораздо большее 1 так, ссылка Xi позволяет устанавливать отношение связи между более чем двумя ресурсами, ассоциировать различные метаданные со ссылками, соединять ресурсы без их модификации 1.