Понятие функциональной зависимости

Пусть R – это отношение. С одной стороны, оно имеет конкретное (постоянное) значение в данный момент времени. С другой стороны, это переменная, которая в каждый момент времени может принять некоторое новое значение.

Понятие ФЗ можно применить и к первому, и ко второму случаю. Однако мы будем рассматривать только второй случай, т.к. он больше соответствует реальности.

Определение функциональной зависимости. Пусть R – переменная отношения. X и Y – произвольные подмножества множества атрибутов R. Тогда Y функционально зависит от X, что в символическом виде записывается как X → Y (читается как «X функционально определяет Y») тогда и только тогда, когда для любого допустимого значения R каждое значение X связано точно с одним значением Y.

Здесь X называют детерминантом ФЗ, а Y – зависимой частью ФЗ.

Пример: Пусть R – это отношение Students. X – код студента, а Y – множество всех атрибутов студента. Тогда X → Y, т.к. X представляет собой первичный ключ, который уникально идентифицирует запись в таблице Students.

Такое утверждение будет верно и для более общего случая: если X – это потенциальный ключ, то множество всех атрибутов R всегда функционально зависит от X.

Однако следует иметь в виду, что если в R имеется ФЗ, левая часть которой не включает потенциальный ключ, то R обладает избыточностью, что затрудняет обеспечение целостности данных и занимает лишние ресурсы системы.

Если ни один атрибут не может быть опущен из левой части, то такая функциональная зависимость называется неприводимой (точнее, неприводимой слева).

Пример:

{ StudentID, FirstName, LastName, MiddleName } → { BirthDate } – приводимая ФЗ.

{ StudentID } → { BirthDate } – неприводимая ФЗ.

Множество функциональных зависимостей называется неприводимым тогда и только тогда, когда оно обладает всеми тремя перечисленными ниже свойствами:

1. Зависимая часть каждой функциональной зависимости содержит только один атрибут.

2. Детерминант каждой функциональной зависимости является неприводимым.

3. Ни одна функциональная зависимость из множества не может быть удалена без потери информации о связях.

Рассмотрение множества неприводимых ФЗ важно для нормализации отношений.

Выделяют два вида ФЗ:

1. Тривиальные ФЗ – это ФЗ, в которых правая часть (Y) является подмножеством левой части (X). С практической точки зрения они не представляют значительного интереса, однако с точки зрения формальной теории зависимостей необходимо учитывать их наличие.

2. Нетривиальные ФЗ. Они действительно являются ограничениями целостности данных, поэтому в дальнейшем мы будем рассматривать именно нетривиальные ФЗ.

Для определения того в какой нормальной форме находится отношение, требуется найти все ФЗ. Существуют три правила Армстронга (шведский математик), позволяющие из начального множества ФЗ вывести возможные ФЗ.

Пусть A, B, C – это подмножества множества атрибутов отношения R, AB – объединение этих подмножеств.

1. Правило рефлексивности. Если множество B является подмножеством множества А, то А → В. (По сути, это определение тривиальной зависимости.)

2. Правило дополнения. Если А → B, то АС → ВС.

3. Правило транзитивности. Если А → B и B→C, то А → С.

Каждое из этих правил может быть доказано на основе определения ФЗ.

Однако в целях упрощения получения всех ФЗ можно вывести еще несколько дополнительных правил (пусть D – это еще одно произвольное подмножество множества атрибутов R):

4. Правило самоопределения. А → А.

5. Правило декомпозиции. Если А → ВС, то А → B и A → C.

6. Правило объединения. Если А → В и А → С, то А → ВС.

7. Правило композиции. Если А → B и С → D, то АС → BD.

8. Теорема всеобщего объединения. Если А→ B и C → D, то А(С – В) → BD.

Название теоремы указывает на то, что некоторые из перечисленных выше правил могут быть выведены как частные случаи этой теоремы.

Однако следует иметь в виду, что эти правила не обеспечивают чёткого алгоритма получения всех ФЗ. Более того, такого алгоритма не существует. Единственный путь – это перебор всех вариантов.