Транзитивность

Пополнение

Рефлексивность

Определение

Пусть F – множество функциональных зависимостей для схемы отношения R, и имеется еще одна функциональная зависимость f : X  Y. Говорят, что функциональная зависимость X  Y логически следует из F, если для любой реализации отношения r(R), удовлетворяющей всем зависимостям из F, удовлетворяется также и зависимость X  Y.

Пример: Пусть существует схема отношения R(A,B,C), и для нее определено следующее множество функциональных зависимостей F = {A  B, B  C}. Тогда функциональная зависимость A  C логически следует из F.

Логическим замыканием F (обозначается как F⁺) называется полное множество функциональных зависимостей, которые логически следуют из F.

Правила вывода Армстронга

Важно иметь возможность из F получить F⁺. F⁺ получается из F с помощью специальных правил вывода.

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

Правила вывода позволяют по заданному множеству F функциональных зависимостей получить F⁺. Причем эти правила являются:

1. полными, в том смысле, что для заданного множества F функциональных зависимостей эти правила позволяют вывести все функциональные зависимости, принадлежащие F⁺;

2. надежными (исчерпывающими), в том смысле, что, используя их, нельзя вывести из F некоторую функциональную зависимость, не принадлежащую F⁺.

Рассмотрим правила вывода. Введем следующие обозначения:

R(A1A2…An) – схема отношения;

U = {A1, A2, …An} – универсальное множество атрибутов;

X ⊆ U, Y ⊆ U, Z ⊆ U, W ⊆ U – некоторые подмножества атрибутов из U;

XY – объединение атрибутов: X ∪ Y ≡ XY

Если имеется некоторая совокупность атрибутов X = YZ (т.е. Y есть некоторое подмножество из X), тогда X  Y.

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

Из этой зависимости следует (если Z = ∅), что X  X.

Или расширение левой части.

Если существует функциональная зависимость X  Y, то XZ  YZ.

Важно, что функциональная зависимость X  Y или принадлежит F, или может быть логически выведена из F с помощью описываемых правил.

Пример:

Пусть дана схема отношения R(A B C D), для которой определена функциональная зависимость

A  B. Рассмотрим некоторую реализацию отношения:

Дано

Следует



Если X  Y и Y  W, то X  W.

Рассмотрим пример:

Дано:

Следует:

