Appearance
Функциональные зависимости
Функциональные зависимости — это основа нормализации баз данных.
Под функциональной зависимостью подразумевается зависимость значения одного атрибута от другого.
Если даны два атрибута А и Б некоторого отношения, то говорят, что Б функционально зависит от А, если в любой момент времени каждому значению А соответствует ровно одно значение Б.
Если возьмем любую таблицу, то значения в кортеже функционально зависят от значений первичного ключа этой таблицы.
Избыточные ФЗ
Избыточной зависимостью называют ситуацию, при которой зависимость заключает информацию, которая может быть получена из других зависимостей.
Правила вывода зависимостей применяются к списку функциональных зависимостей с целью избавиться от избыточных зависимостей.
Набор функциональных зависимостей, получаемый из исходного набора функциональных зависимостей удалением всех избыточных функциональных зависимостей с помощью правила вывода, называется минимальным покрытием.
Избыточные функциональные зависимости следует удалять из набора по одной, каждый раз заново анализируя полученный набор функциональных зависимостей на присутствие в нем избыточных зависимостей.
Пример
За основу возьмем таблицу со следующими атрибутами:
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 допустимо соединять только три вместе; использовать по две таблицы нельзя.
DKNF
Domain-Key Normal Form (DKNF), или нормальная форма доменов и ключей, — нормальная форма, в которой все ограничения отношения следуют из ограничений доменов и ключей.
1НФ–3НФ и НФБК в основном рассматривают функциональные зависимости, 4НФ — многозначные зависимости, а 5НФ — зависимости соединения. DKNF рассматривает все ограничения отношения и проверяет, можно ли вывести их только из доменов и ключей.
Ограничения домена
Ограничение домена задает множество допустимых значений атрибута. Например, возраст может находиться в диапазоне от 18 до 100:
sql
CREATE TABLE employee (
employee_id integer PRIMARY KEY,
age integer CHECK (age BETWEEN 18 AND 100)
);Здесь age ограничен доменом, а employee_id задает ключ.
Ограничения ключа
Ограничение ключа определяет набор атрибутов, однозначно идентифицирующий кортеж:
sql
CREATE TABLE employee (
employee_id integer PRIMARY KEY,
fio text NOT NULL
);Если все остальные ограничения отношения логически выводятся из доменов и ключей, отношение находится в DKNF.
Пример ограничения, не выводимого из домена и ключа
Пусть каждый сотрудник с employee_id от 1 до 100 обязан работать в отделе IT, а остальные — в HR:
employee_id ∈ [1, 100] -> department = IT
Это правило связывает значения разных атрибутов. Уникальность ключа и допустимость отдельных значений сами по себе его не гарантируют, поэтому такое отношение не находится в DKNF.
DKNF имеет важное теоретическое значение, но бизнес-правила часто зависят от нескольких таблиц, состояния системы или внешних условий. Поэтому на практике DKNF обычно используют как ориентир для анализа модели, а не как обязательную конечную точку проектирования.
Шестая нормальная форма (6НФ)
6НФ — нормальная форма, в которой отношение нельзя дальше декомпозировать без потери информации и при этом оно содержит только одну нетривиальную зависимость. На практике это означает, что таблица описывает один факт об одной сущности, обычно вместе с периодом его действия.
6НФ особенно полезна для темпоральных баз данных и хранилищ, где необходимо независимо хранить историю отдельных атрибутов. Если у клиента меняются город и тариф в разные даты, их можно хранить в отдельных таблицах:
text
customer_city(customer_id, city, valid_from, valid_to)
customer_tariff(customer_id, tariff, valid_from, valid_to)Такое разбиение позволяет изменять и версионировать каждый атрибут независимо и не дублировать неизменившиеся значения. В то же время запросы становятся сложнее: для получения полного состояния клиента приходится соединять несколько таблиц.
6НФ не следует применять автоматически. Она оправдана при высокой ценности истории, частых независимых изменениях атрибутов и темпоральном анализе. Для обычных OLTP-систем чрезмерная декомпозиция может увеличить количество JOIN и усложнить сопровождение.
Связь 6НФ и SCD
SCD Type 2 хранит версии измерения целиком, а 6НФ позволяет хранить версии отдельных атрибутов. Поэтому 6НФ может быть основой темпоральной модели, в которой история каждого свойства измерения ведется независимо. Конкретный способ зависит от требований к загрузке и аналитическим запросам.
Денормализация
Денормализация — это процесс ухода от правил нормализации там, где это необходимо.
Для процесса денормализации не существует стандартного алгоритма. Процесс денормализации индивидуален и требует четкого понимания, для чего он необходим, несмотря на появление избыточности.
К денормализации прибегают для сокращения времени обработки запросов и уменьшения затрат ресурсов. В нормализованных базах часто приходится соединять большое количество таблиц или добавлять агрегацию.
Таким образом, денормализацию можно выполнить, сократив количество таблиц или добавив новые столбцы в существующую таблицу. При этом, учитывая избыточность данных, необходимо следить за целостностью данных.
Особенности в разных СУБД
В зависимости от того, в какой РСУБД происходит процесс денормализации, используются различные алгоритмы.
- PostgreSQL: можно использовать материализованные представления.
- MySQL (где отсутствуют материализованные представления): необходимо создавать денормализованную таблицу, которую придется наполнять через триггеры и единую процедуру. На все таблицы, которые участвуют в денормализации и вычислениях, накладываются триггеры, которые будут запускать одну и ту же процедуру, что будет гарантировать корректность и целостность данных.
- Если в РСУБД отсутствуют материализованные представления и триггеры, тогда целостность при денормализации достигается единой функцией на уровне приложения.