Функциональные зависимости и нормализация Если при логическом проектировании

ограничений целостности, то необходимо решить:
из каких отношений должна состоять

БД;
какие атрибуты должны быть у этих отношений.

При проектировании БД возникает две проблемы:
Проблема логического проектирования БД:
Как отразить объекты предметной области в абстрактные объекты модели данных так, чтобы это отражение не противоречило семантике предметной области и было «лучшим»?
Проблема физического проектирования БД:
Как обеспечить эффективность манипулирования данными в рамках конкретной СУБД?

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

Один из вариантов проектирования баз данных – использование моделей сущность – связь (ER-моделей). Данный подход основан на формализации концептуальных представлений разработчика о структуре данных предметной области. Затем используется «отображение» ER-модели на реляционные структуры.

внутри одного отношения.
Различают ФЗ которые выполняются для конкретного значения

отношения и ФЗ которые выполняются для набора всех возможных значений отношения.

Определение
Пусть R – отношение (переменная отношения), а X и Y - произвольные подмножества множества атрибутов R. Тогда Y функционально зависит от X (XY) тогда и только тогда, когда для любого допустимого значения отношения R каждое значение X связано в точности с одним значением Y.

Определение
Тривиальные зависимости - зависимости, которые не могут не выполняться.
Например {X,Y}Y.
Зависимость тривиальна тогда и только тогда, когда правая (зависимая) часть является подмножеством левой (детерминанта).

Иначе говоря, для любого допустимого значения отношения R, обладающего ФЗ (XY), истинно утверждение: если кортежи совпадают по значению X, то они совпадают и по значению Y.

(XY)  xi=xk   yi=yk

при каждом обновлении данных в БД все они должны быть

проверены.
Для обеспечения быстродействия работы БД необходимо минимизировать множество функциональных зависимостей в отношениях.
Поэтому для множества функциональных зависимостей S отношения R желательно определить множество меньшего размера Sm такое, что каждая ФЗ из S могла быть получена на основе ФЗ из Sm.

Из определения потенциального ключа следует, что если X – потенциальный ключ отношения R, то все неключевые атрибуты Y отношения R должны функционально зависеть от X.

Если X – потенциальный ключ, то XiXk и существует XY и X Z .
При этом не обязательно
YiYk и ZiZk

Если отношение R удовлетворяет функциональной зависимости XY и X не является потенциальным ключем, то R будет обладать некоторой избыточностью.

Определение
Замыкание множества функциональных зависимостей S+ - это множество всех ФЗ, которые могут быть получены на основе заданного множества ФЗ путем применения правил выводаS.

АВ. (тривиальная зависимость)
Дополнение: если АВ, то АСВС.
Транзитивность: если АВ и

ВС, то АС.

Используемые обозначения:
А, В, С и D – произвольные подмножества множества атрибутов заданного отношения R,
АВ –объединение множеств А и В. (АВ ::=А  В)

Дополнительные правила (удобны, хотя и выводятся из 1-3):
Самоопределение: AA
Декомпозиция: если ABC, то AB и AC
Объединение: если AB и AC, то ABC
Композиция: если AB и CD, то ACBD
Теорема всеобщего объединения: Если AB и CD, то A(C-D) BD

Этот набор правил является полным (на их основе могут быть получены все ФЗ, которые подразумевает заданный набор ФЗ S) и исчерпывающим (никакие дополнительные (неподразумеваемые S) ФЗ не могут быть выведены).
Т.е. этих правил достаточно для получения замыкания S+.

наличие ФЗ:
ADF
Рассмотрим отношение R , содержащее атрибуты A,B,C,D,E,F

К отношения R, которое содержит в виде подмножества (необязательно собственного)

по крайней мере один потенциальный ключ.
Следовательно, для каждого атрибута А отношения R истина ФЗ КА

На практике обычно не строится замыкание S+ заданного множества ФЗ S , а анализируется принадлежность конкретной ФЗ данному замыканию S+.

Алгоритм построения замыкания К+ множества К для заданного S:
К+=К, K0=K.
Выбрать первую ФЗ XY из S.
Если XK+, то К+= К+Y.
Если рассмотрены все ФЗ из S, то перейти на 5,
иначе выбрать нерассмотренную ФЗ XY из S и перейти на 3.
Если К+=К0, то 6, иначе К0= К+ и перейти на 2.
Конец (получено замыкание К+ множества К для заданного S)

Пусть дано отношение R, множество ФЗ S и предполагаемый суперключ К.
Необходимо определить, будут ли все атрибуты отношения R функционально зависеть от К

часть каждой ФЗ множества S содержит только один атрибут
Левая часть

(детерминант) каждой ФЗ множества S является неприводимой, т.е. ни один атрибут не может быть опущен из детерминанта без изменения замыкания S+.Такая ФЗ называется неприводимой слева или полной ФЗ.
Ни одна ФЗ множества S не может быть опущена из S без изменения замыкания S+.

Если имеются два множества ФЗ S1 и S2 и любая ФЗ Si  S1 так же принадлежит множеству S2 (Si  S2), то есть S1+  S2+, то S2 называется покрытием S1.

Множества ФЗ S1 и S2 некоторого отношения R эквивалентны, если S+=S1+

ФЗ S.
Используя декомпозицию получить из S множество S1 из ФЗ

с одноэлементной правой частью.
Для каждой ФЗ множества S1 проверить каждый атрибут детерминанта: если S1 и множество, полученное в результате устранения некоторого атрибута А в левой части, эквивалентны, то этот атрибут следует удалить.
Для каждой ФЗ f множества S1проверить эквивалентность S1 и S1-f, если они эквивалентны, то f следует удалить из S1.

Для наглядного представления ФЗ используют диаграммы
Пример:
Пусть дано отношение R , содержащее атрибуты A,B,C,D,E,F
И заданы ФЗ: ABC, BE, CDEF
Диаграммы ФЗ для отношения R :

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

области.

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

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

Нормализация – это формальный метод анализа отношений на основе их ключей и существующих функциональных зависимостей

два или более отношений без потери информации.
Основным методом, применяемым

при нормализации отношений является декомпозиция

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

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

концепцией независимых проекций.
Пусть R1 и R2 – проекции отношения

R, полученные в результате декомпозиции.
R1 и R2 независимы тогда и только тогда, когда
каждая ФЗ в отношении R является логическим следствием ФЗ в R1 и R2;
общие атрибуты проекций R1 и R2 образуют потенциальный ключ, по крайней мере, для одной из них.

2. Декомпозиция должна выполняться
с сохранением зависимостей 
Пусть в результате декомпозиции отношения R, имеющего множество ФЗ S, получено:
множество проекций R1, R2… Rn и
множества соответствующих ФЗ S1,S2,…,Sn;
каждая ФЗ множества Si будет относиться только к атрибутам Ri.
Если замыкание множества S’, являющегося объединением множеств Si (S’=S1S2…Sn), равно замыканию множества S (S’+=S+), то декомпозицию можно считать проведенной с сохранением зависимостей.

одной или нескольких повторяющихся групп данных.
Пример:
Ключом в представленной таблице

является поле «Фирма»
При работе с таблицей возможны все указанные ранее аномалии (обновления, удаления, вставки)

отношение содержит уникальные кортежи со скалярными данными.
(Т.е. нет одинаковых строк

в таблице и в каждой ячейке таблицы находится только одно значение)

Отношение находится в определенной нормальной форме (НФ), если оно удовлетворяет заданным условиям этой формы.

Отношение в 1НФ иногда называют просто нормализованным отношением.

Пример:
Приведение ненормализованной таблицы к отношению в 1НФ путем дублирования данных
(возникающая избыточность будет «убрана» в ходе дальнейшей нормализации)

находится во второй нормальной форме (2НФ), если оно находится в

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

Пример :
Дано отношение R , содержащее атрибуты A,B,C,D с первичным ключом (А, В) и ФЗ АВ. Т.к. АВ – ключ отношения, то истины ФЗ АВС и АВ D.
Следовательно, это отношение может быть заменено двумя отношениями R1 и R2:
R1 (A,D) с первичным ключом (A),
R2 (A,B,C) с первичным ключом (A,В) и внешним ключом (A), связанным с R1.

При получения отношений во 2НФ необходимо в отношении 1 НФ устранить частичные зависимости. (Имеет смысл, если детерминанты составные)

Т.к. АВ и АВС, то получаем ВС и АС, т.е. С транзитивно (через В) зависит от А,
т.е имеем избыточное ограничение целостности.

R

R2

R1

оно находится во 2НФ и, кроме этого, каждый неключевой атрибут

отношения нетранзитивно зависит от каждого потенциального ключа этого отношения..

R

R2 с ФЗ A  B  C

R1

R4

R3

Если в отношении имеет место транзитивная зависимость между атрибутами, то для перехода к 3НФ транзитивно-зависимые атрибуты «выносятся» в новое отношение вместе с копией детерминанта.

неприводимая слева ФЗ обладает потенциальным ключом к качестве детерминанта.
Другая

формулировка – Отношение находится в НФБК тогда и только тогда, когда детерминанты являются потенциальными ключами.

Нормальная форма Бойса-Кодда учитывает ФЗ, в которых участвуют все потенциальные ключи отношения, а не только его первичный ключ.
Для отношения с единственным потенциальным ключом 3НФ и НФБК эквивалентны.

Пример:
Дано отношение R{S,D,T}, где: S-студент, D-дисциплина, T-преподаватель.

На R заданы следующие ограничения:
1. Каждый студент, изучающий данную дисциплину, обучается только одним преподавателем.
2. Каждый преподаватель ведет только одну дисциплину (но дисциплина может преподаваться несколькими преподавателями).
Из 1 следует ФЗ {S,D}  T , а из 2 следует ФЗ T  D

и {S,T}. Отношение находится в 3 НФ (но не в

НФБК) и характеризуется определенными аномалиями обновления (Например, при удалении данных о том что некоторый студент изучает определенную дисциплину, может быть утрачены данные о том, что соответствующий преподаватель преподает эту дисциплину). Это связано с тем, что Т является детерминантом ФЗ, но не является потенциальным ключом.

Для решения проблемы необходимо провести декомпозицию данного отношения на два отношения в НФБК:
R{S,D,T} > R1{S,T} и R2{T,D} с единственной ФЗ TD

R1{S,T} – ключ {S,T}, без ФЗ

R2{T,D} – ключ Т, ФЗ TD

Полученные проекции не являются независимыми, так как ФЗ {S,D}  T для R не может быть выведена из ФЗ TD, имеющейся в R1 и R2.

НФБК, поэтому данное условие является желательным, но не обязательным.
Декомпозиция с

образованием НФБК всегда возможноа но не всегда целесообразна (т.к. при такой декомпозиции могут быть «потеряны» ФЗ).

Нормальные формы

Нормализация от 1НФ до НФБК позволяет устранить любые аномалии, вызванные функциональными зависимостями.
Но!
Кроме функциональных зависимостей, существуют и другие виды зависимостей, которые могут вызвать проблемы, связанные с нарушением целостности данных.

для каждого значения A имеется набор значений атрибута B и

набор значений атрибута C, но входящие в эти наборы значения атрибутов B и C не зависят друг от друга, а определяются только значением атрибута A.
Обозначение: A  B и A  C

В данной таблице имеют место две многозначные зависимости:
Торговая фирм  Магазины и Торговая фирм  Товары.
При этом перечень товаров, в общем случае, может не зависеть от адресов магазинов

Пример: Таблица с многозначными зависимостями

Пример не удачный!
Почему?

как тривиальная , если
атрибут B является подмножеством атрибута A,

или A B =R.
Если условия B  A или A B =R не выполняются, то A  B определяется как нетривиальная.

Определение:
Отношение находится в четвертой нормальной форме (4НФ), если оно находится в НФБК и не содержит нетривиальных многозначных зависимостей.

Пример:
Дано ненормализованное отношение R (атрибуты не являются атомарными) без функциональных зависимостей

данном отношении кортеж {D:d,T:t;B:b} будет присутствовать, если дисциплину d ведет

преподаватель t с использованием учебника b.

Отношение R’ находится в НФБК, т.к. является полностью ключевым.
НО! Полученное отношение обладает избыточностью и характеризуется аномалиями обновления (например, на каждого нового преподавателя по предмету требуется ввести количество кортежей, равное числу учебников по данному предмету).

В R’ нет ФЗ, но существуют две многозначные зависимости: D>T и D>B.
Отношение R’ можно заменить двумя более удобными в использовании проекциями R1 {D,T} и R2 {D,B} каждая из которых находится в НФБК (является полностью ключевой).

на две проекции, но можно провести такую декомпозицию на n

(n>2) проекций.
Такие отношения называют «n-декомпозируемыми»

Нормальные формы

Соединение проекций R1{S,P} и R2{P,J} по P дает отношение R’{S,P,J}, в котором имеется лишний кортеж (Т.е. R’ R).
Для того, чтобы исключить «лишний» кортеж необходимо выполнить операцию соединения полученного отношения R’ с проекцией R3{J,S} (по атрибутам J,S)

Итоговый результат не зависит от порядка выполнения соединений!

Пример:
Имеем отношение R{S,P,J} в 4НФ (полностью ключевое, не содержит нетривиальных ФЗ и МЗ) и три его бинарные проекции R1{S,P}, R2{P,J} и R3{J,S}

связанное с таким условием называется зависимостью соединения (ЗС).
Нормальные формы
Определение:
Зависимость

соединения (ЗС) – свойство декомпозиции, которое вызывает генерацию ложных кортежей при обратном соединении декомпозированных отношений с помощью операции естественного соединения

Определение:
Отношение R находится в пятой нормальной форме (5НФ) (проекционно-соединительной НФ, если оно не содержит зависимостей соединения.

Отношение в 5НФ не содержит аномалий, которые могут быть исключены разбиением на проекции.

3НФ (декомпозиция на проекции исключающие транзитивные ФЗ)
3НФ  НФБК (декомпозиция

на проекции, исключающие ФЗ в которых детерминанты не являются потенциальными ключами)
Обобщение п.п.1-3 : Исходное отношение следует разбить на проекции для исключения всех ФЗ, в которых детерминанты не являются потенциальными ключами.
НФБК  4НФ (декомпозиция на проекции, исключающие многозначные зависимости, которые не являются ФЗ). (На практике обычно многозначные зависимости исключаются перед этапами 1-3 путем отделения независимых повторяющихся групп)
4НФ  5НФ (декомпозиция на проекции, исключающие любые зависимости соединения, которые не подразумеваются потенциальными ключами (если их можно выявить))

Общая схема процесса нормализации