XML - статьи

Третья нормальная форма.


Определение 23 (Простые регулярные выражения) Простые (п.) регулярные выражения над множеством E (regS(E))определяются следующим образом:

  • ?-п. регулярное выражение, где обозначает "пустой список"
  • e
    E: e- п. регулярное выражение
  • Если r1 и r2- п. регулярные выражения, то r1, r2 - тоже п. регулярное выражение
  • Если r =e , где e
    E, то r* ,r? r+ - п. регулярные выражения
  • Определение 24 (Третья нормальная форма) Схема S=(T,E,A,p,a,r) представлена во третьей нормальной форме (простая нормальная форма), если:

    e
    E p(e)=r , где r
    regS(E)

    Teoрема 7 (Существование третьей нормальной формы) Для любой схемы S=(T,E,A,p,a,r) существует схема, являющаяся ее упрощением, и представленная в третьей нормальной форме.

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

    Пример 8 Рассмотрим регулярное выражение из примера 7.

    (b|c)?,(f?,b*)*-> (b?,c?)?,f?*,b** -> b??,c??,f?*,b** -> b?,c?,f*,b* -> b*,c?,f*

    В отличие от первой и второй нормальных форм, для третьей нормальной формы можно сформулировать и доказать теорему единственности. Пусть на множестве E введено отношение порядка. Тогда, определим простые упорядоченные регулярные выражения следующим образом:

    Определение 25 (Простые упорядоченные регулярные выражения) Простые упорядоченные (п. у.) регулярные выражения над множеством E (regSO(E))определяются следующим образом:

  • ? -п. у. регулярное выражение, где обозначает "пустой список"
  • e
    E: e- п. у. регулярное выражение
  • Если r =e , где e
    E, то r* ,r? r+ - п. у. регулярные выражения
  • Если r1 и r1- п. регулярные выражения, и
    a1,a2
    E, таких, что
    s1= [e0,..,ei-1,a1,ei+1,..,en], s2= [e'0,..,e'i-1,a2,e'i+1,..,e'n] s1|=r1, и s2|=r2 верно, что e1e2, то r1, r2 - тоже п. у. регулярное выражение

  • Определение 24 (Третья нормальная форма) Схема S=(T,E,A,p,a,r) с заданным отношением порядка на множестве E представлена в третьей нормальной форме (простая нормальная форма), если:

    e
    E p(e)=r , где r
    regSO(E)

    Если не существует двух типов элементов с одинаковым именем, то отношение порядка на множестве E может соответствовать лексикографическому порядку на множестве имен элементов.

    Teoрема 8 (Существование и единственность третьей нормальной формы) Для любой схемы S=(T,E,A,p,a,r), такой, что на множестве Е задано отношение порядка, существует и единственная схема S'=(T,E,A,p',a,r) , представленная в третьей нормальной форме, являющаяся ее упрощением.


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