Основы проектирования реляционных баз данных



              

Аксиомы вывода функциональных зависимостей - часть 5


Теперь, для того чтобы показать полноту аксиом 1-3, покажем, что если при заданном F ФЗ

Х \to Y
не может быть выведена из данных аксиом, то должно существовать такое отношение, в котором справедливы все ФЗ F, кроме ФЗ
Х \to Y
.

Рассмотрим отношение R с двумя кортежами:

X+другие атрибуты
1 1 … 11 1 … 1
1 1 … 10 0 … 0

Все зависимости из F справедливы на R. Следует показать, что

Х \to Y
не удовлетворяется на R. Допустим обратное. Из
X \subseteq Х^+
следует
Y \subseteq Х^+
, иначе два кортежа, совпадая по Х, не совпадают по Y. Тогда ФЗ
Х \to Y
следует из аксиом 1-3, что приводит к противоречию. Таким образом, аксиомы 1-3 полны.

На основе аксиом вывода можно уточнить понятие замыкания множества ФЗ

F - F^+
, как наименьшего множества, содержащего F, которое не может быть расширено за F с помощью аксиом 1, 2 и 3. Понятие замыкания является основным при доказательстве приведенного выше утверждения. Оно также важно при определении, имеет ли множество ФЗ F зависимость
Х \to Y
. Для этого достаточно проверить, принадлежит ли рассматриваемая зависимость множеству F+.

Вычисление замыкания конечного множества ФЗ является трудоемкой задачей, так как необходимо перебрать множество всех подмножеств, а таких множеств, как известно, 2n, где n - число элементов исходного множества. Однако вычислить замыкание X+ для данного множества атрибутов несложно. Алгоритм вычисления приведен ниже. Можно показать, что этот алгоритм корректно вычисляет замыкание X+.

Алгоритм вычисления X+

Input: U - конечное множество атрибутов, множество ФЗ F на U, множество

X \subseteq U
.

Output: X+

  1. Х0 есть Х.
  2. Xi+1 есть Xi плюс множество атрибутов А, для которых в F существует ФЗ
    Y \to Z, A \subseteq Z, Y \subseteq X^i
    .

Условие завершения. Так как U - конечно и

X = X^0 \subseteq \dots \subseteq X^i \subseteq \dots К \subseteq
, то существует i, такое, что Xi = Xi+1.

Пример. Вычислим Х+

Пусть

F = {AB \to C, C \to A, BC \to D, ACD \to B, D \to EG, BE \to C, CG \to BD, CE \to AG} и X=BD
.
  1. X^0=BD
  2. Находим ФЗ, которые в левой части имеют
    B, D, BD - D \to EG
    . Присоединим E и G к X0. X1 = BDEG. Находим ФЗ с левыми частями из
    Х^1 - D \to EG, BE \to C. X^2 = BCDEG
    . Находим ФЗ с левыми частями из
    Х^2 - C \to A, BC \to D, CG \to BD, CE \to AG. X^3 = ABCDEG
    .
  3. X^4 = X^3 \dot (BD)^+ = ABCDEG
    .




Содержание  Назад  Вперед