Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
получаем множество зависимостей, которое обозначим F*n. Ясно, что F*. С
F*n, а если F*. = F*" для
Н АН Ап
всех F и В ? А , то систему правил А можно считать полной.
Т е орем а 3.1. Система правил вывода Fl-F6 является полной.
Доказательство. Допустим, что F*. * F*. для некото-
л В
рых F и В~2. А. Это означает, что существует зависимоси> X -* У, которая
не может быть выведена из F с помощью правил Fl-F6. Это должно быть
справедливо для всех отношений с 48
данным множеством атрибутов. Тем не менее, Мы построим отношение, которое
удовлетворяет всем зависимостям из F*A, но
не удовлетворяет зависимости X -* Y.
Поскольку X -+ X, а из Х-* Z следует X -+ X <8> Z ввиду аддитивности, то
существует максимальное подмножество X* (сложный признак), такое, что X -
+ X* и для любой другой зависимости X -* Z справедливо включение Z С X*.
Пусть pfj, Х2, ..., XJ-множество атрибутов. Отношение, которое мы строим,
состоит из двух строк tut'. Через t(W) будем обозначать ограничение
строки t на простых признаках, входящих в W. Каждый столбец отношения
имеет вид
(а> i
Ъ.
если X. ? X*;
, a.* b., если X. ? X*.
Покажем, что полученное отношение удовлетворяет всем зависимостям W -* Z
из F*. Если W ф X*, то t(W) * t'(W) и зависимость W -* Z выполняется
тривиально. Поэтому предположим, что W С X*. Тогда t(W) = t'(W). Ясно,
что X* -+ W ввиду рефлексивности и проективности. Поскольку X -+ X*,
применение транзитивности дает X -* Z. Следовательно, Z С X*, так что
t(Z) = t'(Z) как только t(W) = t'{W). Это означает, что отношение
удовлетворяет зависимости W -* Z.
Предположим, что выполняется также X -* Y. Тогда Y Q X*. Но так как
зависимость X -*¦ X* входит в F*, то, согласно проективности, (X -* Y) S
Поскольку мы предположили, что (X -* У) ? F*a, приходим к противоречию.
3.3. Декомпозиция на основе функциональных зависимостей
Все признаки в отношении должны быть атомарными (неделимыми), т.е.
значения в домене не являются ни списками, ни множествами простых или
сложных значений. В примере 3.1 признак "Дети", очевидно, не
удовлетворяет этому требованию. Соответствующее отношение следует
представить, расщепляя сложный признак на его составные части.
Пример 3.2.
Отношение "Сотрудники отдела"
Табельный номер Имя Ф.И.О. Возраст Должность Номер комнаты
Телефон
010 Саша Петров Н.Л. 6 Инженер 10 016
010 Игорь Петров Н.Л. 4 Инженер 10 016
010 Вова Петров Н.Л. 2 Инженер 10 016
102 Аня Иванов А.И. 10 Зав. лаб. 20 010
102 Игорь Иванов А.И. 8 Зав. лаб. 20 010
080 Вова Сергеев С.Н. 6 Ст. инженер 10 016
49
Говорят, что отношение приведено при этом к 1-й нормальной форме. В
таблице выделен первичный ключ [Табельный номер, Имя ]. Других возможных
ключей здесь нет. Можно было бы вместо атрибута "Табельный номер"
использовать атрибут "Ф.И.О." (для данного состояния отношения эти
атрибуты находятся во взаимно однозначной зависимости). Однако мы должны
иметь в виду возможность появления нового сотрудника с точно такой же
фамилией, именем и отчеством-ему будет присвоен свой табельный номер.
Поэтому функциональной связи Ф.И.О.-* Табельный номер, вообще говоря, не
существует.
Составляем граф функциональных зависимостей для данного отношения:
Табельный номер
Ф.И.О.
Должность
Имя
Номер комнаты | [Телефон] [Возраст
Говорят, что атрибут X полностью зависит от ключа К, если не существует
функциональной зависимости У -* X для любого собственного подмножества У
С к. В противном случае говорят о частичной (неполной) зависимости.
В нашем примере атрибут "Возраст ребенка" полно зависит от ключа, а
остальные атрибуты частично. Наличие неполной зависимости приводит к
избыточности данных и создает аномалии при обновлении.
Из отношения следует исключить атрибуты, которые не находятся в полной
зависимости от ключа. После этого нужно построить дополнительно одну или
несколько проекций на часть составного ключа и атрибуты, функционально
зависящие от этой части ключа. В нашем примере следует разбить исходное
отношение на два:
Отношение "Сотрудники"
Табельный номер Ф.И.О. Должность Номер комнаты Телефон
010 Петров Н.Л. Инженер 10 016
102 Иванов А.И. Зав. лаб. 20 010
080 Сергеев С.Н. Ст. инженер 10 016
Отношение "Дети сотрудников"
Табельный номер Имя Возраст
010 Саша 6
010 Игорь 4
010 Вова 2
102 Аня 10
102 Игорь 8
080 Вова 6
50
Говорят, что отношение приведено ко 2-й нормальной форме, если каждый
непервичный атрибут (т.е. атрибут, не входящий ни в один из ключей)
функционально полно зависит от каждого возможного ключа.
Дальнейшее устранение избыточности связано с понятием транзитивной
зависимости. Обратимся к отношению "Сотрудники". Граф зависимостей для
этого отношения имеет вид
Табельный номер
> * с *
Ф.И.О.
Должность
Номер комнаты
Телефон
Скажем, что имеет место транзитивная зависимость между признаками X, Y и
Z, если X -* Y, Y -* Z, но Z Y или Y X. В нашем примере транзитивная
зависимость имеет вид
Устранение такой зависимости осуществляется дальнейшим расщеплением
