Нормальные формы: третья и Бойса-Кодда

НЕТ ВОЙНЕ

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

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

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

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

Третья нормальная форма

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

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

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

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

Рассмотрим пример отношений, приведенных в 2НФ, которые еще не находятся в 3НФ:

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]. Из-за того, что [math]\mathrm{Phone}[/math] только транзитивно зависит от ключа, имеют место аномалии вставки, удаления и изменения.

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

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

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

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

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

Аномалии

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

CourseId	Group	Examiner	Phone
1	M3239	Корнеев Г. А.	111-11-11
4	M3439	Корнеев Г. А.	111-11-11
1	M3238	Ведерников Н. В.	222-22-22
2	M3439	Киракозов А. Х.	333-33-33

Функциональные зависимости в данном отношении – это [math]\mathrm{CourseId}, \mathrm{Group} \rightarrow \mathrm{Examiner}[/math], [math]\mathrm{CourseId}, \mathrm{Examiner} \rightarrow \mathrm{Group}[/math] и [math]\mathrm{Examiner} \leftrightarrow \mathrm{Phone}[/math], а также все следующие из них.

Если преподаватель ведет разные предметы у разных групп, такая структура отношения позволяет задать преподавателю разные телефоны, что нарушает целостность БД. Причиной такой аномалии является то, что в данном отношении есть несколько ключей, и каждый атрибут является частью хотя бы одного ключа (в частности, [math]\mathrm{CourseId}, \mathrm{Phone}[/math] – это ключ), тогда как первые три НФ не накладывают никакие ограничения на ключевые атрибуты.

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

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

Отношение находится в нормальной форме Бойса-Кодда (НФБК) тогда и только тогда, когда для любой нетривиальной функциональной зависимости [math]X \rightarrow Y[/math], [math]X[/math] является надключом.

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

Утверждение:

Отношение в НФБК находится в 3НФ

[math]\triangleright[/math]

выполнены все условия 1НФ (имеется ключ, а корректные ФЗ обеспечивают отсутствие повторяющихся и неатомарных атрибутов) выполнено условие 2НФ (так как в левых частях ФЗ только надключи, нет атрибутов, зависящих от части ключа) выполнено условие 3НФ (так как в левых частях ФЗ только надключи, нет атрибутов, зависящих от неключевых атрибутов)

[math]\triangleleft[/math]

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

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

В НФБК запрещены функциональные зависимости от наборов атрибутов, не являющихся надключами. В качестве примера возьмем отношение, расмотренное в секции «Аномалии» третьей нормальной формы.

Приведение в НФБК

Как и в случае с предыдущими двумя нормальными формами, приведение в НФБК осуществляется с помощью декомпозиций по функциональным зависимостям, нарушающим условие из определения НФБК. На рассматриваемом примере только в отношении [math]\mathrm{Examiner} \leftrightarrow \mathrm{Phone}[/math] ни одна из частей не является надключом, поэтому делаем по нему декомпозицию. В данном случае не имеет значения, рассматривать ли зависимость в правую сторону или в левую, поэтому для примера будем использовать [math]\mathrm{Examiner} \rightarrow \mathrm{Phone}[/math]. Получаем отношения

CourseId	Group	Examiner
1	M3239	Корнеев Г. А.
4	M3439	Корнеев Г. А.
1	M3238	Ведерников Н. В.
2	M3439	Киракозов А. Х.

Examiner	Phone
Корнеев Г. А.	111-11-11
Ведерников Н. В.	222-22-22
Киракозов А. Х.	333-33-33

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

Достижимость

Теорема:

Любое отношение может быть декомпозировано на отношения в НФБК

Доказательство:

[math]\triangleright[/math]

пока есть ФЗ, не удовлетворяющие определению НФБК (в том числе определениям более слабых НФ), делаем декомпозицию инвариант: количество атрибутов в каждом отношении строго уменьшается в конце останутся либо отношения из двух атрибутов, которые всегда удовлетворяют НФБК, либо отношения, в которых нет неудовлетворяющих зависимостей, которые находятся в НФБК по определению

[math]\triangleleft[/math]

Замечание. Несмотря на то, что любое отношение можно привести в НФБК, иногда при этом могут «распадаться» функциональные зависимости. Так, например, если рассмотреть отношение, в котором на каждой кафедре конкретный предмет читается только одним преподавателем, и никаким преподавателем не читается два разных предмета, можно обнаружить, что при проведении декомпозии, первая ФЗ ([math]\mathrm{Dept}, \mathrm{Course} \rightarrow \mathrm{Lecturer}[/math]) распадается, так как части ключа оказываются в разных отношениях.

Замечание 2. Всегда можно привести отношение к 3НФ, сохранив все ФЗ, если производить декомпозиции в правильном порядке.

Аномалии

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