itmo_conspects

Лекция 6. Нормализация

На прошлой лекции мы рассматривали реляционную алгебру Кодда

Рассмотрим такое отношение:

ФИО	N группы

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

ФИО	N группы	ОП

Добавление ОП добавляет избыточное дублирование: очевидно, что в одной группе студенты изучают одну образовательную программу

ФИО	N группы	ОП
С1	M3200	09.03.02
С2	M3200	X
С3	M3200	X

Здесь же (помимо избыточного выделения памяти) появляются 2 проблемы:

1) Если номер ОП дублировать на все кортежи, то при изменении номера ОП в одном кортеже в других кортежах он не поменяется - нарушается целостность

2) Если номер ОП хранить только в одном кортеже, то при поиске для другого кортежа придется искать именно тот кортеж - тратим больше времени

И в этом случае говорят, что у нашей модели появляется аномалия

Аномалия - состояние базы данных, которое приводит к противоречию или существенно усложняет обработку данных

Различают 3 типа аномалий:

Аномалия модификации - изменение значения одной записи повлечет за собой изменение значения в другой записи

Пример: при изменении у одного студента номера ОП, зависящего от группы, приходится изменять номер ОП в других местах
Аномалия удаления - при удалении записи может пропасть и другая информация

Пример: при удалении всех студентов связь “N группы”-“ОП” теряется
Аномалия добавления - информацию в таблицу нельзя поместить, пока она не полная или требуется дополнительный просмотр таблицы

Пример: при добавлении нового студента приходится искать номер ОП для других студентов из его группы

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

Рассмотрим виды зависимостей атрибутов:

Функциональная зависимость: в некотором отношении x -> y (y зависит от x) тогда и только тогда, когда каждому значению x соответствует в точности одно значение y. Тогда x - детерминант, y - зависимая часть

В примере выше номер ОП зависит от номера группы

Частичная функциональная зависимость - зависимость неключевого атрибута от части составного потенциального ключа

Пример: создадим такое отношение студентов:

ФИО	N группы	ОП	Факультет	Форма обучения

В нем сделаем ФИО и N группы первичным ключом; тогда номер ОП частично зависит от этого ключа (потому что номер ОП зависит от номера группы)

Полная функциональная зависимость - зависимость неключевого атрибута от всего составного потенциального ключа

Транзитивная функциональная зависимость: атрибуты z транзитивно зависит от x, если найдется такой y, что z зависит от y, а y зависит от x (x -> z => Ǝ y : x -> y, y -> z)

Чтобы избежать зависимостей модели декомпозируют в нормальные формы. Разберем типы нормальных форм:

Отношение является первой нормальной формой (1НФ), если все его атрибуты являются простыми

Так как простоту атрибута мы определяем сами, то принадлежность отношения к 1-ой нормальной форме - чисто условность

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

Переделаем таблицу выше в две других: “Студент”

ФИО	N группы	Форма обучения

и “Группа”

N группы	ОП	Факультет

Все эти отношения являются вторыми нормальными формами. В этом случае мы выиграли по памяти (при большом кол-ве студентов не будет избыточно дублироваться номер ОП), но проигрываем по времени

Отношение является третьей нормальной формой (3НФ), если оно находится во 2НФ и все неключевые атрибуты взаимно независимы и полностью зависят от первичного ключа

Также существует другое эквивалентное определение

Отношение является третьей нормальной формой (3НФ), если оно находится во 2НФ и ни один неключевой атрибут не находится в транзитивной функциональной зависимости от потенциального ключа

Рассмотрим еще раз таблицу с группами:

N группы	ОП	Факультет

Здесь факультет транзитивно зависит от номер группы, исправим это:

Таблица “Группа”:

N группы	ОП

Таблица “Образовательная программа”:

ОП	Факультет

В итоге для получения связи Студент-Факультет нужно объединить целых 3 таблицы

Теперь рассмотрим более экзотические варианты. Введем отношение “Проект”

ИСУ	Паспорт	ID проекта	Роль

Здесь потенциальными ключами являются пары либо “ИСУ”-“ID проекта”, либо “Паспорт”-“ID проекта”

Роль студента в проекте функционально полно зависит от выбранного нами первичного ключа - соблюдается 3НФ

Но здесь возникает аномалия - студент поменял паспорт, в одном проекте это заменили, а в другом проекте нет

Отношение является нормальной формой Бойса-Кодда (БКНФ), если оно находится в 3НФ и детерминанты всех зависимостей являются потенциальными ключами

Паспорт зависит от номера ИСУ, но ИСУ - это не потенциальный ключ, а его часть. Поэтому переведем отношение в БКНФ:

Таблица “Проект”

ИСУ	ID проекта	Роль

Таблица “Паспорт”

ИСУ	Паспорт

Приведем другой пример - таблица лекторов и практиков:

ID Дисциплины	ID Лектора	ID Практика

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

Чтобы исправить это, определим четвертую нормальную форму:

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

Изменим отношение на такое:

ID Дисциплины	ID Преподавателя	Роль

Здесь нет аномалии модификации, но при этом мы теряем связь лектор-практик (допускается, что некоторые лектора несовместимы с некоторыми практиками 🦆)

Заметим, что в отношении без неключевых атрибутов автоматически выполнена 2НФ и 3НФ.

Помимо этих нормальных форм выделяют 5НФ и 6НФ, но на этом курсе рассматриваться они не будут

Заметим, что в ходе декомпозиции модели мы увеличиваем количество отношений, из-за чего скорость поиска уменьшается (добавление дополнительных join не стоят бесплатно)

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

This site is open source. Improve this page.