Xsd: Частичная Проверка

XSD — это язык описания структуры XML-документа.

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

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

В этой статье будет обсуждаться частичная проверка в дополнение к описанному выше, которая позволяет создавать действительные документы «на лету».

Мы рассмотрим, какие возможности может предоставить этот подход и как его реализовать.

Главная цель

Зачем нам вообще может понадобиться создать документ с заданными свойствами и какими свойствами мы можем управлять? Ответ на первый вопрос почти очевиден; Большинство документов представляют собой не просто текст, а наделены некоторой семантикой.

XML решает проблему синтаксического представления, а схема частично решает проблему семантического значения.

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

Наиболее часто используемым механизмом в этом случае является преобразование XSLT, смысл которого можно проиллюстрировать следующей схемой:

XSD: частичная проверка

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

Итак, схема позволяет:

Строго контролировать типизацию узлов данных и атрибутов;
Определять порядок узлов, следить за наличием обязательных узлов и атрибутов;
Требовать уникальности элементов в данном контексте;
Создавайте варианты узлов, требующих наличия тех или иных атрибутов, в зависимости от контекста;
Требовать выполнения определенного предиката для группы узлов или атрибутов.

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

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

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

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

Полная операция проверки больших документов может занять значительное время, десятки секунд и более, что в целом не позволяет использовать подход «атомарное изменение — проверка — отклонение/разрешение».

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

Однако, хорошие XML-редакторы знают, как это сделать, и мы попробуем разобраться, как они это делают.

Необходимая информация о схеме XML

XML-схема W3C — это эволюция идеи XML-ОТД (Определение типа документа).

Оба стандарта описывают схему документа посредством набора объявлений (объектов параметров, элементов и атрибутов), которые описывают его класс (или тип) с точки зрения синтаксических ограничений этого документа.

DTD рассматривает набор регулярных выражений вместо атомарных терминов или элементов словаря типов.

Каждый тип строится на основе других типов, атомарных термов и операций, альтернативных «|», конкатенации «», и операторов «Э», «+», «*», означающих необязательность, наличие одного или нескольких или ноль или более элементов.

Схема XML отличается от XML DTD по синтаксису и расширяет функциональность DTD в трех направлениях:

Шаблоны (any, AnyType, AnyAttribute), позволяющие использовать любой элемент, соответствующий заданному пространству имен;
Группы подстановки, определяющие набор типов, которые можно использовать вместо объявления определенного типа;
Число повторений, определяющее для каждого элемента минимально и максимально допустимое количество его вхождений в тип (обобщение операторов Клини: «*», «+»).

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

Правило Уникальная атрибуция частиц (однозначность частиц) требует, чтобы каждый элемент документа однозначно соответствовал ровно одному элементу xsd:element или xsd:any частице в модели содержимого родительского элемента [2].

Вообще говоря, правило Unique Particle Attribution (UPA) не является строгим требованием к структуре XML-схем, а лишь весьма желательной рекомендацией, и некоторые из используемых схем ему не соответствуют. Рассмотрим простейший пример, иллюстрирующий нарушение правила однозначного определения частиц.

Определим схему следующим образом:

<xsd:element name="root"> <xsd:complexType> <xsd:choice> <xsd:element name="e1"/> <xsd:any namespace="##any"/> </xsd:choice> </xsd:complexType> </xsd:element>

Тогда XML-документ, состоящий из одного элемента, доказывает нарушение правила однозначности; элемент может быть сопоставлен как с xsd:elment, так и с xsd:any одновременно.

К счастью, большинство готовых схем следуют правилу УПА.

Дальнейшие рассуждения будут корректными только в том случае, если схема соответствует правилу УПА, но в целом при небольших модификациях рассуждений можно добиться корректности на схемах, несовместимых с УПА, за счет потери скорости.

Создание валидатора

Для начала определим элементарные изменения в структуре, которые будем проверять на корректность:

ДОБАВИТЬ: создать подэлемент типа x в позиции n;
REMOVE: удаление подэлемента в позиции n;
MOVE: перемещение элемента из позиции n в позицию m (хотя перенос сводится к удалению и добавлению элементов, промежуточное состояние может нарушить валидность документа).

Теперь опишем модель контента сложного типа схемы:

Частица: • MinOccurs – минимальное количество повторений термина (если 0, то термин становится необязательным); • MaxOccurs – максимальное количество повторений термина (допускается бесконечность – inf).
• Термин: описание элемента, образец, последовательность или выбор;
Описание элемента (typedef): • Местное название; • Имя пространства имен (можно опустить, в этом случае элемент считается допустимым в любом пространстве имен); • Группа подстановки – набор всех элементов, принятых в выражениях, содержащих typedef;
Узор (любой): • Имя пространства имен, разрешенное для подстановочного элемента (может отсутствовать);
Последовательность: • Последовательный список допустимых частиц;
Выбор: • Множество приемлемых частиц.

Вы можете перейти непосредственно к алгоритму проверки.

Первое необходимое действие — построить соответствие «тип схемы» -> «автомат, который может проверять на валидность потомков элемента этого типа».

Задача сводится к двум рекурсивным действиям: 1. Строительство недетерминированный конечный автомат (НФА) с заданным конечным состоянием S для данной частицы: а.

Давайте установим начальное состояние n равным S; б.

Если MaxOccurs частицы равен бесконечности (inf): • Добавить новое промежуточное состояние t; полученный в результате преобразования термина в NFA (случай 2); добавим эпсилон-рёбра от t до n и от n до S:

XSD: частичная проверка

в.

Если MaxOccurs частицы равно числу m: • Строим цепочку преобразований термов (MaxOccurs-MinOccurs), начиная с конечного состояния S, добавляя на каждом шаге эпсилон-ребро из промежуточного состояния к конечному состоянию S; Например, для MaxOccurs=4 и MinOccurs=2 мы получаем следующую машину:

XSD: частичная проверка

д. Мы завершаем minOccurs копии преобразования термина из нового начального состояния n в начальное состояние, полученное на предыдущих шагах.

2. Построение недетерминированного конечного автомата с заданным состоянием приема S за заданный терм: а.

Если термин является шаблоном (любым): • Создайте новое состояние b и соедините его с S ребром, помеченным термином type, верните b; б.

Если термин является описанием элемента: • Мы создаем новое состояние b, затем для каждого элемента группы подстановки мы создаем ребро от b до S, помеченное типом элемента и возвращающее b; в.

Если термин является выбором: • Создаем новое состояние b, для каждого элемента выбора создаем автомат (случай 1) и соединяем его эпсилон-ребрами с состоянием b и состоянием S. Возврат b; д. Если термин представляет собой последовательность: • Для каждого элемента выбора создаем автомат (случай 1) и соединяем полученные автоматы в обратном порядке, начиная с состояния S, и возвращаем первое состояние в цепочке; Затем примените Алгоритм Томпсона к полученному НКА [3] для построения детерминированных автоматов.

Алгоритм Томпсона может применяться в тех же случаях, что и алгоритм построения детерминированного автомата Ахо и Ульмана, основанный на сворачивании одинаково помеченных неэпсилонных ребер [4].

Однако в ряде случаев алгоритм Ахо и Ульмана с использованием исходного автомата (созданного на шагах 1–2) не сможет построить детерминированный автомат. Это происходит, когда из одной вершины есть два исходящих ребра, например:

Их метки представляют собой объявления типов с одинаковыми локальными именами и именами в пространстве имен;
Их метки представляют собой названия узоров с перекрывающимися областями;
Метка одного края — это шаблон, другого — описание типа, оба находятся в одном пространстве имен, а описание типа включено в область действия шаблона.

Нетрудно показать, что каждый случай соответствует нарушению ограничения UPA (третий случай уже рассматривался на примере схемы, нарушающей правило однозначного определения частиц).

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

Применим предложенный алгоритм к каждому типу схемы и получим соответствие тип -> автомат, который сможет проверять потомков элемента этого типа.

Осталось решить последнюю задачу — выбор нужного конечного автомата при валидации операции над заданным элементом дерева.

Структура привязки типа проверки (PSVI, Информационный набор после проверки схемы ), порожденный практически любым (например, MSXML или libxml) полный валидатор.

Для любого элемента дерева он указывает на соответствующий ему в описании схемы тип — именно тот, которым мы сгенерировали искомый автомат.

XSD: частичная проверка

В нашем случае реализация структуры PSVI представлена ссылкой на тип схемы для каждого элемента дерева.

Операции MOVE и REMOVE не меняют тип операнда (поэтому не требуют изменения структуры PSVI), а операция ADD вместе с добавлением элемента x потребует добавления типа x в структуру PSVI. Таким образом, наряду с изменением структуры мы также меняем информационный набор привязок типов валидации, решая проблему частичной валидации и поддержания PSVI-дерева без вызова внешнего валидатора.

Сравнение результатов

Вообще говоря, прямого сравнения не будет - ведь мы описали надстройку, решающую конкретную задачу (операции ADD/REMOVE/MOVE) в конкретном случае (соответствие UPA), но хотелось бы показать, что в данном случае В этом случае это дает значительный прирост скорости по сравнению с попыткой использовать полную проверку.

В качестве эталонного валидатора, генерирующего PSVI, был выбран MSXML6, поэтому будем сравнивать его с временем работы.

Количество элементов конструкции	Уровни вложенности	Количество типов схем	Среднее время проверки MSXML6	Среднее время проверки с использованием описанной надстройки
32	4	16	10 мс	<1 ms
32	4	40	16 мс	<1 ms
120000	4	16	51 мс	<2 ms
120000	4	40	62 мс	<2 ms
120000	32	16	2300 мс	<5 ms
120000	32	40	2600 мс	<6 ms

Таким образом, мы получили вполне приемлемое среднее время ожидания проверки, позволяющее реализовать механизм Drag’n’Drop «на лету» в визуальном редакторе и обеспечивающее хорошее количество запросов в секунду для возможной XML-базы данных.