Теория нормализации

наук
Кафедра инженерии программного обеспечения

БД

Функциональные зависимости
Многозначные зависимости
Зависимости по соединению

Нормальные формы
Проектирование схемы реляционной модели данных

отношений реляционной модели данных – это теория, устанавливающая:
каким образом

в 9 покупок, а что если их больше?
Если покупок

Сведения о 9 покупках

одни данные в связи с тем, что не определены другие

Причина! Такая ситуация возможна, когда в одном отношении хранится информация о нескольких сущностях

ПОКУПАТЕЛИ-ПОКУПКИ

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

Составные (неатомарные) данные - 1NF
Неполная (частичная) функциональная зависимость - 2NF
Транзитивная функциональная зависимость - 3NF
Многозначная зависимость - 4NF
Зависимость по соединению - 5NF

Виды нежелательных свойств отношений и нормальные формы, которые их устраняют:

Отношение находится в первой нормальной форме (1NF), если все его

наборы атрибутов A и B. В отношении R B функционально

Формальное определение функциональной зависимости (FD):

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

ключом отношения R, если верно, что:
все атрибуты отношения R функционально

Утверждение: Любое отношение имеет возможный ключ.

Набор К атрибутов отношения R называется суперключом отношения R, если все атрибуты R функционально зависит от К.

систему аксиом Армстронга

множество функциональных зависимостей F и конкретная зависимость А → С,

Например, если в R(A, B, C) и множество F состоит из А → В, то из нее логически следуют (выводимы) следующие зависимости:

(А, С) → В - применяется свойство продолжения;
(А, С) → (В, С) - применяется свойство пополнения.

в отношении R имеется множество FD F. Множество всех FD,

Множество FD F образует полное семейство зависимостей, если F = F+.

Множества FD F и G (логически) эквивалентны, если F+ = G+.

Пусть задано множество FD F. Говорят, что множество FD G образует базис зависимостей F или, то же самое, образует минимальное покрытие F, если G является таким минимальным подмножеством F, что G+ =F+.

ПО существует FD А → В, то в этой ПО

Этот тезис дает формальную основу выявления сущностей предметной области.

форма (2NF)
Пусть в отношении R имеются наборы атрибутов А и

ПОКУПАТЕЛИ-ПОКУПКИ

Атрибут К-ВО полно функционально зависит от (НТ, НП, ДАТА)
Атрибуты ИМЯ и ГОРОД полно функционально зависят от НП
Атрибуты ИМЯ и ГОРОД не полно функционально зависят от (НТ, НП, ДАТА)

FD
ПОКУПАТЕЛИ-ПОКУПКИ
Аномалия обновления. При необходимости изменения города покупа- теля следует помнить,

второй нормальной форме, если оно находится в первой нормальной форме

Теорема (Хита). Отношение R с наборами атрибутов А, В, С , где R.A → R.B, является естественным соединением проекций R[A, B] и R[A, C].

Алгоритм приведения к 2NF. Пусть R имеет множество атрибутов M. Если в R имеется неполная FD R.A → R.B неключевого атрибута B от возможного ключа А, то R разбивается на два отношения: R1[A, B] и R2[M - B]. Если результирующие отношения все еще не находятся в 2NF, то к ним опять применяется этот алгоритм.

Такое разбиение называется бинарной декомпозицией.

содержит информацию о двух сущностях, результирующие – каждое по одной

А необходимо, чтобы исключить тривиальную транзитивную зависимость типа следующей:
2) Условия С

А

С

В

В

А

С

зависимости
КАФЕДРЫ-ФАКУЛЬТЕТЫ


Сущность КАФЕДРА
Сущность ФАКУЛЬТЕТ
Наличие в отношении транзитивной зависимости свидетельствует, что отношение

нормальной форме, если оно находится во второй нормальной форме и

Алгоритм приведения к 3NF. Пусть задано отношение R со множеством атрибутов M. Если в R имеется транзитивная функциональная зависимость R.A → R.B и R.В → R.С неключевого атрибута С от возможного ключа А, то отношение R разбивается на следующие два отношения: R[В, С] и R[M - С]. Если результирующие отношения все еще не находятся в третьей нормальной форме, то к ним опять применяется этот алгоритм.

же, что и при приведении в 2NF:
Исходное отношение содержит информацию

зависимости именно непервичных атрибутов, а не всех атрибутов отношения. Усиленная

Отношение находится в усиленной третьей нормальной форме, если оно находится во второй нормальной форме и не содержит транзитивных зависимостей ВСЕХ атрибутов от возможных ключей.

Это отношение находится в 3NF, но содержит информацию о двух сущностях и поэтому обладает аномалиями

такой же, как в 3NF


Студент

Предмет
Преподаватель
УЧЕБА






Студент

Преподаватель

Преподаватель

Предмет
ПРЕПОДАВАНИЕ
ДИСЦИПЛИНА
Внимание. В результате декомпозиции одна из зависимостей

нормальной форме Бойса-Кодда, если любой детерминант является суперключом.
Утверждение. Усиленная третья нормальная

предметной области отсутствует какая-либо непос- редственная связь между атрибутами А

УЧЕБА

с атрибутами (или наборами атрибутов) А, В, С. Говорят, что

Пример: В отношении УЧЕБА имеются следующие MVD:

Пусть задано отношение R(A,B). MVD А →→ ∅ и А →→ В называются тривиальными так как они присутствуют во любых отношениях .

Предмет →→ Преподаватель Предмет →→ Учебник

набора атрибутов) А, В, С.
MVD обладают следующими аксиомами:

1) Аксиома дополнения
Если А

2) Аксиома пополнения

Если А →→ В и V ⊆ W, то (А, W) →→ (В, V)

3) Аксиома транзитивности

Если А →→ В и В →→ С, то А →→ С – В

следующие две аксиомы, которые связывают многозначные и функциональные зависимости.
Если А

2) Аксиома соединения

Если А →→ В и Z ⊆ B, и для некоторого W, непересекающегося с B имеем W → Z, то A → Z

и А →→ С, то А →→ (В, С)
Если А

2) Псевдотранзитивность

3) Смешанная псевдотранзитивность

Если А →→ В и (А,В) →→ С, то А →→ (С - В)

4) Пересечение и разность

Если А →→ В и А →→ С, то А →→ В ∩ С, А →→ В – С, А →→ С – В

четвертой нормальной форме (4NF), если из существования в нем нетривиальной

Утверждение. Пусть отношение R состоит из атрибутов (или множеств атрибутов) А, В, С. Зависимость А →→ В имеет место в R тогда и только тогда, когда R = R[A, B] * R[A, C].

к 4NF. Пусть задано отношение R с атрибутами А, В,

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

форма
Пусть R является отношением с атрибутами (множествами атрибутов) А1, А2,

JD является тривиальной, если один из наборов атрибутов Ai совпадает со множеством всех атрибутов отношения R.

JD является следствием возможных ключей отношения R, если все Ai (1 ≤ i ≤ n) являются суперключами R.

зависимостей (MVD)
Каждая JD вида *(A, B) в отношении со схемой

На приведенном примере отношение содержит JD *((A,B), (B, C), (A,C)), что можно проверить, вычислив: πA1(R) * πA2(R) *... * πAn(R) .
Однако никакой нетривиальной MVD в нем нет.

В этом можно убедиться, проверив, что ни одна из следующих зависимостей не удовлетворяется:
A →→B, A →→C, B →→A, B →→C, C →→A,C →→B.

в пятой нормальной форме (5NF) тогда и только тогда, когда

Эта нормальная форма также получила название: проекционно-соединительной нормальной формы (PJNF).

Утверждение. Так как любая многозначная зависимость является также и зависимостью по соединению, то любое отношение, находящееся в 5NF (PJNF), также находится и в 4NF.

Введение 5NF аргументируется тем, что никакая n-арная декомпозиция отношения не может быть представлена в виде последовательности бинарных декомпозиций.

BOK, SBJ), которое предназначено для хранения следующей информации:
какие книги

какие книги в каких дисциплинах используются;

какие дисциплины какими преподавателями читаются.

Тот факт, что в отношении занесена следующая информация:

Резниченко использует в своих лекциях книгу «Язык SQL»,

Книга «Язык SQL» используется в предмете ОБДиБЗ» и

Резниченко читает лекции по предмету ОБДиБЗ

еще не свидетельствует, что «Резниченко использует книгу Язык SQL для чтения лекций по предмету ОБДиБЗ»

Отношение TBS находится в 5NF хотя бы потому, что в ней нет JD.

5NF
Если же в отношении TBS действует дополнительное правило (в качестве

то в TBS имеется JD *((TCH, BOK), (BOK, SBJ), (TCH, SBJ)) и это отношение не находится в 5NF, так как в нем единственным ключом является весь набор атрибутов, то есть (TCH, BOK, SUBJ).
В этом случае TBS приводится в 5NF следующим образом:

«Из фактов:
- преподаватель t использует в лекциях книгу b,
- книга b используется в дисциплине s и
- преподаватель t читает лекции по дисциплине s
следует, что преподаватель t использует книгу b для чтения лекций по дисциплине s»,

TBS(TCH, BOK, SBJ) ⇒TB(TCH,BOK), BS(BOK, SBJ), TS(TCH, SBJ)

4NF
Если же в отношении TBS действует дополнительное правило (в качестве

то в TBS имеется JD *((TCH, BOK), (TCH, SBJ)) или, что то же самое, имеются MVD TCH →→ BOK, TCH →→ SBJ, и это отношение не находится не только в 5NF, но и в 4NF.
В этом случае TBS приводится в 4NF (и, более того, в 5NF) следующим образом:

«Из фактов:
- преподаватель t использует в лекциях книгу b,
- преподаватель t читает лекции по дисциплине s
следует, что преподаватель t использует книгу b для чтения лекций по дисциплине s»,

TBS(TCH, BOK, SBJ) ⇒TB(TCH,BOK), TS(TCH, SBJ)

проектирования реляционной схемы
Декомпозиция схемы реляционного отношения
Эквивалентность отношений
Декомпозиция без потери

определении следует уточнить:
процедуру представления отношений в виде совокупности других;
понятие эквивалентности

Тезис об универсальном отношении. Вся ПО может быть представле-на в виде универсального отношения, содержащего все атрибуты ПО.

Задача проектирования. Реляционную схему S0, содержащую схему универсального отношения R:
S0 = {R = },
где U – множество атрибутов, а G – множество зависимостей, необходимо эквивалентно преобразовать в схему SD, представленную в виде совокупности отношений R1,…, Rn:
SD = {Ri = , i = 1, 2, ..., n},
которая была бы в некотором смысле лучше схемы S0.

схемой R(M) называется процедура разбиения R на множество отношений R1,

Декомпозиция обладает свойством соединения без потерь, если R является естественным соединением R1, R2,…, Rn , то есть R= R1 * R2 *…* Rn

Итак, декомпозиция – единственная операция, используемая при разбиении схем отношений

Две совокупности отношений эквивалентны по зависимостям, если они определены на

Если исходной и результирующей схемами являются S0 и SD, то эквивалентность по зависимостям означает следующее:

Где U, Ui – атрибуты S0 и SD, а G, Gi – зависимости S0 и SD.

совокупности отношений эквивалентны по данным, если естественные соединения отношений каждой

Если исходной и результирующей схемами являются S0 и SD, то экви-валентность по данным означает, что такое разбиение производится декомпозицией, обладающей свойством соединения без потерь.
Как добиться, чтобы декомпозиция обладала этим свойством?

Утверждение. Если R1(U1) R2(U2) являются декомпозицией R(U) с сохранением функциональных и/или многозначных зависимостей, то эта декомпозиция обеспечивает соединение без потерь тогда и только тогда, когда: U1 ∩ U2 → (или →→) U1 – U2
либо
U1 ∩ U2 → (или →→) U2 – U1

всегда гарантирует сохранение зависимостей.
Аналогично, не каждое разложение, сохраняющее зависимости,

Эквивалентность нормальных форм.
Декомпозиция универсального отношения вплоть до 3NF сохраняет эквивалентность по данным и по зависимостям.
При приведении универсального отношения к BCNF сохраняется эквивалентность по данным, но теряется эквивалентность по зависимостям.

значит одна схема отношений лучше другой.

Здесь можно говорить о