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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 2 участников)
Строка 1: Строка 1:
Первая и вторая нормальные формы разработаны Эдгаром Коддом и являются достаточно "самоочевидными". Самоочевидность заключается в том, что отношения в первой и второй нормальной формах обладают интуитивно понятными базовыми свойствами, которые логично требовать от отношений, используемых в рамках баз данных.
+
Первая и вторая нормальные формы разработаны Эдгаром Коддом и являются достаточно «самоочевидными». Самоочевидность заключается в том, что отношения в первой и второй нормальной формах обладают интуитивно понятными базовыми свойствами, которые логично требовать от отношений, используемых в рамках баз данных.
  
 
== Первая нормальная форма ==
 
== Первая нормальная форма ==
Строка 27: Строка 27:
 
| 4 || Сегаль А. С. || 666-66-66 ||  
 
| 4 || Сегаль А. С. || 666-66-66 ||  
 
|}
 
|}
 
+
В отношениях такого вида сложно обеспечивать консистентность данных. Рассмотрим пример выше. Первая возникающая проблема заключается в том, что при появлении преподавателя с более, чем двумя телефонами, придется изменять целиком структуру отношения. Вторая проблема – на выполнение запроса «проверить, что никакие два преподавателя не имеют одинаковый телефон» и других запросов, аналогичных данному, потребуется экспоненциальное от количества полей с данными о телефонах время.
В отношениях такого вида сложно обеспечивать консистентность данных. Рассмотрим пример выше. Первая возникающая проблема заключается в том, что при появлении преподавателя с более, чем двумя телефонами, придется изменять целиком структуру отношения. Вторая проблема -- на выполнение запроса "проверить, что никакие два преподавателя не имеют одинаковый телефон" и других запросов, аналогичных данному, потребуется экспоненциальное от количества полей с данными о телефонах время.
 
  
 
==== Неатомарные атрибуты ====
 
==== Неатомарные атрибуты ====
Строка 47: Строка 46:
 
| 4 || Сегаль А. С. || 666-66-66
 
| 4 || Сегаль А. С. || 666-66-66
 
|}
 
|}
 
 
Потенциальным решением проблемы повторяющихся групп является группировка атрибутов по смыслу. На примере показано, как несколько телефонов из прошлого отношения были сгруппированы в единый атрибут, что позволяет не изменять структуру отношения в зависимости от максимального количества телефонов у одного человека. Однако проблема большого времени работы проверки корректности данных все еще остается.
 
Потенциальным решением проблемы повторяющихся групп является группировка атрибутов по смыслу. На примере показано, как несколько телефонов из прошлого отношения были сгруппированы в единый атрибут, что позволяет не изменять структуру отношения в зависимости от максимального количества телефонов у одного человека. Однако проблема большого времени работы проверки корректности данных все еще остается.
  
Строка 57: Строка 55:
  
 
Для того, чтобы привести произвольное отношение <tex>R</tex> в 1НФ, достаточно:
 
Для того, чтобы привести произвольное отношение <tex>R</tex> в 1НФ, достаточно:
 
+
# Рассмотреть все наборы атрибутов, имеющих одинаковый смысл
# рассмотреть все наборы атрибутов, имеющих одинаковый смысл
+
# Для каждого фиксированного значения оставшихся атрибутов сделать по записи на каждое значение выбранных:
# для каждого фиксированного значения оставшихся атрибутов сделать по записи на каждое значение выбранных:
+
#* рассмотрим повторяющиеся атрибуты <tex>A_1, \ldots, A_k</tex>  
## рассмотрим повторяющиеся атрибуты <tex>A_1, \ldots, A_k</tex>  
+
#* рассмотрим оставшиеся атрибуты <tex>B_1, \ldots, B_n</tex>  
## рассмотрим оставшиеся атрибуты <tex>B_1, \ldots, B_n</tex>  
+
#* построим такое отношение <tex>T</tex> на атрибутах <tex>B_1, \ldots, B_n, A</tex>, что <tex>\{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</tex>
## построим такое отношение <tex>T</tex> на атрибутах <tex>B_1, \ldots, B_n, A</tex>, что <tex>\{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</tex>
+
# Аналогичную процедуру повторить для всех неатомарных атрибутов
# аналогичную процедуру повторить для всех неатомарных атрибутов
 
  
 
Отношение, использованое в примерах выше, после приведения в 1НФ будет выглядеть как
 
Отношение, использованое в примерах выше, после приведения в 1НФ будет выглядеть как
 
 
{| class="wikitable"
 
{| class="wikitable"
 
! CourseId !! Lecturer !! Phone
 
! CourseId !! Lecturer !! Phone
Строка 92: Строка 88:
 
* технической/алгоритмической сложность внесения или изменения данных
 
* технической/алгоритмической сложность внесения или изменения данных
 
}}
 
}}
Переход в 1НФ не уменьшает выразительную способность "разрешенных" отношений, но при этом исправляет только самые простые аномалии, поэтому в отношениях в 1НФ, не приведенных хотя бы в 2НФ, могут возникать аномалии более сложного вида.
+
Переход в 1НФ не уменьшает выразительную способность &laquo;разрешенных&raquo; отношений, но при этом исправляет только самые простые аномалии, поэтому в отношениях в 1НФ, не приведенных хотя бы во 2НФ, могут возникать аномалии более сложного вида.
  
 
{{Определение
 
{{Определение
Строка 122: Строка 118:
 
=== Запрещенные конструкции ===
 
=== Запрещенные конструкции ===
  
В 2НФ запрещено, чтобы какие-либо атрибуты функционально зависели от части ключа. Рассмотрим следующий пример, уже приведенный в 1НФ:
+
Во 2НФ запрещено, чтобы какие-либо атрибуты функционально зависели от части ключа. Рассмотрим следующий пример, уже приведенный в 1НФ:
 
 
 
{| class="wikitable"
 
{| class="wikitable"
 
! CourseId !! Year || Lecturer !! Exam
 
! CourseId !! Year || Lecturer !! Exam
Строка 142: Строка 137:
 
Отношения в 1НФ имеют аномалии вставки и удаления (нельзя хранить информацию про экзамен, не зная лектора) и изменения (можно изменить информацию про экзамен по предмету только для одного года). От этих аномалий можно избавиться, если убрать функциональные зависимости от части ключа.
 
Отношения в 1НФ имеют аномалии вставки и удаления (нельзя хранить информацию про экзамен, не зная лектора) и изменения (можно изменить информацию про экзамен по предмету только для одного года). От этих аномалий можно избавиться, если убрать функциональные зависимости от части ключа.
  
=== Приведение в 2НФ ===
+
=== Приведение во 2НФ ===
  
Отношение в 1НФ приводится к 2НФ декомпозицией по "мешающим" функциональным зависимостям. На примере выше такая зависимость только одна &ndash; <tex>\mathrm{CourseId} \rightarrow \mathrm{Exam}</tex>.
+
Отношение в 1НФ приводится к 2НФ декомпозицией по &laquo;мешающим&raquo; функциональным зависимостям. На примере выше такая зависимость только одна &ndash; <tex>\mathrm{CourseId} \rightarrow \mathrm{Exam}</tex>.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
'''Декомпозиция''' отношения <tex>R</tex>, состоящего из наборов атрибутов <tex>A, B, C</tex>, по функциональной зависимости <tex>A \rightarrow B</tex> &ndash; пара отношений <tex>\pi_{A, B} R</tex> и <tex>\pi_{A, C} R</tex>.
 
'''Декомпозиция''' отношения <tex>R</tex>, состоящего из наборов атрибутов <tex>A, B, C</tex>, по функциональной зависимости <tex>A \rightarrow B</tex> &ndash; пара отношений <tex>\pi_{A, B} R</tex> и <tex>\pi_{A, C} R</tex>.
 
}}
 
}}
Декомпозиция рассмотренного примера по "лишней" функциональной зависимости дает следующий результат:
+
Декомпозиция рассмотренного примера по &laquo;лишней&raquo; функциональной зависимости дает следующий результат:
 
{| class="wikitable"
 
{| class="wikitable"
 
! CourseId !! Year || Lecturer
 
! CourseId !! Year || Lecturer
Строка 192: Строка 187:
 
|}   
 
|}   
  
В нем есть две базовые функциональные зависимости: <tex>\mathrm{CourseId}, \mathrm{Year} \rightarrow \mathrm{Lecturer}</tex> и <tex>\mathrm{Lecturer} \rightarrow \mathrm{Phone}</tex>. Несмотря на то, что данное отношение находится в 2НФ, в нем все еще имеют место все три аномалии 1НФ &ndash; аномалии вставки, удаления и изменения (информация о телефонах и о преподавании никак не разделена). Для исправления аномалий 2НФ отношение переводят в [[Нормальные_формы:_третья_и_Бойса-Кодда|третью нормальную форму и выше]].
+
В нем есть две базовые функциональные зависимости: <tex>\mathrm{CourseId}, \mathrm{Year} \rightarrow \mathrm{Lecturer}</tex> и <tex>\mathrm{Lecturer} \rightarrow \mathrm{Phone}</tex>. Несмотря на то, что данное отношение находится во 2НФ, в нем все еще имеют место все три аномалии 1НФ &ndash; аномалии вставки, удаления и изменения (информация о телефонах и о преподавании никак не разделена). Для исправления аномалий 2НФ отношение переводят в [[Нормальные_формы:_третья_и_Бойса-Кодда|третью нормальную форму и выше]].

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

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

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

Определение:
Отношение находится в первой нормальной форме (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НФ отношение переводят в третью нормальную форму и выше.