Теоретические основы защиты информации.

строка появится, а первичный ключ будет null. Теорема доказана.

Пусть дано R(A₁,С₁,..., А_n,С_n), где А₁ - первичный ключ. Первый шаг декомпозиции - создать базовоеотношение R_1,X для каждого значения х атрибута С₁ первичного ключа А₁, т.е. для каждого xÍ(L₁, Н₁)создаем R_1.X(A₁) с классом х. Назовем их "отношениями, связанными с первичным ключом". Если первичный ключ состоит из нескольких атрибутов,

то, в силу равномерности классификации, можно считатьего одним атрибутом А₁ с одним классификационным атрибутом С₁ и для него создать R_1.X(A₁).

Второй шаг. Для произвольного А.(которое может также быть множеством атрибутов, но равномерно классифицированным с атрибутом С_i) образуем базовые отношения (называемые "отношения, связанные с атрибутом А_i").

Для i = 2,...,n каждой паре х,у, xÎ(L₁, Н₁), yÎ(L_i, Н_i), у>х (из теоремы 3) строим R_i,X,Y(A₁, А_i) с классом у.

В этих отношениях, очевидно, А₁ - первичный ключ. Однако таким отношениям присваивается класс у (поднимая, возможно, уровень значения первичного ключа, что при восстановлении исправляется исходя из информации в R_1,X), таким образом, эти отношения одноуровневые по построению. Алгоритм декомпозиции следующий (заменим R на {R_1,X(A₁), R_i,X,Y(A₁, А_i)}): для каждой строки (а₁,с₁,..., a_n,с_n) в R поместим а₁ в R_1,C1 и для i=l,..., n поместим (а₁, а_n) в R_i.C1.Ci. Любая новая строка при коррекции БД разлагается также.

Пример 7. Рассмотрим отношение из примера 1.

Очевидно, что, если исходное отношение - одноуровневое, то процедура декомпозиции тривиальна.

Рассмотрим процедуру восстановления MLS из базовых одноуровневых отношений. Определим оператор "ml", который преобразует строку стандартных отношений R_1,X или R_i,X,Y , в строку MLS отношения.

а) m1(R_i,X) - многоуровневое отношение R' со схемой R'(A₁,C₁). Для каждой строки а₁ в R_1,X строка (а₁, х) строится в R'.

б) m1(R_i,X,Y) - многоуровневое отношение R' со схемой R'(A₁, С₁, А_i, С_i). Для каждой строки а₁, а_i в R_i,X,Y строка (а₁, х, а_i, у) строится в R'.

Обозначим через У_AB оператор Outer-join относительно атрибутов АВ и через U оператор Union. Тогда формула для восстановления R имеет вид:

Recover(R) = È (R’_1,XУ_A1C1R’_2,X У_{A1C1 ...} У_A1C1R’_n,X),

                                         xÎ{L₁,H₁}

где R'_i,X= U         R'_i,X,Y,  i = 2,..., n,

            ye{max(L_i,x),H,)

              R’_1,X = m1(R_1,X),

             R'_i,X,Y =m1(R'_i,X,Y ).

Можно доказать следующую теорему.

Теорема 4. Recover (Decompose R) = R.

Вместо доказательства восстановим пример 1.

Пример 8. m1(R_i,X) = R’_i,X

                  m1(R_i,X,Y) = R’_i,X,Y

Recover(R)=((R'_1SУ_A1C1R’_2SS)У_A1C1