Цели и средства нормализации — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Соединение)
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 2 участников)
Строка 4: Строка 4:
 
'''Нормализация''' — процесс преобразования отношений реляционной базы данных к виду, отвечающему одной из нормальных форм.
 
'''Нормализация''' — процесс преобразования отношений реляционной базы данных к виду, отвечающему одной из нормальных форм.
 
}}
 
}}
Нормализацию целесообразно понимать следующим образом: она помогает спроектировать базу данных таким образом, чтобы сделать более логически приемлемыми операции обновления отдельных кортежей, что в противном случае (т.е. когда проект базы данных не нормализован) может оказаться затруднительным. Эта цель достигается благодаря тому, что в полностью нормализованном проекте предикаты переменных отношения имеют более простой вид.
+
Нормализация помогает привести базу данных к виду обеспечивающему минимальную логическую избыточность. Эта цель достигается благодаря тому, что в полностью нормализованном проекте предикаты переменных отношения имеют более простой вид.
 
__TOC__
 
__TOC__
 
===Цели===
 
===Цели===
 
* Исключение некоторых типов избыточности
 
* Исключение некоторых типов избыточности
 
* Устранение аномалий
 
* Устранение аномалий
* Разработка проекта базы данных, который является достаточно "качественным" представлением реального мира, интуитивно понятен и может служить хорошей основой для последующего расширения
+
* Разработка проекта базы данных, который является достаточно «качественным» представлением реального мира, интуитивно понятен и может служить хорошей основой для последующего расширения
 
* Упрощение процедуры применения необходимых ограничений целостности
 
* Упрощение процедуры применения необходимых ограничений целостности
 +
 
===Следствия===
 
===Следствия===
Полная нормализация приводит к замедлению работы базы так как увеличивается количество логически независимых переменных отношения ⇒ увеличивается количество отдельно хранимых физических файлов, что в свою очередь приводит к появлению большего количества операций ввода-вывода, что и замедляет работу.
+
Полная нормализация приводит к увеличению количества логически независимых переменных отношения, что может привести к снижению скорости выборки ⇒ к замедлению работы базы данных.
  
 
==Средства нормализации==
 
==Средства нормализации==
 +
Для приведения базы данных в нормальную форму будет применяться декомпозиция без потерь. При построении такой декомпозиции используются операции соединения и проекции.
 
===Проекция===
 
===Проекция===
 
{{Определение
 
{{Определение
Строка 21: Строка 23:
 
'''Проекция''' отношения <tex>R</tex> на множество атрибутов <tex>X</tex>: <tex>\pi_X(R) =\{r \cap X|r\in R\}</tex> — это отношение удовлетворяющее свойствам:
 
'''Проекция''' отношения <tex>R</tex> на множество атрибутов <tex>X</tex>: <tex>\pi_X(R) =\{r \cap X|r\in R\}</tex> — это отношение удовлетворяющее свойствам:
 
* Его заголовок формируется из заголовка отношения <tex>R</tex> путем удаления всех атрибутов, не указанных в множестве <tex>X</tex>
 
* Его заголовок формируется из заголовка отношения <tex>R</tex> путем удаления всех атрибутов, не указанных в множестве <tex>X</tex>
* Тело состоит из всех кортежей <tex>{Х_1 r_1 , X_2 r_2, . . . , X_n r_n }</tex>, таких что в отношении <tex>R</tex> присутствует кортеж со значением <tex>r_1</tex> атрибута <tex>X_1</tex>, <tex>r_2</tex> атрибута <tex>X_2</tex> и т.д.
+
* Тело состоит из всех кортежей <tex>{Х_1:r_1 , X_2:r_2, . . . , X_n:r_n }</tex>, таких что в отношении <tex>R</tex> присутствует кортеж со значением <tex>r_1</tex> атрибута <tex>X_1</tex>, <tex>r_2</tex> атрибута <tex>X_2</tex> и т.д.
 
}}
 
}}
  
Строка 31: Строка 33:
 
|id = natural join
 
|id = natural join
 
|definition =
 
|definition =
'''Естественное соединение''' отношений <tex>P_1</tex> и <tex>P_2</tex>: <tex>P_1 P_2 = \{r_1 ∪ r_2 | r_1 ∈ P_1, r_2 ∈ P_2 ∧ π_Y(r_1) = π_Y(r_2)\}</tex> — отношение с заголовком <tex>\{X, Y, Z\}</tex> и телом, состоящим из всех таких кортежей <tex>\{Х_i х_i</tex>, <tex>Y_j y_j</tex>, . . . , <tex>Z_k z_k\}</tex>, что любой из этих кортежей присутствует и в отношении <tex>P_1</tex>, со значением <tex>x_i</tex> атрибута <tex>Х_i</tex> и значением <tex>y_j</tex> атрибута <tex>Y_j</tex>, и в отношении <tex>P_2</tex>, со значением <tex>y_i</tex> атрибута <tex>Y_i</tex> и значением <tex>z_k</tex> атрибута <tex>Z_k</tex>.
+
'''Естественное соединение''' (англ. ''natural join'') отношений <tex>R_1</tex> и <tex>R_2</tex>: <tex>R_1 R_2 = \{r_1 ∪ r_2 | r_1 ∈ R_1, r_2 ∈ R_2 ∧ π_Y(r_1) = π_Y(r_2)\}</tex> — отношение с заголовком <tex>\{X, Y, Z\}</tex> и телом, состоящим из всех таких кортежей <tex>\{Х_i:х_i</tex>, <tex>Y_j:y_j</tex>, . . . , <tex>Z_k:z_k\}</tex>, что любой из этих кортежей присутствует и в отношении <tex>R_1</tex>, со значением <tex>x_i</tex> атрибута <tex>Х_i</tex> и значением <tex>y_j</tex> атрибута <tex>Y_j</tex>, и в отношении <tex>R_2</tex>, со значением <tex>y_i</tex> атрибута <tex>Y_i</tex> и значением <tex>z_k</tex> атрибута <tex>Z_k</tex>.
 
}}
 
}}
 
* Можно понимать как соединение по совпадающим атрибутам
 
* Можно понимать как соединение по совпадающим атрибутам
* Коммутативно
+
* Коммутативно: <tex>R_1 ⋈ R_2 = R_2 ⋈ R_1</tex>
* Ассоциативно
+
* Ассоциативно: <tex>(R_1 ⋈ R_2) ⋈ R_3 = R_1 ⋈ (R_2 ⋈ R_3)</tex>
  
 
[[Файл:Join.png]]
 
[[Файл:Join.png]]
Строка 41: Строка 43:
 
===Декомпозиция===
 
===Декомпозиция===
 
Процедура нормализации предусматривает разбиение, или '''декомпозицию''', данной переменной отношения на другие переменные отношения, причем декомпозиция должна быть обратимой, т.е. выполняться без потерь информации, то есть, соединение отношений, полученных при декомпозиции множества, должно давать исходное отношение
 
Процедура нормализации предусматривает разбиение, или '''декомпозицию''', данной переменной отношения на другие переменные отношения, причем декомпозиция должна быть обратимой, т.е. выполняться без потерь информации, то есть, соединение отношений, полученных при декомпозиции множества, должно давать исходное отношение
Декомпозиция отношения R на множества атрибутов A и B: <tex>R(A, B) = \pi_A(R) ⋈ \pi_B(R)</tex>
+
Декомпозиция отношения <tex>R</tex> на множества атрибутов <tex>A</tex> и <tex>B</tex>: <tex>R(A, B) = \pi_A(R) ⋈ \pi_B(R)</tex>
  
 
[[Файл:Decomposition.png]]
 
[[Файл:Decomposition.png]]
Строка 56: Строка 58:
  
 
====Пример некорректной декомпозиции====
 
====Пример некорректной декомпозиции====
 +
При обратном соединении полученных отношений исходное отношений не было восстановлено — появились записи, которых не было ⇒ декомпозиция некорректна.
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
Строка 66: Строка 69:
  
 
==Теорема Хита==
 
==Теорема Хита==
Теорема Хита утверждает, что если некоторая декомпозиция выполняется в соответствии с определенной ФЗ, то она будет выполнена без потерь.  
+
Теорема Хита утверждает, что если некоторая декомпозиция выполняется в соответствии с определенной функциональной зависимостью, то она будет выполнена без потерь.  
 
{{Теорема
 
{{Теорема
 
|author=Хит
 
|author=Хит
 
|statement=
 
|statement=
Пусть R(XYZ) является отношением, где X, Y и Z — неперескающиеся множества атрибутов. Если R удовлетворяет функциональной зависимости X → Y, то R равно соединению ее проекций по атрибутам X, Y и Y, Z: <tex>R=\pi_XY(R)⋈ \pi_XZ(R)</tex>
+
Пусть <tex>R(XYZ)</tex> является отношением, где <tex>X</tex>, <tex>Y</tex> и <tex>Z</tex> — неперескающиеся множества атрибутов. Если <tex>R</tex> удовлетворяет функциональной зависимости <tex>X → Y</tex>, то <tex>R</tex> равно соединению его проекций по атрибутам <tex>X</tex>, <tex>Y</tex> и <tex>X</tex>, <tex>Z</tex>: <tex>R=\pi_{XY}(R)⋈ \pi_{XZ}(R)</tex>
 
|proof=
 
|proof=
<tex>\subset</tex>
+
Докажем равенство в обе стороны:
 +
 
 +
1. Докажем, что исходное отношение <tex>R</tex> — подмножество соединения проекций.
 +
 
 +
Рассмотрим произвольный кортеж <tex>r</tex> из отношения <tex>R</tex>.
 +
 
 +
Для проекций кортежа <tex>r</tex> на <tex>XY</tex> и <tex>XZ</tex> выполняетя: <tex>π_{XY}(r) ∈ π_{XY}(R), π_{XZ}(r) ∈ π_{XZ}(R)</tex>.
 +
 
 +
Из этого следует, что <tex>r</tex> — подмножество соединения проекций <tex>⇒ ∀ r∈R: r ∈ \pi_{XY}(R)</tex>⋈<tex>\pi_{XZ}(R)</tex>.
 +
 
 +
2. Докажем, что любой кортеж полученного соединения является кортежем отношения <tex>R</tex>.
  
<tex>∀ r ∈ R: π_{XY}(r) ∈ π_{XY}(R), π_{XZ}(r) ∈ π_{XZ}(R) ⇒ r ∈ π_{XY}(R) ⋈ π_{XZ}(R)</tex>
+
Рассмотрим кортеж <tex>(x, y, z)</tex>, принадлежащий соединению <tex>π_{XY}(R) ⋈ π_{XZ}(R)</tex>
  
<tex>\supset</tex>
+
Для того, чтобы <tex>(x, y, z)</tex> был в соеденении, необходимо, чтобы существовали кортежи <tex>(x, y) ∈ π_{XY}(R)</tex> и <tex>(x, z) ∈ π_{XZ}(R)</tex>
  
<tex>(x, y, z) ∈ π_{XY}(R) ⋈ π_{XZ}(R) (x, y) ∈ π_{XY}, (x, z) ∈ π_{XZ}(R)</tex>
+
Из <tex>(x, z) ∈ π_{XZ}(R)</tex> следует, что существует кортеж <tex>(x, y', z) ∈ R</tex> для некоторого <tex>y'</tex>. Это означает, что должен существовать кортеж <tex>(x, y') ∈ π_{XY}(R)</tex>
<tex>Из (x, z) ∈ π_{XZ}(R) ⇒ ∃ y': (x, y', z) ∈ R ⇒ (x, y') ∈ π_{XY}(R)</tex>
+
 
<tex>X → Y ⇒ ∃! y : (x, y) ∈ π_{XY}(R) ⇒ y = y' ⇒ (x, y, z) ∈ R</tex>
+
Поскольку <tex>X → Y</tex>, существует единственный <tex>y: (x, y) ∈ π_{XY}(R) ⇒ y = y' ⇒ (x, y, z) ∈ R</tex>
 
}}
 
}}
 +
 +
Доказательсто первого пункта не опирается на наличие функциональной зависимости ⇒ справедливо следствие:
 +
 +
'''Следствие''' Исходное отношение <tex>R</tex> всегда является подмножеством соединения отношений, полученных при декомпозиции.
 +
 
==См. также==
 
==См. также==
 
* [[Функциональные зависимости: замыкание, эквивалентность и правила вывода]]
 
* [[Функциональные зависимости: замыкание, эквивалентность и правила вывода]]

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

Определение:
Нормализация — процесс преобразования отношений реляционной базы данных к виду, отвечающему одной из нормальных форм.

Нормализация помогает привести базу данных к виду обеспечивающему минимальную логическую избыточность. Эта цель достигается благодаря тому, что в полностью нормализованном проекте предикаты переменных отношения имеют более простой вид.

Цели

  • Исключение некоторых типов избыточности
  • Устранение аномалий
  • Разработка проекта базы данных, который является достаточно «качественным» представлением реального мира, интуитивно понятен и может служить хорошей основой для последующего расширения
  • Упрощение процедуры применения необходимых ограничений целостности

Следствия

Полная нормализация приводит к увеличению количества логически независимых переменных отношения, что может привести к снижению скорости выборки ⇒ к замедлению работы базы данных.

Средства нормализации

Для приведения базы данных в нормальную форму будет применяться декомпозиция без потерь. При построении такой декомпозиции используются операции соединения и проекции.

Проекция

Определение:
Проекция отношения [math]R[/math] на множество атрибутов [math]X[/math]: [math]\pi_X(R) =\{r \cap X|r\in R\}[/math] — это отношение удовлетворяющее свойствам:
  • Его заголовок формируется из заголовка отношения [math]R[/math] путем удаления всех атрибутов, не указанных в множестве [math]X[/math]
  • Тело состоит из всех кортежей [math]{Х_1:r_1 , X_2:r_2, . . . , X_n:r_n }[/math], таких что в отношении [math]R[/math] присутствует кортеж со значением [math]r_1[/math] атрибута [math]X_1[/math], [math]r_2[/math] атрибута [math]X_2[/math] и т.д.


Projection.png

Соединение

Операция соединения имеет несколько разных вариантов, но чаще всего рассматривается естественное соединение.

Определение:
Естественное соединение (англ. natural join) отношений [math]R_1[/math] и [math]R_2[/math]: [math]R_1 ⋈ R_2 = \{r_1 ∪ r_2 | r_1 ∈ R_1, r_2 ∈ R_2 ∧ π_Y(r_1) = π_Y(r_2)\}[/math] — отношение с заголовком [math]\{X, Y, Z\}[/math] и телом, состоящим из всех таких кортежей [math]\{Х_i:х_i[/math], [math]Y_j:y_j[/math], . . . , [math]Z_k:z_k\}[/math], что любой из этих кортежей присутствует и в отношении [math]R_1[/math], со значением [math]x_i[/math] атрибута [math]Х_i[/math] и значением [math]y_j[/math] атрибута [math]Y_j[/math], и в отношении [math]R_2[/math], со значением [math]y_i[/math] атрибута [math]Y_i[/math] и значением [math]z_k[/math] атрибута [math]Z_k[/math].
  • Можно понимать как соединение по совпадающим атрибутам
  • Коммутативно: [math]R_1 ⋈ R_2 = R_2 ⋈ R_1[/math]
  • Ассоциативно: [math](R_1 ⋈ R_2) ⋈ R_3 = R_1 ⋈ (R_2 ⋈ R_3)[/math]

Join.png

Декомпозиция

Процедура нормализации предусматривает разбиение, или декомпозицию, данной переменной отношения на другие переменные отношения, причем декомпозиция должна быть обратимой, т.е. выполняться без потерь информации, то есть, соединение отношений, полученных при декомпозиции множества, должно давать исходное отношение Декомпозиция отношения [math]R[/math] на множества атрибутов [math]A[/math] и [math]B[/math]: [math]R(A, B) = \pi_A(R) ⋈ \pi_B(R)[/math]

Decomposition.png

Пример корректной декомпозиции

Проекции на CId Phone и Lecturer Phone Соединение CId Lecturer и Lecturer Phone
Decomposition Example 1 1.png Decomposition Example 1 2.png

Пример некорректной декомпозиции

При обратном соединении полученных отношений исходное отношений не было восстановлено — появились записи, которых не было ⇒ декомпозиция некорректна.

Проекции на CId Phone и Lecturer Phone Соединение CId Phone и Lecturer Phone
Decomposition Example 2 1.png Decomposition Example 2 2.png

Теорема Хита

Теорема Хита утверждает, что если некоторая декомпозиция выполняется в соответствии с определенной функциональной зависимостью, то она будет выполнена без потерь.

Теорема (Хит):
Пусть [math]R(XYZ)[/math] является отношением, где [math]X[/math], [math]Y[/math] и [math]Z[/math] — неперескающиеся множества атрибутов. Если [math]R[/math] удовлетворяет функциональной зависимости [math]X → Y[/math], то [math]R[/math] равно соединению его проекций по атрибутам [math]X[/math], [math]Y[/math] и [math]X[/math], [math]Z[/math]: [math]R=\pi_{XY}(R)⋈ \pi_{XZ}(R)[/math]
Доказательство:
[math]\triangleright[/math]

Докажем равенство в обе стороны:

1. Докажем, что исходное отношение [math]R[/math] — подмножество соединения проекций.

Рассмотрим произвольный кортеж [math]r[/math] из отношения [math]R[/math].

Для проекций кортежа [math]r[/math] на [math]XY[/math] и [math]XZ[/math] выполняетя: [math]π_{XY}(r) ∈ π_{XY}(R), π_{XZ}(r) ∈ π_{XZ}(R)[/math].

Из этого следует, что [math]r[/math] — подмножество соединения проекций [math]⇒ ∀ r∈R: r ∈ \pi_{XY}(R)[/math][math]\pi_{XZ}(R)[/math].

2. Докажем, что любой кортеж полученного соединения является кортежем отношения [math]R[/math].

Рассмотрим кортеж [math](x, y, z)[/math], принадлежащий соединению [math]π_{XY}(R) ⋈ π_{XZ}(R)[/math]

Для того, чтобы [math](x, y, z)[/math] был в соеденении, необходимо, чтобы существовали кортежи [math](x, y) ∈ π_{XY}(R)[/math] и [math](x, z) ∈ π_{XZ}(R)[/math]

Из [math](x, z) ∈ π_{XZ}(R)[/math] следует, что существует кортеж [math](x, y', z) ∈ R[/math] для некоторого [math]y'[/math]. Это означает, что должен существовать кортеж [math](x, y') ∈ π_{XY}(R)[/math]

Поскольку [math]X → Y[/math], существует единственный [math]y: (x, y) ∈ π_{XY}(R) ⇒ y = y' ⇒ (x, y, z) ∈ R[/math]
[math]\triangleleft[/math]

Доказательсто первого пункта не опирается на наличие функциональной зависимости ⇒ справедливо следствие:

Следствие Исходное отношение [math]R[/math] всегда является подмножеством соединения отношений, полученных при декомпозиции.

См. также

Источники информации