Язык модификации данных формата XML функциональными методами

Д.А. Лизоркин
Труды Института системного программирования РАН

Аннотация: Задача внесения модификаций в данные формата XML является актуальной по природе слабоструктурированных данных. До настоящего времени не был разработан такой язык модификации XML-данных, который бы выступал в роли общепризнанного мирового стандарта.
В данной статье предлагается язык модификации XML-данных, в основу которого были положены функциональные методы программирования и язык функционального программирования Scheme. Функции, являющиеся в языках функционального программирования объектами первого класса, используются в предлагаемом языке модификации XML-данных в роли обработчиков для операций модификации, что позволяет достичь выразительной мощности и расширяемости набора операций модификации при сохранении синтаксической простоты языка.
Производится анализ алгоритмической сложности выполнения операций предлагаемого языка и рассматриваются детали его реализации функциональными методами.

Содержание

1. Введение

2. Существующие языки модификации XML-данных

3. Операция модификации как обработчик узла

3.1. Реализация некоторых операций модификации функциональными методами

3.3.1.1. Вставка нового узла в документ

3.3.1.2. Удаление узла

3.3.1.3. Замена узла новым узлом

3.3.1.4. Переименование узла

3.2. Возможности языка Scheme по выражению операций модификации

4. Зависимая обработка нескольких узлов

4.1. Базовый узел

4.2. Перемещение поддерева

5. Сокращенный синтаксис для описания модификаций

6. Реализация

7. Алгоритмическая сложность

8. Будущие исследования

9. Заключение

Список литературы

1. Введение

Популярность языка разметки XML в качестве формата для хранения, передачи и обработки слабоструктурированных данных делает актуальной для практических приложений потребность в языке модификации XML-документов. Несмотря на актуальность данной задачи, доминирующее внимание консорциума W3C, которому принадлежит авторство большинства спецификаций платформы XML [1], в предыдущие годы было направлено на язык запросов из XML-документов [2], и работа над языком модификации XML-данных была начата в Консорциуме сравнительно недавно [3] и в настоящий момент находится в черновом статусе.

В настоящей статье предлагается язык модификации XML-документов, основанный на подходе к обработке XML-данных функциональными методами, в частности, с помощью языка функционального программирования Scheme. Благодаря близкому соответствию иерархической структурой XML-документа вложенным спискам языка функционального программирования Scheme и свойству функций Scheme быть объектами первого класса обеспечивается выразительная гибкость предлагаемого языка модификаций и минимизируется проблема потери соответствия [4] по сравнению с другими существующими языками модификации XML-документов.

Подход к обработке XML-данных функциональными методами базируется на формате SXML — представлении XML-документов в виде вложенных списков, текстуально записываемых при помощи S-выражений. Языки SXML и XML могут рассматриваться как два синтаксически различных представления Информационного Пространства XML [5]. Для демонстрации соответствия между вложенными тегами XML и вложенными списками SXML, на рис. 1 приведен пример простого XML-документа и его представления на SXML. Каждая из информационных единиц Информационного Пространства XML представляется в виде S-выражения, первым членом которого является либо имя информационной единицы (для типов элемент и атрибут), либо служебное имя, предусмотренное для информационной единицы данного типа в грамматике SXML [6]. Заметим, что спецификация SXML обеспечивает поддержку пространств имен XML, и существует парсер, позволяющий для заданного XML-документа сконструировать его представление на SXML [7].

<?xml version='1.0'?>
<doc>
  <tag attr1="value1" attr2="value2">
    <nested>Text node</nested>
  </tag>
  <empty/>
</doc>

(*TOP* (*PI* xml "version='1.0'")
 (doc
   (tag (@ (attr1 "value1") (attr2 "value2"))
     (nested "Text node")
   )
   (empty)
 ))

Рис. 1: XML-документ (слева) и его представление в SXML

Универсальность представления на SXML узлов всех типов обеспечивает простоту обработки документов формата SXML, а функции Scheme, обладающие свойством объектов первого класса, позволяют прозрачным образом интегрировать конструкции предлагаемого в настоящей статье языка модификации с пользовательскими действиями приложения.

Необходимо сразу же отметить, что в функциональной парадигме программирования под модификацией данных понимается нечто отличное от модификации в контексте процедурной и объектно-ориентированной парадигм программирования. Чисто функциональный стиль подразумевает отсутствие в программе побочных эффектов, что исключает такие широко принятые в процедурном и объектно-ориентированном подходе операции как присваивание новых значений глобальным переменным или перестановка указателей [9]. Модификация в функциональном стиле является операцией, не разрушающей исходные данные, и модификация исходного документа осуществляется за счет конструирования нового документа.

Благодаря отсутствию в программе побочных эффектов, для конструирование модифицированного документа не требуется глубокое копирование исходного документа [8], но, как более подробно обсуждается в разделе 6, неизменные в результате модификации части документа используются в виде единой физической копии для его исходной и результирующей версий [9]. Приложение само решает, каким образом обрабатывать исходный и модифицированный документы. Например, приложение может использовать исходный документ лишь в локальном блоке своего кода, и тогда части, специфичные для исходного документа, будут освобождены автоматическим сборщиком мусора при выходе программы из данного локального блока [10].

Вопрос обеспечения работы нескольких конкурентных приложений над общим документом вкратце затрагивается в разделе будущих исследований, и его детальное исследование находится за пределами данной статьи.

Дальнейшее содержание статьи организовано следующим образом. В разделе 2 дается обзор существующих языков модификации XML-данных и обсуждаются преимущества функционального подхода. В разделе 3 предлагается идея использование функций в качестве обработчиков для операций модификации, иллюстрируется выразительность данного подхода и показывается, как с помощью обработчиков могут быть выражены наиболее распространенные операции существующих языков модификации. В разделе 4 идея обработчиков расширяется возможностью согласованной обработки нескольких узлов документа, что позволяет естественно реализовать такие операции модификации, как перемещение поддеревьев. В разделе 5 вводится сокращенный синтаксис для наиболее употребительных конструкций предлагаемого языка модификаций. Раздел 6 посвящен деталям реализации предлагаемого языка модификаций функциональными методами программирования. Вопрос алгоритмической сложности вычисления запросов на модификацию предлагаемого языка рассматривается в разделе 7. Будущие исследования обсуждаются в разделе 8. Раздел 9 завершает статью.

2. Существующие языки модификации XML-данных

До настоящего времени какого-либо единого стандарта языка модификации XML-данных не существовало. Так, разработанный консорциумом W3C язык запросов к XML-данным XQuery [2] в своей текущей версии является языком, предназначенным лишь для выборки данных и не предоставляющим никаких средств для внесения модификаций в XML-документы. С другой стороны, ввиду большого распространения технологии XML и естественности задачи внесения модификации в XML-данные для практических приложений, имеется ряд разработанных промышленных и академических языков для модификации XML-данных.

При анализе существующих языков модификации XML-данных в первую очередь необходимо отметить работу [11], в которой предлагается детально проработанный язык модификации с описанной формальной семантикой, который является расширением XQuery. По аналогии с понятием запроса в языке XQuery в языке модификаций, предлагаемом в [11], вводится понятие запроса на модификацию (update query). Запрос на модификацию состоит из одной или нескольких операций модификации (update expression), где каждая операция модификации производит некоторое базовое действие над обрабатываемым XML-документом. В работе [11] вводятся следующие виды операций модификации:

• вставка нового узла в дерево документа;

• удаление узла;

• замена узла новым узлом;

• переименование узла.

Для выбора узлов XML-документа, подлежащих изменению данной операцией модификации, в [11] используется язык адресации структурных частей XML-документа XPath [12]. По семантике вычисления запроса на модификацию, операции модификации, входящие в запрос, независимы друг от друга: изменения, производимые в XML-документе одной операцией модификации, не учитываются при выборе узлов, подлежащих изменению другой операцией модификации.

Несмотря на то что набор введенных в [11] операций модификации позволяет выразить любое необходимое изменение XML-документа [13], в языке отсутствует возможность расширения функциональности этих операций или добавления пользовательских операций. В настоящей статье семантика операций модификации определяется с помощью обработчика, представляющего собой произвольную функцию с заданной сигнатурой, благодаря чему достигается полная выразительная мощность языка модификаций из [11] и обеспечивается возможность для приложения по определению собственных операций модификации, равноправных с базовыми операциями вставки, удаления, замены и переименования узлов.

Необходимо также отметить, что в языке модификаций, предложенном в [11], не предоставляется важной операция  перемещения поддеревьев [13] и предлагается реализовывать ее, как комбинацию операций удаления и вставки узлов. Хотя операция перемещения действительно может быть реализована таким образом, в работе [11] не предоставляется никаких средств по обеспечению согласованности операций удаления и вставки при их комбинации с целью получения эффекта перемещения поддерева.

В настоящей статье разработывается механизм зависимой обработки совокупности из нескольких узлов, благодаря которому достигается возможность согласованной модификации узлов, расположенных в разных частях документа, и, в частном случае, функциональность операции перемещения поддеревьев. Разработанный сокращенный синтаксис языка модификаций предоставляет приложению возможность записи операции перемещения поддеревьев в виде наглядного выражения.

Язык модификации XML-данных, предлагаемый в работе [14], также разработан как расширение к XQuery, и в нем используются богатые возможности XQuery по адресации частей обрабатываемого документа и конструированию новых узлов. Несмотря на всю мощность XQuery как языка запросов, при реализации на его основе языка модификаций авторам работы [14] потребовалось расширить язык XPath, являющийся составной частью XQuery, возможностью явной адресации значения конкретного атрибута. Проблема адресации отдельного значения атрибута с целью его модификации не возникает в SXPath — реализации XPath на языке функционального программирования Scheme, — поскольку SXPath позволяет обрабатывать элементы и атрибуты унифицированным образом ввиду их однородного способа представления на SXML [15].

В работе [14] вводится операция суб-модификации (sub-update), позволяющая производить поиск других узлов относительно целевого узла модификации и осуществлять для них рекурсивный вызов операции модификации. По своему назначению операция суб-модификации схожа с предлагаемым в настоящей работе механизмом зависимой обработки совокупности из нескольких узлов. При этом предлагаемый механизм обладает большей декларативностью по сравнению с операцией суб-модификации.

Более декларативным является и предлагаемый в настоящей работе способ задания обрабатываемых узлов, подлежащих модификации. Для сравнения, в языке модификации, разработанном в [14], итерация по обрабатываемым узлам полностью перекладывается на прикладного программиста, что приводит к необходимости использования чрезмерно большого числа итеративных конструкций (for-update) в запросах на модификацию.

Необходимо также отметить, что в работе [14] язык модификаций исследовался в контексте хранения XML-документов в реляционной базе данных, ввиду чего у авторов упомянутой работы возникли проблемы реализационного характера по поддержанию корректной контекстной позиции узлов при вставке нового содержимого между существующими данными [14].

В разрабатываемом группой XML:DB языке модификации XML-документов XUpdate [16] вводится набор операций, аналогичный уже рассмотренным, и для записи запросов на модификацию используется язык XML и специальное пространство имен. Язык XUpdate пока развит хуже по сравнению с рассмотренными выше работами [11] и [14], и до настоящего времени находится в черновом статусе разработки.

3. Операция модификации как обработчик узла

Модификация на предлагаемом в данной статье языке выражается с помощью декларативного запроса, который мы по аналогии с введенной в [11] терминологией будем называть запросом на модификацию (update query). В контексте функциональных методов программирования можно говорить о том, что запрос на модификацию является атомарным в том смысле, что в реализации, детали которой будут обсуждаться в разделе 6, модификация осуществляется за один проход по дереву модифицируемого документа.

Запрос на модификацию может состоять из одной или нескольких операций модификации, где операция модификации предназначена для выполнения некоторого базового действия над частью обрабатываемого документа. Каждая операция модификации адресуется к набору некоторых узлов в документе и выполняет модификацию каждого узла данного набора по отдельности.

Анализируя семантику предлагаемых в [11] операций модификации, можно заметить, что любая из этих операций может быть в обобщенном виде представлена как пара значений:

где выражение_XPath служит для выбора в обрабатываемом XML-документе набора узлов, подлежащих модификации, а обработчик специфицирует воздействие конкретной операции модификации на каждый из выбранных узлов. Обработчик может рассматриваться, как функция, которая получает на вход узел, подлежащий модификации, и возвращает результат воздействия конкретной операции модификации на данный узел.

Предложенное представление операции модификации в виде пары значений получает естественную реализацию в терминах языка функционального программирования Scheme, поскольку в Scheme функции обладают свойством объектов первого класса. Функции как объекты первого класса могут, в частности, передаваться в качестве аргументов другим функциям, что позволяет нам рассматривать обработчик как черный ящик и, таким образом, абстрагироваться от внутренней реализации конкретного обработчика в дизайне языка модификаций.

Рассматривая операцию модификации XML-данных в контексте языка функционального программирования Scheme и формата SXML, определим обработчик как функцию, имеющую следующую сигнатуру:

где node — это узел, подлежащий обработке с помощью данной операции модификации. Поскольку результат операции модификации естественным образом зависит от узла, подлежащего обработке, функция, введенная для представления обработчика, принимает данный узел в качестве аргумента. В соответствии с тем значением, которое вернет обработчик, будет реализовываться та или иная операция модификации.

Будем считать допустимыми возвращаемыми значениями обработчика либо единственный узел, либо набор узлов. В том случае, когда обработчик возвращает единственный узел, этот новый узел будет замещать собой в документе обрабатываемый узел (который был фактическим параметром для данного вызова обработчика). Если обработчик возвращает набор узлов, то этот набор узлов предполагается упорядоченным, и на место обрабатываемого узла в документе подставляются все узлы из полученного набора. В частности, если возвращаемый набор узлов пуст, то обрабатываемый узел удаляется из документа, и вместо него ничего не подставляется [17].

В соответствии с предложенным в данном разделе представлением операции модификации в виде пары значений, с помощью выражения_XPath будет выбираться набор узлов исходного документа, которые подлежат обработке в данной операции модификации. Каждый узел из выбранного набора рассматривается как обрабатываемый узел, и с ним, как с фактическим параметром, вызывается обработчик. Возвращаемый результат обработчика формирует новый узел или узлы, которые заменяют собой обрабатываемый узел. В частности, возвращаемый результат может включать в себя и сам обрабатываемый узел, что производит эффект добавления в дереве документа некоторых новых узлов к обрабатываемому узлу.

Несмотря на простоту рассмотренной семантики обработчика и сопоставленного с ним выражения_XPath, предложенное представление операции модификации в терминах, приближенных к языку функционального программирования Scheme, обладает достаточно широкими возможностями для выражения разнообразных модификаций документов формата SXML. Далее в данном разделе рассматривается реализация с помощью идеи обработчиков некоторых наиболее употребительных операций модификации, затем обсуждаются возможности обработчиков при выражении более сложных операций модификации.

3.1. Реализация некоторых операций модификации функциональными методами

В данном пункте показывается, как имеющиеся в работе [11] операции модификации получают естественное и лаконичное воплощение на языке функционального программирования Scheme при обработке документов в формате SXML.

3.3.1.1. Вставка нового узла в документ

В работах [11] и [14] предлагается 3 разновидности операции вставки нового узла в документ:

• вставка после (insert following), добавляющая новый узел сразу же после обрабатываемого узла таким образом, что они оба имеют общий родительский узел;

• вставка перед (insert preceding), добавляющая новый узел сразу же перед обрабатываемым узлом таким образом что они оба имеют общий родительский узел;

• вставка внутрь (insert into), добавляющая новый узел в качестве дочернего для обрабатываемого узла, последним по порядку документа (document order [12]).

В терминах SXML и функционального программирования эти операции вставки узла представляют собой простую комбинацию примитивов работы над списковыми структурами данных. Так, эффект “вставки перед” и “вставки после” достигается, когда обработчик формирует список, состоящий из добавляемого в документ нового узла и обрабатываемого узла. Соответственно, если в формируемом списке новый узел идет первым, то в дереве документа он будет добавлен перед обрабатываемым узлом (вставка перед), если вторым — то после обрабатываемого (вставка после).

С целью параметризации обработчиков новым узлом, подлежащим вставке, обработчики реализуются как возвращаемый результат функции, которая и осуществляет необходимую параметризацию. Данный подход возможен благодаря тому, что функции Scheme являются объектами первого класса. Реализация обработчиков для “вставки перед” (insert preceding) и “вставки после” (insert following) приведена ниже:

(define (insert-preceding new-node)
  (lambda (node)
    (list new-node node)))

(define (insert-following new-node)
  (lambda (node)
    (list node new-node)))

Заметим, что при параметризации каждой из записанных функций для нескольких разных значений нового узла new-node будет получено несколько разных обработчиков. Рассмотренный дизайн обработчиков по добавлению узлов в виде возвращаемых результатов функций удобен для приложения, поскольку подлежащий вставке новый узел new-node, как правило, известен на этапе формулирования операции модификации, тогда как обрабатываемый узел node становится известным только на этапе обработки дерева документа.

При определении семантики операции “вставки внутрь” следует особо выделять случай, когда обрабатываемый узел является текстовым узлом, т.е. по определению не может содержать узлов, вложенных в него. Реакция на подобную ситуацию может различаться в зависимости от нужд конкретного приложения; ниже показывается реализация, которая оставляет обрабатываемый текстовый узел без изменения:

(define (insert-into new-node)
  (lambda (node)
    (if (not (pair? node))  ; текстовый
        node  ; оставляем без изменения
        (append node (list new-node)))))

В рассматриваемых далее в данном разделе примерах используются выражения модификаций, исходно предложенные в [11], и для них приводятся и обсуждаются аналоги на языке Scheme, записанные в терминах предлагаемой идеи обработчиков.

Пример 1   Запрос, содержащий операцию модификации на “вставку перед”, в терминах синтаксиса, разработанного в [11], записывается в виде:

UPDATE
INSERT
  <warning>High Blood Pressure!</warning>
PRECEDING //blood_pressure[systolic>180]

В контексте предложенной в данной статье идеи использования обработчиков для выражения операций модификации, рассматриваемый запрос получает естественное эквивалентное воплощение на Scheme для обработки документов в форме SXML:

(sxml:modify
 `("//blood_pressure[systolic>180]"
   ,(insert-preceding
     '(warning "High Blood Pressure!"))))

Функция sxml:modify реализует запрос на модификацию, который может состоять из одной или более операций модификации. Операция модификации получает естественную нотацию в виде списка, состоящего из двух членов: выражения XPath и функции, играющей роль обработчика. Использованные при записи операции модификации выражения квази-цитирования (quasiquote, сокращенно обозначаемое символом "`") и снятия цитирования (unquote, сокращенно обозначаемое символом ",") показывают, что первый член списка представляет собой константное выражение, а второй член должен быть вычислен.

Результатом функции sxml:modify является в свою очередь функция, которая и осуществляет обработку документа формата SXML.

В полной аналогии с примером 1 реализуются примеры на “вставку после” и “вставку перед”, и единственное отличие заключается в использовании соответствующего обработчика для каждой из этих операций.

Содержание Вперёд