Разбираемся в функциональных зависимостях БД / Хабр

Привет Хабр! Возможно вас, как и меня, первое знакомство с функциональными зависимостями в базах данных повергло в легкий ступор. Длинные определения, которые не давались даже после третьего прочтения, излишняя абстрактность, когда на простые и понятные примеры поскупились, и прочее прелести «научного» подхода к объяснению сложных тем.

Пора раз и навсегда разобраться во всем этом. Тем не менее, я постараюсь не упускать детали и, где это уместно, углубиться в тему с головой. Без претензии на академичность, но с претензией на ясность. Начнем.

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

Сразу перейдем к примеру. Рассмотрим таблицу:

Студент	Преподаватель	Оценка	Кафедра
Иван	Сазонов	3	Математика
Иван	Никитенко	3	Физика
Рома	Сазонов	5	Математика
Рома	Никитенко	5	Физика

Давайте проанализируем. Если я назову вам фамилию преподавателя — Сазонов, вы сразу сможете сказать, на какой кафедре он работает? Да, это Математика. �� если я назову Никитенко? Совершенно верно — Физика.

Как бы часто фамилия Сазонова ни встречалась в таблице, кафедра у него всегда будет «Математика». Таким образом, атрибут «Кафедра» функционально зависит от атрибута «Преподаватель». Зная одно, мы однозначно определяем другое.

Но таблице есть еще одна закономерность. В данном наборе данных Иван всегда получает «3», а Рома — всегда «5». Кажется, что имя студента однозначно определяет его оценку. Но так ли это на самом деле?

Если мы скажем: «Имя студента определяет оценку», то совершим классическую ошибку.

$Студент \to Оценка$

В этой конкретной выборке это правда, но в реальности завтра Иван может получить «4», или наш Рома получит «2» у другого преподавателя.

Для определения функциональной зависимости нам нужно отличить случайное совпадение в данных от строгого правила. Поэтому без строгого термина здесь не обойтись.

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

Пусть дана некоторая переменная отношения $R$ . $A$ и $B$ — произвольные подмножества множества атрибутов отношения $R$ . Множество $B$ функционально зависит от $A$ (обозначается $A\to B$ ) тогда и только тогда, когда для любого допустимого значения переменной отношения $R$ каждое значение множества $A$ связано в точности с одним значением множества $B$ .

Определение выглядит страшно лишь на первый взгляд. Разбирая каждое предложение в отдельности нам не составит труда осознать его суть.

Пусть дана некоторая переменная отношения .

Речь идет просто о некой таблице в нашей базе данных. В контексте теории реляционных баз данных понятие «переменная отношения» (relation variable) имеет точный смысл, который немного отличается от того, как мы привыкли говорить в обиходе.

Термин переменная здесь используется в таком же смысле, как и в программировании. Например, x = 5 . Здесь x — это переменная, а 5 — это текущее значение. Если мы напишем x = 10, переменная x останется той же самой переменной (то же имя, тот же тип), но ее значение изменится.

В базах данных то же самое. Значение отношения — это конкретный набор данных из строк/кортежей, который находится в таблице прямо сейчас.

Переменная отношения R — это именованный объект, таблица. В разные моменты времени может содержать разные значения отношения (разные наборы строк).

Если бы мы смотрели только на текущие данные, а не на все допустимые значения, мы могли бы увидеть случайные совпадения и посчитать их за функциональную зависимость. Например, если в таблице сейчас всего два человека, обоих зовут «Иван», обоим 30 лет. Глядя только на эти данные, можно ошибочно решить, что Имя определяет Возраст.

( $Имя \to {Возраст}$ ).

Но определение говорит о переменной. Это значит, что правило $A \to B$ должно работать всегда, как бы мы ни меняли данные в таблице.

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

Двигаемся дальше по определению:

и — произвольные подмножества множества атрибутов отношения .

Тут все просто. Атрибуты — это наши столбцы. А подмножества означают, что мы можем оперировать сразу несколькими атрибутами, когда говорим о функциональной зависимости.

Например, в нашей таблице с оценками:

может быть парой {Студент, Преподаватель}.
может быть одним столбцом {Оценка}.

Зависимость {Студент, Преподаватель} $\to$ {Оценка} говорит нам: «Если мы знаем, кто сдавал и кому сдавал, мы точно знаем, какой результат в ведомости».

И, наконец, самая суть:

Множество функционально зависит от (обозначается $A \to B$ ) тогда и только тогда, когда для любого допустимого значения переменной отношения каждое значение множества связано в точности с одним значением множества .

Снова берем нашу функциональную зависимость (давайте сократим до ФЗ) {Студент, Преподаватель} $\to$ {Оценка} и понимаем, что у конкретного студента с конкретным преподавателем может быть лишь одна оценка за предмет.

Подобные ФЗ является ограничением целостности для переменной отношения , потому что она накладывает определенные ограничения на все доступные значения. Ведь мы не можем иметь два кортежа с разными оценками у одного студента и одним преподавателем.

Разобрались? Двигаемся дальше. Возьмем вот такое отношение S:

Студент_ID	Курс_ID	Оценка	Факультет
Иван	Математика	3	МатМод
Иван	Физика	3	МатМод
Иван	Базы данных	3	МатМод
Рома	Математика	5	ФизМод
Рома	Физика	5	ФизМод
Рома	Базы данных	5	ФизМод

Атрибуты:

Студент_ID — уникальный номер студента,
Курс_ID — уникальный номер учебного курса (например, «Базы данных»),
Оценка — результат студента по конкретному курсу,
Факультет — факультет, к которому приписан студент.

Перечислим несколько функциональных зависимостей, которые присутствуют в S.

{Студент_ID, Курс_ID} $\to$ Оценка

Конкретный студент по конкретному предмету может иметь только одну итоговую оценку. Если мы знаем «Кто» и «Что сдавал», мы точно знаем результат.

{Студент_ID, Курс_ID } $\to$ Факультет

Если мы знаем ID студента и ID курса, мы, конечно, можем сказать, на каком факультете учится этот студент. Хотя ID курса тут избыточный, формально правило работает.

{Студент_ID, Курс_ID} $\to$ {Факультет, Оценка}

Пара «Студент + Программа» однозначно определяет сразу весь набор данных о результате и месте учебы.

{Студент_ID, Курс_ID} $\to$ Студент_ID

Это пример тривиальной ФЗ. В математике: если является подмножеством , то $X \to Y$ всегда истинно.

{Студент_ID, Курс_ID} $\to$ {Студент_ID, Курс_ID, Факультет, Оценка}

Ключ таблицы определяет всю строку целиком. Интересный момент: если в переменной отношении , зависимость $A \to B$ и не является потенциальным ключом и не является тривиальной, то вобязательно будет присутствовать некоторая избыточность. Это можно ясно увидеть в нашей таблице S: информация о факультете повторяется много раз.

Бесплатный курс по PostgreSQL

Для Junior- и Middle-специалистов: администраторов баз данных, разработчиков, DevOps-инженеров и аналитиков. Включена бесплатная практика на инфраструктуре Selectel.

Изучить →

А зачем все это

Хороший вопрос. Зачем так париться и искать какие-то зависимости в таблице? Ответ на этот вопрос может быть очень подробным и многосторонним, поэтому его мы коснемся вскользь.

Как я уже упоминал, одна из причин заключается в том, что функциональные зависимости относятся к ограничениям целостности, поэтому желательно, чтобы СУБД обеспечивала их выполнение. В связи с этим для заданного множества функциональных зависимостей S целесообразно найти другое множество T, которое в идеале было бы значительно меньше S, но при этом позволяло бы заменить каждую зависимость из S соответствующей зависимостью из T.

В случае нахождения такого множества T нашей СУБД было бы достаточно проверять соблюдение только зависимостей из T, что автоматически гарантировало бы выполнение всех функциональных зависимостей из множества S. Именно поэтому задача поиска подходящего множества T имеет большое практическое значение.

Нахождение ФЗ и последующий их анализ позволят оптимизировать работу СУБД и сделать опыт администрирования чуть лучше.

Самый простой способ сокращения набора функциональных зависимостей — это исключение из него тривиальных зависимостей. Зависимость называется тривиальной, если она не может не выполняться. Мы видели такое ранее:

$\{ Студент\_ID, Программа\_ID \} \to Студент\_ID$

Как видно, правая часть — это подмножество левой части. Такие ФЗ интереса не представляют. Куда интереснее нетривиальные зависимости, которые действительно являются ограничениями целостности в полном смысле этого понятия.

Про замыкание функциональных зависимостей

Функциональные зависимости редко встречаются по одиночке. На практике за одной ФЗ следуют другая, за ней еще одна и еще одна.

Множество всех зависимостей, которые можно логически вывести из уже имеющихся, называется замыканием и обозначается как $S^{+}$ .

Здесь термин замыкания не имеет ничего общего с замыканием в реляционной алгебре. Для нахождения замыкания на некотором множестве ФЗ используют три «золотых правила» (аксиомы), которые вывел ученый Вильям Армстронг еще в 70-х годах:

Правило рефлексивности (самоочевидность). Если у нас есть набор данных {Студент_ID, Программа_ID}, то из него логически следует {Студент_ID}.

Формула: Если $B \subseteq A$ , то $A \to B$ .

Это та самая тривиальная зависимость.
Правило дополнения. Если мы знаем, что Студент_ID однозначно определяет Факультет, то добавив к обеим частям Программа_ID, мы получим новую рабочую зависимость:

{Студент_ID, Программа_ID} $\to$ {Факультет, Программа_ID}. Мы просто утяжелили обе стороны одним и тем же атрибутом, и равновесие сохранилось.
Правило транзитивности (цепная реакция). Самое полезное правило. Допустим:
Студент_ID $\to$ Кафедра (Студент приписан к одной кафедре).
Кафедра $\to$ Зав_Кафедрой (У каждой кафедры только один начальник).

Следовательно: Студент_ID $\to$ Зав_Кафедрой. Вот мы и нашли скрытую связь!
Транзитивная связь между студентом и зав. кафедрой.
Зная ID студента, мы теперь можем пробросить цепочку и узнать фамилию его зав. кафедры, хотя напрямую в таблице они могли быть не связаны.

С помощью правил Армстронга мы можем обнаружить избыточные зависимости, что является одной из наших целей.

Подведем итоги

Надеюсь, у меня получилось донести до вас суть. Функциональная зависимость — это самый частый вид ограничения целостности в вашей базе данных. По сути это связь «многие к одному» между двумя множествами атрибутов внутри одной таблицы.

Мы научились находить зависимости и выводить новые. Но что, если я скажу вам, что некоторые зависимости — это яд для вашей базы данных?

Посмотрите еще раз на нашу учебную таблицу. Если ID_Студента определяет Факультет, а мы храним это в таблице «Оценки», то каждый раз, когда студент получает новую оценку, мы вынуждены снова и снова записывать его факультет.

А если факультет переименуют? Нам придется менять тысячи строк. А если мы удалим последнюю оценку студента, то внезапно забудем, на каком факультете он учился?

Эти изъяны называются аномалиями, и они возникают в ненормализованных БД. Решается эта проблема с помощью Нормальных форм баз данных. Об этом в следующей статье. До встречи в 1 NF!

Разбираемся в функциональных зависимостях БД

А зачем все это

Про замыкание функциональных зависимостей

Подведем итоги

Публикации

Информация