Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
отношения:
Отношение "Сотрудники"
Табельный номер Ф.И.О. Должность Номер комнаты
010 Петров Н.Л. Инженер 10
102 Иванов А.И. Зав. лаб. 20
080 Сергеев С.Н. Ст. инженер 10
Отношение "Комнаты"
Номер комнаты Телефон
10 20 016 010
После устранения транзитивности зависимостей отношение попадает в 3-ю
нормальную форму.
Задача нахождения транзитивных зависимостей тесно связана с поиском
остовного дерева графа. Соответствующий алгоритм будет рассмотрен в
следующей главе.
3.4. Декомпозиция и условная независимость
В гл. 2, когда речь шла о кластерном анализе в пространстве признаков,
было введено понятие условной независимости признаков.
51
Рассмотрим пример:
в котором У и Z независимы при условии переменным X, У, Z следующие
значения:
X-фамилия лектора,
Z-день недели,
У-номер студенческой группы.
Получаем отношение "Расписание"
Присвоим
Ф.И.О. День недели Номер группы
Петров Н.Л. Понедельник Ф-17
Петров Н.Л. Понедельник М-32
Петров Н.Л. Среда Ф-17
Петров Н.Л. Среда М-32
Иванов А.И. Понедельник Ф-17
Иванов А.И. Понедельник К-10
Здесь существует единственный возможный ключ, содержащий все три
признака, отношение находится в 3-й нормальной форме. Тем не менее,
возможна дальнейшая декомпозиция:
Ф.И.О. День недели
Петров Н.Л. Петров Н.Л. Иванов А.И. Понедельник Среда Понедельник
Ф.И.О. Номер группы
Петров Н.Л. Ф-17
Петров Н.Л. М-32
Иванов А.И. Ф-17
Иванов А.И. К-10
Очевидно, с помощью соединения можно однозначно восстановить исходное
отношение, так что декомпозиция осуществляется без потерь.
52
Рассмотрим два отношения Z) и /?2(A", У), каждое из
которых содержит по два признака. Обозначим через R(X, Z, У) отношение,
полученное соединением этих отношений:
R(X, Z, У) = Пг(Х, Z) X R2(X, Y).
Обозначим через Л , R2, R проекции этих отношений на
строки с фиксированным значением атрибута X, общего для обоих отношений Л
, R^. В нашем примере для X = а имеем
R:
Очевидно, слово Z (r) Y является прямым произведением слов: Z <g> Y = Z, х
У2.
(определение прямого произведения и его свойства даны в пункте
1.14). Таким образом, Z и Y независимы (см. теорему 1.9). Для X = Ъ
получаем
R,:
*1
*2
R:
Слово Z <8> Y является также прямым произведением, a Z и Y независимы.
Таким образом, при соединении отношений Rt(X, Z) и
R2(X> У) получаются слова Z и Y, условно независимые при
условии X. При образовании прямого произведения информация
соответствующих слов суммируется. Если исходное отношение R(X, Z,Y) можно
"расщепить" на два отношения, а затем "соединить", возвращаясь к
исходному отношению, то Z и Y должны быть условно независимы. Тем самым
доказан следующий результат.
53
Теорема 3.2. Для отношения R(X, Z, У) возможна декомпозиция без потерь
тогда и только тогда, когда Z и У условно независимы при условии X. В
этом случае R(X, Z, У) является соединением отношений R^(X, Z) и
R2(X, У).
3.5. Многозначная зависимость
Пус'ъ R {A'j, Х2, ..., А^}-некоторое множество атрибутов (отношение).
Подмножество X С R будем отождествлять со сложным атрибутом, а X <8* У
соответствует объединению множеств X U Y.
Обозначим Z = R - (X <8> У). Если У и Z условно независимы при условии X,
то будем говорить, что X и У связаны многозначной зависимостью
X -*-" У.
Как было показано в гл. 2, это равносильно тому, что
X --Z.
Согласно определению, в этом случае
IQ(Z/X <8> У) = I0(Z/X), /0( Y/Х (r) Z) = /0( Y/X)
и возможна декомпозиция отношения R без потери информации (см. теорему
3.2.).
Для многозначной зависимости существуют правила вывода, аналогичные
правилам для функциональных зависимостей. Эти правила позволяют находить
новые зависимости, если известно некоторое множество многозначных
зависимостей.
Ml. Рефлексивность'. X -*-"Х.
Доказательство.
I0(X/X(r) Z) = 0 = 10(Х/Х).
М2. Пополнение: Если X -*-* У, то X (r) U -*-* У для любого
U.
Доказательство. Достаточно предположить, что U совпадает с простым
атрибутом: U - X.. Если U ? X, то доказательство тривиально. Если U ? У,
то
IQ(Z/X <S>Y<S>U)= Iq(Z/X О У) = I0(Z/X) = IQ(Z/X <S> U).
Если U ? Z, то
Iq(Y/X (r)Z(r)U)= I0(Y/X <S> Z) = /0(У/ X) = I0(Y/X (r) U).
М3. Аддитивность: Если X -"-" У и X -*-* U, то X -"-" -*-* Y(r) U.
Доказательство. Z = R - X <8 Y <8 U.
54
I0(Y0 U/X 0 Z) = I0(Y/X 0 Z) + I0(U/X (r) г (r) y) =
= I0(Y/X) + I0(u/X) =
= I0(Y/X) + I0(U/X 0 У) = I0(Y(r) U/X).
M4. Проективность: -"-" Y и X -"-" t/, то X -*•-"
-*-* Y Г\ U.
Доказательство. Пусть Zj = ./? - (A^ 0 У). Z2 = R -
- (X 0 t/) и Z = - (A^ 0 (У fl t/)). Обозначим через A^, как
обычно, дополнение множества Х, т. е. X = R - X. Тогда
Zj = а: и у, z2 = ^ и и, z = а: и (у n lo = (х и у) п (х и и) = аПТу и
FD17 =
= Zj и Z2 = Zj 0 Z2, 70(Z/AT 0 (У П U)) = IQ(Z{ 0 ZjX 0 (У П U)) =
= /0(Zj/A: 0 (У n U)) + I0(Z2/X <8> (Y П U) <8> Zj) =
= I0(Zt/X) + I0(Z2/X) = /0(Zj/X) + I0(Z2/X 0 Zj) =
= 70(Zj 0 Z2/A) = Iq(Z/X).
M5. Транзитивность: Если X -*-* У и A^ -*-* t/, то
, X -*-* Y U.
Доказательство. Y = (Y - U) U (Y Г\ U). Докажем утверждение, из которого
