Аксиомы вывода

Источник статьи

Автор24 — учеба по твоим правилам

Отношение R в любой момент имеет некоторое семейство F-зависимостей, которым удовлетворяет данное отношение. При этом одно состояние отношения удовлетворяет F-зависимости, а другое – не удовлетворяет. Необходимо найти F – семейство F-зависимостей, которому будут удовлетворять все допустимые состояния отношения R.

Множество функциональных зависимостей, которые применяются к отношению R, является конечным, поскольку существует лишь конечное количество подмножеств множества R. Следовательно, можно определить все F-зависимости, которые удовлетворяют R, путем перебора всех возможных. Время, потраченное на поиск, можно уменьшить в том случае, когда известны некоторые F-зависимости из F. В такой ситуации уменьшение времени поиска возможно зачастую потому, что остальные F-зависимости можно получить с помощью аксиом вывода.

Определение 1

Аксиома вывода является правилом, которое устанавливает, что если отношение удовлетворяет одним F-зависимостям, то оно также должно удовлетворять и некоторым другим F-зависимостям.

F1. Аксиома рефлексивности

Определение 2

Любая функциональная зависимость является рефлексивной по определению: $А \to А$ .

Определение 3

Следствие. При $В \subseteq А$ имеет место функциональная зависимость $А \to В$ .

Так как $В \subseteq А$ , то каждый кортеж проекции на А содержит кортеж проекции на В, что и объясняет следствие.

Пример 1

Пример.

Рассмотрим отношение R(X, Y, Z, W), на котором определено какое-то множество функциональных зависимостей F.

Пусть А={Y, Z, W}, а В={Y, W}, тогда очевидно, что $В \subseteq А$ . Состояния $R_i$ отношения R будут иметь вид

Аксиомы вывода. Автор24 — интернет-биржа заказчиков и авторов

т.е. одна и та же совокупность значений атрибутов, которые входят в В, всегда соответствует одной и той же совокупности значений атрибутов, которые входят в А.

«Аксиомы вывода» 👇

Помощь эксперта по теме работы

Найти эксперта

Решение задач от ИИ за 2 минуты

Решить задачу

Найди решение своей задачи среди 1 000 000 ответов

Найти

Тогда в $F^*$ входит исходное множество зависимостей F, заданные разработчиком зависимости и зависимости, которые сформированы соответственно аксиоме F1, т.е. $F^*= F \cup {X \to X, \ldots, YZW \to YW, \ldots}$ .

Аксиома F1 дает зависимости $А \to А$ , $АВ \to А$ и т.д., называемые тривиальными, характеризующиеся тем, что атрибуты, которые входят в правую часть функциональной зависимости, полностью находятся среди атрибутов, которые входят в левую ее часть.

F2. Аксиома пополнения

Определение 4

Функциональная зависимость $АВС \to В$ принадлежит $F^*$ , если на отношении R выполняется зависимость $А \to В$ и $С \subseteq Х_R$ , $А \subseteq X_R$ , $В \subseteq Х_R$ .

Данная аксиома показывает, что если в R выполняется $А \to В$ , то в левую часть функциональной зависимости можно добавить любые атрибуты, которые принадлежат $Х_R$ , что будет определением зависимостей, которые принадлежат $F^*$ .

F3. Аксиома аддитивности

Согласно данной аксиоме можно выполнить объединение двух функциональных зависимостей, если они имеют одинаковые левые части.

Определение 5

Если в отношении R существуют функциональные зависимости $А \to В$ и $А \to С$ и $А \subseteq Х_R$ , $В \subseteq Х_R$ , $С \subseteq Х_R$ , то отношение удовлетворяет и функциональной зависимости $А \to ВС$ (запись $А \to В \cup С$ принято заменять записью $А \to ВС$ ).

F4. Аксиома проективности

Данная аксиома является обратной к аксиоме аддитивности и дает возможность разделить функциональную зависимость. Согласно аксиоме,

Определение 6

если в отношении R существует функциональная зависимость $А \to ВС$ , то для него будет существовать и функциональная зависимость $А \to В$ (и $А \to С$ ).

Данное утверждение непосредственно вытекает из того, что $В \subset ВС$ (и $С \subset ВС$ ). Учитывают, что запись ВС является сокращением для $В \cup С$ .

F5. Аксиома транзитивности

Определение 7

Если $А \subseteq Х_R$ , $В \subseteq Х_R$ , $С \subseteq Х_R$ и для отношения R существуют зависимости $А \to В$ , $В \to С$ , то для него существует и зависимость $А \to С$ .

F6. Аксиома псевдотранзитивности

Определение 8

Если А, В, С и L – подмножества атрибутов отношения R, в котором существуют зависимости $А \to В$ и $ВС \to L$ , то для него выполняется и зависимость $АС \to L$ .