пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Функциональные зависимости. Аксиомы вывода

6.2.1. Функциональные зависимости

Функциональная зависимость определяется для атрибутов, находящихся в одном и том же отношении в 1НФ. Функциональная зависимость является семантическим свойством атрибутов отношения.

Пусть дана схема отношения R(А1, А2, ...., Аn).

Атрибут А2 функционально зависит от атрибута А1 если каждому значению А1 соответствует единственное значение А2 ( т. е. каждый кортеж, имеющий одно и то же значение А1, должен иметь одно и то же значение А2)

Обозначается подобная ситуация так: А1 → А2. Левая часть функциональной зависимости называется детерминантом, а правая часть — зависимой частью. Отсутствие функциональной зависимости обозначается А -/→ В.

Рассмотренная выше функциональная зависимость — это F-зависимость.

Дадим более общее формальное определение функциональных зависимостей.

Пусть r-отношение со схемой R, а X, Y— подмножества R. Отношение r удовлетворяет функциональной зависимости X → Y, если для любых двух кортежей t1 и t2 в r t1(X) = t2(X), то t1(Y) = t2(Y).

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

Для отношения r(R) в любой момент существует некоторое семейство F-зависимостей, которым это отношение удовлетворяет . Причем одно состояние отношения может удовлетворять F-зависимости, а другое — нет. Требуется выявить семейство F-зависимостей F, которому удовлетворяют все допустимые состояния r.

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

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

Ниже приведены шесть аксиом вывода для F-зависимостей. В их формулировках используется обозначение r для отношения на R, и W, X, У, Z для подмножеств R.

Запишем кратко все аксиомы.

  • F1. Рефлексивность: X → X.
  • F2. Пополнение: Х → Y влечет за собой XZ → Y.
  • F3. Аддитивность: Х → Y и Х → Z влечет за собой Х → YZ.
  • F4. Проективность: Х → YZ влечет за собой Х → Y.
  • F5-Транзитивность: Х → Y и Y → Z влечет за собой Х → Z.
  • F6. Псевдотранзитивность: Х → Y и YZ → W влечет за собой ХZ → W.

07.06.2017; 13:31
хиты: 147
рейтинг:0
Точные науки
информатика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь