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

и разработки языка модификации для


Статья посвящена вопросу исследования и разработки языка модификации для XML-данных. Были проанализированы ограничения, присущие существующим языкам модификации XML-данных, и для преодоления этих ограничений были предложены функциональные методы программирования. При определении семантики действий, осуществляемой конкретной операцией модификации, было предложено использовать функции, обладающие в языке функционального программирования Scheme свойством объектов первого класса, в роли обработчиков для операций модификации. Представление XML-данных в виде списков формата SXML позволило — благодаря наличию в языке Scheme большого количества стандартных функций для работы со списками — в простой и лаконичной форме сформулировать обработчики для всех наиболее употребительных операций модификации.
Для согласованного обеспечения операций модификации, подобных операции перемещения поддеревьев, была выработана более широкая возможность зависимой обработки сразу нескольких расположенных в разных местах документа узлов. Предложенная концепция зависимой обработки узлов естественным образом расширяет идею обработчиков благодаря введенному понятию базового узла операции модификации.
Для возможности написания запросов на модификацию без явной передачи функций в тело запроса, был разработан сокращенный синтаксис для набора наиболее употребительных операций модификации.
В отношении предложенного языка модификаций была сформулирована и формально доказана верхняя временная оценка, утверждающая гарантированное полиномиальное от размера документа и от количества операций модификации время вычисления любого запроса на модификацию, при условиях, что каждый обработчик выполняется за полиномиальное время и что суммарное количество новых узлов, добавляемых в документ в результате модификации, полиномиально от размера исходного документа.
Практическая применимость предложенных в статье идей была проиллюстрирована сделанной реализацией. Реализация использовалась при тестировании операций модификации в разрабатываемой в Институте системного программирования РАН XML-СУБД Sedna [24].

Содержание раздела