Нормальные формы: третья и Бойса-Кодда — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлено следствие из НФБК в 3НФ)
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
Третья нормальная форма исправляет оставшиеся после приведения в 2НФ простые аномалии. Форма Бойса-Кодда является самой сильной формой, не допускающей аномалий, причиной возникновения которых являются сложные функциональные зависимости, и логически находится между третьей и четвертой НФ.
 
Третья нормальная форма исправляет оставшиеся после приведения в 2НФ простые аномалии. Форма Бойса-Кодда является самой сильной формой, не допускающей аномалий, причиной возникновения которых являются сложные функциональные зависимости, и логически находится между третьей и четвертой НФ.
  

Версия 08:13, 1 сентября 2022

НЕТ ВОЙНЕ

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НФ, сохранив все ФЗ, если производить декомпозиции в правильном порядке.

Аномалии

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