Нормальные формы: первая и вторая

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Первая и вторая нормальные формы разработаны Эдгаром Коддом и являются достаточно «самоочевидными». Самоочевидность заключается в том, что отношения в первой и второй нормальной формах обладают интуитивно понятными базовыми свойствами, которые логично требовать от отношений, используемых в рамках баз данных.

Первая нормальная форма

Определение:

Отношение находится в первой нормальной форме (1НФ) тогда и только тогда, когда в отношении нет повторяющихся групп (атрибутов с одинаковым смыслом) все атрибуты атомарны у отношения есть ключ

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

Запрещенные конструкции

Повторяющиеся группы

CourseId	Lecturer	Phone (1)	Phone (2)
1	Корнеев Г. А.		111-11-11
2	Киракозов А. Х.	222-22-22	333-33-33
3	Кудряшов Б. Д.	444-44-44	555-55-55
4	Сегаль А. С.	666-66-66

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

Неатомарные атрибуты

CourseId	Lecturer	Phones
1	Корнеев Г. А.	111-11-11
2	Киракозов А. Х.	222-22-22
		333-33-33
3	Кудряшов Б. Д.	444-44-44
		555-55-55
4	Сегаль А. С.	666-66-66

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

Отсутствие ключа

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

Приведение в 1НФ

Для того, чтобы привести произвольное отношение [math]R[/math] в 1НФ, достаточно:

1. Рассмотреть все наборы атрибутов, имеющих одинаковый смысл
2. Для каждого фиксированного значения оставшихся атрибутов сделать по записи на каждое значение выбранных:
   • рассмотрим повторяющиеся атрибуты [math]A_1, \ldots, A_k[/math]
   • рассмотрим оставшиеся атрибуты [math]B_1, \ldots, B_n[/math]
   • построим такое отношение [math]T[/math] на атрибутах [math]B_1, \ldots, B_n, A[/math], что [math]\{b_1, \ldots, b_n, a\} \in T \Longleftrightarrow \{b_1 \ldots, b_n\} \in \pi_{B_1, \ldots, B_n}R \land a \in \bigcup\limits_{i=1}^k \pi_{A_i}R[/math]
3. Аналогичную процедуру повторить для всех неатомарных атрибутов

Отношение, использованое в примерах выше, после приведения в 1НФ будет выглядеть как

CourseId	Lecturer	Phone
1	Корнеев Г. А.	111-11-11
2	Киракозов А. Х.	222-22-22
2	Киракозов А. Х.	333-33-33
3	Кудряшов Б. Д.	444-44-44
3	Кудряшов Б. Д.	555-55-55
4	Сегаль А. С.	666-66-66

Аномалии

Определение:

Аномалия – эффект, возникающий при недостаточной нормализации БД или сложных зависимостях между данными, влекущий за собой проблемы возможной логической некорректности данных невозможности представления некоторых данных в данной форме технической/алгоритмической сложность внесения или изменения данных

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

Определение:

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

В рассмотренном выше примере невозможно записать информацию о телефоне конкретного преподавателя, если он не читает ни один курс (таким образом, возможность записать [math]\mathrm{Phone}[/math] для конкретного [math]\mathrm{Lecturer}[/math] зависит от наличия соответствующего [math]\mathrm{CourseId}[/math], хотя напрямую они не зависят друг от друга).

Определение:

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

В рассмотренном выше, опять же, примере невозможно удалить информацию о том, что конкретный преподаватель читает конкретный курс, не потеряв его номер телефона (как и в случае с аномалией вставки, возможность хранить [math]\mathrm{Phone}[/math] зависит от существования соответствующего [math]\mathrm{CourseId}[/math]).

Определение:

Аномалия изменения – ситуация, в которой частичное изменение данных нарушает целостность базы данных.

В рассмотренном примере если один преподаватель ведет один курс и имеет два телефона, при изменении [math]\mathrm{CourseId}[/math] в одной из соответствующих ему записей будет невозможно восстановить какой курс на самом деле ведет преподаватель (записи с разными [math]\mathrm{Phone}[/math], но одинаковыми [math]\mathrm{Lecturer}[/math] и [math]\mathrm{CourseId}[/math], должны всегда поддерживаться в таком же состоянии).

Вторая нормальная форма

Определение:

Отношение находится во второй нормальной форме (2НФ) тогда и только тогда, когда оно находится в первой нормальной форме все неключевые атрибуты функционально зависят от ключа целиком, но не от его части

Вторая нормальная форма позволяет избавиться от некоторых аномалий, возникающих в отношениях в 1НФ.

Запрещенные конструкции

Во 2НФ запрещено, чтобы какие-либо атрибуты функционально зависели от части ключа. Рассмотрим следующий пример, уже приведенный в 1НФ:

CourseId	Year	Lecturer	Exam
1	2020	Корнеев Г. А.	yes
2	2019	Киракозов А. Х.	no
2	2020	Киракозов А. Х.	no
3	2019	Левина А. Б.	yes
3	2020	Чепурной А. И.	yes

В данном отношении можно выделить следующие функциональные зависимости: [math]\mathrm{CourseId} \rightarrow \mathrm{Exam}[/math] (наличие экзамена зависит только от предмета) и [math]\mathrm{CourseId}, \mathrm{Year} \rightarrow \mathrm{Lecturer}[/math] (каждый год только один преподаватель читает конкретный предмет). Таким образом, ключ в данном отношении – [math]\mathrm{CourseId}, \mathrm{Year}[/math], но при этом [math]\mathrm{Exam}[/math] зависит только от части ключа.

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

Приведение во 2НФ

Отношение в 1НФ приводится к 2НФ декомпозицией по «мешающим» функциональным зависимостям. На примере выше такая зависимость только одна – [math]\mathrm{CourseId} \rightarrow \mathrm{Exam}[/math].

Определение:

Декомпозиция отношения [math]R[/math], состоящего из наборов атрибутов [math]A, B, C[/math], по функциональной зависимости [math]A \rightarrow B[/math] – пара отношений [math]\pi_{A, B} R[/math] и [math]\pi_{A, C} R[/math].

Декомпозиция рассмотренного примера по «лишней» функциональной зависимости дает следующий результат:

CourseId	Year	Lecturer
1	2020	Корнеев Г. А.
2	2019	Киракозов А. Х.
2	2020	Киракозов А. Х.
3	2019	Левина А. Б.
3	2020	Чепурной А. И.

CourseId	Exam
1	yes
2	no
3	yes

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

Аномалии

Аномалия, свойственная 2НФ, возникает, когда какой-то атрибут зависит от ключа транзитивно через множество неключевых атрибутов. Рассмотрим следующий пример:

CourseId	Year	Lecturer	Phone
1	2020	Корнеев Г. А.	111-11-11
2	2019	Киракозов А. Х.	222-22-22
2	2020	Киракозов А. Х.	222-22-22
3	2019	Левина А. Б.	333-33-33
3	2020	Чепурной А. И.	444-44-44

В нем есть две базовые функциональные зависимости: [math]\mathrm{CourseId}, \mathrm{Year} \rightarrow \mathrm{Lecturer}[/math] и [math]\mathrm{Lecturer} \rightarrow \mathrm{Phone}[/math]. Несмотря на то, что данное отношение находится во 2НФ, в нем все еще имеют место все три аномалии 1НФ – аномалии вставки, удаления и изменения (информация о телефонах и о преподавании никак не разделена). Для исправления аномалий 2НФ отношение переводят в третью нормальную форму и выше.