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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлено подробное описание первой нормальной формы)
(Добавлено подробное описание второй нормальной формы)
Строка 52: Строка 52:
 
==== Отсутствие ключа ====
 
==== Отсутствие ключа ====
  
Отношение без ключа формально не является отношением. Отсутствие ключа говорит о повторяющихся записях, а отношения рассматриваются как '''подмножества ''' декартового произведения других множеств, что в явном виде запрещает повторяющиеся записи.
+
Отношение без ключа формально не является отношением. Отсутствие ключа говорит о повторяющихся записях, а отношения рассматриваются как '''подмножества ''' декартового произведения других множеств, что в явном виде запрещает повторы.
  
 
=== Приведение в 1НФ ===
 
=== Приведение в 1НФ ===
Строка 68: Строка 68:
  
 
{| class="wikitable"
 
{| class="wikitable"
! CourseId !! Lecturer !! Phones
+
! CourseId !! Lecturer !! Phone
 
|-
 
|-
 
| 1 || Корнеев Г. А. || 111-11-11
 
| 1 || Корнеев Г. А. || 111-11-11
Строка 100: Строка 100:
 
'''Аномалия вставки''' – зависимость возможности записать обладающие собственным независимым смыслом данные от наличия другой связанной информации.
 
'''Аномалия вставки''' – зависимость возможности записать обладающие собственным независимым смыслом данные от наличия другой связанной информации.
 
}}
 
}}
В рассмотренном выше примере невозможно записать информацию о телефоне конкретного преподавателя, если он не читает ни один курс (таким образом, возможность записать Phone для конкретного Lecturer зависит от наличия соответствующего CourseId, хотя напрямую они не зависят друг от друга).
+
В рассмотренном выше примере невозможно записать информацию о телефоне конкретного преподавателя, если он не читает ни один курс (таким образом, возможность записать <tex>\mathrm{Phone}</tex> для конкретного <tex>\mathrm{Lecturer}</tex> зависит от наличия соответствующего <tex>\mathrm{CourseId}</tex>, хотя напрямую они не зависят друг от друга).
  
 
==== Аномалия удаления ====
 
==== Аномалия удаления ====
Строка 108: Строка 108:
 
'''Аномалия удаления''' &ndash; невозможность удалить часть данных, не удалив никакую связанную с ней информацию.
 
'''Аномалия удаления''' &ndash; невозможность удалить часть данных, не удалив никакую связанную с ней информацию.
 
}}
 
}}
В рассмотренном выше, опять же, примере невозможно удалить информацию о том, что конкретный преподаватель читает конкретный курс, не потеряв его номер телефона (как и в случае с аномалией вставки, возможность хранить Phone зависит от существования соответствующего CourseId).
+
В рассмотренном выше, опять же, примере невозможно удалить информацию о том, что конкретный преподаватель читает конкретный курс, не потеряв его номер телефона (как и в случае с аномалией вставки, возможность хранить <tex>\mathrm{Phone}</tex> зависит от существования соответствующего <tex>\mathrm{CourseId}</tex>).
  
 
==== Аномалия изменения ====
 
==== Аномалия изменения ====
Строка 116: Строка 116:
 
'''Аномалия изменения''' &ndash; ситуация, в которой частичное изменение данных нарушает целостность базы данных.
 
'''Аномалия изменения''' &ndash; ситуация, в которой частичное изменение данных нарушает целостность базы данных.
 
}}
 
}}
В рассмотренном примере если один преподаватель ведет один курс и имеет два телефона, при изменении CourseId в одной из соответствующих ему записей будет невозможно восстановить какой курс на самом деле ведет преподаватель (записи с разными Phone, но одинаковыми Lecturer и CourseId, должны всегда поддерживаться в таком же состоянии).
+
В рассмотренном примере если один преподаватель ведет один курс и имеет два телефона, при изменении <tex>\mathrm{CourseId}</tex> в одной из соответствующих ему записей будет невозможно восстановить какой курс на самом деле ведет преподаватель (записи с разными <tex>\mathrm{Phone}</tex>, но одинаковыми <tex>\mathrm{Lecturer}</tex> и <tex>\mathrm{CourseId}</tex>, должны всегда поддерживаться в таком же состоянии).
  
 
== Вторая нормальная форма ==
 
== Вторая нормальная форма ==
Требования
 
  
* Первая нормальная форма
+
{{Определение
* Неключевые атрибуты функционально зависят от ключа в-целом, а не от его части.
+
|definition=
 +
Отношение находится во '''второй нормальной форме''' (2НФ) тогда и только тогда, когда
 +
* оно находится в первой нормальной форме
 +
* все неключевые атрибуты [[Функциональные_зависимости:_замыкание,_эквивалентность_и_правила_вывода|функционально зависят]] от ключа целиком, но не от его части
 +
}}
 +
Вторая нормальная форма позволяет избавиться от некоторых аномалий, возникающих в отношениях в 1НФ.
 +
 
 +
=== Запрещенные конструкции ===
 +
 
 +
В 2НФ запрещено, чтобы какие-либо атрибуты функционально зависели от части ключа. Рассмотрим следующий пример, уже приведенный в 1НФ:
 +
 
 +
{| class="wikitable"
 +
! CourseId !! Year || Lecturer !! Exam
 +
|-
 +
| 1 || 2020 || Корнеев Г. А. || yes
 +
|-
 +
| 2 || 2019 || Киракозов А. Х. || no
 +
|-
 +
| 2 || 2020 || Киракозов А. Х. || no
 +
|-
 +
| 3 || 2019 || Левина А. Б. || yes
 +
|-
 +
| 3 || 2020 || Чепурной А. И. || yes
 +
|}
 +
 
 +
В данном отношении можно выделить следующие функциональные зависимости: <tex>\mathrm{CourseId} \rightarrow \mathrm{Exam}</tex> (наличие экзамена зависит только от предмета) и <tex>\mathrm{CourseId}, \mathrm{Year} \rightarrow \mathrm{Lecturer}</tex> (каждый год только один преподаватель читает конкретный предмет). Таким образом, ключ в данном отношении &ndash; <tex>\mathrm{CourseId}, \mathrm{Year}</tex>, но при этом <tex>\mathrm{Exam}</tex> зависит только от части ключа.
 +
 
 +
Отношения в 1НФ имеют аномалии вставки и удаления (нельзя хранить информацию про экзамен, не зная лектора) и изменения (можно изменить информацию про экзамен по предмету только для одного года). От этих аномалий можно избавиться, если убрать функциональные зависимости от части ключа.
 +
 
 +
=== Приведение в 2НФ ===
 +
 
 +
Отношение в 1НФ приводится к 2НФ декомпозицией по "мешающим" функциональным зависимостям. На примере выше такая зависимость только одна &ndash; <tex>\mathrm{CourseId} \rightarrow \mathrm{Exam}</tex>.
 +
{{Определение
 +
|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>.
 +
}}
 +
Декомпозиция рассмотренного примера по "лишней" функциональной зависимости дает следующий результат:
 +
{| class="wikitable"
 +
! CourseId !! Year || Lecturer
 +
|-
 +
| 1 || 2020 || Корнеев Г. А.
 +
|-
 +
| 2 || 2019 || Киракозов А. Х.
 +
|-
 +
| 2 || 2020 || Киракозов А. Х.
 +
|-
 +
| 3 || 2019 || Левина А. Б.
 +
|-
 +
| 3 || 2020 || Чепурной А. И.
 +
|}
 +
{| class="wikitable"
 +
! CourseId !! Exam
 +
|-
 +
| 1 || yes
 +
|-
 +
| 2 || no
 +
|-
 +
| 3 || yes
 +
|}
  
1НФ приводится к 2НФ декомпозицией по мешающим функциональным зависимостям.
+
После данной декомпозиции, как можно заметить, информация об экзамене по предмету и информация о преподавателе по предмету в конкретный год стали независимыми. Это значит, что больше нет аномалий, свойственных 1НФ: вставка, удаление и изменение данных не затрагивают не связанную с ними напрямую информацию.
 +
 
 +
=== Аномалии ===
 +
 
 +
Аномалия, свойственная 2НФ, возникает, когда какой-то атрибут зависит от ключа транзитивно через множество неключевых атрибутов. Рассмотрим следующий пример:
 +
{| 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>. Несмотря на то, что данное отношение находится в 2НФ, в нем все еще имеют место все три аномалии 1НФ &ndash; аномалии вставки, удаления и изменения (информация о телефонах и о преподавании никак не разделена). Для исправления аномалий 2НФ отношение переводят в [[Нормальные_формы:_третья_и_Бойса-Кодда|третью нормальную форму и выше]].

Версия 03:20, 22 декабря 2020

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

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

Определение:
Отношение находится в первой нормальной форме (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. для каждого фиксированного значения оставшихся атрибутов сделать по записи на каждое значение выбранных:
    1. рассмотрим повторяющиеся атрибуты [math]A_1, \ldots, A_k[/math]
    2. рассмотрим оставшиеся атрибуты [math]B_1, \ldots, B_n[/math]
    3. построим такое отношение [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НФ отношение переводят в третью нормальную форму и выше.