XML - статьи

         

Классы регулярных грамматик


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

Определение 8 (Локальные структурные схемы) Структурная схема называется локальной, если не существует двух типов элементов с одинаковым именем.

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

Утверждение 3 (Единственность интерпретации) Пусть S=(T,E,A,p,a,r) локальная структурная схема и XML документ D валиден для S. Пусть также любые два домена из множества Т не пересекаются и для любого типа элемента e, мультимножество имен типов атрибутов из множества a(e) содержит только уникальные значения. Тогда существует и притом единственная интерпретация документа D в терминах S.

Существование интерпретации следует из самой формулировки утверждения. Для доказательства единственности воспользуемся формулировкой интерпретации. Из правила согласования имён элементов, и локальности схемы следует, что в любой интерпретации каждый элемент документа XML должен отображаться на один и тот же тип элемента, так как имена всех типов уникальны. Из того, что любые два домена не пересекаются и из свойства согласования текстовых узлов следует, что в любой интерпретации каждый узел документа XML должен отображаться на один и тот же домен. Таким образом, достаточно проверить, что отображение атрибутов сохраняется в любой интерпретации. Это следует из свойств согласования атрибутов с элементами, согласования имен и значений атрибутов и из того, что для любого типа элемента e, мультимножество имен типов атрибутов из множества a(e) содержит только уникальные значения.

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

Определение 9 (Допустимые символы) Пусть r- регулярное выражение над множеством M. Тогда ? M(r) - это множество, содержащее все элементы из M, которые присутствуют в записи регулярного выражения.


Например, если E={0,1,2}, то ?M((0*,1*))= {0,1}

Теорема 2 ( Критерий допустимости) Пусть r- регулярное выражение над E. Тогда

e
E: e
? M(r)
s=[e0,..,ei-1,e,ei+1,..,en]: s|=r

Определение 10 (Однотипные структурные схемы) Структурная схема S=(T,E,A,p,a,r) называется однотипной, если для любого типа элемента e, все типы элемента из множества ?E(p(e)) обладают разными именами.

Определение 11(Ограничено-однотипные структурные схемы) Структурная схема S=(T,E,A,p,a,r) называется ограниченно-однотипной, если для любого типа элемента e, выполняется следующее условие:

s1=(e0,..,en),
s2=( e'0,..,e'm), где s1|=p(e) и s2|=p(e), и
i:
j< i e'j= ej


name(ei) ? name(e'i)

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

Утверждение 4 (Вложение типов) Любая локальная структурная схема является однотипной структурной схемой. Любая однотипная структурная схема является ограниченно-однотипной структурной схемой

Утверждение 5 (Достаточное условие однотипности) Пусть структурная схема S=(T,E,A,p,a,r) обладает следующим свойством:
e
E: |? M(p(e))|(Количество допустимых символов не превышает 1). Тогда S является однотипной структурной схемой.

Утверждение 6 (Единственность интерпретации) Пусть S=(T,E,A,p,a,r) ограниченно-однотипная структурная схема и XML документ D валиден для S. Пусть также любые два домена из множества Т не пересекаются и для любого типа элемента e, мультимножество имен типов атрибутов из множества a(e) содержит только уникальные значения. Тогда существует и притом единственная интерпретация документа D в терминах S.

Для доказательства этого утверждения необходимо воспользоваться свойством согласования содержания элемента.

В заключении этого раздела, заметим, что исследования, проведенные в работе [13] показали, что множество структурных схем, соответствующих схемам, выраженным на языке DTD принадлежит классу локальных структурных схем. Множество структурных схем, соответствующих схемам, выраженным на языке DTD принадлежит классу однотипных структурных схем. И наконец, множество структурных схем, соответствующих схемам, выраженным на языке Relax NG, является полным множеством структурных схем.


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