СУБД / УМК СУБД

Таблица 9.

Номер студента	ФИО студента	Код дисциплины	Наименование
11	Иванов И.И.	Д1	Математика
12	Петров П.П.	Д1	Математика
13	Сидоров С.С.	Д1	Математика
11	Иванов И.И.	Д2	Информатика
12	Петров П.П.	Д2	Информатика
13	Сидоров С.С.	Д2	Информатика

Деление выполняется над двумя отношениями R1 и R2, имеющими в общем случае разные структуры и часть одинаковых атрибутов. В результате образуется новое отношение, содержащее атрибуты 1-го операнда, отсутствующие во 2-м операнде, и

кортежи 1-го операнда, которые совпали с кортежами 2-го. Для выполнения этой операции 2-й операнд должен содержать лишь атрибуты, совпадающие с атрибутами 1-го.

Например, чтобы узнать, кто из студентов получил по математике 5 и по информатике

4, надо разделить отношения Экзаменационная ведомость на вспомогательное отношение

Мат5Физ4 (Наименование, Оценка) с двумя кортежами: Математика, 5 и Информатика,

4. В результате получим отношение Итог (Номер студента, ФИО студента, Код дисциплины) с одним кортежем – 13, Сидоров, Д1.

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

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

сдавших математику на отлично (Код дисциплины = Д1) AND (Оценка = 5) (табл. 10).

Таблица 10.

Номер студента	ФИО студента	Код дисциплины	Наименование
11	Иванов И.И.	Д1	Математика
13	Сидоров С.С.	Д1	Математика

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

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

Ниже приведен пример исходного отношения R (табл. 11) и результат проекции этого отношения на два его атрибута - Должность и Номер отдела (табл. 12).

45

Таблица 11.

ФИО	Номер отдела	Должность
Иванов И.И.	01	Инженер
Петров П.П.	02	Инженер
Нестеров Н.Н.	01	Инженер

Таблица 12.

Номер отдела	Должность
01	Инженер
02	Инженер
03	Лаборант

Соединение выполняется для заданного условия соединения над двумя логически связанными отношениями. Исходные отношения R1 и R2 имеют разные структуры, в

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

с теми кортежами R2, для которых выполняется условие соединения. В зависимости от этого условия соединение называется: естественным – равенство значений общих атрибутов отношений R1 и R2; эквисоединением – равенство значений атрибутов,

входящих в условие соединения; тета-соединением – другой знак сравнения.

Операция соединения имеет большое значение для РБД, так как в процессе нормализации отношений исходное отношение разбивается на несколько более мелких отношений, которые при выполнении запросов пользователя требуется, как правило,

вновь соединять для восстановления исходного отношения.

Рассмотренные выше операции в той или иной мере реализуются в языке манипулирования данными СУБД (SQL, QBE, другие языки запросов). Язык SQL

является более чем реляционно-полным, так как кроме операций реляционной алгебры содержит полный набор операторов над кортежами – Включить, Удалить, Изменить, а

также реализует арифметические операции и операции сравнения.

Кдостоинствам РМД относятся:

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

минимальная избыточность данных при нормализации отношений;

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

46

К недостаткам РМД можно отнести то, что нормализация данных приводит к значительной их фрагментации, в то время как в большинстве задач необходимо объединение фрагментированных данных.

5.4. Нормализация баз данных

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

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

Схемой базы данных называется структура связей между полями и таблицами.

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

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

вторая, третья, четвертая, пятая нормальная форма, а также нормальная форма Бойса-

Кодда, лежащая между третьей и четвертой.

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

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

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

запрещает повторяющиеся столбцы (содержащие одинаковую по смыслу информацию)

запрещает множественные столбцы (содержащие значения типа списка и т.п.)

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

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

47

Вторая нормальная форма требует, чтобы неключевые столбцы таблиц зависили от первичного ключа в целом, но не от его части.

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

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

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

В качестве примера рассмотрим универсальное отношение сотрудники, содержащее информацию о сотрудниках предприятия (табл. 13).

Таблица 13

	Код	ФИО	Должность	Номер	Наименование	Квалификация
	сотрудника			отдела	отдела
	7513	Иванов И.И.	Программист	128	Отдел	C, Java
					проектирования
	9842	Сергеева С.С.	Администратор	42	Финансовый	DB2
			БД		отдел
	6651	Петров П.П.	Программист	128	Отдел	VB, Java
					проектирования
	9006	Николаев Н.Н.	Системный	128	Отдел	Windows,
			администратор		проектирования	Linux

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

избыточность данных;

потенциальная противоречивость (аномалии).

Под избыточностью понимают повторение данных в разных строках одной таблицы или в разных таблицах БД. Так, для каждого сотрудника отдела 128 повторяются данные

«128, Отдел проектирования».

Аномалии – это проблемы, возникающие в данных из-за дефектов проектирования БД.

Существуют три вида аномалий: вставки, удаления и модификации.

Аномалии вставки проявляются при вводе данных в дефектную таблицу. Добавляя информацию о новом сотруднике, мы должны добавить номер и название отдела. Если ввести данные, не соответствующие имеющимся в таблице (например, 42, отдел проектирования), будет не ясно, какая из строк БД содержит правильную информацию.

48

Аномалии удаления возникают при удалении данных из дефектной схемы.

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

Аномалии модификации возникают при изменении данных дефектной схемы.

Предположим, что отдел 128 решили переименовать в отдел передовых технологий.

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

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

Решение перечисленных проблем состоит в разделении данных и связей, что обеспечивается процедурой нормализации. Концепции и методы нормализации были разработаны Э. Ф. Коддом.

Нормализация отношений – это формальный аппарат ограничений на формирование отношений, который позволяет устранить дублирование и потенциальную противоречивость хранимых данных, уменьшает трудозатраты на ведение БД. Процесс нормализации заключается в декомпозиции исходных отношений на более простые отношения. Цель нормализации – получение такого проекта БД, в котором «каждый факт появляется лишь в одном месте».

Теория нормализации основана на наличии зависимостей между атрибутами отношения. Основными видами зависимостей являются:

функциональные;

многозначные;

транзитивные.

Базовым является понятие функциональной зависимости, поскольку на его основе формируются определения всех остальных видов зависимостей. Атрибут В функционально зависит от атрибута А, если каждому значению А соответствует в точности одно значение В. Математически функциональную зависимость В от А обозначают А ’ В. Это означает, что во всех кортежах с одинаковым значением атрибута

49

А атрибут В будет иметь также одно и то же значение. При этом А и В могут быть составными, то есть состоять из двух и более атрибутов.

Зависимость, при которой каждый неключевой атрибут зависит от всего составного ключа и не зависит от его частей, называется полной функциональной зависимостью. Если атрибут А зависит от атрибута В, а атрибут В зависит от атрибута С (С ’ В ’ А), но обратная зависимость отсутствует, то зависимость А от С называется транзитивной.

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

Многозначные зависимости могут быть:

один-ко-многим (1:М);

многие-к-одному (М:1);

многие-ко-многим (М:М).

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

первая нормальная форма (1НФ);

вторая нормальная форма (2НФ);

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

усиленная 3НФ или нормальная форма Бойса-Кодда (БКНФ);

четвертая нормальная форма (4НФ);

пятая нормальная форма (5НФ).

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

В столбце Квалификация ненормализованной табл. 13 содержатся списки значений (С,

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

50

Таблица 14

	Код	ФИО	Должность	Номер	Наименование	Квалификация
	сотрудника			отдела	отдела
	7513	Иванов И.И.	Программист	128	Отдел	C
					проектирования
	7513	Иванов И.И.	Программист	128	Отдел	Java
					проектирования
	9842	Сергеева С.С.	Администратор	42	Финансовый	DB2
			БД		отдел
	6651	Петров П.П.	Программист	128	Отдел	VB
					проектирования
	6651	Петров П.П.	Программист	128	Отдел	Java
					проектирования
	9006	Николаев Н.Н.	Системный	128	Отдел	Windows
			администратор		проектирования
	9006	Николаев Н.Н.	Системный	128	Отдел	Linux
			администратор		проектирования

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

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

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

Таблица Квалификации_сотрудников (табл. 14) находится в 1НФ, но не удовлетворяет

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

Единственным вариантом является использование в качестве первичного ключа комбинации Код сотрудника и Квалификация. Это порождает схему:

Квалификации_сотрудников (Код сотрудника, ФИО, Должность, Номер отдела,

Наименование отдела, Квалификация).

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

Квалификация ’ ФИО, Должность, Номер отдела, Наименование отдела. Но, кроме того,

мы также имеем: Код сотрудника ’ ФИО, Должность, Номер отдела, Наименование отдела. Другими словами, можно определить имя, должность и отдел, используя только код сотрудника. Это значит, что указанные атрибуты функционально зависимы только от части первичного ключа, а не от всего первичного ключа. Следовательно, указанная схема не находится в 2НФ.

51

Для приведения этой схемы в 2НФ необходимо декомпозировать исходное отношение на два, в которых все неключевые атрибуты будут полностью функционально зависеть от ключа: сотрудники (Код сотрудника, ФИО, Должность, Номер отдела, Наименование отдела) и Квалификации_сотрудников (Код сотрудника, Квалификация) (табл. 15–16).

Таблица 15

Код	ФИО		Должность				Номер		Наименование
сотрудника							отдела		отдела
7513	Иванов И.И.		Программист				128	Отдел проектирования
9842	Сергеева С.С.		Администратор БД				42	Финансовый отдел
6651	Петров П.П.		Программист				128	Отдел проектирования
9006	Николаев Н.Н.		Системный				128	Отдел проектирования
			администратор
Таблица 16.
		Код сотрудника			Квалификация
		7513			C
		7513			Java
		9842			DB2
		6651			VB
		6651			Java
		9006			Windows
		9006			Linux

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

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

Формально, для приведения схемы в 3НФ необходимо исключить все транзитивные зависимости. Схема отношения сотрудники (табл. 15) содержит следующие функциональные зависимости: Код сотрудника ’ ФИО, Должность, Номер отдела,

Наименование отдела и Номер отдела ’ Наименование отдела.

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

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

52

Должность, Номер отдела) и отделы (Номер отдела, Наименование отдела) (табл. 17–

18).

Таблица 17

Код		ФИО		Должность		Номер отдела
сотрудника
7513		Иванов И.И.		Программист	128
9842		Сергеева С.С.		Администратор БД	42
6651		Петров П.П.		Программист	128
Таблица 18.
	Номер отдела		Наименование отдела
	42		Финансовый отдел
	128		Отдел проектирования

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

Алгоритм приведения ненормализованных схем в 3НФ показан на рис. 18. На практике построение 3НФ в большинстве случаев является достаточным и приведением к ней процесс построения реляционной БД заканчивается.

53

Ненормализованная схема
Расщипить схему на схемы без	Объявить один или более атрибутов
повторяющихся групп	главным ключом (самый малый ключ)

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

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

Проверить, что все неключевые атрибуты являются взаимосвязанными

Исключить избыточные атрибуты или расщипить схему

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

Рисунок 18. Алгоритм приведения ненормализованных схем в 3НФ Запомнить правила нормализации помогает изречение: «Нормализация – это ключ,

целый ключ и ничего, кроме ключа».

Нормальные формы высших порядков (4НФ и 5НФ) представляют больший интерес для теоретических исследований, чем для практики проектирования БД. В них

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

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

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

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

’ А, где К – первичный ключ, а А – атрибут.

54