Коллектив Авторов - Базы данных: конспект лекций
Inv <F(S)> r(S) = ∀X → Y ∈F(S) [inv <X → Y> r(S)].
Итак, это множество ограничений, накладываемое функциональными зависимостями, расшифровывается следующим образом: для любого правила из системы функциональных зависимостей X → Y, принадлежащего множеству функциональных зависимостей F(S), действует ограничение функциональных зависимостей inv <X → Y> r(S), определенных над множеством отношения r(S).
Пусть какое-то отношение r(S) удовлетворяет этому ограничению.
Применяя правила вывода Армстронга к функциональным зависимостям, определенным для множества F(S), можно получить новые функциональные зависимости, как уже было сказано и доказано нами ранее. И, что показательно, ограничениям этих функциональных зависимостей отношение F(S) будет автоматически удовлетворять, что видно из расширенной формы записи правил вывода Армстронга. Напомним общий вид этих расширенных правил вывода:
Правило вывода 1. inv < X → X > r(S);
Правило вывода 2. inv <X → Y> r(S) ⇒ inv <X ∪ Z → Y> r(S);
Правило вывода 3. inv <X → Y> r(S) & inv <Y ∪ W → Z> r(S) ⇒ inv <X ∪ W → Z>;
Возвращаясь к нашим рассуждениям, пополним множество F(S) новыми, выведенными из него же с помощью правил Армстронга зависимостями. Будем применять эту процедуру пополнения до тех пор, пока у нас не перестанут получаться новые функциональные зависимости. В результате этого построения мы получим новое множество функциональных зависимостей, называемое замыканием множества F(S) и обозначаемое F+(S).
Действительно, такое название вполне логично, ведь мы собственноручно путем длительного построения «замкнули» множество имеющихся функциональных зависимостей само на себе, прибавив (отсюда «+») все новые функциональные зависимости, получившиеся из имеющихся.
Необходимо заметить, что этот процесс построения замыкания конечен, ведь конечна сама схема отношения, на которой и проводятся все эти построения.
Само собой разумеется, что замыкание является надмножеством замыкаемого множества (действительно, ведь оно больше!) и ни сколько не изменяется при своем повторном замыкании.
Если записать только что сказанное в формулярном виде, то получим:
F(S) ⊆ F+(S), [F+(S)]+= F+(S);
Далее из доказанной истинности (т. е. законности, правомерности) правил вывода Армстронга и определения замыкания следует, что любое отношение, удовлетворяющее ограничениям заданного множества функциональных зависимостей, будет удовлетворять ограничению зависимости, принадлежащей замыканию.
X → Y ∈ F+(S) ⇒ ∀r(S) [inv <F(S)> r(S) ⇒ inv <X → Y> r(S)];
Итак, теорема полноты системы правил вывода Армстронга утверждает, что внешняя импликация может совершенно законно и обоснованно быть заменена эквивалентностью.
(Доказательство этой теоремы мы рассматривать не будем, так как сам процесс доказательства не столь важен в нашем конкретном курсе лекций.)
Лекция № 10. Нормальные формы
1. Смысл нормализации схем баз данных
Понятие, которое мы будем рассматривать в данном разделе, связано с понятием функциональных зависимостей, т. е. смысл нормализации схем баз данных неразрывно связан с понятием ограничений, накладываемых системой функциональных зависимостей, и во многом следует из этого понятия.
Исходной точкой любого проектирования базы данных является представление предметной области в виде одного или нескольких отношений, и на каждом шаге проектирования производится некоторый набор схем отношений, обладающих «улучшенными» свойствами. Таким образом, процесс проектирования представляет собой процесс нормализации схем отношений, причем каждая следующая нормальная форма обладает свойствами, в некотором смысле лучшими, чем предыдущая.
Каждой нормальной форме соответствует определенный набор ограничений, и отношение находится в некоторой нормальной форме, если удовлетворяет свойственному ей набору ограничений. Примером может служить ограничение первой нормальной формы – значения всех атрибутов отношения атомарны.
В теории реляционных баз данных обычно выделяется следующая последовательность нормальных форм:
1) первая нормальная форма (1 NF);
2) вторая нормальная форма (2 NF);
3) третья нормальная форма (3 NF);
4) нормальная форма Бойса – Кодда (BCNF);
5) четвертая нормальная форма (4 NF);
6) пятая нормальная форма, или нормальная форма проекции-соединения (5 NF или PJ/NF).
(В данный курс лекций включается подробное рассмотрение первых четырех нормальных форм базовых отношений, поэтому мы не будем подробно разбирать четвертую и пятую нормальные формы.)
Основные свойства нормальных форм состоят в следующем:
1) каждая следующая нормальная форма в некотором смысле лучше предыдущей нормальной формы;
2) при переходе к следующей нормальной форме свойства предыдущих нормальных форм сохраняются.
В основе процесса проектирования лежит метод нормализации, т. е. декомпозиции отношения, находящегося в предыдущей нормальной форме, на два или более отношений, которые удовлетворяют требованиям следующей нормальной формы (с этим мы столкнемся, когда нам самим придется по мере прохождения материала проводить нормализацию того или иного базового отношения).
Как уже упоминалось в разделе, посвященном созданию базовых отношений, заданные множества функциональных зависимостей, накладывают соответствующие ограничения на схемы базовых отношений. Эти ограничения в общем случае реализуются двумя методами:
1) декларативно, т. е. с помощью объявления в базовом отношении различного вида первичных, кандидатных и внешних ключей (это метод, получивший наибольшее распространение);
2) процедурно, т. е. написанием программного кода (использованием упомянутых выше так называемых триггеров).
При помощи простой логики можно понять, в чем же заключается смысл нормализации схем баз данных. Нормализовывать базы данных или приводить базы данных к нормальному виду – это значит определять такие схемы базовых отношений, чтобы максимально уменьшить необходимость написания программного кода, увеличить производительность работы базы данных, облегчить поддержку целостности данных по состоянию и ссылочной целостности. То есть сделать код и работу с ним максимально простой и удобной разработчикам и пользователям.
Для того чтобы наглядно в сравнении продемонстрировать работу ненормализованной и нормализованной базы данных, рассмотрим следующий пример.
Пусть у нас имеется базовое отношение, содержащее информацию о результатах экзаменационной сессии. Такую базу данных мы уже рассматривали раньше.
Итак, вариант 1 схемы базы данных.
Сессия (№ зачетной книжки, Фамилия, Имя, Отчество, Предмет, Оценка)
В этом отношении, как видно из изображения схемы базового отношения, задан составной первичный ключ:
Primary key (№ зачетной книжки, Предмет);
Также в этом отношении задана система функциональных зависимостей:
{№ зачетной книжки} → {Фамилия, Имя, Отчество};
Приведем табличный вид небольшого фрагмента базы данных с данной схемой отношения. Этот фрагмент мы уже применяли в рассмотрении ограничений функциональных зависимостей, поэтому на его примере нам будет довольно легко понять и данную тему.
Здесь для поддержания целостности данных по состоянию, т. е. для выполнения ограничения системы функциональной зависимости {№ зачетной книжки} → {Фамилия, Имя, Отчество} при изменении, например, фамилии необходимо просматривать все кортежи этого базового отношения и последовательно вводить необходимые изменения. Однако так как это довольно громоздкий и трудоемкий процесс (особенно если мы имеем дело с базой данных большого учебного заведения), разработчики систем управления базами данных пришли к выводу, что этот процесс необходимо автоматизировать, т. е. сделать автоматическим. Теперь контроль выполнения этой (и любой другой) функциональной зависимости можно организовывать автоматически при помощи правильного объявления в базовом отношении различных ключей и так называемой декомпозиции (т. е. разбиения чего-либо на несколько самостоятельных частей) этого отношения.
