 |
Решетка ценности информации в РБД
|
|
|
|
Предположим, что мы хотим внести решетку ценностей (например, MLS) в конкретную информацию, которая хранится и обрабатывается на ЭВМ. Рассмотрим примеры механизмов такого внесения и проблемы, которые здесь возникают. Для определенности рассмотрим информацию, структурированную и обрабатываемую при помощи реляционной базы данных. Такая модель информации называется реляционной моделью данных (РМ). Материалы следующих параграфов 1.5 и 1.6 базируются на работах D.Denning, T.Lunt и их коллег.
РМ состоит из отношений, которые представляют собой таблицы со многими входами, и алгебры отношений, которая позволяет строить новые отношения в терминах других отношений (в РМ входят также правила целостности хранимой информации и производной информации).
Каждое отношение R определяется схемой R (А1,...,Аn), которая характеризуется множеством атрибутовА1,..., Аn, т.е. переменных, описывающих входы таблицы.Отношение состоит из множества записей (векторов или строк), которые представляют собой значения данных в области определения атрибутов (то есть элементы таблицы - значения атрибутов).
Реляционная алгебра состоит из операторов для выбора всех или части записей, имеющих определенные значения из отношения (таблицы), и для добавления данных в различные отношения.
Для иллюстрации рассмотрим базу данных "Flight"("Полеты''). Эта база определена следующими схемами. Отношение ITEM с атрибутами: номера мест, имена, веса. Отношение Flight с атрибутами: номер рейса, дата вылета, назначение, общий вес груза. ОтношениеPAYLOAD, дающее количество использованных местна борту во время полета.
ITEM (ITEM #, ITEMNAME, Weight)
Flight (Flight #, Date, Dest, Weight)
PAYLOAD (Flight #, ITEM #, QTY, Weight)
Множество схем, определяющих отношения в базе данных, само представляется как отношение
|
|
|
Relation (Relname, Attmame),
которое содержит атрибуты всех отношений (иногда используется два отношения: одно для названий отношений, другое - для названий атрибутов).Например, в этой таблице запись
< Flight, Weight >
определяет, что отношение Flight содержит атрибутWeight.
Функциональная зависимость (FD)
Пусть X и Y два множества атрибутов в схеме R.
Определение. X функционально определяет Y(обозначается Х->Y) тогда и только тогда, когда не
существует двух различных строк (векторов) в R с одноименными значениями из X и различными из Y.
Например, в классном журнале с атрибутами имя, присутствие и отметка за данное число. Атрибут имя функционально определяет все остальные атрибуты.
Функциональная зависимость позволяет определить базовое для РМ понятие первичного ключа отношения.
Определение. Множество атрибутов называется кандидатом в ключи для отношения, если оно функционально определяет все другие атрибуты и является минимальным множеством (т.е. ни один атрибут из множества не может быть исключен так, чтобы оно по-прежнему функционально определяло остальные).
Определение. Для любого отношения один из кандидатов в ключи отношения выделяется и называется первичным ключом.
Замечание. Первичный ключ не обновляется. Первичный ключ может быть использован для выбора спецификации строк в отношении и для того,чтобы связать отношение в нечто целое.
Определение. Первичный ключ для R1, помещенныйв R2, называется вторичным ключом в R2.
Одно из основных правил целостности данных связано с первичным ключом. Целостность для элементов информации реляционной базы данных: ни одна строка таблицы не может принимать нулевое значение в каком-либо атрибуте из первичного ключа.Это свойство означает, что любые строки однозначно идентифицируемы.
Понятие функциональной зависимости позволяет определить и исследовать некоторые каналы утечки в базах данных, которые появляются из возможности вывода из одних объектов других (или еще один случай потока информации). Пусть множество F - это класс пар Х-->Y, X, YÍU=Attr(R) - множество атрибутов R.
|
|
|
Теорема 1. 1.Если YÍXÍU, то X->Y.
2. Если X->Y, Y->Z, X,Y,ZÍU, то X->Z.
3. Если X->Y, X->Z, X,Y ZÍU, то X->YÇZ.
4.Если X->Y, X->Z, X,Y,ZÍU, то X->YÈZ.
Доказательство.
1. Пусть есть два набора значений атрибутов Y, что у¹у'. Y соответствует компонентам вектора X, для которых значения атрибутов в X не совпадают на у и у'.
2. Для строк с различными значениями атрибутовY значения векторов для атрибутов X различны. Для строк с различными значениями Z значения Y различны. Тогда значения X различны. Следовательно,X->Z.
3. Очевидно.
4. а¹a' из YÈZ, тогда отличаются значения атрибутов хотя бы Y или Z, например, Z. Тогда есть отличия на X. Теорема доказана.
Определение. Множество пар функциональных зависимостей F+ называется замыканием множества пар функциональных зависимостей F, если F+ -множество всех функциональных зависимостей, которые порождаются множеством F при помощи пп.1, 2, 3, 4 теоремы 1, то есть конструктивно построены, исходя из F, используя правила теоремы.
Определение. Два множества функциональных зависимостей (FD) F и G называются эквивалентными,если F+=G+.
Доказанная ниже теорема позволяет значительно сократить класс множеств FD, которые необходимо изучать для одного и того же F+. B частности, достаточно ограничиться редуцированными FD, эквивалентными F.
Определение. Множество F функциональныхзависимостей называется редуцированным, если:
1) в F нет двух пар Х->Y и X'->Y' таких, чтоX=X' и Y¹Y';
2) для всех X->Y в F XÇY=0.
Теорема 2. Для произвольного F существует редуцированный G такой, что F+=G+.
Доказательство. Для каждого Х->Y из F построим эквивалентные функциональные зависимости в G, удовлетворяющие условиям редуцированного класса. Пусть X->Y, X'->Y' из F такие, чтоХ=Х', Y¹Y'.Если Y¹Y', то возьмем в G X->YÈY' по п. 4.
Наоборот: если в G есть X->YÈY', то в G+ по п.1есть YÈY'->Y и YÈY'->Y'.
Тогда по п. 2 теоремы 1 в G+ есть Х->Y, Х->Y'.Пункт 1 доказан.
Пусть Х->Y, XÇY¹Æ.
Отсюда по п.1 и п.2 теоремы 1: Y->Y\(YÇX)=>Y->X->Y\(YÇX).
|
|
|
Обратно. Если X->Y\(YÇX) есть в G, то Х->Y есть в G+, т.к. по п.1 теоремы 1: X->XÇY и Х->(Y\ (YÇX))È(XÇY)=Y по п.4. Теорема доказана.
Использование функциональной зависимости для компрометации базы данных иллюстрируется следующим простым примером.
Пример 1. Пусть R - отношение в реляционной базе данных некоторой компании, содержащее атрибуты имя - ранг - зарплата. Предположим, что зарплата - совершенно секретные сведения, а имя и ранг - секретные. Предположим также, что в R выполняется следующая функциональная зависимость РАНГ -> зарплата, что означает, что все служащие одного ранга получают одинаковую зарплату. Тогда пользователь, имеющий допуск к данным не выше секретно, может получить допуск к совершенно секретной информацию о конкретном лице, если он знает соответствие ранг-зарплата хотя бы для некоторых лиц.
Для того, чтобы проанализировать возможность возникновения подобных зависимостей, надо изучить все множество F+ для набора исходных зависимостей F. Это удобнее сделать, если F - редуцированное множество, что не ограничивает общности, благодаря доказанной теореме.
Целостность в РМ.
Если описывать условия целостности данных в РМ формально, это можно сделать, определив конъюнкцию одного или нескольких условий, которым должны удовлетворять набор атрибутов, выраженных формулами какого-либо языка.
Пример 2. Ограничения целостности данных могут иметь следующий вид:
I=(R.1A>O)Ù(R1.A=R2.A)Ù(0<R1.B+R2.B<100),где R1.A - атрибут А в отношении R1, R2.A -соответственно в R2, R1.B - атрибут В в R1, R2.В -в R2.
Если даны I1,...Im, то область состояний D базы данных определяется формулой
где под Ik также подразумевается множество значений, которые могут принимать атрибуты базы данных, удовлетворяющие логической формуле Ik. Будем предполагать D¹Æ.
|
|
|
