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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Кавычки)
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 75: Строка 75:
 
|}
 
|}
  
Функциональные зависимости в данном отношении &ndash; это <tex>\mathrm{CourseId}, \mathrm{Group} \rightarrow \mathrm{Examiner}</tex>, <tex>\mathrm{CourseId}, \mathrm{Examiner} \rightarrow \mathrm{Group}</tex> и <tex>\mathrm{Examiner} \leftrightarrow \mathrm{Phone}</tex>, а также все порождаемые ими.
+
Функциональные зависимости в данном отношении &ndash; это <tex>\mathrm{CourseId}, \mathrm{Group} \rightarrow \mathrm{Examiner}</tex>, <tex>\mathrm{CourseId}, \mathrm{Examiner} \rightarrow \mathrm{Group}</tex> и <tex>\mathrm{Examiner} \leftrightarrow \mathrm{Phone}</tex>, а также все следующие из них.
  
Если преподаватель ведет разные предметы у разных групп, такая структура отношения позволяет задать преподавателю разные телефоны, что нарушает целостность БД. Причиной такой аномалии является то, что в данном отношении есть несколько ключей, и каждый атрибут является частью хотя бы одного ключа (в частности, <tex>\mathrm{CourseId}, \mathrm{Phone}</tex> &ndash это ключ), тогда как первые три НФ не накладывают никакие ограничения на ключевые атрибуты.
+
Если преподаватель ведет разные предметы у разных групп, такая структура отношения позволяет задать преподавателю разные телефоны, что нарушает целостность БД. Причиной такой аномалии является то, что в данном отношении есть несколько ключей, и каждый атрибут является частью хотя бы одного ключа (в частности, <tex>\mathrm{CourseId}, \mathrm{Phone}</tex> &ndash; это ключ), тогда как первые три НФ не накладывают никакие ограничения на ключевые атрибуты.
  
 
== Нормальная форма Бойса-Кодда ==
 
== Нормальная форма Бойса-Кодда ==
Строка 83: Строка 83:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Отношение находится в '''нормальной форме Бойса-Кодда''' (НФБК) тогда и только тогда, когда
+
Отношение находится в '''нормальной форме Бойса-Кодда''' (НФБК) тогда и только тогда, когда для любой нетривиальной функциональной зависимости <tex>X \rightarrow Y</tex>, <tex>X</tex> является надключом.
* оно находится в третьей нормальной форме
 
* для любой нетривиальной функциональной зависимости <tex>X \rightarrow Y</tex>, <tex>X</tex> является надключом
 
 
}}
 
}}
Нормальная форма Бойса-Кодда исправляет аномалии, возникающие из-за перекрывающихся ключей. В частности, если отношение находится в 3НФ и в нем нет перекрывающихся ключей, оно автоматически находится в НФБК.
+
Следует отметить, что определение НФБК не требует 3НФ. Однако можно доказать, что любое отношение в НФБК автоматически находится в 3НФ.
  
Поскольку, опираясь только на функциональные зависимости, нельзя потребовать более сильное условие, чем надключ в левой части каждой ФЗ, то нФБК &ndash; &laquo;совершенная&raquo; НФ с точки зрения только функциональных зависимостей.
+
{{Утверждение
 +
|statement=Отношение в НФБК находится в 3НФ
 +
|proof=
 +
* выполнены все условия 1НФ (имеется ключ, а корректные ФЗ обеспечивают отсутствие повторяющихся и неатомарных атрибутов)
 +
* выполнено условие 2НФ (так как в левых частях ФЗ только надключи, нет атрибутов, зависящих от части ключа)
 +
* выполнено условие 3НФ (так как в левых частях ФЗ только надключи, нет атрибутов, зависящих от неключевых атрибутов)
 +
}}
 +
 
 +
Нормальная форма Бойса-Кодда исправляет аномалии, возникающие из-за перекрывающихся ключей. В частности, если отношение находится в 3НФ и в нем нет перекрывающихся ключей, оно автоматически находится в НФБК. Поскольку, опираясь только на функциональные зависимости, нельзя потребовать более сильное условие, чем надключ в левой части каждой ФЗ, то НФБК &ndash; &laquo;совершенная&raquo; НФ с точки зрения только функциональных зависимостей.
  
 
=== Запрещенные конструкции ===
 
=== Запрещенные конструкции ===

Текущая версия на 19:23, 4 сентября 2022

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

Аномалии

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