Классы регулярных грамматик
В этом разделе мы приводим классификацию структурных схем. Данный метод заимствован из работы [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. Тогда
Определение 10 (Однотипные структурные схемы) Структурная схема S=(T,E,A,p,a,r) называется однотипной, если для любого типа элемента e, все типы элемента из множества ?E(p(e)) обладают разными именами.
Определение 11(Ограничено-однотипные структурные схемы) Структурная схема S=(T,E,A,p,a,r) называется ограниченно-однотипной, если для любого типа элемента e, выполняется следующее условие:
name(ei) ? name(e'i)
Следующие два утверждения очевидны и будут приведены без доказательств.
Утверждение 4 (Вложение типов) Любая локальная структурная схема является однотипной структурной схемой. Любая однотипная структурная схема является ограниченно-однотипной структурной схемой
Утверждение 5 (Достаточное условие однотипности) Пусть структурная схема S=(T,E,A,p,a,r) обладает следующим свойством:
Утверждение 6 (Единственность интерпретации) Пусть S=(T,E,A,p,a,r) ограниченно-однотипная структурная схема и XML документ D валиден для S. Пусть также любые два домена из множества Т не пересекаются и для любого типа элемента e, мультимножество имен типов атрибутов из множества a(e) содержит только уникальные значения. Тогда существует и притом единственная интерпретация документа D в терминах S.
Для доказательства этого утверждения необходимо воспользоваться свойством согласования содержания элемента.
В заключении этого раздела, заметим, что исследования, проведенные в работе [13] показали, что множество структурных схем, соответствующих схемам, выраженным на языке DTD принадлежит классу локальных структурных схем. Множество структурных схем, соответствующих схемам, выраженным на языке DTD принадлежит классу однотипных структурных схем. И наконец, множество структурных схем, соответствующих схемам, выраженным на языке Relax NG, является полным множеством структурных схем.
