1. Определение замыкания множества атрибутов

Замыкание множества атрибутов (обозначается как ( X^+ )) — это множество всех атрибутов отношения, которые функционально следуют из множества атрибутов ( X ) при заданной системе функциональных зависимостей ( F ).

Формально:
( X^+ = { A \mid F \models X \rightarrow A } ), то есть это все атрибуты ( A ), которые детерминируются атрибутами из ( X ) на основе аксиом Армстронга (рефлексивности, пополнения и транзитивности).

Суть: Замыкание отвечает на вопрос: «Если известно значение набора атрибутов ( X ), значения каких еще атрибутов мы можем однозначно вычислить во всех допустимых экземплярах отношения?»

2. Алгоритм построения замыкания множества атрибутов (Итеративный)

Алгоритм предназначен для вычисления ( X^+ ) по заданному множеству ФЗ ( F ).

Входные данные:

• Множество атрибутов ( X ).
• Множество функциональных зависимостей ( F ).

Выходные данные:

• Замкнутое множество ( X^+ ).

Шаги алгоритма:

1. Инициализация:
   ( Closure = X ).

2. Итерация:
   Пока в ( Closure ) происходят изменения:

   • Для каждой функциональной зависимости ( LHS \rightarrow RHS ) из ( F ):
     • Если ( LHS \subseteq Closure ), то добавить все атрибуты из ( RHS ) в ( Closure ) (( Closure = Closure \cup RHS )).

3. Завершение:
   Алгоритм останавливается, когда за проход по всем зависимостям не было добавлено ни одного нового атрибута. Результат ( Closure ) является искомым замыканием.

Пример:
Пусть ( R(A, B, C, D, E) ), ( F = { A \rightarrow B, B \rightarrow C, CD \rightarrow E } ).
Вычислим ( {A}^+ ):

• Шаг 0: ( Closure = {A} ).
• Шаг 1: ( A \rightarrow B ) применима → добавляем B. ( Closure = {A, B} ).
• Шаг 2: ( B \rightarrow C ) применима → добавляем C. ( Closure = {A, B, C} ).
• Шаг 3: ( CD \rightarrow E ) НЕ применима, так как ( D \notin Closure ).
• Итог: ( {A}^+ = {A, B, C} ).

3. Алгоритм проверки эквивалентности множеств функциональных зависимостей

Два множества ФЗ ( F ) и ( G ) называются эквивалентными (( F \equiv G )), если их замыкания (множества всех логических следствий) совпадают: ( F^+ = G^+ ).
На практике это означает, что любая зависимость из ( F ) выводима из ( G ), и наоборот.

Алгоритм проверки эквивалентности:

Для доказательства ( F \equiv G ) необходимо проверить два условия:

1. Каждая зависимость из ( F ) следует из ( G ).
2. Каждая зависимость из ( G ) следует из ( F ).

Пошаговая процедура:

1. Проверка ( F \subseteq G^+ ):

   • Для каждой функциональной зависимости ( f: X \rightarrow Y ) из множества ( F ):
     • Вычислить замыкание ( X^+ ) относительно множества зависимостей ( G ) (используя алгоритм из п. 2).
     • Если ( Y \subseteq X^+ ), то зависимость ( f ) выводима из ( G ). Если хотя бы для одной ( f ) это условие не выполняется → множества не эквивалентны.

2. Проверка ( G \subseteq F^+ ):

   • Для каждой функциональной зависимости ( g: X \rightarrow Y ) из множества ( G ):
     • Вычислить замыкание ( X^+ ) относительно множества зависимостей ( F ).
     • Если ( Y \subseteq X^+ ), то зависимость ( g ) выводима из ( F ). Если условие нарушается → множества не эквивалентны.

3. Вывод:

   • Если оба пункта выполнены успешно, то ( F \equiv G ). В противном случае — не эквивалентны.

4. Алгоритм построения минимального покрытия (канонического покрытия) множества функциональных зависимостей

Минимальное покрытие (или неприводимое множество) ( F_{min} ) — это множество ФЗ, эквивалентное исходному ( F ), но обладающее свойствами:

1. Правая часть каждой зависимости содержит ровно один атрибут (справа нет множеств).
2. Левая часть каждой зависимости минимальна (нельзя удалить ни один атрибут из ( LHS ), не изменив замыкание).
3. В множестве нет избыточных зависимостей (ни одну из них нельзя удалить, не потеряв эквивалентности).

Алгоритм построения минимального покрытия:

Шаг 1. Приведение правых частей к единичным атрибутам (Декомпозиция)

Для каждой зависимости ( X \rightarrow A_1 A_2 … A_n ) заменить её на набор зависимостей:
( X \rightarrow A_1, X \rightarrow A_2, …, X \rightarrow A_n ).

Шаг 2. Минимизация левых частей (Сокращение атрибутов в детерминантах)

Для каждой зависимости ( X \rightarrow A ) и для каждого атрибута ( B \in X ):

• Временно удалить ( B ) из левой части: ( X’ = X \setminus {B} ).
• Вычислить ( (X’)^+ ) относительно текущего множества зависимостей (уже с учётом возможных изменений).
• Если ( A \in (X’)^+ ), значит атрибут ( B ) в левой части избыточен. Удаляем ( B ) из ( X ) окончательно (заменяем ( X \rightarrow A ) на ( X’ \rightarrow A )).

Шаг 3. Удаление избыточных зависимостей

Для каждой зависимости ( f: X \rightarrow A ) в текущем множестве:

• Временно удалить ( f ) из множества ( F ), получаем ( F’ ).
• Вычислить замыкание ( X^+ ) относительно ( F’ ).
• Если ( A \in X^+ ), значит ( f ) логически следует из остальных зависимостей и является избыточной. Удаляем ( f ) из множества навсегда.

Важное замечание: Порядок обработки зависимостей на шагах 2 и 3 может влиять на конкретный вид минимального покрытия, но все получаемые варианты будут эквивалентны исходному множеству.

Пример полного построения минимального покрытия

Дано: ( F = { AB \rightarrow C, C \rightarrow A, BC \rightarrow D, ACD \rightarrow B, D \rightarrow EG } ).

Шаг 1. Декомпозиция:
( AB \rightarrow C )
( C \rightarrow A )
( BC \rightarrow D )
( ACD \rightarrow B )
( D \rightarrow E )
( D \rightarrow G )

Шаг 2. Минимизация левых частей:

• Для ( AB \rightarrow C ):

  • Попробуем удалить ( A ): ( (B)^+ ) по F = {B} (ничего не даёт) → ( C \notin (B)^+ ), оставляем A.
  • Попробуем удалить ( B ): ( (A)^+ = {A} ) → ( C \notin (A)^+ ), оставляем B.
  • Итог: ( AB \rightarrow C ) (неизменно).

• Для ( BC \rightarrow D ):

  • Удалим B: ( (C)^+ = {C, A} ) (через ( C \rightarrow A )). D не входит → оставляем B.
  • Удалим C: ( (B)^+ = {B} ). D не входит → оставляем C.
  • Итог: ( BC \rightarrow D ).

• Для ( ACD \rightarrow B ):

  • Удалим A: ( (CD)^+ ).
    Из ( D \rightarrow E, D \rightarrow G ) и ( BC \rightarrow D ) (но нет B) — из CD ничего не следует, кроме E, G. B не входит → оставляем A.
  • Удалим C: ( (AD)^+ ).
    Из D получаем E, G. Из A ничего. B нет → оставляем C.
  • Удалим D: ( (AC)^+ ).
    Из C → A, из A ничего. B нет → оставляем D.
  • Итог: ( ACD \rightarrow B ).

Шаг 3. Удаление избыточных зависимостей:

Проверим ( AB \rightarrow C ). Удалим её. Найдём ( (AB)^+ ) по оставшимся:
( AB ) → из ( C \rightarrow A ) (но А уже есть), ( BC \rightarrow D ) (нет С), ( ACD \rightarrow B ) (нет C,D), ( D \rightarrow E,G ) (нет D).
Итог: ( (AB)^+ = {A, B} ). ( C ) не входит → зависимость НЕ избыточна, оставляем.

Проверим ( C \rightarrow A ). Удалим её. ( (C)^+ ) по остальным:
C → нет правил с C в левой, кроме ( BC \rightarrow D ) (нет B). Итог: ( {C} ). A не входит → оставляем.

Проверим ( BC \rightarrow D ). Удалим. ( (BC)^+ ):
B и C, есть ( C \rightarrow A ) → добавляем A. Есть ( ACD \rightarrow B ) (но нет D). Итог: ( {A, B, C} ). D нет → оставляем.

Проверим ( ACD \rightarrow B ). Удалим. ( (ACD)^+ ):
A, C, D. Из D → E,G. Из C → A (уже есть). BC → D (нет B). Итог: ( {A, C, D, E, G} ). B нет → оставляем.

Проверим ( D \rightarrow E ). Удалим. ( (D)^+ ):
Из D → G (оставшаяся). Больше ничего. E не входит → оставляем.

Проверим ( D \rightarrow G ). Удалим. ( (D)^+ ):
Из D → E. G не входит → оставляем.

Результат минимального покрытия:
( F_{min} = { AB \rightarrow C, C \rightarrow A, BC \rightarrow D, ACD \rightarrow B, D \rightarrow E, D \rightarrow G } ).

Итоговое резюме