Базы данных. Лекции - База данных, лекционный курс. Базы данных лекционный курс

• Название: Базы данных лекционный курс
• Анкор: Базы данных
• Дата: 10.03.2022
• Размер: 1.23 Mb.
• Имя файла: Лекции - База данных, лекционный курс.doc
• Тип: Документы; #390809
• страница: 8 из 11

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

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

Примером отношения, находящегося в 1НФ, является отношение Консультант. На этом примере мы уже пояснили, почему отношение, находящееся в 1НФ, имеет нежелательную структуру.

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

Атрибут A_i отношения r называют основным атрибутом, если он является элементом первичного ключа данного отношения.

Рассмотрим отношение Факультет (Код факультета, Наименование факультета, ФИО декана, № телефона).

Функционально зависимы следующие атрибуты (исходим из предположения, что на одном телефонном номере может «висеть» несколько абонентов):

К од факультета

Наименование факультета

ФИО декана

№ телефона

Таким образом, в рассматриваемом отношении три возможных ключа: Код факультета, Наименование факультета, ФИО декана. Выберем в качестве первичного ключа атрибут Код факультета. Атрибуты Наименование факультета, ФИО декана, № телефона, не являющиеся основными, функционально полно зависят от первичного ключа отношения, значит отношение находится во 2НФ.

Рассмотрим отношение СтудентКурспроект (№ студента, Код предмета, ФИО студента, № группы, ФИО преподавателя, Процент выполнения). Предположим, что в одной группе могут учиться полные однофамильцы. Тогда у этого отношения один возможный ключ: № студента, Код предмета. Атрибуты ФИО студента и № группы не являются основными, но функционально зависят от основного атрибута № студента, являющегося элементом ключа (т. е. отношение не находится во 2НФ).

ФЗ между атрибутами данного отношения:

№ студента

Код предмета

ФИО студента

№ группы

ФИО преподавателя

Процент выполнения

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

№ студента

ФИО студента

№ группы

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

Код предмета

ФИО преподавателя

Процент выполнения

получим два отношения во 2НФ.

Отношения Студент (№ студента, ФИО студента, № группы) и Курспроект (№ студента, Код предмета, ФИО преподавателя, Процент выполнения) являются проекциями исходного отношения, естественное соединение которых даст его. Таким образом, в процессе преобразования никакая информация не теряется, любая информация, которая может быть получена из первоначальной структуры, может быть получена и из новой структуры. Обратное, однако, неверно: новая структура может содержать информацию (например, о студентах, еще не получивших задания на курсовое проектирование), которая не может быть представлена в первоначальной структуре. В этом смысле новая структура является более точным отображением реального мира.

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

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

Транзитивная зависимость определяется следующим образом: если X  Y и Y  Z, то X  Z (Z транзитивно зависит от X).

Приведение отношения к 3НФ заключается в устранении транзитивных зависимостей в отношении путем разбиения исходного отношения r(X, Y, Z) на: r1(X, Y) и r2(Y, Z).

Рассмотрим отношение Общежитие (Код студента, № группы, № комнаты, Староста комнаты).

F-зависимости между атрибутами данного отношения:

К од студента

№ группы

№ комнаты

Староста комнаты

Возможным и единственным ключом отношения является атрибут Код студента. Отношение находится во 2НФ, но не в третьей, так как неосновной атрибут Староста комнаты зависит от атрибута № комнаты, который, в свою очередь, зависит от ключа отношения Код студента, и, следовательно, атрибут Староста комнаты транзитивно зависит от ключа. Данное отношение имеет недостатки (например, если студент переходит жить в другую комнату, то работающему с данной БД необходимо, кроме номера комнаты, не забыть изменить и старосту комнаты).

Для устранения недостатков разобьем отношение на следующие два:

К од студента № комнаты

№ группы Староста комнаты

№ комнаты

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

Отношение может быть в 3НФ и при этом все же иметь некоторые нежелательные свойства.

Например, рассмотрим отношение ГАИ (город, адрес, индекс), где индекс – это индекс отделения связи, адрес – название улицы, номер дома и номер квартиры.

F-зависимости между атрибутами отношения:

Г ород

Адрес

Индекс

Т. е. полный адрес определяет почтовый индекс, а тот, в свою очередь, определяет название города, но не определяет адрес.

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

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

Для устранения недостатков 3НФ вводится четвертая нормальная форма, имеющая две разновидности.

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

Определение: отношение r находится в НФБК, если и только если каждый детерминант отношения является возможным ключом.

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

Пример отношения в НФБК: ВыдачаВозврат (Код книги, Код читателя, Дата выдачи, Дата возврата).

Функциональные зависимости, имеющие место в данном отношении:

К од книги Код книги

Дата выдачи Дата возврата

Код читателя Код читателя

Дата возврата Дата выдачи

Функциональные зависимости определены из следующих соображений: любая книга берется (соответственно возвращается) не один раз и разными читателями (т.е. по любому атрибуту данного отношения нельзя однозначно определить никакой другой атрибут); любой читатель может взять одну книгу дважды (т.е. по коду книги и по коду читателя нельзя однозначно определить дату выдачи книги); в один день читатель может взять (соответственно отдать) несколько книг (т.е. по коду читателя и дате выдачи (дате возврата) книги нельзя однозначно определить код книги). Таким образом, имеем два детерминанта, составные атрибуты: Код книги, Дата выдачи и Код книги, Дата возврата и они же являются возможными ключами отношения.

Может оказаться так, что отношение в 3НФ нельзя будет привести к НФБК без потери зависимостей между атрибутами этого отношения.

Обратимся, например, к отношению ГАИ (город, адрес, индекс), которое не находится в НФБК, так как имеет место зависимость индекс  город.

Это отношение можно разбить на отношения: ГА (город, адрес) и АИ (адрес, индекс), но тогда зависимость индекс  город будет утеряна.

Определение второй разновидности четвертой нормальной формы (4НФ): отношение r находится в 4НФ тогда и только тогда, когда при существовании многозначной зависимости в r атрибута Y от атрибута X, все остальные атрибуты r функционально зависят от Х.

Атрибут Х многозначно определяет атрибут Y, если с каждым значением x может использоваться значение y из фиксированного подмножества значений Y. Обозначается: X ↠ Y.

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

В качестве примера рассмотрим отношение КПУ (Курс, Преподаватель, Учебник), где Курс – наименование курса, Преподаватель – фамилия преподавателя, Учебник – название учебника. Пусть данному курсу может соответствовать любое число преподавателей и любое количество учебников, и пусть преподаватели и учебники не зависят друг от друга.

Экземпляр отношения КПУ, касающийся только одного курса:

Курс	Преподаватель	Учебник
Физика	Иванов	Основы механики
Физика	Иванов	Законы оптики
Физика	Петров	Основы механики
Физика	Петров	Законы оптики

Атрибут Курс многозначно определяет атрибут Преподаватель и имеется многозначная зависимость атрибута Учебник от атрибута Курс:

Курс ↠ Преподаватель;

Курс ↠ Учебник.

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

Для устранения недостатков отношения, представленного в 3НФ, выполняют разложение по многозначным зависимостям данного отношения, т. е. отношение r (A, B, C), где A ↠ B и A ↠ C, разбивают на два: r1 (A, B) и r2 (A, C).

Для нашего примера: КП (Курс, Преподаватель), КУ (Курс, Учебник). Каждое из полученных отношений находится в четвертой нормальной форме.

Приведем примеры выявления нормальной формы отношений.

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

а) б)


Необходимо определить, в какой нормальной форме находится данное отношение.

Для варианта а: имеем две функциональные зависимости: А  С и А, В  D, т.е. ключом отношения является составной атрибут А, В. Будем считать, что каждый из имеющихся атрибутов имеет атомарное значение. Тогда рассматриваемое отношение находится в 1НФ. Отношение не находится во 2НФ, в силу имеющейся функциональной зависимости неосновного атрибута С от атрибута А – части ключа.

Для варианта б: имеем три функциональные зависимости: D  A, D  B и A, B  C, т.е. ключом отношения является атрибут D. Будем считать, что каждый из имеющихся атрибутов имеет атомарное значение. Тогда рассматриваемое отношение находится в 1НФ. Отношение находится во 2НФ, т.к. все неосновные атрибуты: A, B и С функционально полно зависят от ключа отношения. Отношение не находится в 3НФ, так как неосновной атрибут С транзитивно зависит от ключа D: D  A, B  C.
Тесты для самоконтроля



1. Нормализованным отношением называют:

а) отдельный листинг отношения в некоторый момент времени;

б) отношение, каждый домен которого содержит только атомарные значения;

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

2. Атрибут Б некоторого отношения функционально зависит от атрибута А того же отношения, если:

а) в каждый момент времени каждому значению атрибута А соответствует не более чем одно значение атрибута Б;

б) с каждым значением а может использоваться значение б из фиксированного подмножества значений Б;

в) в каждый момент времени каждому значению атрибута А соответствует не менее чем одно значение атрибута Б.

3. Множество атрибутов Б функционально полно зависит от множества атрибутов А, если:

а) Б не зависит ни от какого подмножества А;

б) Б зависит от любого подмножества А;

в) А является элементом ключа.

4. Атрибут С транзитивно зависит от атрибута А, если:

а) С В и B  А;

б) А ↠С;

в) А В и B  C.

5. Любое нормализованное отношение:

а) не находится в 1НФ;

б) находится в 1НФ;

6. Отношение находится в 3НФ, если каждый его неосновной атрибут:

а) не транзитивно зависит от первичного ключа отношения;

б) зависит от детерминанта отношения;

в) функционально полно зависит от первичного ключа отношения.

7. Приведение отношения к 4НФ заключается:

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

б) в разложении отношения по многозначным зависимостям;

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

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

а) информация не будет утеряна.

б) будет утеряна информация.

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

а) б)



в) г)


д)


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

6. ДЕКОМПОЗИЦИОННЫЙ МЕТОД ПРОЕКТИРОВАНИЯ

РЕЛЯЦИОННОЙ БАЗЫ ДАННЫХ
6.1. Общий подход к декомпозиции

Этапы проектирования:

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

2) Определяются все функциональные зависимости между атрибутами данного отношения.

3) Определяется, находится ли отношение в нормальной форме Бойса - Кодда. Если да, то проектирование завершается, если нет, то осуществляется декомпозиция, т.е. разбиение отношения.

4) Шаги 2 и 3 повторяются для каждого нового отношения, полученного в результате декомпозиции. Проектирование завершается, когда все отношения будут находиться в НФБК.

Декомпозиция может осуществляться следующим образом:

• 
  Пусть отношение r(A, B, C, D, E,…) не находится в НФБК. Определяется F-зависимость, являющаяся причиной того, что отношение r не находится в НФБК, например, С  D (атрибут С является детерминантом, но не является возможным ключом).
  
• 
  Создаются два новых отношения: r1(A, B, С, Е,…) и r2(C, D), где зависимостная часть F-зависимости – атрибут D был выделен из отношения r и опущен при формировании отношения r1, F–зависимость С  D была полностью использована при формировании отношения r2. Отношения r1 и r2 являются проекциями отношения r.
  

Такая декомпозиция называется декомпозицией без потерь при естественном соединении (т. е. естественное соединение r1 и r2 даст исходное отношение r).

Например, обратимся к отношению Консультант (№ студента, ФИО студента, № комнаты, № телефона, № курса, Семестр, Оценка), которое является универсальным отношением.

F-зависимости отношения Консультант (были определены нами ранее):

№ студента  ФИО студента;

№ студента  № комнаты;

№ студента  № телефона;

№ комнаты  № телефона;

№ телефона  № комнаты;

№ студента, № курса, Семестр  Оценка.

Возможным и единственным ключом отношения является составной атрибут: № студента, № курса, Семестр. Имеются три детерминанта, не являющиеся возможными ключами: № студента, № комнаты, № телефона. Необходимо выбрать F-зависимость для проведения первой проекции. Для этого отыскивают «цепочку» F-зависимостей вида: А  В  С и используют для проекции крайнюю правую зависимость. В нашем случае такими цепочками являются:

№ студента  № комнаты  № телефона;

№ студента  № телефона  № комнаты.

а) Выбрав F-зависимость № комнаты  № телефона, получим следующие отношения:

r1(№ студента, № курса, Семестр, Оценка, ФИО студента, № комнаты);

r2(№ комнаты, № телефона).

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

Отношение r1 не находится в НФБК (детерминант № студента не является возможным ключом) и поэтому разбивается далее.

Детерминант № студента имеет два зависимых атрибута:

№ студента  ФИО студента

№ студента  № комнаты

Эти две зависимости в r1 можно рассматривать как одну с составной правой частью:

№ студента  ФИО студента, № комнаты.

Выбирая данную F-зависимость для проведения второй проекции, получим следующие отношения:

r3(№ студента, ФИО студента, № комнаты);

r4(№ студента, № курса, Семестр, Оценка).

Данные отношения находятся в НФБК. Проектирование завершено: отношения r2, r3, r4 могут быть использованы при формировании БД для консультанта.

б) Выбрав для проведения первой проекции F-зависимость № телефона  № комнаты, получим следующие отношения:

r1(№ студента, № курса, Семестр, ФИО студента, № телефона, Оценка);

r2(№ телефона, № комнаты).

Отношение r2 находится в НФБК, r1 – нет. Разбиваем r1 на следующие два отношения:

r3(№ студента, ФИО студента, № телефона);

r4(№ студента, № курса, Семестр, Оценка).

Отношения r3 и r4 находятся в НФБК, проектирование завершено.

Таким образом, имеем два различных решения. Какое из двух решений является «лучшим», определяется выбором проектировщика и зависит до некоторой степени от того, как планируется использовать БД.