Функциональные методы обработки XML-данных Дмитрий Лизоркин, ВМиК МГУ, ИСП РАН

План доклада Введение/мотивация; SXML: XML-документ как S-выражение; XPath: функциональный подход; SXPath как язык запросов; Расширение языка запросов поддержкой ссылок XLink; Оптимизация XPath.

XML-данные XML – стандарт de facto для слабоструктурированных данных; XML-данные могут варьироваться по степени структурированности –Document oriented: This is an important note –Data oriented: 123 Microsoft Ave. Hawthorne NY

Обработка XML-данных Написание документов с разметкой –XML -> HTML, TeX, PDF,…; –Трансформации на языке XSLT; Выборка из XML-документов –XPath, XQuery; Использование ЯП общего назначения –Часто просто приходится использовать; –XSLT не позиционируется как ЯП общего назначения.

Обработка XML-данных (2)

Потеря соответствия (1) Daniela Florescu (редактор языка XQuery): «Для меня остается полной загадкой, как разработчикам удается реализовывать свои заказы, представленные в трех различных видах (XML, Java/C# и кортежи) – тратить так много времени на поддержание согласованности и написание преобразований, и так много времени на копирование данных из одного формата в другой. Подобное «животное с тремя ногами», как его называют, – это техническое недоразумение...»

Потеря соответствия (2) Daniela Florescu (продолжение): «...Множество людей хотят видеть языки программирования с прирожденной поддержкой для XML»

Функциональные методы Результат вычисления полностью определяется аргументами; XSLT, XQuery – функциональные языки; Языки функционального программирования. Scheme; Теория лямбда-исчисления; Способ организации повторяющихся вычислений – рекурсия –Хорошо подходит для задач обработки древовидной структуры XML-документа.

S-выражение S-выражение определяется рекурсивно: –Атом: строка, число, символ,...; –Последовательность S-выражений в скобках. (table (style "font-size: x-large")) (tr (td (align "right")) "Talks") (td (align "center")) " = ") (td "slides & transition")))

SXML: XML-документ в виде S-выражения Text node (tag (attr1 "value1") (attr2 "value2")) (nested "Text node") (empty) )

SXML-документ Одновременно наглядное внешнее представление и основная структура данных языка функционального программирования Scheme; S-выражения могут представлять и данные, и код; Дуализм кода и данных. `(weight (unit "kg")),(+ 10 2))

Свойства SXML XML и S-выражения – две реализации XML Information Set; Поддержка пространств имен XML; Отображение XML SXML прямолинейно; Парсер SXML функция (read) Внешнее представление для SXML может быть использовано как формат хранения.

XPath XPath – язык адресации частей XML- документа; Документ как дерево узлов; Путь доступа – последовательность шагов доступа /child::chapter[position()=2]/child::para[position()=last()] Путь доступа – ось, тест узла, ноль или более предикатов descendant::item[attribute::color="red"][child::engine]

SXPath: процессор языка XPath для XML-документов Путь доступа – функция: –Принимает контекстный узел и возвращает результат шага доступа для данного узла; –Принимает набор узлов и возвращает объединение результатов по каждому из узлов; Путь доступа – соединение шагов доступа по принципу суперпозиции –Функция, вычисляющая путь доступа над деревом (S)XML-документа.

Функциональный подход к вычислению XPath (node-join (sxml:descendant (ntype?? doc)) (sxml:child (ntype?? chapter)) (sxml:attribute (ntype?? title)) ) (sxpath "descendant::doc/chapter/attribute::title")

S-выражение как синтаксис SXPath Путь доступа в виде S-выражения: '(table (tr 2) (td 3))) Аналог сокращенного синтаксиса XPath (XPath abbreviated syntax): "table/tr[2]/td[3]" "child::table/child::tr[position()=2]/child::td[position()=3]" Список => может обрабатываться средствами языка Scheme; Может рассматриваться как «родной» синтаксис для SXPath (native syntax).

Расширение XPath Библиотека базовых функций XPath –Отдельная спецификация Консорциума W3 Язык XPath не предоставляет механизм определения функций; Не предоставляет интерфейса внешних функций (foreign functions); XPath + ( Java | C++ | Perl | PHP |...) … = Потеря соответствия.

Расширение SXPath Списковый и текстовый синтаксисы SXPath могут комбинироваться: (sxpath '(table (tr 3) Могут использоваться примитивы низкого уровня: (sxpath `(elem,(sxml:child (ntype?? 'para)))) Любая функция Nodeset->Nodeset: (sxpath `(// reservation,(lambda (nodeset) (filter reservation-confirmed? nodeset)) name *text*))

SXPath – больше чем XPath XPath –Выбирает существующую часть XML-документа; –Ограниченный набор функций в предикатах; –Отсутствуют средства создания новых узлов; SXPath: –Любая функция Nodeset->Nodeset может быть использована в качестве шага доступа; –Предикат может быть специфицирован как функция Scheme; –Могут создаваться новые узлы SXML.

Язык запросов XQuery Язык запросов к XML-данным; Модель данных – общая с языком XPath; Операции над объектами из модели данных –Конструирование новых узлов; FLWOR-выражение: for $p in document("auction")/site/people/person where empty($p/homepage/text()) return { attribute name {$p/name/text()}}

SXPath + Scheme как язык запросов Enumerate-filter-map-accumulate; В 1979 г. Richard Waters обнаружил, что 90% кода на Фортране в пакете для научных расчетов укладывается в данную парадигму; FLWOR-выражение как новый синтаксис для enumerate-filter-map- accumulate.

XQuery vs. Scheme for $p in document("auction")/site/people/person where empty($p/homepage/text()) return { attribute name {$p/name/text()}} (map (lambda (p) `(person "name/text()") p)))) (filter (lambda (p) (null? ((sxpath "homepage/text()") p))) ((sxpath "site/people/person") (sxml:document "auction.xml"))))

Язык XML Linking Language Язык описания связей между ресурсами при помощи XML; Свойства гиперссылок HTML + –Соединение более двух ресурсов; –Метаданные; –Отдельно от связываемых ресурсов; Переходы между ресурсами: –Определяются при помощи дуги XLink; –Исходный и целевой ресурсы дуги.

Расширение языка запросов поддержкой XLink Запросы к совокупности XML-документов, связанных ссылками XLink; Переход в терминах XLink соответствует определению оси в XPath; Вводится ось traverse: по узлу – исходному ресурсу получить целевой ресурс. /purchase-order/order[item/traverse::printer]/ customer/traverse::person/name/text()

Расширение языка запросов поддержкой XLink (2) Запросы к дуге XLink –Переход по дуге в зависимости от параметров дуги; Вводится представление дуги XLink в виде виртуального XML-документа; Ось arc – получения дуги, ось traverse- arc – переход по дуге: arc::third-party[actuate="onRequest"]/traverse-arc::* Расширение реализовано в SXPath.

Оптимизация вычисления выражений XPath Причины экспоненциальной сложности существующих реализаций XPath (Saxon, Xalan, XT) –Дублирующие узлы на промежуточных шагах доступа; –Для глубоко вложенных предикатов XPath количество их вызовов превосходит максимальное число различных значений контекста.

Эксперимент 1: узлы-дубликаты Простой XML-документ: Последовательность путей доступа: lpath1=//a/b lpath2=//a/b/parent::a/b lpath3=//a/b/parent::a/b/parent::a/b lpath4=//a/b/parent::a/b/parent::a/b/parent::a/b...

Результаты эксперимента (1) Время выполнения для Saxon (справа): Аналогичные результаты для Xalan и XT.

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

Результаты эксперимента (2) Проведенная оптимизация:

Эксперимент 2: предикаты Тот же простой XML-документ: Последовательность путей доступа: lpath1=//a/b[count(parent::a/b) > 1] lpath2=//a/b[count(parent::a/b[ count(parent::a/b) > 1]) > 1] lpath3=//a/b[count(parent::a/b[ count(parent::a/b[ count(parent::a/b) > 1]) > 1]) > 1]

Результаты эксперимента (1) Время выполнения для Saxon (справа): Аналогичные результаты для Xalan и XT.

Оптимизация вычисления глубоко вложенных предикатов XPath В статике определяются глубоко вложенные предикаты: количество их потенциальных вызовов больше количества различных контекстов; Количество вызовов зависит от использования в предикатах контекстной позиции/размера; Глубоко вложенные предикаты вычисляются в самом начале фазы выполнения, для всех комбинаций контекста.

Результаты эксперимента (2) Проведенная оптимизация:

Отложенные вычисления в языке программирования Scheme Delay: возвращает «обещание» вычислить данное ей выражение; Force: потребовать принудительное вычисление «обещания»; «Обещание» вычисляется не более 1 раза; Глубоко вложенные предикаты XPath: вычисляются только для тех комбинаций контекста, которые реально требуются.

Метрика Размер документа: |D| = = Количество узлов в документе + + Суммарная длина строк в текстовых узлах и значениях атрибутов + + Максимальная длина имени. Размер выражения XPath: |E| = = Количество шагов доступа + + Количество базовых выражений + + Максимальная длина строковых констант.

Верхние оценки времен вычисления Путь доступа без предикатов: O(|E|·|D|) Выражения XPath, не использующее контекстную позицию/размер и операции обобщенного сравнения: O(|E|·|D|²) Большинство практических выражений XPath: O(|E|·|D|³) Любое выражение XPath: O(|E|²·|D|^5)

Заключение Преодоление проблемы потери соответствия при обработке XML; Язык запросов SXPath; Расширение поддержкой ссылок языка XLink; Гарантированное полиномиальное время вычисления запросов; Рабочий прототип; Google: Dmitry Lizorkin homepage.