4.6. Функциональная зависимость.

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

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

При наличии X->Y любые две записи, содержащие одинаковые значения X, должны включать и совпадающие значения Y. Это ограничение распространяется не только на уже имеющиеся записи, но и на те, которые могут быть добавлены в рассматриваемое отношение. Пусть R(F1, F2):

F1 F2

A h

B i

C j

B k

Видно, что F2 не зависит функционально от F1, т.к. значению B соответствует два разных значения (i, k). Можно предположить, что F2->F1. Однако положительно утверждать это можно было бы только при условии, что в отношение нельзя ввести запись, нарушающую однозначное соответствие поля F2 полю F1 (например, (C, k)).

Если X – составное поле, то Y находится в полной функциональной зависимости от X тогда и только тогда, когда:

1. Y функционально зависит от X

2. Y не зависит функционально от любого подмножества полей, входящих в X, не совпадающего с X.

Вспомним отношение S = (МАГАЗИН, ТОВАР, НДС). В нем НДС функционально зависит от пары МАГАЗИН и ТОВАР (действительно, любой такой паре значений соответствует одно и тоже значение НДС). Но по смыслу этой величины, НДС зависит только от поля ТОВАР. Следовательно, НДС не обладает полной функциональной зависимостью от пары МАГАЗИН, ТОВАР (но обладает полной функциональной зависимостью от поля ТОВАР).

4.7. Связь между фз и полной декомпозицией отношения.

Соединение проекций отношения R по условию совпадения общих атрибутов всегда является надмножеством исходного отношения. Иногда это истинное надмножество, т. е. оно включает кортежи, которые отстутствовали в исходном отношении (см. п. о полной декомпозиции, пример с отношением S). Однако, как мы имели возможность убедиться, иногда удается подобрать полную декомпозицию, т. е. обеспечить возможность получения точного исходного отношения путем соединения проекций. Критерий, гарантирующий такую возможность, устанавливается теоремой Хита (Heath).

Пусть отношение R = (A, B, C) (A, B, C – возможно составные поля).

Теорема Хита (Heath): если A->B, то R=R[A,B] join R[A,C].

Доказательство проведем от противного (чтобы доказать, что из P следует Q, достаточно доказать, что из отрицания Q следует отрицание P). А именно, докажем, что из факта R <> R[A,B] join R[A,C] следует, что B не зависит функционально от A.

Доказательство:

Предположим, что (a, b, c)  R[A, B] join R[A, C], но (a, b, c)  R. Тогда (a, b)  R[A, B], (a, с)  R[A, С]. Следовательно, имеются (a, b, c’)  R и (a, b’, c)  R такие, что c <> c’, b <> b’. Следовательно, отсутсвует функциональная зависимость A -> B.

Итак, доказано, что при функциональной зависимости B от A проекции R[A, B] и R[A, C] образуют полную декомпозицию R.

Еще один способ доказательства:

Пусть R1 = R[H,J] join R[J,K]. Возьмем произвольную запись из R: (h, j, k). Очевидно, (h, j)  R[H,J], (j,k)  R[J,K]. Исходя из определения R1 и свойств операции условного соединения, можно заключить, что (h, j, k)  R1. Следовательно, каждая запись R принадлежит R1.

Возьмем произвольную запись из R1: (h’, j’, k). Известно, что R1[H, J] = R[H, J] (по определению R1). Следовательно, (h’, j’, k)  R. Кроме того, R1[J, K] = R[J, K] (по определению R1). Следовательно, (h, j’, k’)  R. Т. к. по условию теоремы, J->K, то из наличия записей (h’, j’, k) и (h, j’, k’) следует, что k=k’. Следовательно, каждая запись R1 принадлежит R. Следовательно, R1=R.

Рассмотрим иерархию степеней “совершенства” свойств отношений. В этой иерархии 5НФ является “венцом совершенства” а остальные формы – приближением к нему.