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

Функциональные зависимости — это основа нормализации баз данных.

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

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

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

Избыточные ФЗ

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

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

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

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

Пример

За основу возьмем таблицу со следующими атрибутами:

unit_id, emp_id, fio

Здесь можно выделить следующие функциональные зависимости:

unit_id -> emp_id и emp_id -> fio, то есть unit_id функционально определяет emp_id, а emp_id функционально определяет fio.

Можно записать как F = {unit_id -> emp_id, emp_id -> fio}.

Отношение R(A, B, C)

Давайте немного изменим обозначения и представим отношение в следующем виде:

R(A, B, C)

Есть отношение R(A, B, C), в котором есть следующие функциональные зависимости: F = {A -> B, B -> C}.

Если F представляет собой набор функциональных зависимостей, то замыкание F, обозначаемое как F+, представляет собой набор всех функциональных зависимостей, логически подразумеваемых F.

Можем предположить следующие логически возможные зависимости, которые могут существовать: F+ = {A -> C, A -> A, B -> B, C -> C}.

Количество возможных первичных ключей

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

Комбинации ключей	Количество ключей в комбинации
A	1
B	1
C	1
AB	1
AC	1
BC	1
ABC	1
Итого	7

То есть всего может быть 7 вариантов первичных ключей в данной таблице.

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

[ \frac{n!}{(n-r)! \cdot r!} ]

где r — количество атрибутов в ключе, а n — количество атрибутов в отношении.

Для отношения из 10 атрибутов будет 1023 комбинации первичных ключей.

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

Аксиомы Армстронга

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

• Рефлексивность
• Пополнение
• Транзитивность

Рефлексивность

Если В является подмножеством А, то А функционально определяет В.

Данная зависимость является тривиальной: правая часть таких зависимостей содержится в левой. То есть А -> В.

Пример: emp_id -> fio.

Пополнение

Если А функционально определяет В, то АС функционально определяет ВС. То есть если А -> В, то АС -> ВС.

Доказательство от обратного:
Представим, что зависимость АС -> ВС не соблюдается.

unit_id	fio
A1	C1
A2	C2

emp_id	fio
B1	C1
B2	C2

Пусть А1С1 = А2С2, но В1С1 != В2С2.
По аксиоме рефлексивности из первого равенства А1С1 = А2С2 следует, что А1 = А2. Так как А функционально определяет В, то В1 = В2, и из неравенства В1С1 != В2С2 следует, что С1 != С2. Но это нарушает тривиальную зависимость АС -> С.
Таким образом, мы доказываем, что зависимость АС -> ВС должна соблюдаться.

Транзитивность

Если А функционально определяет В и В функционально определяет С, то А функционально определяет С.
То есть если А -> В и В -> С, то А -> С. Такая зависимость является избыточной и должна быть устранена.

unit_id	emp_id
A1	B1
A2	B2

emp_id	fio
B1	C1
B2	C2

Доказательство от обратного:
Предположим, что зависимость А -> С не соблюдается: А1 = А2, но С1 != С2.
Из наличия зависимости А -> В следует, что В1 = В2, а потому из наличия зависимости В -> С следует, что С1 = С2. Значит, предположение об отсутствии функциональной зависимости А -> С не является верным.

Правила вывода

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

• Самодетерминированность
• Декомпозиция
• Объединение
• Композиция
• Накопление

Самодетерминированность

Когда А -> А, что прямо следует из аксиомы Рефлексивности.

Декомпозиция

Если А -> ВС, то А -> В и А -> С. Согласно рефлексивности следует, что ВС -> В, согласно транзитивности следует, что А -> В. Таким же образом из ВС -> С и транзитивности следует зависимость А -> С.

Объединение

Если А -> В и А -> С, то А -> ВС. Согласно аксиоме Пополнения следует, что А -> АВ и АВ -> ВС, а согласно транзитивности следует, что А -> ВС.

Композиция

Когда А -> В и С -> D, то АС -> BD. Согласно пополнения получим зависимость АС -> ВС и ВС -> BD, а применив транзитивность получим, что АС -> BD.

Накопление

Если А -> ВС и В -> D, то А -> ВСD. Применяя пополнение, получим, что ВС -> ВСD, и применяя транзитивность, получим, что А -> ВСD.

Вывод

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

---

Нормализация

Нормализация — это метод проектирования базы данных, который используется для разработки таблицы реляционной базы данных до более высокой нормальной формы.

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

Как правило, 3НФ является желаемым результатом, и дальнейшая нормализация может приводить к не нужному результату, из-за которого усложняется выборка данных.

Первая нормальная форма (1НФ)

Первая нормальная форма (1НФ) — основа нормализации данных. Таблица считается приведенной к 1НФ, если выполняются следующие условия:

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

Пример приведения к 1НФ

Исходная таблица пользователей:

user_name	passport	address
Иванов Иван Иванович	4508 785231
Петров Семен Семенович	4724 254965
Федоров Максим Петрович	5746 420983

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

Таблица пользователей:

last_name	first_name	middle_name	serial_pass	number_pass	address_id	city_id
Иванов	Иван	Иванович	4508	785231	1	1
Петров	Семен	Семенович	4724	254965	2	2
Федоров	Максим	Петрович	5746	420983	3	3

Таблица городов:

city_id	city_name
1	Москва
2	Саратов

Таблица адресов:

address_id	street	house
1	Проспект Мира	17
2	Елисейские поля	1
3	тупик Последний	2

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

Вторая нормальная форма (2НФ)

Чтобы таблица соответствовала 2 нормальной форме (2НФ), она должна быть в 1НФ. 2НФ говорит о том, что все значения в кортеже зависят от значения первичного ключа. Если в таблице составной первичный ключ, то значения в кортеже должны зависеть от всего состава первичного ключа, а не от его части.

Пример приведения к 2НФ

Дана таблица, которая находится в 1НФ и хранит информацию по проектам:

project_manager_id	project_id	project_name	start_date	end_date
1	7	Рога с копытами	01.05.2023	24.08.2023
2	25	Просто без точки	10.11.2023	31.12.2023

В данной таблице составной первичный ключ из атрибутов project_manager_id и project_id.
Столбец project_name зависит только от идентификатора проекта и не имеет отношения к руководителю проекта.

Нормализуем данную таблицу, убрав атрибут project_name, который не принадлежит таблице.

Таблица проектов и менеджеров:

project_manager_id	project_id	start_date	end_date
1	7	01.05.2023	24.08.2023
2	25	10.11.2023	31.12.2023

Таблица проектов:

project_id	project_name
7	Рога с копытами
25	Просто без точки

Теперь наборы значений в кортежах в двух таблицах зависят полностью от своих первичных ключей.

Третья нормальная форма (3НФ)

Чтобы БД соответствовала требованиям 3НФ, она должна находиться в 1НФ и 2НФ. Таблица находится в 3НФ, когда в таблице отсутствуют избыточные транзитивные функциональные зависимости. То есть отсутствуют атрибуты, которые зависят от неключевых атрибутов.

Пример приведения к 3НФ

Возьмем таблицу с проектами, где будет идентификатор проекта, название проекта, идентификатор руководителя проекта и его адрес проживания:

project_id	project_name	project_manager_id	pm_address
1	some_project_1	7	some_address_1
2	some_project_2	24	some_address_2

Так как первичным ключом является столбец project_id, то все неключевые атрибуты в таблице должны зависеть от данного атрибута, но столбец pm_address зависит от столбца project_manager_id, который не имеет ограничения первичного ключа, то есть столбец pm_address не принадлежит данной таблице.

Нормальная форма Бойса-Кодда (НФБК)

НФБК — нормальная форма Бойса-Кодда. Достигается, когда отношение находится в 1НФ, 2НФ и 3НФ. НФБК — это расширенная и более строгая 3НФ. Если в таблице простой первичный ключ (один атрибут имеет данное ограничение), то НФБК является 3НФ.

Отношение находится в НФБК, когда каждая нетривиальная и неприводимая слева функциональная зависимость обладает потенциальным ключом в качестве детерминанта.

Пример приведения к НФБК

Возьмем таблицу по слушанию судебных дел, где есть номер зала заседания, номер статьи, ФИО судьи и тип слушания:

hall_number	article	judge	type_of_hearing
1	171	Иванов Иван	закрытое
1	516	Петров Петр	закрытое
2	126	Семенов Михаил	открытое

Предположим, что статьи делятся на две категории, которые могут проходить только в открытом режиме и только в закрытом режиме. По статьям 171 и 516 могут быть только закрытые слушания, а по 126 — только открытые. Если составить список всех потенциально возможных составных первичных ключей, то получим:

• [hall_number, article]
• [hall_number, judge]
• [type_of_hearing, judge]
• [judge, article]

В данном случае все атрибуты входят в какой-либо из составных первичных ключей, то есть требования 2НФ соблюдены. Транзитивные функциональные зависимости отсутствуют, значит таблица находится в 3НФ. Но также существует функциональная зависимость между статьей и типом слушания, где тип слушания не может являться первичным ключом для статьи, значит таблица не соответствует требованиям НФБК.

Проблема будет заключаться в том, что для любой статьи можно указать любой тип слушания, что является аномалией модификации.

Проведем декомпозицию на два отношения:

Таблица слушаний:

hall_number	article	judge
1	171	Иванов Иван
1	516	Петров Петр
2	126	Семенов Михаил

Таблица типов слушаний по статьям:

article	type_of_hearing
171	закрытое
516	закрытое
126	открытое

Теперь между нашими атрибутами отсутствуют какие-либо неявные зависимости, а значит таблицы находятся в соответствии с требованиями НФБК.

Четвертая нормальная форма (4НФ)

Отношение соответствует требованиям 4НФ, когда соответствует всем предыдущим НФ и в таблице отсутствуют многозначные зависимости. Таблица должна иметь как минимум три столбца (допустим, А, В и С), которые формируют составной первичный ключ. При этом В и С между собой никак не связаны и не зависят друг от друга, но по отдельности зависят от А, и для каждого значения А есть множество значений В, а также множество значений С. Данную многозначную зависимость можно записать как А→В, А→С.

Пример приведения к 4НФ

Возьмем таблицу, в которой фиксируется, какой сотрудник в каком магазине совершил продажу товара:

staff_id	store_id	product_id
1	2	87
1	1	54
2	1	52

Так как здесь составной первичный ключ из трех столбцов, то данная таблица автоматически находится в НФБК. Но из-за многозначной зависимости сотрудник → магазин и сотрудник → товар таблица нарушает требования 4НФ. То есть сотрудник может продавать в разных магазинах и может продавать разный товар. А в каком магазине будет продан товар и будет ли товар продан именно в этом магазине — не важно. Аномалия заключается в том, что при продаже нового товара можно указать ложный магазин.

Чтобы привести данную таблицу к 4НФ, сделаем декомпозицию на две таблицы:

Таблица «Сотрудник-Магазин»:

staff_id	store_id
1	2
1	1
2	1

Таблица «Сотрудник-Товар»:

staff_id	product_id
1	87
1	54
2	15
2	1
2	52

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

Пятая нормальная форма (5НФ)

Чтобы получить 5НФ, нужно разделять таблицы на более малые таблицы для устранения избыточности данных. Разбиение идет до тех пор, пока нельзя будет воссоздать оригинальную таблицу путем объединения всех малых таблиц. Требование 5НФ заключается в том, чтобы в таблице каждая нетривиальная зависимость соединения определялась потенциальным ключом этой таблицы.

Пример

Возьмем предыдущий пример, когда мы нормализовали таблицы до 4НФ. Была исходная таблица в НФБК:

staff_id	store_id	product_id
1	2	87
1	1	54
2	1	52

После декомпозиции получили 2 малые таблицы, которые находятся в 4НФ:

staff_store:

staff_id	store_id
1	2
1	1
2	1

staff_product:

staff_id	product_id
1	87
1	54
2	15
2	1
2	52

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

В данном случае применяется приведение таблиц к 5НФ, когда данные нужно декомпозировать по «цикличной» зависимости, то есть staff_id → store_id, store_id → product_id и staff_id → product_id. Необходимо создать еще одну таблицу, которая будет хранить данные о том, в каком магазине какой товар был продан:

product_store:

product_id	store_id
87	2
54	1
15	2
1	1
52	2

После нормализации до 5НФ таблицы staff_store, staff_product, product_store допустимо соединять только три вместе; использовать по две таблицы нельзя.

---

Денормализация

Денормализация — это процесс ухода от правил нормализации там, где это необходимо.

Для процесса денормализации не существует стандартного алгоритма. Процесс денормализации индивидуален и требует четкого понимания, для чего он необходим, несмотря на появление избыточности.

К денормализации прибегают для сокращения времени обработки запросов и уменьшения затрат ресурсов. В нормализованных базах часто приходится соединять большое количество таблиц или добавлять агрегацию.

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

Особенности в разных СУБД

В зависимости от того, в какой РСУБД происходит процесс денормализации, используются различные алгоритмы.

• PostgreSQL: можно использовать материализованные представления.
• MySQL (где отсутствуют материализованные представления): необходимо создавать денормализованную таблицу, которую придется наполнять через триггеры и единую процедуру. На все таблицы, которые участвуют в денормализации и вычислениях, накладываются триггеры, которые будут запускать одну и ту же процедуру, что будет гарантировать корректность и целостность данных.
• Если в РСУБД отсутствуют материализованные представления и триггеры, тогда целостность при денормализации достигается единой функцией на уровне приложения.

---

Медленно меняющиеся измерения (SCD)

Медленно меняющиеся измерения (от англ. Slowly Changing Dimensions, SCD) — механизм отслеживания изменений в данных измерения в терминах хранилища данных.

Применяется в случае, если данные меняются не очень часто и не по расписанию.

Пример таких данных: ФИО пользователя, адрес контрагента, дата рождения, дата продажи и так далее. Иногда изменение таких данных может привести к потере целостности при работе с историческими данными.

Постановка проблемы

Представим ситуацию: есть данные о продаже:

payment_id	customer_id	staff_id	store_id	amount
1	7	1	1	500
2	10	1	2	700

Есть данные по сотрудникам:

staff_id	fio	store_id
1	Иванов Петр	1
2	Максим Сергеевич	2

Насколько текущие данные позволяют отследить перевод сотрудника 1 в магазин 2?

Типы SCD

Тип 0 (SCD0) — Нулевой тип

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

customer_id	fio	born_date	born_city	passport
1	Иванов Петр	01.05.1974	Самара	4477 050607

Здесь born_date и born_city — данные, которые никогда не изменятся, но ФИО или данные паспорта могут быть изменены.

Тип 1 (SCD1) — Первый тип

Использует простое перезаписывание: данные в таблице полностью заменяются на новые. Историчность при этом полностью теряется.

customer_id	fio	born_date	born_city	passport
1	Семенов Петр	01.05.1974	Самара	5588 323344

После того как пользователь поменял ФИО и паспорт, данные изменились, но мы потеряли то, что было изначально. Если какие-то данные были привязаны к паспорту (кредиты, сертификаты и т.д.), эти связи будут потеряны.

Тип 2 (SCD2) — Второй тип

Использует добавление новой строки и дополнительных столбцов. Позволяет сохранить историчность.

customer_id	fio	born_date	born_city	passport	active	created_date
1	Иванов Петр	01.05.1974	Самара	4477 050607	false	01.01.2020
1	Семенов Петр	01.05.1974	Самара	5588 323344	true	17.06.2021

Сохраняется историчность данных, но данные начинают создавать избыточность. Чтобы контролировать, какая из записей актуальна, добавляются служебные столбцы active и created_date для версионности.

Тип 3 (SCD3) — Третий тип

Использует добавление новых столбцов-атрибутов, хранящих предыдущее значение для поддержания историчности. SCD2 позволяет хранить любое количество изменений, а SCD3 — ровно столько, сколько заранее отведено под это столбцов.

Исходное состояние:

customer_id	fio	passport	old_fio	old_passport	change_date
1	Иванов Петр	4477 050607	null	null	null

После изменения:

customer_id	fio	passport	old_fio	old_passport	change_date
1	Семенов Петр	5588 323344	Иванов Петр	4477 050607	17.06.2021

Историчность сохранена, но пользователь не может больше менять ФИО или паспорт (или для этого потребуется добавлять новые столбцы).

Тип 4 (SCD4) — Четвертый тип

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

Основная таблица (после изменений):

customer_id	fio	born_date	born_city	passport	actual_date
1	Семенов Петр	01.05.1974	Самара	5588 323344	17.06.2021

Таблица с изменениями:

customer_id	fio	passport	actual_date
1	Иванов Петр	4477 050607	01.01.2020

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

Выбор типа SCD

Какой именно тип использовать (или возможно сочетание типов) зависит от конкретной задачи и структуры данных.

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