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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Создание страницы)
 
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 3 участников)
Строка 1: Строка 1:
−
==Третья нормальная форма==
+
Третья нормальная форма исправляет оставшиеся после приведения в 2НФ простые аномалии. Форма Бойса-Кодда является самой сильной формой, не допускающей аномалий, причиной возникновения которых являются сложные функциональные зависимости, и логически находится между третьей и четвертой НФ.
−
Требования
 
  
−
* Вторая нормальная форма
+
== Третья нормальная форма ==
−
* Неключевые атрибуты не транзитивно зависят от ключа
 
  
−
Приведение к 3НФ: декомпозиция по последней функциональной зависимости в транзитивной цепочке.
+
{{Определение
 +
|definition=
 +
Отношение находится в '''третьей нормальной форме''' (3НФ) тогда и только тогда, когда
 +
* оно находится во [[Нормальные_формы:_первая_и_вторая|второй нормальной форме]]
 +
* неключевые атрибуты непосредственно (нетранзитивно) [[Функциональные_зависимости:_замыкание,_эквивалентность_и_правила_вывода|функционально зависят]] от ключей
 +
}}
 +
Третья нормальная форма позволяет исправить те аномалии, которые не были исправлены при переходе от 1НФ к 2НФ из-за транзитивных функциональных зависимостей.
  
−
==Нормальная форма Бойса-Кодда==
+
=== Запрещенные конструкции ===
−
Требования
 
  
−
* В каждой нетривиальной функциональной зависимости X -> Y, X является надключом.
+
Рассмотрим пример отношений, приведенных в 2НФ, которые еще не находятся в 3НФ:
 +
{| class="wikitable"
 +
! 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
 +
|} 
  
−
Исключается ситуация, когда существует зависимость неключевого атрибута не только от ключа, но и от каких-то других неключевых атрибутов.
+
В нем есть две базовые функциональные зависимости: <tex>\mathrm{CourseId}, \mathrm{Year} \rightarrow \mathrm{Lecturer}</tex> и <tex>\mathrm{Lecturer} \rightarrow \mathrm{Phone}</tex>. Из-за того, что <tex>\mathrm{Phone}</tex> только транзитивно зависит от ключа, имеют место аномалии вставки, удаления и изменения.
  
−
НФБК сильнее 3НФ. Приводится из 3НФ декомпозицией по мешающим атрибутам, если это возможно (например, нельзя выбросить часть ключа, которая функционально зависит от неключевого атрибута).
+
=== Приведение в 3НФ ===
  
−
Особенности: распадение функциональных зависимостей на части, находящиеся в разных отношениях.
+
Отношение в 2НФ приводится в 3НФ похожим образом на то, как 1НФ приводится в 2НФ &ndash; с помощью декомпозиции по неудовлетворяющим условию функциональным зависимостям. Чтобы избавиться от транзитивных зависимостей, выполним декомпозицию по последней в каждой цепочке ФЗ зависимости, и будем повторять такую операцию, пока все цепочки зависимостей не станут длины 1. В данном примере единственная цепочка ФЗ &ndash; это <tex>\mathrm{CourseId}, \mathrm{Year} \rightarrow \mathrm{Lecturer} \rightarrow \mathrm{Phone}</tex>. Выполнив декомпозицию по <tex>\mathrm{Lecturer} \rightarrow \mathrm{Phone}</tex>, получим
 +
{| class="wikitable"
 +
! CourseId !! Year || Lecturer
 +
|-
 +
| 1 || 2020 || Корнеев Г. А.
 +
|-
 +
| 2 || 2019 || Киракозов А. Х.
 +
|-
 +
| 2 || 2020 || Киракозов А. Х.
 +
|-
 +
| 3 || 2019 || Левина А. Б.
 +
|-
 +
| 3 || 2020 || Чепурной А. И.
 +
|} 
 +
{| class="wikitable"
 +
! Lecturer || Phone
 +
|-
 +
| Корнеев Г. А. || 111-11-11
 +
|-
 +
| Киракозов А. Х. || 222-22-22
 +
|-
 +
| Левина А. Б. || 333-33-33
 +
|-
 +
| Чепурной А. И. || 444-44-44
 +
|}
  
−
НФБК {{---}} совершенная нормальная форма, если учитывать функциональные, но не множественные зависимости.
+
Нетрудно заметить, что после приведения в 3НФ не остается никаких &laquo;неявных&raquo; зависимостей между атрибутами одного отношения. Благодаря этому, аномалии вставки, удаления и изменения больше не проявляются: не зависимые друг от друга напрямую неключевые данные никак не влияют на возможности сохранить или обновить ту или иную информацию.
 +
 
 +
=== Аномалии ===
 +
 
 +
Отношения в 3НФ все еще подвержены аномалии обновления, но в более редких случаях. Рассмотрим следующий пример, в котором у каждого преподавателя свой телефон и каждый преподаватель принимает у ровно одной группы.
 +
{| class="wikitable"
 +
! CourseId || Group || Examiner || Phone
 +
|-
 +
| 1 || M3239 || Корнеев Г. А. || 111-11-11
 +
|-
 +
| 4 || M3439 || Корнеев Г. А. || 111-11-11
 +
|-
 +
| 1 || M3238 || Ведерников Н. В. || 222-22-22
 +
|-
 +
| 2 || M3439 || Киракозов А. Х. || 333-33-33
 +
|}
 +
 
 +
Функциональные зависимости в данном отношении &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; это ключ), тогда как первые три НФ не накладывают никакие ограничения на ключевые атрибуты.
 +
 
 +
== Нормальная форма Бойса-Кодда ==
 +
 
 +
{{Определение
 +
|definition=
 +
Отношение находится в '''нормальной форме Бойса-Кодда''' (НФБК) тогда и только тогда, когда для любой нетривиальной функциональной зависимости <tex>X \rightarrow Y</tex>, <tex>X</tex> является надключом.
 +
}}
 +
Следует отметить, что определение НФБК не требует 3НФ. Однако можно доказать, что любое отношение в НФБК автоматически находится в 3НФ.
 +
 
 +
{{Утверждение
 +
|statement=Отношение в НФБК находится в 3НФ
 +
|proof=
 +
* выполнены все условия 1НФ (имеется ключ, а корректные ФЗ обеспечивают отсутствие повторяющихся и неатомарных атрибутов)
 +
* выполнено условие 2НФ (так как в левых частях ФЗ только надключи, нет атрибутов, зависящих от части ключа)
 +
* выполнено условие 3НФ (так как в левых частях ФЗ только надключи, нет атрибутов, зависящих от неключевых атрибутов)
 +
}}
 +
 
 +
Нормальная форма Бойса-Кодда исправляет аномалии, возникающие из-за перекрывающихся ключей. В частности, если отношение находится в 3НФ и в нем нет перекрывающихся ключей, оно автоматически находится в НФБК. Поскольку, опираясь только на функциональные зависимости, нельзя потребовать более сильное условие, чем надключ в левой части каждой ФЗ, то НФБК &ndash; &laquo;совершенная&raquo; НФ с точки зрения только функциональных зависимостей.
 +
 
 +
=== Запрещенные конструкции ===
 +
 
 +
В НФБК запрещены функциональные зависимости от наборов атрибутов, не являющихся надключами. В качестве примера возьмем отношение, расмотренное в секции &laquo;Аномалии&raquo; третьей нормальной формы.
 +
 
 +
=== Приведение в НФБК ===
 +
 
 +
Как и в случае с предыдущими двумя нормальными формами, приведение в НФБК осуществляется с помощью декомпозиций по функциональным зависимостям, нарушающим условие из определения НФБК. На рассматриваемом примере только в отношении <tex>\mathrm{Examiner} \leftrightarrow \mathrm{Phone}</tex> ни одна из частей не является надключом, поэтому делаем по нему декомпозицию. В данном случае не имеет значения, рассматривать ли зависимость в правую сторону или в левую, поэтому для примера будем использовать <tex>\mathrm{Examiner} \rightarrow \mathrm{Phone}</tex>. Получаем отношения
 +
{| class="wikitable"
 +
! CourseId || Group || Examiner
 +
|-
 +
| 1 || M3239 || Корнеев Г. А.
 +
|-
 +
| 4 || M3439 || Корнеев Г. А.
 +
|-
 +
| 1 || M3238 || Ведерников Н. В.
 +
|-
 +
| 2 || M3439 || Киракозов А. Х.
 +
|}
 +
{| class="wikitable"
 +
! Examiner || Phone
 +
|-
 +
| Корнеев Г. А. || 111-11-11
 +
|-
 +
| Ведерников Н. В. || 222-22-22
 +
|-
 +
| Киракозов А. Х. || 333-33-33
 +
|}
 +
 
 +
После приведения в НФБК свойство независимости не связанных друг с другом напрямую данных теперь распространяется и на ключевые атрибуты, что позволяет полностью исплючить аномалии изменения.
 +
 
 +
=== Достижимость ===
 +
 
 +
{{Теорема
 +
|statement=Любое отношение может быть декомпозировано на отношения в НФБК
 +
|proof=
 +
* пока есть ФЗ, не удовлетворяющие определению НФБК (в том числе определениям более слабых НФ), делаем декомпозицию
 +
* инвариант: количество атрибутов в каждом отношении строго уменьшается
 +
* в конце останутся либо отношения из двух атрибутов, которые всегда удовлетворяют НФБК, либо отношения, в которых нет неудовлетворяющих зависимостей, которые находятся в НФБК по определению
 +
}}
 +
 
 +
'''Замечание.''' Несмотря на то, что любое отношение можно привести в НФБК, иногда при этом могут &laquo;распадаться&raquo; функциональные зависимости. Так, например, если рассмотреть отношение, в котором на каждой кафедре конкретный предмет читается только одним преподавателем, и никаким преподавателем не читается два разных предмета, можно обнаружить, что при проведении декомпозии, первая ФЗ (<tex>\mathrm{Dept}, \mathrm{Course} \rightarrow \mathrm{Lecturer}</tex>) распадается, так как части ключа оказываются в разных отношениях.
 +
 
 +
'''Замечание 2.''' Всегда можно привести отношение к 3НФ, сохранив все ФЗ, если производить декомпозиции в правильном порядке.
 +
 
 +
=== Аномалии ===
 +
 
 +
В НФБК не может быть аномалий, связанных с функциональными зависимостями, так как на них наложено самое сильное ограничение. Однако есть более сложные виды зависимостей и аномалий. Так, [[Многозначные_зависимости_и_четвертая_нормальная_форма|аномалии многозначных зависимостей исправляются четвертой НФ]], а [[Зависимости_соединения_и_пятая_нормальная_форма|аномалии зависимостей соединения исправляются пятой НФ]].

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

Аномалии

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Нормальные_формы:_третья_и_Бойса-Кодда&oldid=85078»