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

Пополнение

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

Определение

Определение

Пусть 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. Рассмотрим некоторую реализацию отношения:

            Дано   Следует
R (A B C D)   A B   A C B C
  a1 b1 c1 d1   a1   b1   a1 c1   b1 c1
  a2 b2 c1 d1   a2   b2   a2 c1   b2 c1
  a1 b1 c1 d2   a1   b1   a1 c1   b1 c1
  a3 b2 c2 d3   a3   b2   a3 c2   b2 c2
  a1 b1 c2 d2   a1   b1   a1 c2   b1 c2

 

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

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

                Дано:       Следует:
R (A B C D)   A B и B C   A C
  a1 b1 c2 d1   a1   b1   b1   c2   a1   c2
  a2 b2 c1 d2   a2   b2   b2   c1   a2   c1
  a3 b1 c2 d1   a3   b1   b1   c2   a3   c2
  a3 b1 c2 d3   a3   b1   b1   c2   a3   c2