Теоретические основы технологии баз данных. Функциональные зависимости, аксиомы и ключи

1. Функциональные зависимости (ФЗ)

1.1. Определение

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

Пусть дано отношение R со схемой S. Атрибут (или множество атрибутов) Y функционально зависит от множества атрибутов X (обозначается X → Y) тогда и только тогда, когда для любого допустимого экземпляра отношения R каждому значению X соответствует ровно одно значение Y.

Простыми словами: Если мы знаем значение X, мы однозначно можем определить значение Y. В любой момент времени в таблице не может быть двух кортежей с одинаковым X, но разным Y.

Пример: В отношении Сотрудники (ТабНомер, Имя, Отдел, Оклад) существует ФЗ: ТабНомер → Имя (по номеру узнаем имя). Однако Имя → ТабНомер неверно, так как одно имя могут носить разные люди (неоднозначность).

1.2. Тривиальные и нетривиальные зависимости

Тривиальная ФЗ: Зависимость, где Y является подмножеством X (X → Y). Она выполняется всегда (например, {Имя, Возраст} → Имя).
Нетривиальная ФЗ: Y не является подмножеством X (X → Y и Y ⊄ X). Именно такие зависимости описывают семантику предметной области.
Совсем нетривиальная: X ∩ Y = ∅.

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

Для логического вывода одних ФЗ из других используется полная система аксиом, предложенная Уильямом Армстронгом. Эти аксиомы являются звуковыми (порождают только истинные ФЗ) и полными (позволяют вывести все возможные ФЗ).

Пусть A, B, C — подмножества атрибутов отношения R.

2.1. Базовый набор (3 аксиомы)

Рефлексивность (Axiom of Reflexivity): Если B ⊆ A, то A → B. (Смысл: подмножество всегда определяет само себя. Все тривиальные зависимости выводятся отсюда).
Пополнение (Axiom of Augmentation): Если A → B, то для любого множества C выполняется AC → BC (или A ∪ C → B ∪ C). (Смысл: если X определяет Y, то можно добавить один и тот же атрибут Z с обеих сторон, зависимость сохранится).
Транзитивность (Axiom of Transitivity): Если A → B и B → C, то A → C. (Смысл: цепное правило, как в математике: если a=b и b=c, то a=c).

2.2. Дополнительные правила вывода (Следствия из аксиом)

Хотя трех аксиом достаточно для полноты, на практике удобно использовать производные правила:

Объединение (Union / Additive rule): Если A → B и A → C, то A → BC. (Одно и то же множество определяет несколько атрибутов → можно объединить правые части).
Декомпозиция (Decomposition / Projective rule): Если A → BC, то A → B и A → C. (Обратное объединению: можно разбить правую часть).
Псевдотранзитивность (Pseudotransitivity): Если A → B и BC → D, то AC → D. (Позволяет “подставить” зависимость в левую часть другой зависимости).

3. Полнота и непротиворечивость (Надежность) системы аксиом

Это два ключевых свойства, которые делают аксиомы Армстронга математически корректным инструментом проектирования.

3.1. Непротиворечивость (Звуковость / Soundness)

Определение: Система аксиом является непротиворечивой (звуковой), если любая ФЗ, выведенная из заданного множества F с помощью этих аксиом, обязательно логически следует из F (т.е. является истинной для всех отношений, удовлетворяющих F).

Доказательство: Аксиомы рефлексивности, пополнения и транзитивности очевидно истинны для любого отношения. Применяя их, мы не можем получить ложную зависимость. Это гарантирует, что мы не “сгенерируем” несуществующую связь.

3.2. Полнота (Completeness)

Определение: Система аксиом является полной, если для любого множества ФЗ F любая ФЗ, которая логически следует из F (т.е. верна во всех отношениях, где верны F), может быть выведена из F путем многократного применения этих аксиом.

Смысл полноты: Аксиомы дают нам исчерпывающий механизм. Если зависимость существует в реальности (следует из семантики), мы гарантированно сможем ее вывести, используя только эти три правила, без необходимости перебора всех кортежей базы данных.

Итог: Благодаря полноте и непротиворечивости, мы можем безопасно оперировать замыканием множества зависимостей (F⁺), не заглядывая в сами данные.

4. Замыкание множества атрибутов (X⁺)

Хотя аксиомы позволяют выводить ФЗ, на практике для проверки, является ли атрибут ключевым, используется алгоритм вычисления замыкания множества атрибутов.

Определение: X⁺ — это множество всех атрибутов, которые функционально определяются множеством X (включая сам X).

Алгоритм вычисления (итеративный):

Начальное состояние: X⁺ = X.
Ищем ФЗ вида (A → B), где A ⊆ X⁺, но B ⊄ X⁺.
Добавляем B в X⁺ (X⁺ = X⁺ ∪ B).
Повторяем шаги 2-3, пока X⁺ перестанет расти.

5. Определение первичного ключа

5.1. Строгое определение через замыкание

Множество атрибутов K является первичным ключом отношения R, если оно удовлетворяет двум условиям:

Уникальность (Свойство идентификации): K⁺ = S (все атрибуты схемы отношений). То есть K функционально определяет все остальные атрибуты.
Минимальность (Неизбыточность / Irreducibility): Никакое собственное подмножество K’ ⊂ K не обладает свойством уникальности (т.е. (K’)⁺ ≠ S).

5.2. Кандидаты в ключи (Candidate Keys)

Отношение может иметь несколько различных множеств атрибутов, удовлетворяющих этим двум условиям. Каждое такое множество называется потенциальным ключом (или ключом-кандидатом).

Один из потенциальных ключей выбирается проектировщиком в качестве первичного ключа (Primary Key). Остальные кандидаты становятся альтернативными ключами (Alternate Keys).

5.3. Отличие от суперключа

Суперключ — это любое множество атрибутов, содержащее в себе ключ (K ∪ {любой атрибут}). Оно также определяет все атрибуты (X⁺ = S), но не минимально. Первичный ключ — это всегда суперключ, но суперключ не всегда первичный ключ (он избыточен).

5.4. Определение первичного ключа через правила вывода

Для практической проверки минимальности используется аксиома декомпозиции:

Проверяем, что K → Атрибут_1, K → Атрибут_2 … и т.д.
Затем пытаемся удалить атрибут A из K. Если для (K \ {A}) всё еще выполняется (K \ {A}) → Все_атрибуты, значит, текущий K не минимален, и мы нашли более короткий ключ.

Резюме

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