XML - статьи

Преобразования структурных схем


В этом разделе мы обсудим различные методы преобразования структурных схем. Эти преобразования можно разделить на три вида:

  • Эквивалентные преобразования - приводящие к схеме эквивалентной исходной,

    • Слабо-эквивалентные - приводящие к схеме, множество валидируемых документов, которой совпадает с множеством валидируемых документов исходной схемы с точностью до перестановки порядка элементов в документе,

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

Определение 12 (Эквивалентность структурных схем) Схемы D и D' эквивалентны, если множества валидируемых XML документов каждой из этих схем совпадают.

Теорема 3 (Достаточное условие эквивалентности) Две схемы S=(T,E,A,p,a,r) и S'=( T',E',A',p',a',r') эквивалентны если существует взаимно однозначное отображение M=( ф,? ,? ), где ф:E> E' ;? : E> E'; ? : T > T' обладающее следующими свойствами (отображение M-1 обладает аналогичными свойствами):

  • ?(t)? t
  • name(e)= name( ф( e))
  • ф(r)? r
  • a ?? (a)(сохраняются все свойства типов атрибута)
  • e
    a
    a(e): ? (a)
    a'(ф (e)) и R(ф (e))
    ?(a(e))
  • s=[s0,..,sn] s|=p(e)==>s'=[M(e0),..,M(en)]|=p'(ф (e))

    • Для доказательства достаточно проверить, что каждый XML документ, удовлетворяющий схеме S должен удовлетворять схеме S' . Проверка того, что каждый XML документ, удовлетворяющий схеме S' удовлетворяет схеме S, производится аналогично. Итак, пусть D|=S , где D - XML документ. В силу определения 6 должна существовать интерпретация I=( ф',?',?') документа D в терминах S. Рассмотрим отображение I'=M*I =(ф*ф', ?*? ', ?*?'). Докажем, что это интерпретация документа D в терминах S'.

  • e
    ED: name(e)= name ( ф'(e))=name(ф*ф '(e)) (согласование имени элементов)
  • a
    AD: name(e)= name (? '(a))=name(?*? ' (a)) value(a)
    dom(? '(a)) = dom(?*? '(a)) (согласование имен и значений атрибутов)
  • t
    TD: value(t)
    ?' (t) ? ?*? ' (t)(согласование текстовых узлов)
  • ae
    Ae : ?'( ae)
    a(ф '(e)) ==>?*? ' ( ae)
    a( ф*ф' (e)) (согласование атрибутов с элементами)
  • e
    ED: I(e0),.., I(en) |= p( ф'(e)) ==> I(e0),.., I(en) |= p(ф *ф' (e)) (согласование содержания элемента)


    • Остальные свойства интерпретации проверяются аналогично.

    В случае, когда E? E' шестое условие принимает следующий вид p
    p'.

    Следствие 1 (Критерий эквивалентности схем, отличающихся только структурами) Пусть S=(T,E,A,p,a,r) и S'=( T,E,A,p',a,r) две структурные схемы, у которых множество валидируемых XML документов непустое, и отличающиеся только регулярными выражениями, задающими структурное вложение. Тогда схемы S и S' эквивалентны тогда и только тогда, когда
    e
    E p(e)
    p'(e)

    Достаточное условие является следствием теоремы 3, а необходимое условие проверяется на множестве экземпляров XML документов, удовлетворяющих схемам.


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