XML - статьи



              

Структурные ограничения XML - часть 6


Как видно из рисунка, все узлы дерева помимо корня являются листами. Для формирования структурной схемы, необходимо выполнить следующие действия:

  • Множество E формируется следующим образом: для каждого узла типа "элемент", мы создаем отдельный тип элемента
  • Множество A формируется следующим образом: для каждого узла типа "атрибут", мы создаем отдельный тип атрибута. Доменный тип состоит из одного значения - значения данного узла в документе
  • Множество T формируется следующим образом: для каждого текстового узла в документе мы создаем отдельный домен, состоящий только из одного значения
  • Отображение a задается по следующим правилам: для любого типа элемента e - множество a(e) состоит из типов атрибутов, соответствующих атрибутам того элемента XML, который задавал e.
  • Отображение e задается по следующим правилам: для любого типа элемента e - p(e) - это выражение вида (e0,..,en) где ei это либо тип элемента, либо домен, задаваемый i-м дочерним узлом того элемента XML, который задавал e.
  • Тип элемента r (корневой тип) задается корневым элементом дерева XML.
  • Легко убедиться, что исходный документ удовлетворяет данной схеме. Также любой XML документ, удовлетворяющий данной схеме, совпадает с исходным документом. То есть схема является тривиальной. Индуктивный переход осуществляется следующим образом. Пусть утверждение доказано для документа, максимальная глубина которого равна n. Пусть у нас есть документ XML глубины n+1. В терминах XML модели, его можно представить в виде дерева глубины n+1. Рассмотрим множество поддеревьев, с корнями в дочерних узлах корневого документа исходного дерева. Их максимальная глубина не превышает n. По предположению индукции им ставится в соответствие тривиальные схемы. Общая схема формируется путем объединения множеств E,T,A каждой из этих тривиальных схем и продлением отображений a и p . Затем мы формируем еще один тип элемента r, соответствующий корню исходного XML документа, и продляем отображения a и p на него. Отображение a(r) возвращает множество атрибутов корневого элемента, а p(r)=(r0,..,rn), где ri - корневой тип элемента тривиальной схемы, порожденный i-м узлом.

    Способ создания тривиальной схемы, использованный в утверждении 2, задает инъективное отображение множества документов XML на множество схем. Этот результат используется в работе [15] для реализации алгоритмов трансляции выражений алгебры управления структурными схемами в выражения языка запроса к данным XML. Легко показать, что все домены из множества T - доменных типов тривиальной схемы содержат в точности одно значение.

    Лемма 1 (Достаточное условие тривиальности) Любая схема S=(T,E,A,p,a,r) такая, что для любого типа элементов e, регулярное выражение p(e) имеет вид r1,..,rnn, где ri есть символы базового алфавита, является тривиальной или пустой схемы.




    Содержание  Назад  Вперед