XML - статьи



              

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


Например, если 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, является полным множеством структурных схем.




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