Модуль2_Проектирование БД

Если X →Y и Z Y , то X → Z , всякая ФЗ функционально определяет любое

подмножество атрибутов своей функции.

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

Графический метод минимизации набора функциональных зависимостей

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

Вершинами графа ФЗ являются атрибуты, образующие аргументы и функции заданных зависимостей, а дугами служат сами функциональные зависимости. Таким образом, граф – просто визуальное представление исходного набора ФЗ.

Исходный набор ФЗ, заданных в отношении СТУДЕНТ, представляется графом, изображенным на рис 12.1.

90

Факультет

Специальность

Фамилия	Успевае-	Стипендия
	мость
И.О.

Рис. 12.1. Граф функциональных зависимостей атрибутов в отношении СТУДЕНТ

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

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

Фамилия И.О.	Нетрудно заметить,		что зависимость		{Специальность,
Фамилия И.О.}	Æ {Факультет}		является следствием (выводится) из
зависимости {Специальность} Æ			{Факультет}	применением правила
расширения. Поэтому зависимость
{Специальность,	Фамилия И.О.}	Æ {Факультет}		можно исключить.
Далее видим, что в вершину Стипендия ведут также две дуги,
представляющие параллельные пути от вершины
{Специальность, Фамилия И.О.}.		Один из этих путей задан зависимостью
{Специальность,	Фамилия И.О.}	Æ	{Стипендия}, которая по правилу
транзитивности может быть выведена из зависимостей
{ Специальность,	Фамилия И.О.}	Æ	{Успеваемость}		и {Успеваемость}
Æ {Стипендия}.

91

Поэтому функциональную зависимость

{Специальность, Фамилия И.О.} Æ {Стипендия} также можно не включать в минимальное покрытие.

После удаления двух выводимых зависимостей получаем граф показанный на рис. 12.2.

Факультет

Специальность

	Фамилия	Успевае-	Стипендия
		мость
	И.О.

Рис.12.2. Граф функциональных зависимостей, составляющих минимальное покрытие

В этом графе отсутствуют параллельные пути. Следовательно, в нем нет выводимых зависимостей. Таким образом, минимальное покрытие для исходного набора из пяти зависимостей состоит из трех следующих ФЗ:

{Специальность} Æ {Факультет}, {Специальность, Фамилия И.О.} Æ {Успеваемость},

{Успеваемость} Æ {Стипендия}.

Именно эти зависимости следует сохранять при декомпозиции схемы отношения СТУДЕНТ с первичным ключом {Специальность, ФИО}.

СТУДЕНТ (Факультет, Специальность, Фамилия И.О., Успеваемость, Стипендия)

92

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

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

Лекция 13. Нормальные формы отношений

Первая нормальная форма (1НФ) отношения

– это отношение, в котором каждый его атрибут состоит их атомарных (неделимых) с точки зрения базы данных значений.

Примером ненормализованного отношения может служить таблица СТУДЕНТ, представленная в следующем виде:

			Таблица 13.1
Факультет Специальность		ФИО	Успеваемость Стипендия
		Котов Юрий . . . . . . . . . . . . . . . . . . . . . . .
		Владимирович	.
АСОИиУ		Петров Петр
		Алексеевич
РТФ		Попов Илья
		Иванович
		. . . . . . . . .

ВМКСС

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

Нормализованное отношение (в 1НФ) будет иметь вид:

					Таблица 13.2
	Факультет	Специальность	ФИО	Успеваемость	Стипендия
	РТФ	АСОИиУ	Петров Петр	. . . . . . . . . . . . . . . . . . . . . .
			Алексеевич	.	. .
	РТФ	АСОИиУ	Котов Юрий

93

РТФ

РТФ

. . . . . . . . . .

АСОИиУ

АСОИиУ

. . . . . . . . . . .

Владимирович Попов Илья Иванович

. . . . . . . . . . . . .

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

Вторая нормальная форма (2НФ) отношения

Нормализованное отношение находится во второй нормальной форме, если для каждого неключевого атрибута в отношении существует ФЗ, в которой аргументом являются все атрибуты первичного ключа данного отношения. Т.е. если P – множество атрибутов, составляющих первичный ключ отношения, а А – любой атрибут, не вошедший в первичный ключ (A P) , отношение будет во 2НФ, если в нем существуют ФЗ вида P Æ A и не существуют зависимости X Æ A, где Х P . Данное условие должно выполняться для

всех неключевых атрибутов.

Проверим принадлежность отношения СТУДЕНТ второй нормальной

форме. Из набора ФЗ,	составляющих минимальное покрытие, следует, что
атрибуты Успеваемость	и Стипендия функционально зависят от обоих

атрибутов первичного ключа {Специальность, ФИО}. При этом неважно, что

атрибут Стипендия	зависит транзитивно. Следовательно,	эти	атрибуты
удовлетворяют определению второй нормальной формы. В		то	же время

атрибут Факультет функционально зависит от атрибута Специальность, составляющего часть первичного ключа. Значит, атрибут Факультет и его зависимость {Специальность} Æ {Факультет} противоречат определению 2НФ. Чтобы отношение СТУДЕНТ привести ко 2НФ, необходимо из него исключить атрибут Факультет, перенося эти данные в отдельную таблицу. Однако, если в отдельную таблицу поместить только один атрибут Факультет,

94

то будет потеряно соответствие факультетов специальностям, т.е. разрушена ФЗ {Специальность} Æ {Факультет}. Для сохранения этой зависимости в отдельное отношение необходимо переместить атрибуты Специальность и Факультет. Нетрудно проверить, что в этом отношении ключом является Специальность, от которой единственный неключевой атрибут Факультет зависит функционально. Таким образом, отношение СТУДЕНТ преобразуется в два новых отношения СТУДЕНТ и Специальность, находящиеся во 2НФ:

СТУДЕНТ (Специальность, Фамилия И.О., Успеваемость, Стипендия)

Специальность (Специальность, Факультет)

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

Третья нормальная форма (3НФ)

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

В полученном при переходе во 2НФ отношении СТУДЕНТ атрибут Стипендия транзитивно – через атрибут Успеваемость – зависит от ключа. Поэтому отношение не находится в 3НФ. Для преобразования отношения СТУДЕНТ в 3НФ выносим из него атрибут Стипендия. Но чтобы при этом не разрушать зависимость {Успеваемость} Æ {Стипендия} в новое отношение включаем атрибуты Успеваемость и Стипендия. Окончательно в третьей нормальной форме получаем три отношения:

СТУДЕНТ (Специальность, Фамилия И.О., Успеваемость)

95

Стипендия (Успеваемость, Стипендия)

Специальность (Специальность, Факультет)

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

Для пояснения свойств нормальных форм была выполнена последовательная нормализация отношения СТУДЕНТ. В общем случае для декомпозиции отношения в 3НФ не обязательно последовательно строить сначала 1НФ, потом 2НФ и 3НФ. Для этого можно воспользоваться следующей простой процедурой приведения отношения сразу в 3НФ.

Алгоритм декомпозиции отношения в третью нормальную форму

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

Иначе каждой функциональной зависимости из минимального покрытия вида Х Æ У ставится в соответствие своя схема отношения вида C ( X Y ) .

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

ХÆ У1 ,

ХÆ У2 ,

. . . . . . . .

Х Æ Ут ,

96

то все эти зависимости создают одно отношение со схемой

C ( X Y1 Y2 ... Ym ) .

В процессе приведения отношения в 3НФ возможно появление особых ситуаций.

1. В минимальном покрытии оказались зависимости, образующие цикл вида: Х Æ У , Y Æ Z , Z Æ X , с подграфом на рис. 13.1.

Y

X Z

Рис. 13.1. Исходный граф ФЗ

Используя правило транзитивности, из любой пары этих зависимостей можно вывести зависимость, которая будет ориентирована навстречу третьей из заданных ФЗ. Например, из зависимостей Х Æ У , Y Æ Z выводится зависимость Х Æ Z , ориентированная навстречу исходной зависимости Z Æ X . Если построить все возможные транзитивные зависимости, граф приобретает вид, показанный на рис. 13.2.

Y

X Z

Рис. 13.2. Преобразованный граф ФЗ

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

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

97

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

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

В заключение рассмотрим пример минимизации набора зависимостей и нормализации отношения, не связанного с какой-либо предметной областью. Дана схема отношения С(А1, А2, А3, А4, А5), где С – имя отношения,

А1, А2, А3, А4, А5 – имена атрибутов в заданном отношении. На атрибутах данного отношения задано исходное множество ФЗ:

{А1}	Æ	{А2},
{А1}	Æ	{А3},
{А2}	Æ	{А4},
{А3}	Æ	{А4},
{А1, А2}	Æ	{А5},
{А3}	Æ	{А5}.

Требуется: 1) найти минимальное покрытие исходного множества ФЗ, 2) преобразовать отношение со схемой С в 3НФ.

98

Решение 1. Чтобы обнаружить в исходном наборе выводимые зависимости,

представляем заданное множество зависимостей в виде графа (рис. 13.3).

	A2
A1	A4
	A5

A3

Рис. 13.3 Исходный граф ФЗ

Поскольку в вершину A5 ведут две дуги, имеет смысл начать поиск выводимых зависимостей с одной из них. На основании правила транзитивности из зависимостей {А1} Æ {А3} и {А3} Æ {А5} выводится промежуточная зависимость {А1} Æ {А5}. С этой зависимостью граф имеет вид, показанный на рис. 13.4.

	A2
A1	A4
	A5

A3

Рис. 13.4 Граф с дополнительной выводимой ФЗ

99