Отношение R в любой момент имеет некоторое семейство F-зависимостей, которым удовлетворяет данное отношение. При этом одно состояние отношения удовлетворяет F-зависимости, а другое – не удовлетворяет. Необходимо найти F – семейство F-зависимостей, которому будут удовлетворять все допустимые состояния отношения R.
Множество функциональных зависимостей, которые применяются к отношению R, является конечным, поскольку существует лишь конечное количество подмножеств множества R. Следовательно, можно определить все F-зависимости, которые удовлетворяют R, путем перебора всех возможных. Время, потраченное на поиск, можно уменьшить в том случае, когда известны некоторые F-зависимости из F. В такой ситуации уменьшение времени поиска возможно зачастую потому, что остальные F-зависимости можно получить с помощью аксиом вывода.
Статья: Аксиомы вывода
Аксиома вывода является правилом, которое устанавливает, что если отношение удовлетворяет одним F-зависимостям, то оно также должно удовлетворять и некоторым другим F-зависимостям.
F1. Аксиома рефлексивности
Любая функциональная зависимость является рефлексивной по определению: $А \to А$.
Следствие. При $В \subseteq А$ имеет место функциональная зависимость $А \to В$.
Так как $В \subseteq А$, то каждый кортеж проекции на А содержит кортеж проекции на В, что и объясняет следствие.
Пример.
Рассмотрим отношение R(X, Y, Z, W), на котором определено какое-то множество функциональных зависимостей F.
Пусть А={Y, Z, W}, а В={Y, W}, тогда очевидно, что $В \subseteq А$. Состояния $R_i$ отношения R будут иметь вид
т.е. одна и та же совокупность значений атрибутов, которые входят в В, всегда соответствует одной и той же совокупности значений атрибутов, которые входят в А.
Тогда в $F^*$ входит исходное множество зависимостей F, заданные разработчиком зависимости и зависимости, которые сформированы соответственно аксиоме F1, т.е. $F^*= F \cup {X \to X, \ldots, YZW \to YW, \ldots}$.
Аксиома F1 дает зависимости $А \to А$, $АВ \to А$ и т.д., называемые тривиальными, характеризующиеся тем, что атрибуты, которые входят в правую часть функциональной зависимости, полностью находятся среди атрибутов, которые входят в левую ее часть.
F2. Аксиома пополнения
Функциональная зависимость $АВС \to В$ принадлежит $F^*$, если на отношении R выполняется зависимость $А \to В$ и $С \subseteq Х_R$, $А \subseteq X_R$, $В \subseteq Х_R$.
Данная аксиома показывает, что если в R выполняется $А \to В$, то в левую часть функциональной зависимости можно добавить любые атрибуты, которые принадлежат $Х_R$, что будет определением зависимостей, которые принадлежат $F^*$.
F3. Аксиома аддитивности
Согласно данной аксиоме можно выполнить объединение двух функциональных зависимостей, если они имеют одинаковые левые части.
Если в отношении R существуют функциональные зависимости $А \to В$ и $А \to С$ и $А \subseteq Х_R$, $В \subseteq Х_R$, $С \subseteq Х_R$, то отношение удовлетворяет и функциональной зависимости $А \to ВС$ (запись $А \to В \cup С$ принято заменять записью $А \to ВС$).
F4. Аксиома проективности
Данная аксиома является обратной к аксиоме аддитивности и дает возможность разделить функциональную зависимость. Согласно аксиоме,
если в отношении R существует функциональная зависимость $А \to ВС$, то для него будет существовать и функциональная зависимость $А \to В$ (и $А \to С$).
Данное утверждение непосредственно вытекает из того, что $В \subset ВС$ (и $С \subset ВС$). Учитывают, что запись ВС является сокращением для $В \cup С$.
F5. Аксиома транзитивности
Если $А \subseteq Х_R$, $В \subseteq Х_R$, $С \subseteq Х_R$ и для отношения R существуют зависимости $А \to В$, $В \to С$, то для него существует и зависимость $А \to С$.
F6. Аксиома псевдотранзитивности
Если А, В, С и L – подмножества атрибутов отношения R, в котором существуют зависимости $А \to В$ и $ВС \to L$, то для него выполняется и зависимость $АС \to L$.
