Проблема полиинстантинации.

Суть проблемы поясним на простом примере.

Пример 6. Пусть пользователь получил обзор, как это было сделано в примере 2 и решил дополнить его имеющимся в его распоряжении данными. Это нельзя запрещать, т.к. легко строится канал утечки. Предположим, что он достроил отношение примера 2.

A1	C1	A2	C2	A3	C3
mad	S		S	X	S
foo	S		S	U	S
ark	S		S	Z	S

Тогда в базе данных появились две таблицы с одинаковым набором значений ключевого атрибута, в том виде, как он виден пользователю. Это явление получило название полиинстантинация. Одно из решений проблемы - ввести классификационные атрибуты в состав ключевых атрибутов.

Построим декомпозицию произвольной MLS R в семейство стандартных базовых отношений БД. Тогда реальные отношения получаются как обзор этих базовых. При этом, стандартные базовые отношения будут одноуровневыми. Отсюда следует, что механизм хранения их идентичен механизму хранения в обычной БД (не MLS), т.е. имеется ввиду отображение при помощи программного обеспечения в файлы, сегменты и т.д. Механизм защиты здесь - внешний и не связан с конкретными элементами информации. Этот механизм определяет защиту и доступ к информации любого заданного класса.Сначала несколько замечаний.

Определение. Пусть множество атрибутов А одинаково классифицируются на всех строках отношения, тогда говорят, что они равномерно классифицированы.

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

Доказательство. Если первичный ключ не равномерно классифицирован, то возможно существует пользователь, который не имеет права на высший класс, но имеет право на низший. В этом случае, в обзоре этого отношения в атрибуте высшего класса первичного ключа должны стоять null, что противоречит требованиям целостности хранимой информации (в первичном ключе нельзя иметь null). Аналогично, если какой-то элемент имеет класс меньший, чем элементы первичного ключа, то в обзоре эта строка появится, а первичный ключ будет 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 (R'_3SS U R'_3STS)) U

U (R'_1TSУ_A1C1R’_2TSTSУ_A1C1R'_3TSTS).

Отсюда получаем отношение примера 1.

 

Заключение

В данной лекции были рассмотрены основные модели ценности информации и проиллюстрированы примеры их использования для обработки информации.

⇐ Предыдущая123

Поделиться:

Воспользуйтесь поиском по сайту: